Федеральное агентство по образованию
ГОУ ВПО «Уральский Федеральный Университет имени первого Президента России Б.Н.Ельцина»
Высшая школа экономики и менеджмента
Кафедра анализа систем и принятия решений
КУРСОВАЯ РАБОТА
по дисциплине «Имитационное моделирование»
на тему: «Решение задачи коммивояжера методом Монте-Карло»
Руководитель:
Нормоконтролёр:
Студент гр. ЭМ‑391601: .
Оценка
Дата защиты
Члены комиссии
Екатеринбург
2011
СОДЕРЖАНИЕ
Задание на выполнение курсовой работы.. 3
Введение. 4
РАЗДЕЛ 1. теоретическая основа.. 5
РАЗДЕЛ 2. блок-схема.. 6
РАЗДЕЛ 3. Описание параметров и переменных.. 8
РАЗДЕЛ 4. Текст программы в mathcad.. 9
РАЗДЕЛ 5. Верификация.. 11
Заключение. 12
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.. 13
Задание на выполнение курсовой работы
Необходимо решить задачу коммивояжёра методом Монте-Карло. Найти кратчайший (по возможности) маршрут, включающий все города и начинающийся и заканчивающийся в 1 - м городе, и его длину.
|
Города |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
1 |
9 |
9 |
1 |
9 |
4 |
1 |
2 |
1 |
1 |
9 |
4 |
8 |
4 |
1 |
1 |
9 |
7 |
6 |
6 |
|
2 |
|
1 |
9 |
7 |
6 |
2 |
5 |
1 |
9 |
7 |
2 |
6 |
3 |
1 |
9 |
5 |
1 |
1 |
1 |
|
3 |
|
|
9 |
5 |
5 |
8 |
1 |
9 |
8 |
1 |
3 |
2 |
1 |
9 |
4 |
9 |
5 |
5 |
7 |
|
4 |
|
|
|
5 |
8 |
9 |
4 |
2 |
1 |
4 |
5 |
9 |
4 |
1 |
2 |
3 |
4 |
5 |
8 |
|
5 |
|
|
|
|
5 |
5 |
6 |
4 |
7 |
8 |
9 |
1 |
3 |
9 |
5 |
4 |
8 |
3 |
9 |
|
6 |
|
|
|
|
|
8 |
9 |
7 |
6 |
4 |
1 |
2 |
2 |
3 |
8 |
5 |
1 |
1 |
5 |
|
7 |
|
|
|
|
|
|
5 |
7 |
7 |
8 |
1 |
5 |
9 |
2 |
9 |
5 |
2 |
3 |
6 |
|
8 |
|
|
|
|
|
|
|
5 |
8 |
9 |
8 |
6 |
4 |
3 |
8 |
5 |
6 |
5 |
7 |
|
9 |
|
|
|
|
|
|
|
|
4 |
3 |
8 |
5 |
1 |
9 |
2 |
6 |
6 |
7 |
2 |
|
10 |
|
|
|
|
|
|
|
|
|
2 |
3 |
1 |
1 |
5 |
4 |
4 |
6 |
5 |
2 |
|
11 |
|
|
|
|
|
|
|
|
|
|
5 |
7 |
3 |
8 |
9 |
4 |
2 |
1 |
8 |
|
12 |
|
|
|
|
|
|
|
|
|
|
|
5 |
4 |
2 |
1 |
6 |
3 |
5 |
5 |
|
13 |
|
|
|
|
|
|
|
|
|
|
|
|
7 |
3 |
2 |
8 |
6 |
5 |
3 |
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
9 |
3 |
2 |
1 |
4 |
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
9 |
8 |
2 |
1 |
|
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
6 |
7 |
9 |
|
17 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
8 |
5 |
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
3 |
|
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
Введение
В MathCAD имеется ряд встроенных функций, задающих используемые в математической статистике законы распределения. Они вычисляют как значение плотности вероятности различных распределений по значению случайной величины х, так и некоторые сопутствующие функции. Все они, по сути, являются либо встроенными аналитическими зависимостями, либо специальными функциями. Большой интерес представляет наличие генераторов случайных чисел, создающих выборку псевдослучайных данных с соответствующим законом распределения.
РАЗДЕЛ 1. теоретическая основа
Методами Монте-Карло называют любую статистическую процедуру, включающую в себя приемы статистической выборки. Не останавливаясь на общих идеях метода Монте-Карло, рассмотрим его применение к решению задачи коммивояжера.
Вершину l -принимают за начальную и закладывают в урну жетоны с номерами от 2 до n. Тщательно перемешав жетоны, вытаскивают их по одному и записывают номера, например . При этом получают гамильтонов контур l, . Подсчитывают длину этого контура и запоминают ее. После этого процедуру повторяют, и если новый маршрут окажется хуже, его тотчас забывают, а если лучше, то забывают предыдущий, а новый запоминают. Проводя такую процедуру многократно, можно с высокой степенью вероятности рассчитывать на то, что удастся найти если и не наилучший, то достаточно хороший маршрут.
Для проведения таких испытаний обычно используют ЭВМ, снабженные датчиками случайных чисел, что позволяет за короткое время просмотреть значительное число маршрутов [2, 460].
РАЗДЕЛ 2. блок-схема
Построим необходимые детальные блок-схемы.
Блок-схема подпрограммы «spisok ()» представлена на рисунке 1.
Блок-схема программы представлена на рисунке 2.
РАЗДЕЛ 3. Описание параметров и переменных
M – треугольная матрица, на пересечении строки i и столбца j лежит длинна пути, который необходимо пройти из города i в город j.
M1 – симметричная матрица путей между городами.
Ngor – параметр, содержащий число городов, которые необходимо пройти.
spisok() – подпрограмма, возвращающая порядок, в котором необходимо пройти города.
Broskov – параметр, содержащий количество маршрутов, которые необходимо проверить.
x – массив, хранящий порядок в котором необходимо пройти города.
q – переменная, используемая для временного хранения значений.
a – переменная, хранящая случайно сгенерированный, равномерно распределённый, округлённый в меньшую сторону номер города.
Smin – переменная, хранящая кратчайший маршрут.
S – переменная, хранящая длину пути текущего маршрута.
sp – переменная, хранящая порядок прохождения городов.
put – массив, хранящий порядок прохождения городов при кратчайшем маршруте.
Sum – программа, возвращающая кратчайший маршрут и порядок прохождения городов при кратчайшем маршруте.
n – переменная, содержащая количество проверенных маршрутов.
РАЗДЕЛ 4. Текст программы в mathcad
РАЗДЕЛ 5. Верификация
Для проверки правильности работы программы зададим квадратную матрицу путей M1 размера три на три.
Результаты работы программы:
- порядок прохождения городов: из первого города во второй, из второго в третий, из третьего в первый;
- кратчайший путь 15.
Всего в данной задаче есть два возможных маршрута (1,2,3,1) или (1,3,2,1). Рассчитаем пути каждого из них. В первом случае получаем путь 2 + 6 +7 = 15. Во втором – 5 + 8 + 4 = 17. Следовательно, наша программа работает правильно.
Заключение
Целью данной курсовой работы являлось написание программы в MathCad для решения задачи коммивояжера методом Монте-Карло, т.е. нахождения кратчайшего маршрута. Также мы построили детальные блок-схемы и описали переменные и параметры, используемые в программе. Провели верификацию и сделали вывод, что программа работает корректно.
Самый короткий маршрут для 20 городов был выявлен при значении параметра Broskov 10000000. Длина этого маршрута 45. Маршрут представлен на рисунке 3.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
- Бородачев С.М. Имитационное моделирование в экономике: учебное пособие /С.М. Бородачев. – Екатеринбург: ГОУ ВПО «УГТУ-УПИ», 2007. – 35 с.
- Коршунов Ю.М. Математические основы кибернетики. – М.,1987
- Электронный учебник по MathCAD – Ресурс доступен: http://www.exponenta.ru/soft/Mathcad/Mathcad.asp
Скачать: