Транспортной называется задача линейного программирования, основанная на поиске оптимальных «маршрутов перевозки» путем создания циклов. По сути задача сводится к тому, чтобы найти оптимальный способ перевозки груза из точки А в точку B при минимальных затратах.
Условие сбалансированной транспортной задачи:
Необходимо перевести 140 единиц продукта от производителей на склады. Цены перевозок по маршрутам указаны также в таблице. Требуется найти наиболее дешевый вариант перевозки.
|
B1 |
B2 |
B3 |
B4 |
|
A1 |
10 |
7 |
12 |
5 |
20 |
A2 |
3 |
8 |
5 |
2 |
40 |
A3 |
2 |
14 |
4 |
6 |
30 |
A4 |
7 |
11 |
2 |
13 |
50 |
|
15 |
45 |
20 |
60 |
140 |
Решение:
Сначала путем распределения 140 единиц продукта методом северо-западного угла получим опорные решения:
|
B1 |
B2 |
B3 |
B4 |
|
A1 |
1510 |
57 |
12 |
5 |
20 |
A2 |
3 |
408 |
5 |
2 |
40 |
A3 |
2 |
14 |
204 |
106 |
30 |
A4 |
7 |
11 |
2 |
5013 |
50 |
|
15 |
45 |
20 |
60 |
140 |
В таком первоначальном варианте стоимость транспортировки будет равна 150+35+320+80+60+650=1295. Понятно, что существуют варианты более оптимальные,, нежели данный опорный вариант. Для их нахождения следует выделить один из отрицательных циклов. Например такой:
Легко проверить, что он отрицательный: 7-10+5-13= -11. После перегруппировки внутри данного цикла мы получаем следующее:
|
B1 |
B2 |
B3 |
B4 |
|
A1 |
10 |
57 |
12 |
15 5 |
20 |
A2 |
3 |
408 |
5 |
2 |
40 |
A3 |
2 |
14 |
204 |
106 |
30 |
A4 |
157 |
11 |
2 |
3513 |
50 |
|
15 |
45 |
20 |
60 |
140 |
При этом варианте цена составит уже 1130 единиц, т.е. на 165 единиц меньше.
Найдем еще один отрицательный цикл:
Этот цикл также является отрицательным: 2-4+6-13= -9. Теперь, чтобы уменьшить общую цену, проведем перегруппировку в пределах этого цикла:
|
B1 |
B2 |
B3 |
B4 |
|
A1 |
10 |
57 |
12 |
15 5 |
20 |
A2 |
3 |
408 |
5 |
2 |
40 |
A3 |
2 |
14 |
4 |
306 |
30 |
A4 |
157 |
11 |
20 2 |
1513 |
50 |
|
15 |
45 |
20 |
60 |
140 |
Теперь общая цена составляет еще меньше: 950 единиц.
Однако, здесь имеются и еще отрицательные циклы, вот один из них:
Очевидно, что этот цикл является отрицательным: 2-8+7-5= -4. Произведем перегруппировку внутри данного цикла:
|
B1 |
B2 |
B3 |
B4 |
|
A1 |
10 |
207 |
12 |
5 |
20 |
A2 |
3 |
258 |
5 |
15 2 |
40 |
A3 |
2 |
14 |
4 |
306 |
30 |
A4 |
157 |
11 |
20 2 |
1513 |
50 |
|
15 |
45 |
20 |
60 |
140 |
И опять таки мы получаем более рациональный ответ: 890.
Проделывая далее подобные операции мы можем найти оптимальное решение. Однако, должно быть, большую часть мы уже проделали, и наиболее оптимальное решение не будет намного отличаться от найденного, тем более, что мы уже получили огромный выигрыш в 405 единиц.