Решение транспортных задач

В качестве примера приведем решение транспортной задачи ЛП с помощью таблицы. Транспортная таблица состоит из m строк и n столбцов. В правом верхнем углу каждой клетки будем ставить стоимость С_ij перевозки единицы груза из A_i в B_j, а в центр клетки поместим перевозку X_ij.

Таблица 5.6

Таблица 5.7

Составим опорный план. Можно применить метод «северо-западного угля». Пусть пункт В₁ подал заявки на 18 единиц груза. Удовлетворим ее из запасов А₁. После этого в нем остается еще 30-18=12 единиц груза. Отдадим их пункту В₂. Но заявка этого пункта еще не удовлетворена. Выделим остаток 27-12 из запасов А₂ и т.д. рассуждая аналогичным образом, составим таблицу 5.8. Полученный план перевозок является опорным, но вряд ли он является оптимальным в смысле стоимости перевозок.

þ Напомним, что прямая, которая имеет с областью, по крайней мере, одну общую точку, притом так, что вся область лежит по одну сторону от этой прямой, называется опорной по отношению к этой области.

Таким образом, задача ЛП на геометрическом языке может быть сформулирована так: среди прямых уровня функции цели ¦ найти опорную по отношению к ОДР и притом так, чтобы вся область лежала со стороны больших значений ¦. Наш план - не оптимальный. Сразу видно, что его можно улучшить, если произвести в нем «циклическую перестановку», уменьшив перевозки в «дорогой» клетке (2.3) со стоимостью 12. но зато, увеличив перевозки в «дешевой» клетке (2.4) со стоимостью 6. чтобы план оставался опорным, мы должны при этом сделать одну из свободных клеток базисной, а одну из базисных - свободной.

Сколько единиц груза можем мы перенести по циклу следующему циклу: (2.4) ®(3.4) ®(3.3) ®(2.3), увеличивая перевозки в нечетных вершинах цикла и уменьшая в четных? Очевидно, не больше 11 единиц (иначе перевозки в клетке (3.4) стали бы отрицательными). Также очевидно, что в результате циклического переноса допустимый план остается допустимым - баланс заявок и запасов не нарушается. Произведем перенос и запишем улучшенный план в таблицу 5.8.

таблица 5.8

Таблица 5.9

посмотрим, что мы сэкономили. Общая стоимость плана в табл. 5.7 равна:

‡₁=18´13+12´7+15´8+33´12+9´10+11´8+15´10+15´15=1287.

Общая стоимость плана табл. 5.6 равна:

‡₂=18´13+12´7+15´8+22´12+11´6+20´10+15´10+15´15=1243.

Таким образом, нам удалось уменьшить стоимость перевозок на 44 единицы.

Действительно алгебраическая сумма стоимостей, стоящих в вершинах цикла со знаком «+», если перевозки в этой вершине увеличиваются, и со знаком «-», если уменьшаются (так называемая «цена цикла»). в данном случае равна 6-8+10-12=-4. Значит, при переносе одной величины груза по этому циклу стоимость уменьшается на 4. А мы перенесем 11 единиц. Следовательно, цена цикла 4 ^. 11=44.

Попробуем еще раз улучшить план табл. 5.8 с помощью цикла (табл. 5.9) с ценой: 5-15+14-13=9. Перебрасывая 15 единиц груза, сокращаем стоимость на: 9 ^. 15=135.