Расчет потенциалов.Расчет потенциалов выполняют по загруженным клеткам таблицы поставок, для которых:
где αi, βj – потенциал i -ой строки и j -ой колонки соответственно. Для первой строки принимают α 1=0, затем остальные потенциалы рассчитывают по загруженным клеткам в соответствии с выражением (6.14). Результаты расчетов заносят в таблицу поставок. Таблица 6.2 Таблица поставок
5. Проверка плана на оптимальность. Проверка опорного плана на оптимальность осуществляется по незагруженным клеткам. Если для всех незагруженных клеток выполняется условие:
то найденный опорный план является оптимальным. Оптимальное решение будет единственным, если для всех незагруженных клеток выполняется условие:
Если для какой-либо незагруженной клетки условие (6.15) не выполняется, то опорный план не является оптимальным и переходят к следующему этапу.
6. Поиск «вершины максимальной неоптимальности» (ВМН). По незагруженным клеткам, для которых условие (6.15) не выполняется, рассчитывают оценки:
где Среди полученных оценок находят наибольшую, т.е.:
которая соответствует ВМН. Клетку, соответствующую ВМН, в таблице поставок помечают «+».
|
, (6.16)
, (6.17)
. (6.18)
, (6.19)
– множество пар индексов (i, j), соответствующих незаполненным клеткам, для которых не выполняется условие оптимальности (6.15). Данные оценки характеризуют размер экономии транспортных издержек на 1 ед. перевозимого груза.
, (6.20)
