Товары со складов A1 A2 A3 развозятся потребителям B1

Проверим необходимое и достаточное условие разрешимости задачи:
a=50+70+70=190;
b= 50+70+70=190.
190 = 190. Следовательно, модель задачи - закрытая.
Заполним первоначальную таблицу методом северо-западного угла.
x11 = min(50,50) = 50;
x22 = min(70,70) = 70;
x33 = min(70,70) = 70.
A1
v1 = 19 A2
v2 = 11 A3
v3 = 16 Запасы
B1
u1 = 0 -5019
50 +5011
0 17
- 50
B2
u2 = 1 23
- -5012
70 +5017
0 70
B3
u3 = -5 +5012
- 7
- -5011
70 70
Потребности 50 70 70
Подсчитаем число занятых клеток таблицы, их 3, что не соответствует условию: m+n-1 = 5. Из этого делаем вывод, что опорный план является вырожденным.
Пусть x12 = 0 и x23 = 0.
Подсчитаем число занятых клеток таблицы, их 5, что соответствует условию: m+n-1 = 5 . Из этого делаем вывод, что теперь опорный план является невырожденным.
Минимальные затраты при опорном плане составят:
Z(x) = 19*50 + 11*0 + 12*70 + 17*0 + 11*70 = 2560 руб.
Проверим план на оптимальность методом потенциалов и при необходимости улучшим его.
Ui+Vj=CBij
u1 + v1 = 19; u1 = 0; v1 = 19;u1 + v2 = 11; u2 = 1; v2 = 11;
u2 + v2 = 12; u3 = -5; v3 = 16.u2 + v3 = 17; u3 + v3 = 11;
Занесем значения u1, u2, u3, v1, v2, v3 в таблицу и посчитаем оценку.
∆Cij=Ui+Vj-CBij ≤ 0
13 = 0 + 16 – 17 = -1 <0;
21 = 1 + 19 – 23 = -3 <0;
31 = -5 + 19 – 12 = 2 >0;
32 = -5 + 11 – 7 = -1 <0;
План не оптимален, т.к