КОМИТЕТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ НОВГОРОДСКОЙ ОБЛАСТИ

Боровичский техникум строительной индустрии и экономики

«Утверждаю»

Зам.директора по учебной работе (зав. отделением)

________________

«__» ______________20__ г.

Задание на курсовое проектирование

По предмету __Математические методы___________

Студенту группы П-41 .

Олешкевич Дмитрию Хосровичу .

Тема. Решение задачи о коммивояжере, прямой алгоритм.

.

Пояснительная записка

Введение

1. Общая часть

   1. Постановка задачи

      1. Экономическая постановка задачи

      2. Математическая постановка задачи

   2. Обзор существующих решений

2. Технологическая часть

2.1 Нелинейное программирование. Общий вид задач нелинейного программирования Модели нелинейного программирования. Методы решения задач нелинейного программирования.

3. Специальная часть

   1. Описание метода решения.

   2. Решение задачи теста для написания и отладки программы

   3. Анализ полученных результатов

   4. Разработка алгоритма

   5. Обоснование выбора средств разработки

   6. Описание программных модулей

   7. Тестирование программы

   8. Инструкция пользователю

Заключение

Приложение А. Глоссарий понятий

Приложение Б. Текст программы

Приложение В. Видовые экраны работы программы

Приложение Г. Алгоритм решения задачи

Введение

В настоящее время существуют такие типы задач как задачи математического программирования. Существуют множество видов таких задач и способов их решения. В данном случае мы будем рассматривать вид задач математического программирования под названием задачи «Коммивояжёра». Цель задачи – отыскать наилучший маршрут для торговца, который должен объехать города и вернуться в исходный город, как правило за кратчайшее время или с наименьшими затратами. Такие задачи актуальны во многих областях таких как: автомобильные, судовые, железно – дорожные перевозки или в конвейерном производстве. В условиях задачи указывается критерий маршрута и соответствующие матрицы расстояний или стоимостей и т.д. В задачах указывается, что маршрут должен быть одинарным. В современной интерпретации задачи торговца формулируется так: в произвольном порядке обойти все вершины графа по кратчайшему пути и вернуться в исходную вершину, причем каждая вершина проходится 1 раз. Обычно задачу о торговце решают с помощью прямого алгоритма, т.к. для человека расчет такой задачи занимает много времени, и создаются программы для облегчения вычислений.

В данном курсовом проекте будет рассмотрен вопрос о создании программы для решения задачи «коммивояжёра» прямым алгоритмом.

1. Общая часть

1. Постановка задачи

1.1.1. Экономическая постановка задачи

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

Расстояния между городами указаны в таблице 1.

Таблица 1.

	1	2	3	4	5	6	7
1		5	11	6	3	15	8
2	5		7	12	6	7	2
3	11	7		3	6	3	7
4	6	12	3		2	4	13
5	3	6	6	2		2	5
6	15	7	3	4	1		4
7	8	2	7	13	5	4