В следующих транспортных задачах найти такие объёмы перевозок однородной продукции от поставщиков к потребителям

В следующих транспортных задачах найти такие объёмы перевозок однородной продукции от поставщиков к потребителям при которых общие затраты на перевозку продукции будут минимальными. В таблицах заданы объёмы запасов продукции у поставщиков (Ai), объемы потребности в продукции потребителей (Bj) и удельные затраты на перевозку единицы продукции от поставщиков к потребителям (пересечение соответствующих строк и столбцов таблицы).

Bj
Ai 1 2 3 4
37 127 43 34
1 21 2 1 1 4
2 9 7 0 2 4
3 168 6 2 0 7
Определим тип задачи. ∑Ai=21+9+168=198;
∑Bj =37+127+43+34=241.
Условие баланса не соблюдается. Запасы не равны потребностям=> открытый тип.
Потребность в продукции больше, чем запасов на 241– 198=43 единиц. Для того чтобы преобразовать эту задачу в закрытую, необходимо ввести 4 фиктивного поставщика с объёмом запасов 43 единиц. Удельные затраты полагаем равными нулю.
Bj
Ai 1 2 3 4
37 127 43 34
1 21 2 1 1 4
2 9 7 0 2 4
3 168 6 2 0 7
4 43 0 0 0 0
Решим задачу методом минимального элемента.
Bj
Ai 1 2 3 4
37 127 43 34
1 21 2 21 1 1 4
2 9 7 9 0 2 4
3 168 28 6 97 2 43 0 7
4 43 9 0 0 34 0 0
Находим наименьшую стоимость и заполняем таблицу.
m + n - 1 = 7
Z=1*21+0*9+6*28+2*97+0*43+0*9+0*34=383 
Метод потенциалов
Проверим исходный план, построенный методом минимального элемента, на оптимальность:
Пусть u1 = 0. u1 + v2 = 1; v2 = 1 u2 + v2 = 0; u2 = -1 u3 + v2 = 2; u3 = 1 u3 + v1 = 6; v1 = 5 u4 + v1 = 0; u4 = -5 u4 + v4 = 0; v4 = 5 u3 + v3 = 0; v3 = -1 
Bj
Ai v1=5 v2=1 v3=-1 v4=5
37 127 43 34
u1=0 21 2 21 1 1 4
u2=-1 9 7 9 0 2 4
u3=1 168 28 6 97 2 43 0 7
u4=5 43 9 0 0 34 0 0
План не оптимален, т.к есть клетки, для которых условие ui + vj ≤ cij не выполнено.
Строим цикл:
Bj
Ai v1=5 v2=1 v3=-1 v4=5
37 127 43 34
u1=0 21 + 2 -21 1 1 4
u2=-1 9 7 9 0 2 4
u3=1 168 -28 6 +97 2 43 0 7
u4=5 43 9 0 0 34 0 0
θ = min{21; 28} = 21
Bj
Ai v1=2 v2=-2 v3=-4 v4=2
37 127 43 34
u1=0 21 21 2 1 1 4
u2=2 9 7 9 0 2 4
u3=4 168 7 6 118 2 43 0 7
u4=2 43 9 0 0 34 0 0
u1 = 0. 
u1 + v1 = 2; v1 = 2 u3 + v1 = 6; u3 = 4 u3 + v2 = 2; v2 = -2 u2 + v2 = 0; u2 = 2 u3 + v3 = 0; v3 = -4 u4 + v1 = 0; u4 = -2 u4 + v4 = 0; v4 = 2 
Т.к ui + vj ≤ cij. выполнено=> план оптимален
Z= 2*21+0*9+6*7+2*118+0*43+0*9+0*34=320 
Ответ: 320