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

Пример 4. Построим цикл для загрузки клетки (3,1) в транспортной таблице (табл. 10).

Таблица 10.

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

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

Фиктивный перенос по циклу может применяться при решении транспортной задачи методом потенциалов.

Таблица 11.

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

Приведем алгоритм метода потенциалов.

Шаг 0. Берут любой невырожденный опорный план перевозок, в котором отмечены m+n-1 базисных клеток (остальные клетки – свободные).

Шаг 1. Для этого плана вычисляют потенциалы (,), исходя из условия: в любой базисной клетке псевдостоимости равны стоимостям:

. ()

Один из платежей назначают произвольно, например, равным нулю.

Шаг 2. Рассчитывают псевдостоимости для всех свободных клеток:

. ()

Шаг 3. Проверяют условие: для всех свободных клеток псевдостоимость не превышает стоимости перевозок груза. Если условие выполняется, то план оптимален, иначе переходят к шагу 4.

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

Шаг 5. Проверяют «невырожденность» нового опорного плана. Если план вырожден, то его сводят к невырожденному, объявляя часть свободных клеток условно занятыми, и переходят к шагу 1.

Шаги 1-5 алгоритма итерационно повторяются, пока не будет найден оптимальный план.

Пример 5. Решим транспортную задачу, заданную в табл 3. В примере 2 был найден вырожденный опорный план по методу минимального элемен­та (табл. 7) для этой транспортной задачи. Найдем оптимальный план методом потенциалов.

Для сведения плана к невырожденному в табл. 7 условно занимают две свободные клетки и объявляют их базисными. Клетки необходимо выбрать так, чтобы вокруг оставшихся свободных клеток можно было строить циклы. Например, нельзя одновременно объявить базисными клетки (1,1) и (2,1). Также свободным клеткам, которые условно занимаются, должна соответствовать как можно меньшая стоимость перевозки единицы груза. В табл. 12 приведена полученная транспортная таблица, в условно занятых свободных клетках нули выделены «жирным» шрифтом.

Таблица 12.

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

На первом шаге вычисляют потенциалы производителей и потребителей (,), для чего составляется система уравнений:

; ; ; ;

; ; . ()

Один из потенциалов задается произвольно, например: . Далее вычисляются потенциалы производителей и потребителей из системы уравнений (). Результаты вычислений представлены в табл. 13.

Таблица 13.

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

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

На третьем шаге проверяют выполнение условий оптимальности. Для двух клеток (1,3) и (4,2) псевдостоимость выше стоимости, поэтому план не оптимален.

На четвертом шаге для улучшения плана перевозок загружается переносом по циклу клетка (1,3), как имеющая максимальную по модулю цену цикла. Цена цикла равна -4. По циклу может быть перенесено максимум 10 единиц груза (табл. 14). Следовательно, циклический перенос приведет к уменьшению стоимости плана перевозок на 40 условных единиц.

Таблица 14.

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

В табл. 15. приведена транспортная таблица после циклического переноса. Стоимость плана составила: z=770-40=730.

Таблица 15.

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

На пятом шаге проверяют «невырожденность» нового опорного плана. В табл. 15 число базисных клеток равно 7. Следовательно, план невырожденный опорный и можно переходить ко второй итерации, к шагу 1.