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

Проверим условие разрешимости транспортной задачи:
i=13ai=180+350+20=550
j=15bj=110+90+120+80+150=550
Т.к. ai=bj, то имеем ТЗ закрытого типа.
Составим математическую модель:
xij > 0, i=1,2,3, j=1..5
x11+x12+x13+x14+x15=180x21+x22+x23+x24+x25=350x31+x32+x33+x34+x35=20x11+x21+x31=110x12+x22+x32=90x13+x23+x33=120x14+x24+x34=80x15+x25+x35=150
F = 7x11 + 12x12 + 4x13 + 6x14 + 5x15 + x21 + 8x22 + 6x23 + 5x24 + 3x25 + 6x31 + 13x32+ 8x33+ 7x34 + 4x35 min
Найдем исходный опорный план методом наименьшей стоимости.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены.
110 90 120 80 150
180
7 60 12 120 4
6
5
350 110 1 10 8
6 80 5 150 3
20
6 20 13
8
7
4
Т.о . мы получили первый опорный план:
X0=0601201101000200 008015000
Проверим число базисных клеток. В общем случае их должно быть: m+n-1=7 шт., т.е. заполненных клеток должно быть 7 штук. В таблице это выполняется, значит, исходный опорный план найден верно. Найдем значение целевой функции
F(x) = 12*60 + 4*120 + 1*110 + 8*10 + 5*80 + 3*150 + 13*20 = 2500
Проверим полученный план на оптимальность. Для этого найдем значение потенциалов поставщиков и потребителей Ui и Vj соответственно (потенциалы находим только для базисных клеток) по формуле Ui Vj Cij, полагая, что U1=0. Составим и решим следующую систему:
U1+V2=12; V2=12U2+V2=8; U2=-4U2+V1=1; V1=5U2+V4=5; V4=9U2+V5=3; V5=7U3+V2=13; U3=1U1+V3=4; V3=4
Найдем оценки свободных клеток по формуле: ij Ui Vj Cij:
11=0+5-7=-214=0+9-6=315=0+7-5=223=-4+4-6=-6
31=1+5-6=033=1+4-8=-334=1+9-7=335=1+7-4=4
Т.к