Решить транспортную задачу методом потенциалов

Проверим условие разрешимости транспортной задачи:
i=13ai=9+16+5=30
j=15bj=11+7+8+4=30
Т.к. ai=bj, то имеем ТЗ закрытого типа.
Составим математическую модель:
xij > 0, i=1,2,3, j=1..4
x11+x12+x13+x14=9x21+x22+x23+x24=16x31+x32+x33+x34=5x11+x21+x31=11x12+x22+x32=7x13+x23+x33=8x14+x24+x34=4
Z=2x11 + 5x12 + 8x13 + x14 + 8x21 + 3x22 + 9x23 + 2x24 + 7x31+ 4x32+ 6x33+ 3x34min
Найдем исходный опорный план методом северо-западного угла. Заполнять начинаем с клетки (1;1):
Поставщики Потребители
11 7 8 4
9 9 2 - 5 - 8 - 1
16 2 8 7 3 7
9 - 2
5 - 7 - 4 1 6 4 3
Искомый элемент равен c11=2. Для этого элемента запасы равны 9, потребности 11. Поскольку минимальным является 9, то вычитаем его.x11 = min(11,9) = 9; b1=2, x21=min(16,2)=2; вычеркиваем первый столбец и первую строку.
x22=min(14,7)=7, вычеркиваем 2 столбец . x23=min(7,8)=7, вычеркиваем 2 строку. x33=min(5,1)=1, вычеркиваем 3 столбец. х34=min(4,4)=4, вычеркиваем 3 строку и 4 столбец.
Т.о. мы получили первый опорный план: X0=9 2 0 070 0 7 1 0 0 4
Проверим число базисных клеток. В общем случае их должно быть: m+n-1=6 шт., т.е. заполненных клеток должно быть 6 штук. В таблице это выполняется, значит, исходный опорный план найден верно. Найдем значение целевой функции
F(x) = 2*9 + 8*2 + 3*7 + 9*7 + 6*1 + 3*4 = 136
Проверим полученный план на оптимальность. Для этого найдем значение потенциалов поставщиков и потребителей Ui и Vj соответственно (потенциалы находим только для базисных клеток) по формуле Ui Vj Cij, полагая, что U1=0. Составим и решим следующую систему:
U1+V1=2; V1=2U2+V1=8; U2=6U2+V2=3; V2=-3U2+V3=9; V3=3U3+V3=6; U3=3U3+V4=3; V4=0
Находим косвенные стоимости:
c’12=u1+v2=0-3=-3;c’13=u1+v3=0+3=3;
c’14=u1+v4=0+0=0;c’24=u2+v4=6+0=6;
c’31=u3+v1=3+2=5;c’32=u3+v2=3-3=0.
Находим разности:
γ12=с12-c’12=5+3=8;
γ13=с13-c’13=8-3 =5;
γ14=с14-c’14=1-0=1;
γ24=с24-c’24=2-6=-4;
γ31=с31-c’31=7-5=2;
γ32=с32-c’32=4-0=0.
Так как есть разности меньше нуля, то решение не является оптимальным.
Т.к