Решение задачи коммивояжера (с транспортным уклоном)

Краткое описание

СОДЕРЖАНИЕ

ВВЕДЕНИЕ…3                                                                                                                       

1.ТЕОРЕТИЧЕСКИЕ И МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

1.1.Понятие и история задачи коммивояжера. Методы решения..5

1.2.Представление в виде графов. Метрическая задача…10

1.3.Формулировка в виде задачи дискретной оптимизации…15

1.4.Формулировка и некоторые свойства решений задачи коммивояжера…18           

1.5.Метод ветвей и границ…19    

1.6.Метод эластичной сети …21                                                                                    

2.ВЫБОР ОПТИМАЛЬНОГО ПУТИ В ТРАНСПОРТНОЙ СЕТИ: МЕТОДИКА РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА.

ЗАКЛЮЧЕНИЕ...28                                                                                                           

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ...29                                                                                                                 

ВВЕДЕНИЕ

Математическое программирование — область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.

Один из разделов математического программирования - линейным программированием.   Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспективного, текущего и оперативного планирования и управления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах развития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т. д. 

Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов), производственно-транспортных и других задач.

На практике довольно обширно применение задачи коммивояжера. В частности ее можно использовать для поиска кратчайшего маршрута при гастролях эстрадной группы по городам, нахождения последовательности технологических операций обеспечивающей наименьшее время выполнения всего производственного цикла и пр.

Задача коммивояжера является одной из знаменитых задач теории комбинаторики и  пользуется популярностью благодаря тому, что к ней сводится большое количество  практических задач. Для решения задачи коммивояжера используют различные  группы простейших методов: полный и случайный перебор, жадный и деревянный  алгоритмы, метод имитации отжига. Широкое применение получили различные  модификации более эффективных методов, таких как метод ветвей и границ, генетических  алгоритмов, а также алгоритм муравьиных колоний . 

Задача коммивояжера была поставлена в 1934 году. Постановка задачи: выбрать  оптимальный маршрут поездки из одного города в другой с заездом в указанные города.

В данной курсовой работе рассматривается  задача коммивояжера.

Целью курсовой работы является решение задачи коммивояжера.