Ц и к л п е р е с ч е т а

У л у ш е н и е п л а н а п е р е в о з о к.

План перевозок можно улучшить, перенося некоторые перевозки без нарушения баланса из клетки в клетку по замкнутому циклу. Ц и к л о м в транспортной таблице называют несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90 ˚. Ценой цикла называют увеличение перевозок при перемещении одной единицы груза по означенному циклу. Обозначим цену цикла через γ, При перемещении k единиц товара по циклу Ц стоимость перевозок увеличивается на k γ,

Очевидно для перемещения плана имеет смысл перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удастся совершить такое перемещение, стоимость, стоимость плана уменьшается на соответствующую величину k γ.

Так как перевозки не могут быть отрицательными, Мы будем пользоваться только теми циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. (условимся отмечать знаком «+» те вершины цикла, в которых перевозки увеличиваются, знаком «-«--» - те вершины, в которых они уменьшаются.

Метод последовательного улучшения плана перевозок и состоит в том, что в таблице отыскиваются циклы с отрицательной ценой, по ним перемещаются перевозки, и план улучшается до тех пор, пока циклов с отрицательной ценой уже не останется. Приэтом при каждом шаге (цикле) заменяют одну свободную переменную на базисную, т.е. заполняют одну свободную клетку и взамен ее освобождают одну из базисных клеток. Общее количество базисных клеток остается неизменным и равным

m + n -- 1.

Пример 3. Найти оптимальный план для транспортной задачи, приведенной в таблице 3.6.

Таблица 3. 6

Решение. Составляем опорный план методом северо-западного угла.(табл.3.7)

Стоимость этого плана равна: 22 • 10 + 9 • 7 + 25 • 6 + 23 • 5 + 18 • 6 + 20 • 7 = =796.

Число базисных переменных, как и полагается в невырожденном случае, равно

r = m + n – 1 = 3 + 4 -- 1 = 6.

Попробуем улучшить план, заняв свободную клетку (2,4) с минимальной стоимостью 4. Цикл, соответствующий этой клетке, показан в табл. 3.7. Цена этого цикла равна γ = 4 –7 + 6 = -- 2.

Таблица 3.7

По этому циклу мы можем переместить максимум 20 единиц товара (чтобы не получить в клетке (3,4) отрицательной перевозки).Новый улучшенный план показан в табл. 3.8.

Таблица 3.8

Cтоимость этого плана L₂ = 796 + 20 (-- 2) = 756. В нем по-прежнему шесть базисных клеток.

Для дальнейшего улучшения плана обратим внимание на свободную клетку (2,1) со стоимостью. Цикл, соответствующий этой клетке, показан в табл. 3.8; цена его 7 – 6 + 5 –10 = --4. По этому циклу переместим 22 единицы товара, чем уменьшим стоимость перевозок до L₃ = 756 + 22 (--4) = 668 (см. табл. 3.9).

Таблица 3.9

Продолжаем дальше улучшить этот план, подсчитывая цены циклов, начинающихся положительной вершиной в свободной клетке. Просматриваем имеющиеся свободные клетки таблицы 3.9 и определяем цену цикла каждой из них. Все эти цены (можно проверить) или положительные или нулевые, следовательно, никакое дальнейшее циклическое перенесение перевозок не может улучшить план перевозок.

Таким образом, план, полученный в табл. 3.9 является оптимальным.

Дата добавления: 2014-01-07