Автор работы: Пользователь скрыл имя, 31 Марта 2011 в 19:14, курсовая работа
Целью данной курсовой работы является рассмотрение задачи коммивояжера, способов её решения.
Рассмотрена задача коммивояжёра, а также приведён алгоритм метода ветвей и границ для решения задачи коммивояжёра.
Введение
1. Теоретическая часть 6
1.1 Основные понятия теории графов 6
1.2 Формулировка и некоторые свойства решений задачи коммивояжера. 8
1.3 Постановка задачи коммивояжера как задачи на графе 10
1.4 Условия существования Гамильтонова контура 10
1.5 Метод ветвей и границ…………………………………………………. 11
1.6 Практическое применение задачи коммивояжера…………………… 17
2. Практическая часть 20
Заключение
Список используемой литературы
Действия 1-3 (переналадка с i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому
С[i,j] = max(t(x), t(y), t(z))
Теперь,
как и в предыдущем случае, задача
составления оптимальной программы для
дыропробивного пресса сводится к задаче
коммивояжера (здесь - симметричной).
Инвестор, располагающий суммой в 300 тысяч денежных единиц, может вложить свой капитал в акции автомобильного концерна А и строительного предприятия В. Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в два раза больше, чем акций В, причём последних можно купить не более чем на 100 тысяч денежных единиц. Дивиденды по акциям А составляют 8% в год, по акциям В – 10%. Какую максимальную прибыль можно получить в первый год?
Пусть
цены на акции одинаковы для A и B и равны:
ЦA = ЦB = 1 тыс.
Информация о работе Решение задач коммивояжёра, способов её решения