методом ветвей и границ

Задача про коммивояжера. Пусть n есть городов. Известна матрица расстояний между любой парой городов .Выезжая из начального города, коммивояжер должен побывать во всех городах ровно один раз и вернуться в начальный город. Необходимо узнать в каком порядке нужно объезжать города, чтобы пройденный путь был минимальным.

Введем неизвестные

Тогда получаем задачу

Первая группа ограничений говорит о том, что коммивояжер выезжает из каждого города один раз, а вторые о том, что он один раз въезжает в каждый город.

Пример: Рассмотрим пример объезда 4 городов. Задана матрица расстояний между городами:

	i \ j	1	2	3	4
	1	¥	4	5	3
	2	6	¥	7	2
	3	5	7	¥	8
	4	4	2	3	¥

Необходимо найти последовательность объезда городов так чтобы путь был минимальным.

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

i \ j	1	2	3	4
1	¥	4	5	3	3
2	6	¥	7	2	2
3	5	7	¥	8	5
4	4	2	3	¥	2

i \ j	1	2	3	4
1	¥	1	2	0
2	4	¥	5	0
3	0	2	¥	3
4	2	0	1	¥
	0	0	1	0

i \ j	1	2	3	4
1	¥	1	1	0
2	4	¥	4	0
3	0	2	¥	3
4	2	0	0	¥

Обозначим полученную матрицу через .

В ней на месте минимальных переездов стоят 0.

Посчитаем оценку данного множества:

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

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

Нашли первую пару городов объезда - переезд из города 2 в город 4. Проверим это. Для этого множество разобьем на два множества: .

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

Множество - - множество всех переездов, в которых запрещен переезд из города 2 в город 4. Этому множеству соответствует матрица, полученная из матрицы заменой элемента .

Рассмотрим :

i \ j	1	2	3
1	¥	1	1	1
3	0	2	¥	0
4	2		0	0

i \ j	1	2	3
1	¥	1	1
3	0	2	¥
4	2		0

i \ j	1	2	3
1	¥	0	0
3	0	2	¥
4	2		0
	0	0	0

Рассмотрим :

i \ j	1	2	3	4
1	¥	1	1	0
2	4	¥	4
3	0	2	¥	3
4	2	0	0	¥

Так как то дальше дробить мы будем множество . Для этого оценим нули множество :

Нашли следующую пару объезда: .

Дробим множество .

Рассмотрим :

i \ j	2	3
1	0
4		0

Мы получили матрицу второго порядка. Дальнейшее дробление невозможно. Получили объезд:

Длина объезда:

Рассмотрим :

i \ j	1	2	3
1	¥	0	0
3		2	¥
4	2		0

Так как , то найденный переход оптимален и его длина 14.

Построим дерево решений.

Графическое изображение переезда.

Вопрос для самоподготовки

1. Сформулируйте задачу о коммивояжере?

2. Что определяют ограничения в задаче о коммивояжере?

3. По какому признаку множественное число решений разделяется на подмножества?

4. На матрице какого порядка мы заканчиваем решение задачи, и почему?

Литература.

Основна

1. Зайченко Ю.П. Исследование операций.- К.:Высшая школа,1988-552с.
2. Зайченко Ю.П. Исследование операций. Сборник задач.- К.:Высшая школа,1990-239с.
3. Юхименко Б.І. Математичне програмування для єкономистів. Навчальний посібник.- Одеса: Наука та техника,2006 – 167с.
4. Вітлінський В.В. Моделювання економіки: Навч. посібник. –К.: КНЕУ, 2003.-408с.

Дополнительная

1. Вагнер Г. Основы исследования операций. В 3т.- М.:Мир,1983
2. Кутковецкий В.Я. Дослідження операцій. Навчальний посібник. –К.:2004.-350с.
3. Наконечний С.І., Савіна С.С. Математичне програмування –К.: 2003.-452с.