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

Для решения задачи необходимо выполнение следующего условия:cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей. Проверим. Запасы поставщиков: 20 + 10 + 12 = 42 единиц продукции. Потребность потребителей: 19 + 31 + 10 = 60 единиц продукции.
Суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.
Для решения задачи необходимо выполнение следующего условия:количество задействованных маршрутов = количество поставщиков + количество потребителей - 1. Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.
В первую очередь, будем задействовать маршруты с наименьшей стоимостью доставки.
Поставщик Потребитель Запас
B 1 B 2 B 3
A 1 5 3 1 10
A 2 3 2 4 20
A 3 4 1 2 30
Потребность 15 20 25
10 = min { 25, 10 }
Поставщик Потребитель Запас
B 1 B 2 B 3
A 1 5 3 10
1 10   нет
A 2 3 2 4 20
A 3 4 1 2 30
Потребность 15 20 2515
20 = min { 20, 30 }
Поставщик Потребитель   Запас  
B 1 B 2 B 3
A 1 5 3 10
1   10   нет  
A 2 3 2 4   20  
A 3 4 20
1 2   30   10  
Потребность 15 20нет 2515
10 = min { 15, 10 }
Поставщик Потребитель Запас
B 1 B 2 B 3
A 1 5 3 10
1 10   нет
A 2 3 2 4 20
A 3 4 20
1 10
2 30   10   нет
Потребность 15 20нет 25155
15 = min { 15, 20 }
Поставщик Потребитель Запас
B 1 B 2 B 3
A 1 5 3 10
1 10   нет
A 2 15
3 2 4 20   5
A 3 4 20
1 10
2 30   10   нет
Потребность 15нет 20нет 25155
5 = min { 5, 5 }
Поставщик Потребитель Запас
B 1 B 2 B 3
A 1 5 3 10
1 10   нет
A 2 15
3 2 5
4 20   5   нет
A 3 4 20
1 10
2 30   10   нет
Потребность 15нет 20нет 25155нет
Стоимость доставки продукции, для начального решения, не сложно посчитать.
10*1 + 15*3 + 5*4 + 20*1 + 10*2 = 115 ден . ед.
Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число u i , называемое потенциалом поставщика.Каждому потребителю B j ставим в соответствие некоторое число v j , называемое потенциалом потребителя.
Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.Значение одного потенциала необходимо задать. Пусть u2 = 0. Последовательно найдем значения потенциалов.
Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.Значение одного потенциала необходимо задать. Пусть u2 = 0. Последовательно найдем значения потенциалов.
A2B1 :   v1 + u2 = 3         v1 = 3 - 0 = 3
A2B3 :   v3 + u2 = 4         v3 = 4 - 0 = 4
A3B3 :   v3 + u3 = 2         u3 = 2 - 4 = -2
A1B3 :   v3 + u1 = 1         u1 = 1 - 4 = -3
A3B2 :   v2 + u3 = 1         v2 = 1 - (-2) = 3
Найдем оценки незадействованных маршрутов.
A1B1 :   Δ11 = c11 - ( u1 + v1 ) = 5 - ( -3 + 3 ) = 5
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 3 - ( -3 + 3 ) = 3
A2B2 :   Δ22 = c22 - ( u2 + v2 ) = 2 - ( 0 + 3 ) = -1
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 4 - ( -2 + 3 ) = 3
Поставщик Потребитель   U  
B 1 B 2 B 3
A 1 5 3 10
1   u1 = -3  
A 2 15
3 2 5
4   u2 = 0  
A 3 4 20
1 10
2   u3 = -2  
  V     v1 = 3     v2 = 3     v3 = 4  
Есть отрицательные оценки, следовательно, возможно получить новое решение, как минимум, не хуже имеющегося.
ШАГ №1.
Выберем ячейку A2B2, ее оценка отрицательная