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

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



Даны множество вершин и множество дуг . Здесь вершины представляют города, а дуги ‑ упорядоченные пары и городов, между которыми возможна непосредственная поездка, время которой . Цель ‑ нахождение маршрута, начиная с города 1, с минимальным временем, и проходящего через каждый город только один раз.

Введем бинарную решающую переменную :

Задача коммивояжера может быть сформулирована в виде следующей задачи ДО:

при ограничениях

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

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






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



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