Экономико-математические модели и методы



страница6/7
Дата06.06.2016
Размер0.62 Mb.
1   2   3   4   5   6   7

Метод потенциалов

Метод потенциалов - метод, обеспечивающий улучшение начального плана перевозок. При этом происходит переход от одного плана перевозок к другому (от одной матрицы перевозок к другой) до тех пор, пока уменьшение суммарной стоимости перевозок станет невозможным.


  1. Циклы матрицы перевозок



Цикл – замкнутая ломаная с вершинами в клетках и звеньями, расположенными вдоль строк и столбцов матрицы перевозок. В каждой вершине встречаются два звена, причем одно из них располагается по строке, а другое – по столбцу. Число вершин цикла чётно. Циклом может быть самопересекающаяся ломаная, но точки ее самопересечения не могут быть вершинами цикла.


а б в
Рис. 3. Простейшие циклы

На рис. 3 звездочкой отмечены клетки матрицы, включенные в состав цикла. На рис. 3 в кружком отмечена точка самопересечения.



Означенный цикл – цикл, в котором некоторой вершине приписан знак +, а затем при обходе цикла в каком-либо направлении знаки чередуются.

Сдвигом по циклу на величину назовем увеличение объемов перевозок во всех клетках, отмеченных знаком + и уменьшение объемов перевозок на во всех клетках цикла, отмеченных знаком –.

  1. Метод потенциалов, его алгоритм



Теорема

Если план транспортной задачи является оптимальным, то ему соответствует система из m+ n чисел и , удовлетворяющих условиям:



для ,

для , .

Числа , называются потенциалами соответственно поставщиков и потребителей.

Данная теорема позволяет построить алгоритм нахождения решения транспортной задачи.

АЛГОРИТМ



  1. Для ТЗ с правильным балансом находим начальный план перевозок методом северо-западного угла или методом минимального элемента.

  2. Для каждой базисной клетки составляем уравнение . Так как число базисных клеток m + n – 1, то система m + n – 1 уравнений с m + n неизвестными имеет бесконечное множество решений. Для определенности положим u1 = 0. Тогда все остальные потенциалы находятся однозначно. Вносим их в матрицу перевозок.

  3. Для свободных клеток находим суммы соответствующих потенциалов, помещаем их в нижний правый угол свободных клеток матрицы.

  4. Для всех свободных клеток проверяем выполнение условия оптимальности:

  • если для всех свободных клеток ( ), то задача решена; выписываем полученный оптимальный план перевозок из последней матрицы, подсчитываем его стоимость;

  • если для одной или нескольких свободных клеток, то переходим к п. 5.

  1. Находим ту свободную клетку, для которой имеет наибольшее по модулю отрицательное значение. Строим для нее означенный цикл. Свободной клетке приписываем знак +. Все вершины означенного цикла, кроме расположенной в клетке (i,j), должны находиться в базисных клетках.

  2. Выполняем сдвиг по циклу на величину , равную наименьшему из чисел, стоящих в «отрицательных» вершинах цикла. Если наименьшее значение достигается в нескольких «–» клетках, то при сдвиге следует поставить базисный нуль во всех таких клетках, кроме одной. Тогда число базисных клеток сохранится и будет равно m + n 1, это необходимо проверять при расчетах.

Клетки матрицы, не входящие в цикл, остаются без изменения.

Строим новую матрицу перевозок.



  1. Переход к шагу 2.


Примечание. При решении задачи может возникнуть ситуация, в которой . Тогда при сдвиге свободная клетка становится базисной .
Пример 5. Составить математическую модель ТЗ, решить ТЗ:

Запишем матрицу перевозок (табл. 3.4).

Таблица 3.4

Bj

Ai B1B2В3B4Запасы aiA110

0

20



1115A212

7

9



20

25A30

14

16

18



5Потребности bj515151045

45


  1. Пусть – количество единиц груза, которое нужно перевезти из пункта Аi в пункт Bj .

  2. Ограничения:

а) по запасам


б) по потребностям


  1. Целевая функция: . Требуется составить план перевозок, чтобы их суммарная стоимость была минимальной.

  2. Данная ТЗ с правильным балансом: 15 + 25 + 5 = 5 + 15 + 10; 45 = 45.

  3. Начальный план перевозок найден в п. 3.3.2 методом минимального элемента (табл.3.3) Выпишем найденную матрицу перевозок.

  4. Находим потенциалы базисных клеток:

Матрица перевозок

Bj

Ai B1B2В3B4Запасы aiu1=0A110

00

1520



211

1315u2=7A212

177

09

1520



1025u3= -10A30

514


-1016

-818


35Потребности bj515151045

45




  1. Для свободных клеток находим суммы соответствующих потенциалов, заносим их в матрицу в нижний правый угол свободных клеток.

  2. Для свободных клеток проверяем выполнение условия оптимальности: для . Для клеток (1,4) и (2,1) условие не выполнено.

  3. , Для свободных клеток строим обозначенный цикл.

  4. Производим сдвиг по циклу на Клетка (2,1) становится базисной , а клетка (1,1) – свободной.

  5. Переходим к шагу 2 алгоритма метода потенциалов.

  6. Строим новую матрицу перевозок.



Матрица перевозок.

u1=010

50

1520



21113

u2=712

07

09



152010

u3= -50

514


-516

-3188



Для свободной клетки (1,4) условие оптимальности не выполнено. Строим для нее обозначенный цикл, осуществляем сдвиг по циклу на Клетка (1,4) становится базисной , клетка (2,4) – свободной. Строим новую матрицу перевозок.



Матрица перевозок

u1=010

50

520



21110

u2=712

07

109



152018

u3= -50

514


-516

-3186





  1. Переходим к шагу 2 метода потенциалов:



Для всех свободных клеток .

Полученный план является оптимальным:


.

При данном плане стоимость перевозок:


.




  1. Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница