33

Содержани

Введение 4

Глава 1. Сущность задачи коммивояжёра 6

1.1. Элементы теории графов. Цикл Гамильтона 6

1.2. Постановка задачи коммивояжера 8

1.3. Методы решения ЗК 10

1.3.1. Жадный алгоритм 10

1.3.2 Деревянный алгоритм 13

1.3.3. Метод ветвей и границ 17

1.3.4. Алгоритм Дейкстры 18

1.4 Анализ методов решения задачи коммивояжера 19

Глава 2. Практическая реализация задачи коммивояжёра 20

2.1 Решение задачи коммивояжёра методом ветвей и границ 20

2.2 Решение задачи с помощью программы «Нахождение оптимального маршрута» 25

2.3 Решение задачи с помощью сайта Semestr.ru 26

Заключение 32

Список используемой литературы 33

Введение 3

Глава 1. Сущность задачи коммивояжёра 5

1.1. Элементы теории графов. Цикл Гамильтона 5

1.2. Постановка задачи коммивояжера 7

1.3. Методы решения ЗК 9

1.3.1. Жадный алгоритм 9

1.3.2. Деревянный алгоритм 12

1.3.3. Метод ветвей и границ 16

1.3.4. Алгоритм Дейкстры 17

1.4 Анализ методов решения задачи коммивояжера 18

Глава 2. Практическая реализация задачи коммивояжёра 20

2.1 Решение задачи коммивояжёра методом ветвей и границ 20

2.2 Решение задачи с помощью программы «Нахождение оптимального маршрута» 25

2.3 Решение задачи с помощью сайта Semestr.ru 26

Заключение 31

Список используемой литературы 32

Введение

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

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

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

Для реализации поставленной цели необходимо, выполнить следующие задачи:

• рассмотреть и ввести основные понятия теории графов;

• раскрыть сущность методов ветвей и границ, «жадного» алгоритма, «деревянного» алгоритма, алгоритма Дейкстры решения задачи коммивояжёра;

• показать применение перечисленных методов на практике ;

• изучить компьютерную программу «Нахождение оптимального маршрута», а также интернет-реализацию решения данной задачи с помощью сайта semestr.ru;

Мой курсовой проект имеет следующую структуру:

• введение, в котором раскрывается актуальность целей и задач курсового проекта;

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

• заключение, в котором подводятся итоги выполненной работы.

При написание курсового проекта были изучены, работы следующих ведущих экономистов Фомин Г.П., Степочкина С.А., Сигорский В. П., Кузнецов Ю. Н., Липатов Е. П., Бондарев В. М., Рублинецкий В. И. и других, а также интернет ресурс http://semestr.ru.