Решение:
Так как суммарные запасы поставщиков 10 + 18 + 27 = 55, а суммарный спрос потребителей 13 + 18 + 15 + 17 = 63 и эти величины не равны, то задача является открытой.
Для
получения закрытой транспортной задачи
введём фиктивного поставщика с
поставляемым объёмом груза
и с нулевыми стоимостями перевозок всем
потребителям.
Получим следующую модель задачи:
Поставщики |
Потребители |
|||
13 |
18 |
15 |
17 |
|
10 |
2,4 |
5 |
4 |
7 |
18 |
2 |
5 |
4 |
9 |
27 |
2 |
6 |
6 |
10 |
8 |
0 |
0 |
0 |
0 |
Построим начальный план перевозок методом минимальной стоимости:
|
13 |
18 |
15 |
17 |
||||
10 |
|
2,4 |
|
5 |
|
4 |
|
7 |
|
10 |
|
|
|||||
18 |
|
2 |
|
5 |
|
4 |
|
9 |
|
3 |
15 |
|
|||||
27 |
|
2 |
|
6 |
|
6 |
|
10 |
13 |
5 |
|
9 |
|||||
8 |
|
0 |
|
0 |
|
0 |
|
0 |
|
|
|
8 |
|||||
Стоимость перевозки при этом составит:
13*2 + 10*5 + 3*5 + 5*6 + 15*4 + 9*10 + 8*0 = 271 ден.ед.
Проверку плана на оптимальность и, при необходимости, дальнейшее его оптимизирование проведём методом потенциалов.
Рассчитываем потенциалы:
и
Ранг системы равен: rang = m + n – 1 или в нашем случае rang = 4 + 4 – 1 = 7
Количество
отмеченных клеток 7, т.е. u1
можно взять произвольно (например 0),
остальные значения u и v
высчитываются. Получив значения u
и v считаем значения
потенциалов
:
|
13 |
18 |
15 |
17 |
ui |
||||
10 |
-1,4 |
2,4 |
0 |
5 |
0 |
4 |
2 |
7 |
0 |
0 |
10 |
0 |
0 |
||||||
18 |
-1 |
2 |
0 |
5 |
0 |
4 |
0 |
9 |
0 |
0 |
3 |
15 |
0 |
||||||
27 |
0 |
2 |
0 |
6 |
-1 |
6 |
0 |
10 |
1 |
13 |
5 |
0 |
9 |
||||||
8 |
-8 |
0 |
-4 |
0 |
-5 |
0 |
0 |
0 |
-9 |
0 |
0 |
0 |
8 |
||||||
vi |
1 |
5 |
4 |
9 |
271 |
||||
Критерием
оптимальности плана перевозок является
условие
.
В
полученном случае есть клетка, где это
условие не выполняется:
.
Построим для неё цикл перераспределения
груза и проведём перераспределение
груза по циклу, указанному стрелками
на min(10, 9) = 9 единиц груза.
Получим следующий план:
|
13 |
18 |
15 |
17 |
||||
10 |
|
2,4 |
|
5 |
|
4 |
|
7 |
|
1 |
|
9 |
|||||
18 |
|
2 |
|
5 |
|
4 |
|
9 |
|
3 |
15 |
|
|||||
27 |
|
2 |
|
6 |
|
6 |
|
10 |
13 |
14 |
|
|
|||||
8 |
|
0 |
|
0 |
|
0 |
|
0 |
|
|
|
8 |
|||||
со стоимостью перевозки 13*2 + 1*5 + 3*5+ +14*6 + 15*4 + 9*7 + 8*0 = 253 ден.ед.
Рассчитываем потенциалы:
|
13 |
18 |
15 |
17 |
ui |
||||
10 |
-1,4 |
2,4 |
0 |
5 |
0 |
4 |
0 |
7 |
0 |
0 |
1 |
0 |
9 |
||||||
18 |
-1 |
2 |
0 |
5 |
0 |
4 |
-2 |
9 |
0 |
0 |
3 |
15 |
0 |
||||||
27 |
0 |
2 |
0 |
6 |
-1 |
6 |
-2 |
10 |
1 |
13 |
14 |
0 |
0 |
||||||
8 |
-6 |
0 |
-2 |
0 |
-3 |
0 |
0 |
0 |
-7 |
0 |
0 |
0 |
8 |
||||||
vi |
1 |
5 |
4 |
7 |
253 |
||||
Вычислив потенциалы для полученного плана видим, что все , т.е. условие оптимальности выполняется.
Отбрасывая фиктивного поставщика окончательно получаем
Ответ: минимальная стоимость перевозки 253 ден. ед.
План перевозок:
|
13 |
18 |
15 |
17 |
10 |
|
1 |
|
9 |
18 |
|
3 |
15 |
|
27 |
13 |
14 |
|
|