11. УЛУЧШЕНИЕ ПЛАНА ПЕРЕВОЗОК. ЦИКЛ ПЕРЕСЧЕТА

В предыдущем параграфе мы уже бегло познакомились со способом улучшения плана, состоящим в том, что некоторые перевозки, без нарушения баланса, переносятся из клетки в клетку по некоторому замкнутому циклу. Здесь мы рассмотрим эти циклические перестановки подробнее.

Возьмем транспортную таблицу, состоящую, например, из строк и столбцов (число строк и столбцов несущественно).

Циклом в транспортной таблице мы будем называть несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90°.

Например, в табл. 11.1 изображены два цикла: первый с четырьмя вершинами (2,1), (2,3), (4,3), (4,1) и второй — с восемью вершинами (1,4), (1,6), (4,6), (4,4), (3,4), (3,5), (5,5), (5,4). Стрелками показано направление обхода цикла.

Таблица 11.1

Таблица 11.2

Нетрудно убедиться, что каждый цикл имеет четное число вершин и, значит, четное число звеньев (стрелок).

Условимся отмечать знаком «+» те вершины цикла, в которых перевозки увеличиваются, а знаком «-» — те вершины, в которых они уменьшаются. Цикл с отмеченными вершинами будем называть «означенным». В табл 11.2 показано два означенных цикла: первый с четырьмя вершинами (1,1), (1,2), (3,2) и (3,1) и второй с восемью вершинами (3, 4), (3,6), (5, 6), (5,3), (2,3), (2,5), (4,5) и (4,4).

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

Назовем ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, причем стоимости, стоящие в положительных вершинах, берутся со знаком «+», а в отрицательных — со знаком «-». Например, для цикла в табл. 11.2 цена равна:

а для цикла

Обозначим цену цикла Ц через у. При перемещении одной единицы груза по циклу Ц стоимость перевозок увеличивается на величину у; при перемещении по нему k единиц груза стоимость перевозок увеличивается на

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

Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, т. е. оптимальный план достигнут.

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

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

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

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

Таблица 11.3

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

Стоимость этого плана равна:

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

Попробуем улучшить план, заняв свободную клетку (2,4) с минимальной стоимостью 4. Цикл, соответствующий этой клетке, показан в табл. 11.4. Цена этого цикла равна .

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

Таблица 11.4

Таблица 11.5

Таблица 11.6

Таблица 11.7

Таблица 11.8

Таблица 11.9

Стоимость этого плана . В нем по-прежнему шесть базисных клеток.

Для дальнейшего улучшения плана обратим внимание на свободную клетку стоимостью 5. Цикл, соответствующий этой клетке, показан в табл. 11.5; цена его По этому циклу переместим 22 единицы груза, чем уменьшим стоимость перевозок до (см. табл. 11.6).

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

Примененный выше метод отыскания оптимального решения транспортной задачи называется распределительным; он состоит в непосредственном отыскании свободных клеток с отрицательной ценой цикла и в перенесении перевозок по этому циклу.

Пример 2. Найти оптимальный план перевозок для ТЗ, условия которой приведены в табл. 11.7.

Решение. Строим опорный план способом северо-западного угла; он получается вырожденным. Чтобы избежать этого, нарушаем баланс запасов и заявок на 8 в первой и третьей строках, не нарушая общего баланса (сумма запасов равна сумме заявок). После этого строим опорный план также способом северо-западного угла (табл. 11.8), в нем ровно столько базисных переменных, сколько нужно: пять. Улучшаем план перевозок переносом единиц груза по циклу, показанному в табл. 11.8; получим новый, лучший план (см. табл. 11.9).

План, приведенный в табл. 10.9, еще не оптимален, так как цикл с началом в свободной клетке (2,1) имеет отрицательную цену:

Перемещаем по этому циклу 20 единиц груза; получим табл. 11.10.

Цена цикла, начинающегося в клетке (2,2) табл. 11.10, также отрицательна: Однако, по этому циклу можно перенести только перевозку, равную е. Тем не менее, сделаем это и получим новый план (Табл. 11.11).

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

Заметим, что примененный здесь метод «ликвидации вырождения» путем -изменения запасов не совсем удобен, так как требует дополнительных действий с -измененными данными. Проще было бы при заполнении табл. 10.8 не изменять запасы, а «вообразить» их себе измененными и вместо поставить в базисной клетке (3,3) просто нуль. Базисная клетка с нулевой перевозкой тем будет отличаться от свободной, что в ней нуль проставлен, а в свободной — нет. Дальнейшие манипуляции с транспортной таблицей будут совершенно такими же, как если бы в базисных клетках стояли только положительные перевозки, с той лишь разницей, что когда одна из отрицательных вершин цикла окажется в базисной клетке с нулевой перевозкой, нужно переносить по этому циклу нулевую перевозку (фиктивный перенос). Если в транспортной таблице немного (одна-две) базисных переменных обращаются в нуль, можно рекомендовать этот простой метод вместо -изменений запасов (заявок).

Таблица 11.10

Таблица 11.11

Таблица 11.12

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