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

Закрываем потребности b1 поставкой из а1 и этот столбец исключаем из дальнейшего рассмотрения. Остаток груза из а1 отправляем потребителю b2 и строку а1 исключаем из дальнейшего рассмотрения. Затем весь груз из а2 отправляем в b2, исключая строку а2 и частью груза из а3 закрываем потребность b2, исключая столбец b2. Далее закрываем потребность b3 поставкой из а3, а остаток груза из а3 отправляем потребителю b4. Груз из а4 отправляем потребителю b4. Опорный план составлен.

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

Z1 = 95·17 + 10∙12 + 70∙11 + 80∙19 + 135∙22 + 25·27 + 85·7 = 8265 д.е.

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

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

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

V1 = C11 - U1 = 17 - 0 = 17; V2 = C12 - U1 = 12 - 0 = 12; U2 = C22 - V2 = 11 - 12 = -1;3 = C32 - V2 = 19 - 12 = 7; V3 = C33 - U3 = 22 - 7 = 15; V4 = C34 - U3 = 27 - 7 = 20.4 = C44 - V4 = 7 - 20 = -13;

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

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

Е13 = С13 - (V3 + U1) = 17 - (15 + 0) = 2; Е14 = С14 - (V4 + U1) = 21 - (20 + 0) = 1;

Е21 = С21 - (V1 + U2) = 6 - (17 - 1) = -10; Е23 = С23 - (V3 + U2) = 20 - (15 - 1) = 6;

Е24 = С24 - (V4 + U2) = 28 - (20 - 1) = 9; Е31 = С31 - (V1 + U3) = 10 - (17 + 7) = -14;

Е41 = С41 - (V1 + U4) = 18 - (17 - 13) = 14; Е42 = С42 - (V2 + U4) = 14 - (12 - 13) = 15;

Е43 = С43 - (V3 + U4) = 23 - (15 - 13) = 21;

Среди характеристик свободных клеток есть две отрицательные (Е21 = -10 и Е31 = -14), значит полученный план не оптимален.

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

Таблица 2