Курсовая решение задачи коммивояжера

КУРСОВАЯ РАБОТА
по дисциплине "Исследование операций в экономике"

Тема: “Решение задачи коммивояжера”

Новокузнецк 2010
Оглавление

Введение 3
1 Математическое обеспечение 4
2 Алгоритм решения 7
3 Программное обеспечение 8
4 Исследовательская часть 10
Заключение 20
Список использованных источников 21
Приложение А 65

Введение
Каждыйчеловек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. В середине XX века был создан специальный математический аппарат, помогающийэто делать “по науке”. Соответствующий раздел математики называется математическим программированием.
Актуальность выбранной темы: сейчас решение данной задачи необходимо во многих областях промышленности и народного хозяйства, связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовыеи железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий.
Цель курсовой работы изучить метод полного перебора для решения одной задач линейного программирования – задачи «О коммивояжере» и составить алгоритм и программу для ее решения.

1 Математическое обеспечение
1.1 Постановка задачи.
Классическая постановка задачи окоммивояжере выглядит следующим образом:
Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:
– маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
– в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти всегорода, при этом не побывав ни в одном городе дважды.
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице как бы вычеркивается диагональ). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющегоминимальную сумму затрат.

1.2 Анализ методов решения

Для решения «Задачи коммивояжера» существует несколько методов решения. Отличаются они прежде всего скоростью решения и точностью.
«Жадный» алгоритм
Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путем выбора самого короткого, еще не выбранного ребра при условии, что оно не образует цикл цикла с уже выбраннымиребрами. Жадным этот алгоритм называется потому, что на последних шагах приходится жестоко расплачиваться за его жадность. Алгоритм быстрый, но не точный.
Деревянный алгоритм
Суть метода состоит в построении кратчайшего остовного дерева. Погрешность такого алгоритма равна единице, скорость высокая.
Полный перебор
Практически применим только в задачах малого размера. Напомним, чтозадача коммивояжера с n городами требует при полном переборе рассмотрения (n-1)!/2 туров в симметричной задаче и (n-1)! туров в несимметричной задачи.
Метод ветвей и границ
К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали удачный алгоритм решения задачи коммивояжера и тем самым способствовали популяризацииподхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения задач коммивояжера было придумано несколько других модификаций метода, но в большинстве учебников излагается работа Литтла.
Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху –...