Лабораторная работа #6

Министерство Образования и Науки Российской Федерации

Санкт-Петербургский государственный

электротехнический университет «ЛЭТИ»

им. В.И. Ульянова (Ленина)

Кафедра МОЭВМ

Отчет

по лабораторной работе №6

по дисциплине "Методы оптимизации"

" Задача о коммивояжере"

Выполнили: Быстров И.С.,

Заречнев М.А.,

Филиппов К.В.

Проверил: Балтрашевич В.Э.

Санкт-Петербург

2005

Цель работы

Изучение метода ветвей и границ на примере решения задачи коммивояжера.

Сведения

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

Формально она может быть поставлена так:

минимизировать

при условиях

(1)

(2)

перестановка

(3)

где - индексы ненулевых переменных , не содержит внутренних циклов.

Здесь

- стоимость переезда из i-го города в j-и,

1, если путь из i-го города в j-и включается в маршрут коммивояжера

0, иначе

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

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

а) если оценка снизу целевой функции на каком-либо подмножестве больше, чем "рекорд", то соответствующее подмножество можно исключить из дальнейшего рассмотрения;

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

Процесс разбиения на подмножества удобно фиксировать в виде дерева, вершины которого соответствуют подмножествам.

Описанная выше общая схема будет работоспособной только в том случае, если конкретизировать в ней два ключевых момента:

а) способ выбора очередного подмножества, подлежащего разбиению, и правило, по которому оно осуществляется;

б) метод получения оценки.

1. Правило разбиения:

а) любое подмножество разбивается на две части;

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

в) правило выбора упомянутого пути будет приведено ниже.

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

Подмножество маршрутов удобно кодировать с помощью пары:

а) - набора путей, включаемых во все маршруты подмножества;

б) матрицы вида:

		...
		...
.
.		...
.
		...

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

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

1. Редуцировать матрицу стоимостей, т.е. последовательно вычесть из каждой строки ее минимальный элемент, после чего осуществить ту же процедуру применительно к столбцам. Сумма вычитаемых в процессе редукции чисел Х - редукционная сумма - даст искомую оценку.

2. Для каждого из нулевых элементов редуцированной матрицы вычислить

3. Осуществить разбиение по тому пути, для которого величина максимальна.

4. В подмножестве маршрутов исключающих путь , соответствующую стоимость положить равной бесконечности и провести редукцию по i-и строке и j-му столбцу. Сумма даст оценку снизу.

5. В подмножестве маршрутов, включающих путь , осуществить следующую последовательность действий:

а) вычеркнуть элементы i-и строки и j-го столбца;

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

в) провести редукцию получившейся матрицы;

г) добавить редукционную сумму к Х и получить оценку снизу для рассматриваемого подмножества.

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

Исследования

Здесь

C_ij - стоимость переезда из i-го города в j-й,

1, если путь из i-го города j-й включается в марш-

X_ij = ­рут коммивояжера,

О, иначе.

Матрица стоимостей путей

n=6

1 2 3 4 5 6

1 10000 36 51 24 11 46

2 28 10000 17 46 10 20

3 7 41 10000 58 2 35

4 25 60 45 10000 55 59

5 48 20 33 26 10000 38

6 50 27 19 14 52 10000

1. Ш

   Приведенная матрица

   1 2 3 4 5 6

   1 10000 7 25 1 0 17

   2 21 10000 0 32 8 0

   3 0 21 10000 44 0 15

   4 0 22 10 10000 35 21

   5 41 0 16 12 10000 18

   6 43 7 2 0 50 10000

   аг1

1 2 3 4 5 6

1 10000 36 51 24 11 46

2 28 10000 17 46 10 20

3 7 41 10000 58 2 35

4 25 60 45 10000 55 59

5 48 20 33 26 10000 38

6 50 27 19 14 52 10000

Выбор дуги, исключение которой приводит к наибольшему штрафу: (5,2) h = 19

Оценка снизу длины рекордного маршрута= 107

2. Шаг 2

Исключаем дугу, по которой надо запретить движение во избежания преждевременного замыкания маршрута : (2,5)

1 3 4 5 6

1 10000 25 1 0 17

2 21 0 32 10000 0

3 0 10000 44 0 15

4 0 10 10000 35 21

6 43 2 0 50 10000

Выбор дуги, исключение которой приводит к наибольшему штрафу: (2,6) h = 15

Оценка снизу длины рекордного маршрута= 109

3. Шаг 3

Исключаем дугу (6,5) так как с ребрами (5,2),(2,6) образует цикл

1 3 4 5

1 10000 23 1 0

3 0 10000 44 0

4 0 8 10000 35

6 43 0 0 10000

Выбор дуги, исключение которой приводит к наибольшему штрафу: (4,1) h = 8

Оценка снизу длины рекордного маршрута= 109

4. Шаг 4

Исключаем дугу (1,4), так как с ребром (4,1) образует цикл

3 4 5

1 23 10000 0

3 10000 44 0

6 0 0 10000

Выбор дуги, исключение которой приводит к наибольшему штрафу: (3,5) h = 44

Оценка снизу длины рекордного маршрута= 132

5. Шаг 5

Исключаем дугу (6,3), так как с ребрами (3,5), (5,2),(2,6) образует цикл

Длина рекордного маршрута: L=10000

нижняя оценка : w = 132

Количество дуг: Y = 6

Маршрут: 1  3  5  2  6  4  1

Оценки длин альтернативных маршрутов	Оценки длины текущего маршрута
126	107
122	109
117	109
153	132
10000	132
10000	132

Оценка альтернативного маршрута на 3-м уровне ниже текущей, следовательно, нужно повторить алгоритм с 3-го уровня:

6. Ш

   сокращенная матрица расстояний:

   1 2 3 4 5 6

   1 10000 7 25 1 0 17

   2 21 10000 0 32 8 0

   3 0 21 10000 44 0 15

   4 10000 12 0 10000 25 11

   5 41 0 16 12 10000 18

   6 43 7 2 0 50 10000

   аг 6

1 2 3 4 5 6

1 10000 36 51 24 11 46

2 28 10000 17 46 10 20

3 7 41 10000 58 2 35

4 10000 60 45 10000 55 59

5 48 20 33 26 10000 38

6 50 27 19 14 52 10000

Выбор дуги, исключение которой приводит к наибольшему штрафу: (3,1) h=21

Оценка снизу длины рекордного маршрута= 117

7. Шаг7

Исключаем дугу (1,3), так как с дугой (3,1) образует цикл

2 3 4 5 6

1 7 10000 1 0 17

2 10000 0 32 8 0

4 12 0 10000 25 11

5 0 16 12 10000 18

6 7 2 0 50 10000

Выбор дуги, исключение которой приводит к наибольшему штрафу: (5,2) h=19

8. Шаг 8

Исключаем дугу (2,5), так как с дугой (5,2) образует цикл

3 4 5 6

1 10000 1 0 17

2 0 32 10000 0

4 0 10000 25 11

6 2 0 50 10000

Выбор дуги, исключение которой приводит к наибольшему штрафу: (1,5) h=26

Оценка снизу длины рекордного маршрута= 117

9. Шаг 9

Исключаем дугу (2,3), так как с дугами (3,1) и (1,5) (5,2) образует цикл

3 4 6

2 10000 32 0

4 0 10000 11

6 2 0 10000

Выбор дуги, исключение которой приводит к наибольшему штрафу: (2,6) h=43

Оценка снизу длины рекордного маршрута= 117

10. Шаг 10

Исключаем дугу (6,3), так как с дугами (3,1), (1,5) и (5,2) (2,6) образует цикл

Длина рекордного маршрута: L=109

нижняя оценка : w = 117

Количество дуг: Y = 6

Маршрут: 3  1  5 2  6  4  3

Оценки длин альтернативных маршрутов	Оценки длины текущего маршрута
138	117
136	117
143	117
160	117
10000	117
10000	117

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

N города Оценка

3  1 7

1  5 11

5  2 20

2  6 20

6  4 14

4  3 45

Вывод

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

7