Транспортная задача в матричной постановке

Проверим выполнение условия баланса. Сумма мощностей поставщиков равна сумме мощностей потребителей
23+24+16+20=19+16+16+16+16
Задача закрытого типа
Построим методом минимальной стоимости первоначальный план.
Метод заключается в следующем: выбираем клетку с наименьшей стоимостью, например клетку (1,1) и помещаем в нее 19 единиц груза. Это означает, что от поставщика А1 вывезено19 единиц груза и доставлено потребителю В1. У поставщика А1 осталось 4 единиц груза, потребитель В1 полностью удовлетворен , вычеркиваем первый столбец. Ищем следующий минимальный элемент, это клетка (1,5). Помещаем в нее 4 единиц груза. От поставщика А1 вывезено все груза и в А1 больше нет грузов, строку А1 вычеркиваем, и так далее.
Получим
Запас В1
В2
В3 В4
В5
А1
23 3
19 7
11
0 12
5
4
А2
24 10
12
8 18
15
16 18
А3 16 11 15 20
16 17 14
А4
20 8
9
8 19
22 8
12
Потребность 19 16 16 16 16
Контроль: число базисных (занятых клеток) равно 8 (m+n-1=5+4-1=8)
Стоимость доставки продукции для начального решения составляет:
Z0= 3-19+5*4+12*8+15*16+20*16+9*8+8*12=901Решим задачу методом потенциалов
Проверим оптимальность начального решения методом потенциалов.
Каждому поставщику Аi поставим в соответствие некоторое число Ui - потенциал поставщика, каждому потребителю Вj поставим в соответствие некоторое число Vj - потенциал потребителя .
Для заполненных клеток, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута, т.е. Ui+Сij=Vj, где Сij- тариф перевозки от поставщика Аi к потребителю Вj
Пусть U1=0. Для заполненных клеток
(1,1) U1+C11=0+3=3⇒ V1=3
(1,3) U1+C13=0+11=11 ⇒ V3=11
(1,5) U1+C15=0+5=5⇒ V5=5
(3,3) U3+C33= U3+20=11⇒ U3=-9
(4,5) U4+C45= U4+8=5⇒ U4=-3
(4,2) U4+C42=-3+9=6⇒ V2=6
(2,2) U2+C22= U2+12=6⇒ U2=-6
(2,4) U2+C24=-6+15⇒9 V4=9
Потребность 19 16 16 16 16
Запас В1
В2
В3 В4
В5
А1
23 3
19 7
11
0 12
5
4 U1=0
А2
24 10
12
8 18
15
16 18 U2=-6
А3 16 11 15 20
16 17 14
U3=-9
А4
20 8
9
8 19
22 8
12 U4=-3
V1=3
V2=6 V3=11 V4=9 V5=5
Проверим на оптимальность пустые клетки, используя условие Ui+Сij≥Vj
3,1: -9+11≤3
3,4: -9+17≤9
.
Для клетки (3,4) построим цикл (3,4)-(3,3)-(1,3)-(1,5)-(4,5)-(4,2)-(2,2)-(2,4)
Потребность 19 16 16 16 16
Запас В1
В2
В3 В4
В5
А1
23 3
19 7
0 11
233621180860233622215496
+ 12
5
3714171808604
-
А2
24 10
12
3085521298863022021298868
+ 18
15
37586212988616
- 18
А3 16 11 15 20
23362225515516
- 17
+ 14
А4
20 8
9
267566900558
- 19
22 8
12
+
Клетка (3,4) – вершина цикла, она находится в пустой клетке, остальные вершины находятся в заполненных клетках