Построение оптимального плана перевозок груза с минимальной стоимостью

Порядок составления опорного плана этим методом описан в задаче 7.1.

Стоимость перевозок по этому плану:

Z1 = 95·17 + 10∙12 + 70∙11 + 55∙19 + 135∙22 + 50·27 + 60·7 = 8290 д.е.

Число заполненных клеток должно быть m + n -1 = 4 + 5 - 1 = 8, что имеет место в действительности, т.е. план не вырожден.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:

Ui = Cij - Vj; Vj = Cij - Ui;

Определяем характеристики клеток, оставшихся свободными по формуле:

Eij = Cij - (Vj + Ui) (вписаны в правый нижний угол).

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

Строим для клетки а3b1 с отрицательной характеристикой (-14), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (55), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. №2) с ценой z2 = 7520.

Среди характеристик свободных клеток есть отрицательные значит полученный план не оптимален.

Строим для клетки а1b4 с отрицательной характеристикой (-13), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (40), находящихся в углах цикла, смежных с этой клеткой.

Получаем новый план (табл. №3) с ценой z3 = 7000.

Таблица 3