Методы решения задачи коммивояжера
Курсовая по предмету:
"Информатика"
Название работы:
"Методы решения задачи коммивояжера"
Автор работы: Юлия
Страниц: 71 шт.
Год:2011
Краткая выдержка из текста работы (Аннотация)
Введение
Один из основных путей повышения эффективности работы транспорта — это модернизация системы управления и организации его работы. В последнее время все более интенсивно в процессы мониторинга, моделирования сложных транспортных объектов, принятия решений и контроля их исполнения, составляющих суть управления на транспорте, внедряются методы математического моделирования, а также обеспечивающие их передовые информационные технологии.
В силу специфики основных технологических процессов на транспорте, представляется перспективным использование мате-матического аппарата теории графов. Характерными примерами может служить управление маневровой работой на сортировочных станциях, развозом грузов по сети магазинов города. Вместе с тем, многокритериальность указанных задач управления, а также их программно-математическое обеспечение, не в полной мере учитывающее специфику некоторых задач, повышают вероятность ошибочных действий со стороны человека-оператора, и, как следствие, вероятность сбоев в работе сортировочных станций, автотранспортных предприятий, срывов графиков движения поездов и автомашин. В связи с этим формализация (математическое описание) задач управления транспортными системами на основе использования задачи коммивояжера актуальна, так как позволяет использовать разработанные машинные методы принятия обоснованных решений.
Задачи управления транспортными потоками являются многокритериальными и плохо формализуются вследствие нестационарности и зашумленности исходной информации, противоречивым экономическим, технологическим, экологическим и другим требованиям. Важнейшими проблемами совершенствования систем автоматического управления является повышение надежности и точности их функционирования, безопасности и быстродействия. Решение этих задач позволит снять ряд технологических и организационно-экономических проблем.
Содержание работы
Введение 2
1. Теоретическая часть 4
1.1. Содержательное описание 4
1.2. Математическая модель 4
1.3. Постановка оптимизационной задачи 6
1.4. Методы решения задачи коммивояжера 6
1.4.1. Метод ветвей и границ 6
1.4.2. Алгоритм Литтла 9
1.4.3. Генетические алгоритмы 11
2. Практическая часть 12
2.1. Постановка задачи 12
2.2. Решение задачи методом полного перебора 13
2.3. Решение задачи методом ветвей и границ 25
2.4. Решение задачи методом Литтла 27
2.5. Программное решение муравьинным методом 36
2.6. Сравнение методов решения задачи коммивояжера 46
Заключение 47
Литература 48
Приложение 50
Использованная литература
- О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., «Мир», 1965, 174 с.
- В. П. Сигорский. Математический аппарат инженера. - К., «Техніка», 1975, 768 с.
- Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.
- Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. – М., Наука, 1979, 345 с.
- Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с.
- В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. – Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.
- Ф. А. Новиков Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с.
- Bonavear E., DorigoM. Swarm Intelligence: from Natural to Artificial Systems.— Oxford University Press, 1999.— 307 p.
- Corne D., Dorigo M., Glover F. New Ideas in Optimization.— McGrav Hill, 1999.
- Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization // Reader for CEU Summer University Course «Complex System».— Budapest, Central European University, 2001.— P. 1–38
- http://irida.ulb.ac.de/ACO/ACO.html.
- http://www.iwr.uniheidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html.
- Reimann M. Ant Based Optimization in Good Transportation. PhD Thesis. University of Vienna.— Vienna, Austria, 2002.— 149 p.
- Caro G. D., DorigoM. Anet: a Mobile Agents Approach to Adaptive Routing. Technical Report IRIDA 97 12. IRIDA— Universite Libre de Brusseles.— Brussels, Belgium, 1997.— 27 p.
- http://www.swarm.org.
- Cherix D. Note preliminaire sur la structure, la phenologie et le regime alimentaire d'une super colonie de Formica lugubris Zett. // Insects Sociaux 27, 1980.— P. 226–236.