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

Проверим необходимое и достаточное условие разрешимости задачи:
ai=17+37+46=100>bi=27+43+22+19=111.
Таким образом, потребности покупателей превышают запасы, что говорит о том, что модель исходной транспортной задачи является открытой. Для того, чтобы получить закрытую модель, введем дополнительного поставщика с запасом
a4=bi-ai=111-110=11.
Составим таблицу:
b1
b2
b3
b4
Запасы
a1
22 24 19 29 17
a2
18 30 32 26 37
a3
28 20 17 32 46
a4
0 0 0 0 11
Потребности 27 43 22 19
Построим опорный план, используя метод наименьшей стоимости:
mincij=c33=17,
x33=mina3,b3=min46,22=22.
Таблица примет вид:
b1
b2
b3
b4
Запасы
a1
22 24 – 29 17
a2
18 30 – 26 37
a3
28 20 17 22
32 46 – 22 = 24
a4
0 0 – 0 11
Потребности 27 43 22 – 22 = 0 19
mincij=c21=18,
x33=mina2,b1=min37,27=27.
Таблица примет вид:
b1
b2
b3
b4
Запасы
a1
– 24 – 29 17
a2
18 27
30 – 26 37 – 27 = 10
a3
– 20 17 22
32 24
a4
– 0 – 0 11
Потребности 27 – 27 = 0 43 0 19
mincij=c32=20,
x32=mina3,b2=min24,43=24.
Таблица примет вид:
b1
b2
b3
b4
Запасы
a1
– 24 – 29 17
a2
18 27
30 – 26 10
a3
– 20 24
17 22
– 24 – 24 = 0
a4
– 0 – 0 11
Потребности 0 43 – 24 = 19 0 19
mincij=c12=24,
x12=mina1,b2=min17,19=17.
Таблица примет вид:
b1
b2
b3
b4
Запасы
a1
– 24 17
– – 17 – 17 = 0
a2
18 27
30 – 26 10
a3
– 20 24
17 22
– 0
a4
– 0 – 0 11
Потребности 0 19 – 17 = 2 0 19
mincij=c24=26,
x24=mina2,b4=min10,19=10.
Таблица примет вид:
b1
b2
b3
b4
Запасы
a1
– 24 17
– – 0
a2
18 27
30 – 26 10
10 – 10 = 0
a3
– 20 24
17 22
– 0
a4
– 0 – 0 11
Потребности 0 2 0 19 – 10 = 9
mincij=c42=0,
x42=mina4,b2=min11,2=2.
Таблица примет вид:
b1
b2
b3
b4
Запасы
a1
– 24 17
– – 0
a2
18 27
– – 26 10
0
a3
– 20 24
17 22
– 0
a4
– 0 2
– 0 11 – 2 = 9
Потребности 0 2 – 2 = 0 0 9
mincij=c44=0,
x44=mina4,b4=min9,9=9.
Таблица примет вид:
b1
b2
b3
b4
Запасы
a1
– 24 17
– – 0
a2
18 27
– – 26 10
0
a3
– 20 24
17 22
– 0
a4
– 0 2
– 0 9
9 – 9 = 0
Потребности 0 0 0 9 – 9 =0
Полученный опорный план является допустимым, так как все грузы вывезены от поставщиков, потребности всех покупателей удовлетворены, а также план соответствует системе ограничений транспортной задачи