Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



Пример простой комбинаторной задачи – задача о назначениях. Здесь требование целочисленности выполняется автоматически, поскольку задача о назначениях представляет собой частный случай транспортной задачи (в котором m = n, a i = b j = 1). Более общий случай представляет собой задача коммивояжера.

Имеется n +1 городов; задана матрица С = расстояний между этими городами. Выезжая из исходного города (с номером 0), коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в город 0. В каком порядке объезжать следует города, чтобы суммарное расстояние было минимальным?

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

Параметры задачи

x ij = 1, если коммивояжер из города i переезжает в город j,

x ij = 0 в противном случае,

где i, j = 0, 1, 2,..., n.

Задача минимизации

(суммарное расстояние минимальное)

при условиях

(коммивояжер выезжает из каждого города, кроме начального, один раз)

(коммивояжер въезжает в каждый город, кроме начального, один раз)

ui – uj + nх ij ≤ n - 1, , i ≠ j.

Здесь переменные ui принимают целые неотрицательные значения. Последнее условие вводится для того, чтобы путь коммивояжера не распался на несколько не связанных между собой подциклов (задача о назначениях) – любой путь состоит из одного цикла.





Дата публикования: 2014-11-04; Прочитано: 469 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...