2015-07-21
449
Враховуючи те, що круїз е круговим, в якості методу оптимізації обираємо методи рішення «задачі комівояжера».
Постановка завдання задачі комівояжера полягає в наступному: мається n портів, відстані між ними (табл. 1.3) задані у вигляді матриці C = (cij), де i.j = (1…n). В таблиці 1.3 кожному порту призначено номер від одиниці до n.
Кожне значення cij є відстанями між вихідним портом i та портом заходу j, тому їх величини не можуть мати від’ємного значення, тому cij 
0, 
.
В загальному випадку cij 
cji (на приклад коли cji є вартість проїзду з міста j в місто i, яке не дорівнює переїзду з міста i в місто j). Така задача вважається несиметричною. Враховуючи особливості роботи морського транспорту та географічне розташування портів круїзу, наша задача має симетричний характер, тобто cij = cji.
Треба знайти найкоротший замкнутий маршрут, який проходить через кожен порт тільки один раз з поверненням в перший базовий порт і який мінімізує сумарну пройдену відстань.
Математична постанова завдання може бути представлена в наступному вигляді:
|
|
|
 ;
| (1.24) |
| (1.25) |
| (1.26) |
Xij 
| (1.27) |
У РГЗ цю задачу варто вирішувати за допомогою засобу «Пошук рішення» програми електронних таблиць Microsoft EXCEL.
Інструкція для роботи із засобом «Пошук рішення» програми електронних таблиць Microsoft EXCEL наведена в додатку
Результати рішення задачі представляються у вигляді схеми.
У додатку А РГЗ необхідно представити відповідний «Звіт про результати» рішення задачі комівояжера.
