Задача о коммивояжере (стр. 5 )

Двигаются по первой строке вправо и заполняют клетку (1,3): . Предложения первого поставщика исчерпаны, клетка (1,4) заполняется нулем.

Двигаются по третьему столбцу вниз и заполняют клетку (2,3): (табл. 6). Запасы второго поставщика исчерпаны. В клетку (2,4) заносится нуль.

Таблица 6.

объем объем потребления производства	120	50	110	190
200	120	50	30	0
40	0	0	40	0
110	0	0	40	70
120	0	0	0	120

Далее заполняется клетка (3,3): . В клетку (4,3) заносится нуль; в клетку (3,4): ; в клетку (4,4): .

Полученный план перевозок (табл. 6) – допустимый, так как для него выполняются условия баланса и опорный, так как число базисных клеток равно 7 и r=m+n-1=4+4-1=7.

Стоимость плана перевозок составляет:

.

Метод северо-западного угла — наиболее простой метод на­хождения опорного плана, при его построении не учитываются стоимости перевозок. План перевозок, полученный по этому методу, обычно бывает достаточно далек от оптимального.

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

Шаг 0. Условие транспортной задачи задают в виде транспортной таблицы (табл. 1).

Шаг 1. Проверяют выполнение условия баланса. Если условие баланса не выполняется, т. е. задача открытая, то ее сводят к закрытому типу.

Шаг 2. Создают таблицу плана перевозок (табл. 2), в которой заполнены только объемы производства и объемы потребления. Выбирают клетку таблицы, которой соответствует минимальная стоимость перевозки единицы продукции от производителя к потребителю. В выбранную клетку аналогично методу северо-за­падного угла помещают максимально возможное число единиц продукции, разрешенное ограничениями на запасы и заявки. После этого, если предложение производителя исчерпано, остальные клетки соответствующей строки заполняют нулями; если спрос удовлетворен, остальные клетки соответствующего столбца заполняют нулями.

Процесс продолжается до тех пор, пока не заполнены все клетки таблицы перевозок.

Пример 2. Определить опорное решение по методу минимального элемен­та для транспортной задачи, заданной в табл 3.

На первом шаге проверяют выполнение балансовых условий, сводят задачу к закрытому типу и переходят к табл. 4.

На втором шаге создают пустую таблицу плана перевозок и начинают ее заполнение (табл. 7).

Таблица 7.

объем объем потребления производства	120	50	110	190
200	0	10	0	190
40	0	40	0	0
110	0	0	110	0
120	120	0	0	0

Минимальная стоимость перевозки единицы продукции соответствует клеткам (4,1), (4,2), (4,3), (4,4): с41= с42= с43= с44=0. Начать заполнение таблицы перевозок можно с любой из этих клеток. Пусть . Остальные клетки четвертой строки и первого столбца заполняются нулями.

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

Далее заполняется клетка (1,4), как имеющая наименьшую стоимость перевозок единицы продукции: . Оставшиеся клетки четвертого столбца заполняются нулями. Затем заносится в клетку (1,2): ; в клетку (2,2): .

В результате получен допустимый план перевозок, все балансовые условия выполнены (табл. 7). План перевозок также опорный и вырожденный, так как число базисных клеток равно 5 и меньше r=7.

Стоимость плана перевозок составляет:

и значительно ниже стоимости плана, полученного методом северо-западного угла.

Метод потенциалов. Метод позволяет найти оптимальное решение транспортной задачи.

Идея метода потенциалов, его экономическая интерпретация. Пусть каждый из пунктов производства продукции вносит за перевозку единицы груза (неважно куда) какую-то сумму ; в свою очередь, каждый из пунктов потребления также вносит за перевозку единицы груза (все равно, откуда) сумму ; эти платежи передаются некоторому третьему лицу («перевозчику»).

Предположим, что интересы пунктов i и j не противоречат друг другу и они действуют как единая экономическая система. Перевозка единицы груза из i-го в j-ый пункт объективно стоит , а стороны вместе платят за эту перевозку «перевозчику» сумму:

, ()

величина называется «псевдостоимостью» перевозки единицы груза из i-го пункта производства в j-ый пункт потребления.

Платежи и не обязательно должны быть положительными: не исключено, что «перевозчик» сам платит тому или другому пункту какую-то премию за перевозку.

Оптимальным будет такой план перевозок, при котором пункты i и j не переплачивают «перевозчику» ничего сверх объективной стоимости перевозок , т. е. такой план, любое отступление от которого не выгодно для пунктов производства и потребления, так как заставит их платить за перевозку больше, чем если бы они возили грузы сами.

Для доказательства метода потенциалов рассмотрим теорему «о платежах».

Теорема «о платежах». Для заданной совокупности платежей (,) суммарная псевдостоимость перевозок при любом допустимом плане перевозок сохраняет одно и то же значение:

. ()

В формуле () величина С зависит только от совокупности платежей (,), но не зависит от того, каким именно допустимым планом мы пользуемся.

Доказательство. Имеем:

. ()

Преобразуем первую из двойных сумм в выражении (). Вынесем из-под знака суммы по j:

. ()

Так как план является допустимым, то для него выполняется балансовое условие:

, ()

откуда:

. ()

Аналогичным образом преобразуется второе слагаемое в ():

. ()

Подставляя () и () в () получим:

. ()

В формуле () правая часть не зависит от плана перевозок , а зависит только от запасов , заявок и платежей (,).

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

Далее необходимо установить взаимосвязь между псевдостоимостями и истинными стоимостями перевозок .

Предположим, что план невырожденный (число базисных клеток в таблице перевозок равно m+n-1). Для всех этих клеток . Определим платежи (,) так, чтобы во всех базисных клетках псевдостоимости были равны стоимостям:

; ()

Для свободных клеток соотношение между стоимостью и псевдостоимостью может быть какое угодно:

.

Соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным, или же он может быть улучшен.

Докажем следующую теорему.

Теорема. Если для всех базисных клеток плана ():

,

а для всех свободных клеток ():

,

то план является оптимальным и никакими способами улучшен быть не может.

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

. ()

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

. ()

На основании ранее доказанного эта сумма равна некоторой константе С:

. ()

Теперь изменим план , заменив его каким-то другим планом . Обозначим стоимость нового плана:

, ()

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

.

Поэтому сумма () не может быть меньше, чем сумма ():

. ()

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

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

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

1.  Для всех базисных клеток:

. ()

2.  Для всех свободных клеток:

. ()

План, обладающий такими свойствами, называется потенциальным, а соответствующие ему платежи (,) – потенциалами пунктов и .

Пользуясь этой терминологией, доказанную выше теорему можно сформулировать следующим образом:

Всякий потенциальный план – оптимален.

Процедура построения потенциального (оптимального плана) состоит в следующем.

В качестве первого приближения к оптимальному берется любой опорный план. Для этого плана потенциалы (,), соответствующие базисным клеткам, подчиняются условию: сумма потенциалов равна стоимости перевозки единицы груза (). Уравнений всего m+n-1, а число неизвестных равно m+n. Следовательно, потенциал одного пункта можно задать произвольно (например, равным нулю). После этого из m+n-1 уравнений можно найти остальные потенциалы, а по ним вычислить псевдостоимости () для каждой свободной клетки. Если оказалось, что все эти псевдостоимости не превосходят стоимостей (), то план оптимален. Если нет, то план может быть улучшен переносом перевозок по циклу.

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

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

Цена цикла – увеличение стоимости перевозок при перемещении одной единицы груза по циклу. Цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла. Стоимости, стоящие в положительных вершинах, берутся со знаком «+», а в отрицательных – со знаком «–».

Пример 3. В табл. 8 приведена транспортная таблица, в которой отмечен цикл. Пусть требуется загрузить клетку (4,1). Максимальное число единиц, которое может быть перенесено, равно 40, так как это минимальное количество единиц груза в отрицательных вершинах. Цена цикла: .

Таблица 8.

объем объем потребления производства	120	50	110	190
200	7 120 -	8 50	3 30 +	2 0
40	4 0	5 0	9 40	8 0
110	9 0	2 0	1 40 -	6 70 +
120	0 0 +	0 0	0 0	0 120 -

Транспортная таблица после циклического переноса приведена в табл. 9. Стоимость плана увеличиться на 40 единиц и составит: z=2150+40=2190. Очевидно, что выполненный циклический перенос удаляет от оптимального решения и перенос по циклу имеет смысл только при отрицательной цене цикла.

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

Таблица 9.

объем объем потребления производства	120	50	110	190
200	7 80	8 50	3 70	2 0
40	4 0	5 0	9 40	8 0
110	9 0	2 0	1 0	6 110
120	0 40	0 0	0 0	0 80

Если количество базисных клеток в транспортной таблице меньше r=m+n-1, (план вырожденный), то необходимо перейти от него к невырожденному опорному плану. Для этого часть свободных клеток объявляют условно занятыми и работают с ними как с базисными клетками.