Исследование операций. Лекция 8. Задача коммивояжера

1.

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
ЛЕКЦИЯ 8
ЗАДАЧА КОММИВОЯЖЕРА

2.

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

3.

Задача коммивояжера:
математическая постановка
• Имеется полный граф с n вершинами
(ориентированный или неориентированный)
• Известны веса, приписанные ребрам (или
дугам)
• Найти гамильтонов цикл с минимальной
суммой весов дуг (тур)

4.

Задача коммивояжера:
матрица стоимостей
Граф со взвешенными дугами описывается
матрицей смежности
(матрица стоимостей, платежная матрица)
«Стоимость» тура АБВГА
А Б В Г
1+6+3+4=14
А х
1
5
4
Б 1
х
6
7
«Стоимость» тура АГВБА
В 5
6
х
3
4+3+6+1=14
Г
4
7
3
х
Задача симметричная –
«стоимость» перемещения из Х в У и из У в Х
одинаковая

5.

Задача коммивояжера:
несимметричная матрица стоимостей
Задача несимметричная – «стоимость»
перемещения из Х в У и из У в Х разная хотя бы
для одной пары Х и У.
«Стоимость»
тура
АБВГА
А Б В Г
2+8+3+4=17
А х
2
5
6
Б 1
х
8
7
«Стоимость» тура АГВБА
В 5
6
х
3
6+3+6+1=16
Г
4
7
3
х

6.

Метод ветвей и границ
1. Выбирается одно из ребер, например,