Дальнейшая оптимизация решения
Полученный результат распределения составляет 2*20+2*10+2*30+1*10+2*20 = 170 рублей.
Метод минимальных тарифов на этом же примере дал результат стоимостью 210 рублей, а метод северо-западного угла — 290 руб., то есть — наименее оптимальный. Проверить этот результат на оптимальность и, при необходимости, окончательно его оптимизировать можно при помощи метода потенциалов (который в этом примере покажет, что это распределение оптимально)
Пример №2
Задача:
На три базы A1, A2, A3 поступил однородный гр уз в количествах, соответственно равных 160, 140 и
170 ед. Это груз требуется перевезти в четыре пункта назначения В1, В2, В3 и В4 соответственно в количествах 120, 50, 190 и 110 ед.
Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в таблице:
Пример №2
Пункты |
Пункты назначения |
|
||
отправления |
В1 |
В2 |
В3 |
В4 |
А1 |
7 |
8 |
1 |
2 |
А2 |
4 |
5 |
9 |
8 |
А3 |
9 |
2 |
3 |
6 |
Потребности |
120 |
50 |
190 |
110 |
Разности по |
|
|
|
|
столбцам |
|
|
|
|
Запас |
Разности по |
ы |
строкам |
160
140
170 
470
Пример №2
Пункты |
Пункты назначения |
|
||
отправления |
В1 |
В2 |
В3 |
В4 |
А1 |
7 |
8 |
1 |
2 |
|
|
|
|
110 |
А2 |
4 |
5 |
9 |
8 |
А3 |
9 |
2 |
3 |
6 |
Потребности |
120 |
50 |
190 |
110 |
Разности по |
3 |
3 |
2 |
4 |
столбцам |
|
|
|
|
Запас |
Разности по |
ы |
строкам |
160 |
1 |
50 |
|
140 |
1 |
170 |
1 |
470 |
|
Пример №2
Пункты |
Пункты назначения |
|
||
отправления |
В1 |
В2 |
В3 |
В4 |
А1
А2 
А3
Потребности
Разности по столбцам
7 |
8 |
1 |
2 |
|
|
50 |
110 |
4 |
5 |
9 |
8 |
9 |
2 |
3 |
6 |
120 |
50 |
190 |
110 |
|
|
140 |
|
3 |
3 |
2 |
4 |
3 |
3 |
2 |
|
Запас |
Разности по |
|
ы |
строкам |
|
160 |
1 |
6 |
50 |
|
|
140 |
1 |
1 |
170 |
1 |
1 |
470 |
|
|
Пример №2
Пункты
отправления
А1
А2 А3
Потребности
Разности по столбцам
Пункты назначения |
|
||
В1 |
В2 |
В3 |
В4 |
7 |
8 |
1 |
2 |
|
|
50 |
110 |
4 |
5 |
9 |
8 |
9 |
2 |
3 |
6 |
|
|
140 |
|
120 |
50 |
190 |
110 |
|
|
140 |
|
3 |
3 |
2 |
4 |
3 |
3 |
2 |
|
5 |
3 |
6 |
|
Запас |
Разности по |
||
ы |
строкам |
||
160 |
1 |
6 |
|
50 |
|
|
|
140 |
1 |
1 |
1 |
170 |
1 |
1 |
1 |
30 |
|
|
|
470 |
|
|
|
Пример №2
Пункты |
Пункты назначения |
|
||
отправления |
В1 |
В2 |
В3 |
В4 |
А1 |
7 |
8 |
1 |
2 |
|
|
|
50 |
110 |
А2 |
4 |
5 |
9 |
8 |
А3 |
9 |
2 |
3 |
6 |
|
|
30 |
140 |
|
Потребности |
120 |
50 |
190 |
110 |
|
|
20 |
140 |
|
Разности по |
3 |
3 |
2 |
4 |
столбцам |
3 |
3 |
2 |
|
|
|
|||
|
5 |
3 |
6 |
|
|
5 |
3 |
|
|
Запас |
Разности по |
|||
ы |
строкам |
|
||
160 |
1 |
6 |
|
|
50 |
|
|
|
|
140 |
1 |
1 |
1 |
1 |
170 |
1 |
1 |
1 |
7 |
30 |
|
|
|
|
470 |
|
|
|
|
Пример №2
Пункты |
Пункты назначения |
|
||
отправления |
В1 |
В2 |
В3 |
В4 |
А1 |
7 |
8 |
1 |
2 |
|
|
|
50 |
110 |
А2 |
4 |
5 |
9 |
8 |
А3 |
9 |
2 |
3 |
6 |
|
|
30 |
140 |
|
Потребности |
120 |
50 |
190 |
110 |
|
|
20 |
140 |
|
Разности по |
3 |
3 |
2 |
4 |
столбцам |
3 |
3 |
2 |
|
|
|
|||
|
5 |
3 |
6 |
|
|
5 |
3 |
|
|
Запас |
Разности по |
|||
ы |
строкам |
|
||
160 |
1 |
6 |
|
|
50 |
|
|
|
|
140 |
1 |
1 |
1 |
1 |
170 |
1 |
1 |
1 |
7 |
30 |
|
|
|
|
470 |
|
|
|
|
Пример №2
Пункты |
Пункты назначения |
|
||
отправления |
В1 |
В2 |
В3 |
В4 |
А1 |
7 |
8 |
А2 |
4 |
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
120 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
А3 |
9 |
|
|
|
|
|
2 |
|
|
|
30 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Потребности |
120 |
50 |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
|
|
|
|
|
|
|
|
|||||||||||||
Разности по |
3 |
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
столбцам |
3 |
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
12
50 110
98
36
140
190 110
140 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
2 |
|
|
|
|
|
4 |
|||||||||||||||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Запас |
Разности по |
||||
ы |
строкам |
|
|
||
160 |
1 |
6 |
|
|
|
50 |
|
|
|
|
|
140 |
1 |
1 |
1 |
1 |
1 |
20 |
|
|
|
|
|
170 |
1 |
1 |
1 |
7 |
|
30 |
|
|
|
|
|
470 |
|
|
|
|
|
Пример №2
Пункты |
Пункты назначения |
|
||
отправления |
В1 |
В2 |
В3 |
В4 |
А1 |
7 |
8 |
А2 |
4 |
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
120 |
20 |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
А3 |
9 |
|
|
|
|
|
2 |
|
|
|
30 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Потребности |
120 |
50 |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
|
|
|
|
|
|
|
|
|||||||||||||
Разности по |
3 |
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
столбцам |
3 |
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
12
50 110
98
36
140
190 110
140 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
2 |
|
|
|
|
|
4 |
|||||||||||||||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Запас |
Разности по |
|
||||
ы |
строкам |
|
|
|
||
160 |
1 |
6 |
|
|
|
|
50 |
|
|
|
|
|
|
140 |
1 |
1 |
1 |
1 |
1 |
0 |
20 |
|
|
|
|
|
|
170 |
1 |
1 |
1 |
7 |
|
|
30 |
|
|
|
|
|
|
470 |
|
|
|
|
|
|