СОДЕРЖАНИЕ
ВВЕДЕНИЕ…3
1.ТЕОРЕТИЧЕСКИЕ И МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА
1.1.Понятие и история задачи коммивояжера. Методы решения..5
1.2.Представление в виде графов. Метрическая задача…10
1.3.Формулировка в виде задачи дискретной оптимизации…15
1.4.Формулировка и некоторые свойства решений задачи коммивояжера…18
1.5.Метод ветвей и границ…19
1.6.Метод эластичной сети …21
2.ВЫБОР ОПТИМАЛЬНОГО ПУТИ В ТРАНСПОРТНОЙ СЕТИ: МЕТОДИКА РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА.
ЗАКЛЮЧЕНИЕ...28
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ...29
ВВЕДЕНИЕ
Математическое программирование — область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.
Один из разделов математического программирования - линейным программированием. Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспективного, текущего и оперативного планирования и управления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах развития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т. д.
Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов), производственно-транспортных и других задач.
На практике довольно обширно применение задачи коммивояжера. В частности ее можно использовать для поиска кратчайшего маршрута при гастролях эстрадной группы по городам, нахождения последовательности технологических операций обеспечивающей наименьшее время выполнения всего производственного цикла и пр.
Задача коммивояжера является одной из знаменитых задач теории комбинаторики и пользуется популярностью благодаря тому, что к ней сводится большое количество практических задач. Для решения задачи коммивояжера используют различные группы простейших методов: полный и случайный перебор, жадный и деревянный алгоритмы, метод имитации отжига. Широкое применение получили различные модификации более эффективных методов, таких как метод ветвей и границ, генетических алгоритмов, а также алгоритм муравьиных колоний .
Задача коммивояжера была поставлена в 1934 году. Постановка задачи: выбрать оптимальный маршрут поездки из одного города в другой с заездом в указанные города.
В данной курсовой работе рассматривается задача коммивояжера.
Целью курсовой работы является решение задачи коммивояжера.
Не нашли готовую?