Имеются 3 пункта поставки однородного груза A1

Bj
Ai
B1
B2
B3
B4
B5
Запасы
A1
6 9 12 15 4 280
A2
12 7 11 5 3 170
A3
9 5 17 14 10 260
Потребности 160 140 200 100 110
i=13ai=280+170+260=710;
i=15bj=160+140+200+100+110=710.
Так как i=13ai=i=15bj, следовательно, задача закрытая.
Построим начальный базисный план методом минимальной стоимости. Назначение перевозок начинаем с клетки (2;5), имеющей минимальную стоимость перевозки 3. В клетку (2;5) записываем наименьшее из значений a2 и b5 x25=min170;110=110 и исключаем из дальнейшего рассмотрения пятый столбец. Вычеркнув пятый столбец, корректируем запасы второго поставщика на величину x25=110, a2=170-110=60. Следующая поставка осуществляется от второго поставщика четвертому потребителю. В клетку (2;4) назначаем перевозку x24=min60;100=60, исключаем из дальнейшего рассмотрения второго поставщика. Корректируем потребности четвертого потребителя b4=100-60=40. С оставшейся матрицей поступаем аналогично предыдущему:
x32=min260;140=140; a3=260-140=120;b2=140-140=0;
x11=min280;160=160; a1=280-160=120;b1=160-160=0;
x13=min120;200=120; a1=120-120=0;b3=200-120=80;
x34=min120;40=40; a3=120-40=80;b4=40-40=0;
x33=min80;80=80; a3=80-80=0;b3=80-80=0.
План перевозок, построенный методом минимальной стоимости:
Bj
Ai
B1
B2
B3
B4
B5
Запасы
A1
6
160 9 12
120 15 4
280
A2
12
7 11 5
60 3
110 170
A3
9
5
140 17
80 14
40 10
260
Потребности 160 140 200 100 110
Суммарные затраты, соответствующие данному плану X0 равны
ZX0=6∙160+12∙120+5∙60+3∙110+5∙140+17∙80+14∙40=5650 ден . ед.
Построенный начальный план перевозок является невырожденным, так как число назначенных перевозок xij равно m+n-1=3+5-1=7.
С помощью метода потенциалов вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках. Если известен ui, то vj=cij-ui, если известен vj, то ui=cij-vj. Положим, например, u1=0. Тогда будут вычислены и остальные потенциалы строк и столбцов.
u1=0;
v1=c11-u1=6-0=6;
v3=c13-u1=12-0=12;
u3=c33-v3=17-12=5;
v2=c32-u3=5-5=0;
v4=c34-u3=14-5=9;
u2=c24-v4=5-9=-4;
v5=c25-u2=3--4=7.
vj
ui v1=6
v2=0
v3=12
v4=9
v5=7
u1=0
6
160 9 12 -
120 15 4 +
u2=-4
12
7 11 5 +
60 3 -
110
u3=5
9
5
140 17 +
80 14 -
40 10
Для незагруженных клеток вычислим величины превышения стоимости ∆ij=cij-ui-vj:
∆12=9-0-0=9; ∆14=15-0-9=6;
∆15=4-0-7=-3<0; ∆21=12--4-6=10;
∆22=7--4-0=11; ∆23=11--4-12=3;
∆31=9-5-6=-2<0; ∆35=10-5-7=-2<0.
Полученный план не оптимален. Среди оценок ∆ij имеются отрицательные значения. Потенциальной является клетка 1;5. От клетки 1;5 строим замкнутый контур: 1;5, 2;5, 2;4, 3;4,3;3,(1;3). Начиная с клетки 1;5 разметим вершины контура попеременно знаками плюс «+», минус «-», обходя замкнутый контур в любом направлении