Решить данную транспортную задачу методом потенциалов (опорный план составить при помощи любого из рассмотренных

Решить данную транспортную задачу методом потенциалов (опорный план составить при помощи любого из рассмотренных методов). Поставщики Потребители Запасы продукции B1 B2 B3 A1 3 5 7 68 A2 7 5 3 34 A3 1 2 3 141 Потребности в продукции 48 144 175

Суммарные запасы продукции составляют 68+34+141=243
Суммарный потребности потребителей 48+144+175=367
Задача открытая, поэтому вводим фиктивного поставщика с запасами продукции 367-243=124 и заведомо высокой стоимостью перевозок, например 10.
Поставщики Потребители Запасы продукции
B1
B2
B3
A1
3 5 7 68
A2
7 5 3 34
A3
1 2 3 141
A4
10 10 10 124
Потребности в продукции 48 144 175
Составляем первоначальный план перевозок методом минимальной стоимости (заполняем максимально возможный объем поставки стоимостью 1: a31=48, затем – поставки стоимостью 2: a32=93 и т.д.):
b1=48
b2=144
b3=175
a1=68
3 5 7
68
a2=34
7 5 3
34
a3=141
1 2 3
48 93
a4=124
10 10 10
51 73
Число занятых клеток равно 6, при этом n + m – 1= 3 + 4 – 1 =67, то есть план невырожденный. Рассчитаем систему потенциалов. Полагаем u1=0.
Из первой строки: u1+v3=7 v3=7.
Из третьего столбца: u2+v3=3,u4+v3=10 u2=-4,u4=3
Из четвертой строки: u4+v2=10 v2=7
Из третьего столбца: u3+v2=2 u3=-5
Из третьей строки: u3+v1=1 v1=6.
После этого находим величины ∆ij=ui+vj-cij для всех незанятых поставками клеток:
v1=6
v2=7
v3=7
u1=0
3 5 7
68
3 2
u2=-4
7 5 3
34
-5 -2
u3=-5
1 2 3
48 93
-1
u4=3
10 10 10
51 73
-1
Поскольку есть положительные величины, план не оптимален

. Выбираем точку с максимальным значением: ∆11=3. Проведем перераспределение поставок: построим прямоугольник перераспределения через 6 клеток. Находим минимальную поставку среди отрицательных вершин: 48.
v1=6
v2=7
v3=7
u1=0
3 5 7
+
68-
3 2
u2=-4
7 5 3
34
-5 -2
u3=-5
1 2 3
48-
93+
-1
u4=3
10 10 10
51-
73+
-1
После перераспределения новый план поставок имеет вид:
b1=48
b2=144
b3=175
a1=68
3 5 7
48
20
a2=34
7 5 3
34
a3=141
1 2 3
141
a4=124
10 10 10
3 121
Число занятых клеток равно 6, то есть план невырожденный. Пересчитываем систему потенциалов, находим ∆ij:
v1=3
v2=7
v3=7
u1=0
3 5 7
48
20
2
u2=-4
7 5 3
34
-8 -2
u3=-5
1 2 3
141
-3
-1
u4=3
10 10 10
3 121
-4
Поскольку есть положительная величина ∆11=2, план не оптимален