Читайте также:
|
Задача о коммивояжере – одна из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году. В своей области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются всё новые методы решения.
Постановка задачи. Коммивояжер должен объехать N городов. Известны затраты (стоимостные, временные, расстояния) на переезд между i – м и j – м городом, которые заданы в виде матрицы. Коммивояжер, выехав из исходного города, должен объехать все города, посетив каждый один раз, и вернуться в исходный. Требуется определить в каком порядке следует объезжать города, чтобы суммарные затраты были минимальными.
Если затраты на переезд между каждой парой городов не зависят от направления движения, то задача называется симметричной, в противном случае – несимметричной.
К задаче коммивояжера сводится ряд практических задач. Она решается во многих областях, связанных с замкнутыми и при этом жестко связанными по времени системами. Например, конвейерное производство (в этом случае величины означают затраты времени, или стоимостные затраты на переналадку конвейера при переходе от выполнения операции i к операции j), многооперационные обрабатывающие комплексы (определяется оптимальный порядок обработки различных изделий на одном и том же оборудовании), судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий.
Модель. В качестве переменных выбираются элементы матрицы переездов:
Пусть.
- переезд из i-го города в j-ый включается в маршрут;
- в противном случае.
Ограничения группы (а) задают условие: в каждый город коммивояжер въезжает только один раз. Ограничения группы (b) задают условие: из каждого города коммивояжер выезжает только один раз.
При решении задачи также необходимо учесть дополнительное условие, недопускающее появление неполных замкнутых циклов (см. рисунок 3.3).
Например, для задачи с 5-ю городами в модель добавляются следующие блоки условий
Условия блока (3.6) не допускают появления неполных замкнутых циклов между парами городов. Условия блока (3.7) не допускают появления неполных замкнутых циклов между тремя городами. Аналогичный блок условий (3.8) вводится для всех четверок городов.
В [4] приведен еще один вид математической записи комплекса ограничений, описывающих это дополнительное условие.
Задача является задачей булевского программирования.
Методы реше
метод ветвей и границ для задачи о коммивояжере; этот метод является эвристическим в том смысле, что он не использует модельного представления задачи, а различные ограничения задачи, такие как, например, условие связанности полного цикла учитываются непосредственно в алгоритме метода;
венгерский методом с модификацией, отвергающей решения с неполными замкнутыми циклами [4];
методы ЦЛП при преобразовании модели к модели ЦЛП; такой подход требует полное модельное описание задачи, включая моделирование условия связанности полного цикла; теоретически такой подход возможен, но с точки зрения вычислительных затрат очень не эффективен.
Дата добавления: 2015-09-10; просмотров: 107 | Поможем написать вашу работу | Нарушение авторских прав |