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

Суммарные запасы Σ аі = 30+40+10+18+10=108 ,
суммарные потребности Σ bj=20+40+30+20=110.
Σ аі = Σ bj, запасы не равняются потребностям, то есть это открытая модель транспортной задачи. Вводим фиктивного (шестого) поставщика с запасами а6 = 2. Это будет шестая строка таблицы с нулевыми стоимостями перевозок. Эти клетки при заполнении таблицы заполняем в последнюю очередь.
Составим математическую модель задачи.
Пусть хіj – количество единиц груза, которое планируется перевезти из пункта Аі к пункту Вj (это план перевозок). Тогда общая стоимость всех перевозок будет : Z = Σ Σ Cij хij, ее необходимо минимизировать.
Количество единиц не может быть отрицательной, поэтому
хіj ≥ 0.
Из условия задачи вытекает, что должны выполняться такие условия :
Σ хіj = аі , i =1,2,3,4,5,6,
то есть весь груз из пунктов Аі необходимо вывезти.
Кроме того нужды потребителей Вj должны быть полностью удовлетворены, то есть Σ хіj = bj , j = 1,2,3,4.
Таким образом, математическая модель задачи имеет вид :
1415415120015Z = Σ Σ Cij хіj → min
Σ хіj = аі , і=1,2,3,4,5,6
Σ хіj = bj , j = 1,2,3,4.
хіj ≥ 0
00Z = Σ Σ Cij хіj → min
Σ хіj = аі , і=1,2,3,4,5,6
Σ хіj = bj , j = 1,2,3,4.
хіj ≥ 0
Для поиска начального опорного плана используем метод “минимальной стоимости” или другое название - метод “минимального элемента”.
Составим транспортную таблицу, в углы клеток запишем заданные тарифы Сіj, а в середины клеток будем последовательно заносить значения хіj по схеме :
Из всей таблицы стоимостей выбираем клетку АіВj с наименьшей стоимостью Сіj, то есть ищем min Сіj , и заносим в нее число хіj = min {аі , bj }.
Потом вычеркиваем и больше не рассматриваем строку, которая отвечает поставщику, запасы которого полностью исчерпаны, или столбец, который отвечает потребителю, нужды которого полностью удовлетворенны.
В части таблицы , которая осталась после вычеркивания, снова ищем min Сіj и процесс распределения продолжаем до тех пор, пока все запасы не будут исчерпаны, а нужды – удовлетворены.
Фиктивные клетки заполняем в последнюю очередь.
В1
В2
В3
В4
Запасы
аі
А1 ___ 5
1 ___ 7 ___ 6
30
а1 = 30
А2
1 ___ 5 ___ 8
1

20
20
а2 = 40 а2’= 20
А3 ___ 5 ___ 6
3 ___ 3
10
а3 = 10
А4 ___ 2 ___ 5
1 ___ 4
18
а4 = 18
А5 ___ 3
7 ___ 9 ___ 1
10
а5 = 10
А6,ф ___ 0 ___ 0
0 ___ 0
2
а6 = 2
Потребн
bj b1 = 20 b2 = 40 b3 = 30 b4 = 20 110
b2 ’= 10 b3 ’= 12
b3 ''= 2
Транспортная таблица заполнена . Получено 7 занятых клеток. Начальный опорный план имеет вид :
х12 =30; х21 = 20; х24 = 20; х33 =10; х43 = 18; х52 = 10; х63 = 2; остальные хіj = 0
Стоимость этого плана :
Z = 30∙1 + 20∙1 + 20∙1 + 10∙3 + 18·1 + 107 = 188.
Теперь нужно проверить этот план на оптимальность с помощью метода
потенциалов. Числа ui и vj - это потенциалы, которые находим из условия: ui + vj = Сіj для занятых клеток, причем u1= 0.
Для применения метода потенциалов опорный план должен быть невырожденным, т.е. число занятых клеток должно равняться m + n – 1 = 6 + 4 – 1 = 9, поэтому в две незанятых клетки с небольшой стоимостью, не образующих цикл с остальными занятыми клетками, например, в клетки А3В2 заносим нулевые перевозки х41 =0 и х54 =0 и считаем эти клетки занятыми.
Добавим к таблице строку и столбец для записи потенциалов, вычислим эти потенциалы и проверим выполнение условия оптимальности : ui + vj ≤ Сіj для всех свободных (не занятых ) клеток.
vj
uі В1
В2
В3
В4
v1 =-5
v2 =1
v3 =-6
v4 =-5
аі
А1 u1= 0
5
1
7
6
0-55
30
0-67
0-56
30
А2 u2 =6 + 1
5
8 1
4918671086020
6+15
6-68
20
40
А3 u3 =9
5
6
3
3
9-55
9+16
10
9-53
10
А4 u4 =7 2
5 + 1
4
0
7+15
18
7-54
18
А5 u5 =6
3 7
9 + 1
6-53
10
6-69
0
10
А6,ф u6 =6
0 + 0 0
0
6-50
6+10
2
650
2
bj
20
40
30
20
110

Видим, что условие оптимальности нарушено в семи клетках (неравенства выделены красным цветом), причем наибольная разность (6+1=7-0=7) - в клетке А6В2, т.е