Задача про коммивояжера. Пусть 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. На матрице какого порядка мы заканчиваем решение задачи, и почему?
Литература.
Основна
- Зайченко Ю.П. Исследование операций.- К.:Высшая школа,1988-552с.
- Зайченко Ю.П. Исследование операций. Сборник задач.- К.:Высшая школа,1990-239с.
- Юхименко Б.І. Математичне програмування для єкономистів. Навчальний посібник.- Одеса: Наука та техника,2006 – 167с.
- Вітлінський В.В. Моделювання економіки: Навч. посібник. –К.: КНЕУ, 2003.-408с.
Дополнительная
- Вагнер Г. Основы исследования операций. В 3т.- М.:Мир,1983
- Кутковецкий В.Я. Дослідження операцій. Навчальний посібник. –К.:2004.-350с.
- Наконечний С.І., Савіна С.С. Математичне програмування –К.: 2003.-452с.