18. Транспортная задача и ее ранг.

Поставщик	Потребители				Запасы
	В1	В2	В3	В4
А1	х11 ^1	х12 ^2	х13 ^5	х14 ^3		60
А2	х21 ^1	х22 ^6	х23 ^5	х24 ^2		120
А3	х31 ^6	х32 ^5	х33 ^7	х34 ^4		100
Потребители	20	110	40	110

Составим математическую модель этой задачи. Обозначим: x_ij - объем перевозки груза от поставщика А_i к потребителю B_j.

Поставки в дальнейшем будут записываться в середину клетки. Поскольку все запасы должны быть реализованы, а спросы удовлетворены, то получим систему уравнений:

1 2 5 3 1 6 5 2 6 5 7 4	60 120 100
20 110 40 110

Это задача линейного программирования. Ее называют транспортной задачей.

Алгоритм решения ТЗ:

1)проверяем тип модели ТЗ и в случае открытой модели сводим к закрытой 2)находим опорный план перевозок методом наименьшего тарифа 3)проверяем план (таблицу) на удовл. систем уравнений и на невырожденность. В случае вырождения плана добавляем условно заполненные клетки с поставкой, равной нулю. 4)проверяем опорный план на оптимальность; а)составляем систему уравнений потенциалов по заполненным клеткам б)находим одно из ее решений при α₁=0 в)находим суммы α_i + β_j = C_ij (косвенные тарифы для всех пустых клеток) г)сравниваем косвенные тарифы с истинными: если косв. тарифы не превосходят собственных истинных (c_ij <= c_ij) во всех пустых клетках, то план оптимален (критерий оптимальности выполняется) решение закончено; ответ дается в виде плана перевозок последней таблицей и значения min f Если критерий оптимальности не выполняется, то переходим к следующему шагу. 5)Для перехода к следующей таблице плана выбираем а)одну из пустых клеток, где косвенный тариф больше истинного c_ij > c_ij б)составим цикл пересчета для этой клетки и расставляем знаки «+» и «-» в вершинах цикла путем их чередования, приписывая пустой клетке знак «+» в)находим число пересчета цикла x=min (x_ij) <- (фигурные скобки) г)составляем новую таблицу, добавляя x «+»-ые клетки и отним-ся x из поставок «-»-ых клеток цикла. 5) см. п. 3

19. Проверка опорного плана на оптимальность (метод потенциалов).

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций.

Общая схема отдельной итерации такова.

По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:

Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

 

Рассмотрим подробнее процесс определения потенциалов текущего плана транспортной задачи. Потенциал первого пункта потребления принимаем равным нулю

Теперь, зная его, мы можем определить потенциалы для всех пунктов производства, связанных с первым пунктом ненулевыми перевозками.

Для свободных клеток транспортной таблицы вычисляются величины

называемые разностями потенциалов. В таблице они выписаны для всех небазисных клеток под ценами.

Разность потенциалов можно трактовать как увеличение цены продукта при его перевозке из пункта i в пункт j.

Процесс «улучшения» плана состоит в определении вводимой и выводимой клеток, в чем прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.

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

В построенной цепочке, начиная с вводимой клетки (которая считается первой), помечаются вершины: нечетные — знаком «+», а четные знаком «—». Знаком «+» отмечаются те клетки, в которых объемы перевозок должны увеличиться (таковой, в частности, является клетка, вводимая в план, поскольку она должна стать базисной). Знаком «—» — те клетки, в которых перевозки уменьшаются с целью сохранения баланса. Среди множества клеток, помеченных знаком «—», выбирается клетка с наименьшим значением.

Она и становится кандидатом на вывод, т. к. уменьшение объема перевозок на большую величину может привести к отрицательным значениям x_i,j в других «минусовых» клетках. Затем производится пересчет плана по цепочке: к объемам перевозок в клетках, помеченных знаком «+», добавляется объем q, а из объемов клеток, помеченных знаком «—», он вычитается. В результате ввода одной клетки и вывода другой получается новый базисный план, для которого на следующей итерации описанные выше действия повторяются.

Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения вырожденного плана. Возможность получения вырожденного плана уже отмечалась при описании метода северо-западного угла. Нетрудно заметить, что вырожденный план также может получиться на этапе преобразования текущего плана по цепочке: если одинаковое минимальное значение будет достигнуто сразу на нескольких клетках, помеченных знаком «—», то при вычитании перемещаемого по цепочке объема в новом плане будет меньше чем m + n-1 ненулевых компонент.

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