Транспортная задача с решением

Транспортной называется задача линейного программирования, основанная на поиске оптимальных “маршрутов перевозки” путем создания циклов. По сути задача сводится к тому, чтобы найти оптимальный способ перевозки груза из точки А в точку B при минимальных затратах.

Условие сбалансированной транспортной задачи:

Необходимо перевести 140 единиц продукта от производителей на склады. Цены перевозок по маршрутам указаны также в таблице. Требуется найти наиболее дешевый вариант перевозки.

Решение:

Сначала путем распределения 140 единиц продукта методом северо-западного угла получим опорные решения:

В таком первоначальном варианте стоимость транспортировки будет равна 150+35+320+80+60+650=1295. Понятно, что существуют варианты более оптимальные,, нежели данный опорный вариант. Для их нахождения следует выделить один из отрицательных циклов. Например такой:

Легко проверить, что он отрицательный: 7-10+5-13= -11. После перегруппировки внутри данного цикла мы получаем следующее:

При этом варианте цена составит уже 1130 единиц, т.е. на 165 единиц меньше.

Найдем еще один отрицательный цикл:

Этот цикл также является отрицательным: 2-4+6-13= -9. Теперь, чтобы уменьшить общую цену, проведем перегруппировку в пределах этого цикла:

Теперь общая цена составляет еще меньше: 950 единиц.

Однако, здесь имеются и еще отрицательные циклы, вот один из них:

Очевидно, что этот цикл является отрицательным: 2-8+7-5= -4. Произведем перегруппировку внутри данного цикла:

И опять таки мы получаем более рациональный ответ: 890.

Проделывая далее подобные операции мы можем найти оптимальное решение. Однако, должно быть, большую часть мы уже проделали, и наиболее оптимальное решение не будет намного отличаться от найденного, тем более, что мы уже получили огромный выигрыш в 405 единиц.