Метод минимальной стоимости. Метод двойного предпочтения. Метод Мюллера Мербаха. Оптимизация решения транспортной задачи с использованием метода потенциалов, страница 3

Итерация 1.Шаг1. Построение допустимого плана выполним по методу минимальной стоимости. 

Приближенный оптимальный план транспортной задачи по критерию времени может быть найден с помощью модифицированного метода разрешающих слагаемых  - автор И.В, Романовский. Приведем краткое его описание.

Шаг1. Построение первоначального плана. В каждом столбце матрицы с_ijотыскивается минимальное значение времени и в соответствующую клетку заносится  величина спроса соответствующего столбца.

Шаг2.Расчитываются небалансы по каждой строке

Производится метка строк в соответствии со знаками небалансов Если небаланс строка называется недостаточной, если ,  то избыточной. Нейтральные строки, ,  также классифицируются на недостаточные и избыточные в зависимости от связи с  абсолютно недостаточной ,  или абсолютно избыточной, , строкой.

Шаг3. Проверка получен ли оптимальный и допустимый план:  Да, если все небалансы одного знака или равны нулю. Если - нет, переход к шагу 4.

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

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

Рассмотрим пример, приведенный в таблицах 7.4-7.8. Пусть необходимо выполнить план спецперевозок, и найти минимальный срок их окончания. В качестве ограничений выступают вагоны.В качестве критерия оптимальности используются сутки, затраченные на передвижение вагона.

 Таблица 7.3.