На трех складах оптовой базы сосредоточен однородный груз в количествах 103

A=103+205+152=460;
b= 111+134+108+107=460 .
a =b= 460.
Следовательно, модель задачи – закрытая. Заполним первоначальную таблицу методом наименьшей стоимости.
x32 = min(152,134) = 134;
x21 = min(205,111) = 111;
x14 = min(103,107) = 103;
x24 = min(94,4) = 4;
x33 = min(18,108) = 18;
x23 = min(90,90) = 90.
Получим первый опорный план: Таблица 1
111 134 108 107
103 7
7
+906
-904
103 u1 = 0
205 3
111 7
-909
90 +904
4 u2 = 0
152 4
2
134 4
18 4 u3 = -5
v1 = 3 v2 = 7 v3 = 9 v4 = 4
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 =6. Из этого делаем вывод, что опорный план является невырожденным.
Минимальные затраты при первом опорном плане составят:
F(x) = 4*103 + 3*111 + 9*90 + 4*4 + 2*134 + 4*18 = 1911.
Проверим план на оптимальность методом потенциалов и при необходимости улучшим его .
ui+vj=сij (смотрим заполненные клетки)
u1 + v4 = 4; u1 = 0; v1 = 3;u2 + v1 = 3; u2 = 0; v2 = 7;
u2 + v3 = 9; u3 = -5; v3 = 9;u2 + v4 = 4; v4 = 4.u3 + v2 = 2;
u3 + v3 = 4.
Занесем значения u1, u2, u3, v1, v2, v3, v4 таблицу 1 и посчитаем оценки.
Проверим словие: ui+vj≤сij (смотрим пустые клетки)
11 = 0 + 3 = 3 ≤ 7 (верно);
12 = 0 + 7 = 7 ≤ 7 (верно);
13 = 0 + 9 = 9 ≤ 6 (неверно);
22 = 0 + 7 = 7 ≤ 7 (верно);
31 = -5 + 3 = -2 ≤ 4 (верно);
34 = -5 + 4 = -1 ≤ 4 (верно).
План не оптимален, т.к