Контрольная Распределительный метод решения транспортной задачи, номер: 69875

1. Распределительный метод решения транспортной задачи 3
Литература 16

1. Распределительный метод решения транспортной задачи

Данный метод состоит в последовательном улучшении опорного плана перевозок путем отыскания на каждом шаге выгодных циклов переноса грузов. Опорный план для данного метода (как и для других методов решения транспортной задачи методом потенциалов) можно сформировать, применяя метод «северо-западного» угла.
Более подробно рассмотрим теперь процесс формирования очередного цикла переноса на каждом новом шаге алгоритма.
Очевидно, что при перемещении х единиц груза по некоторому циклу с ценой g стоимость перевозок изменяется на величину х×g.
Тогда, для улучшения текущего плана перевозок имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна.
Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что оптимальный план достигнут.
При улучшении плана циклическими переносами пользуются приемом, заимствованным из симплекс-метода: на каждом шаге (цикле) заменяют одну свободную переменную на базисную, т.е. заполняют одну клетку и взамен того освобождают одну из базисных клеток.