Автор: Пользователь скрыл имя, 03 Ноября 2012 в 17:22, контрольная работа
Сейчас трудно сказать, когда люди впервые вступили на палубу судна с целью не только добраться из пункта А в пункт Б, но и получить при этом максимум удовольствия от самого путешествия. Так было положено начало индустрии морских круизов, а вместе с тем и весьма прибыльному бизнесу организации отдыха и развлечений на море. Рост спроса на этот вид услуг стимулировал дальнейшее развитие строительства пассажирских судов, уже специально предназначенных для круизов. В наше время туристы путешествуют по морю в настоящих плавучих замках, а наиболее известные верфи мира ведут борьбу за привлечение заказов на сооружение новых, еще более крупных пассажирских судов, начало эксплуатации которых может оказать значительное влияние не только на формирование круизного рынка, но и на экономическое развитие отдельных регионов, в частности Европы, Карибского региона.
Введение
1.Маркетинговое исследование круизного маршрута
1.1 Описание региона
1.2 Описание судна
1.3 Общая характеристика круиза
1.4 Определение оптимального маршрута
Приведенная константа подмножества G3 равняется 0. Нижняя граница гамильтоновых контуров равняется:
S(G3) = 2386+0 = 2386
Приведенная константа подмножества G4 равняется:
S(G4) = 2386+389 = 2775
Для дальнейшего ветвления выбираем множество G3. Множество G4 исключается. В приведенной матрице G3 оценим нули.
Шаг 13. Оценивание нулей в G3. Таблица 14
j i |
1 |
2 |
3 |
ai |
|
1 |
∞ |
0-344 |
344 |
344 |
2 |
0-344 |
∞ |
0-344 |
0 |
5 |
344 |
0-344 |
∞ |
344 |
bj |
344 |
0 |
344 |
0 |
Наибольшая сумма констант: 344, для ребра (1,2).
Получим две матрицы , G5 и G6, включающие и исключающие дугу (1,2).
Шаг 14. Матрица G5. Таблица 15
j i |
1 |
3 |
ai |
|
2 |
∞ |
0 |
0 |
5 |
344 |
∞ |
344 |
bj |
344 |
0 |
688 |
Шаг 15. Матрица G6. Таблица 16
j i |
1 |
2 |
3 |
ai |
|
1 |
∞ |
∞ |
344 |
344 |
2 |
0 |
∞ |
0 |
0 |
5 |
344 |
0 |
∞ |
0 |
bj |
0 |
0 |
0 |
344 |
Продолжаем ветвление матрицы G6, исключаем G5 (сумма констант приведения больше у G5).
S(G5) = 2386+688 = 3074
S(G6) = 2386+344 = 2730
Шаг 16. Матрица G6.Оценим нули. Таблица 17
j i |
1 |
2 |
3 |
ai |
|
1 |
∞ |
0-344 |
344 |
344 |
2 |
∞ |
∞ |
0-344 |
0 |
5 |
0-0 |
0-0 |
∞ |
0 |
bj |
0 |
0 |
344 |
344 |
Наибольшая сумма констант для ребра (1,2) – 344.
Получаем снова две матрицы (два подмножества: G7 и G8).
Шаг 17. Матрица G7. Таблица 18
j i |
1 |
3 |
ai |
|
2 |
∞ |
0 |
0 |
5 |
0 |
∞ |
0 |
bj |
0 |
0 |
0 |
S(G7) = 2730+0 = 2730
Шаг 18. Матрица G8. Таблица 19
j i |
1 |
2 |
3 |
ai |
|
1 |
∞ |
∞ |
344 |
344 |
2 |
∞ |
∞ |
0 |
0 |
5 |
0 |
0 |
∞ |
0 |
bj |
0 |
0 |
0 |
344 |
S(G8) = 2730+344 = 3074 (исключаем)
Включаем ребра (2,3) и (5,1).
В итоге, получаем гамильтонов цикл: 4-5-1-2-3-4. Круизная линия: Дубровник - Венеция - Одесса - Стамбул - Катаколон - Дубровник. Протяженность линии: 309+1504+344+404+557 =3118 миль.
Ветвление по подмножеству G2 приводит к идентичному результату, но противоположному направлению движения.
Решение задачи коммивояжера с использованием надстройки MS EXCEL «Поиск решения»
Задача. Найти решение задачи коммивояжера для графа с заданной матрицей расстояний с использованием надстройки «Поиск решения».
Исходные данные:
|
Порты отправления |
Порты захода | ||||
Одесса(1) |
Стамбул(2) |
Катаколон(3) |
Дубровник(4) |
Венеция(5) | |
Одесса (1) |
∞ |
344 |
748 |
1299 |
1504 |
Стамбул (2) |
344 |
∞ |
404 |
886 |
1160 |
Катаколон (3) |
748 |
404 |
∞ |
557 |
832 |
Дубровник (4) |
1299 |
886 |
557 |
∞ |
309 |
Венеция (5) |
1504 |
1160 |
832 |
309 |
∞ |
Решение далее: