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

<10 11 12 131415 16 >

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

Таблица 5.6

	ПН	В₁	В₂	В₃	В₄	В₅	Запасы а_i
ПО
A₁	¹³	⁷	¹⁴	⁷	⁵
A₂	¹¹	⁸	¹²	⁶	⁸
A₃	⁶	¹⁰	¹⁰	⁸	¹¹
A₄	¹⁴	⁸	¹⁰	¹⁰	¹⁵
Заявки b_j

Таблица 5.7

	ПН	В₁	В₂	В₃	В₄	В₅	Запасы а_i
ПО
A₁	18 ¹³	12 ⁷	¹⁴	⁷	⁵
A₂	¹¹	15 ⁸	33¹²	⁶	⁸
A₃	⁶	¹⁰	9¹⁰	11⁸	¹¹
A₄	¹⁴	⁸	¹⁰	15¹⁰	15¹⁵
Заявки b_j

Составим опорный план. Можно применить метод «северо-западного угля». Пусть пункт В₁ подал заявки на 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

	ПН	В₁	В₂	В₃	В₄	В₅	Запасы а_i
ПО
A₁	18 ¹³	12 ⁷	¹⁴	⁷	⁵
A₂	¹¹	15 ⁸	33¹²	11⁶	⁸
A₃	⁶	¹⁰	20¹⁰	⁸	¹¹
A₄	¹⁴	⁸	¹⁰	15¹⁰	15¹⁵
Заявки b_j

Таблица 5.9

	ПН	В₁	В₂	В₃	В₄	В₅	Запасы а_i
ПО
A₁	^-3 ¹³	12 ⁷	¹⁴	⁷	⁺15⁵
A₂	¹¹	15 ⁸	22¹²	11⁶	⁸
A₃	⁶	¹⁰	20¹⁰	⁸	¹¹
A₄	⁺15¹⁴	⁸	¹⁰	15¹⁰	^-¹⁵
Заявки b_j

посмотрим, что мы сэкономили. Общая стоимость плана в табл. 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.