Розв’язання задачі комівояжера
ДЕРЖАВНА
МИТНА СЛУЖБА УКРАЇНИ
АКАДЕМІЯ
МИТНОЇ СЛУЖБИ УКРАЇНИ
Контрольна
робота
З
ДИСЦИПЛІНИ:
«Економіко-математичне
моделювання»
Варіант
10
Виконала:
Студентка гр.
ЕО09-2
Зеленська Каріна
Перевірила:
Лебідь Оксана
Юріївна
м.
Дніпропетровськ
Завдання 5
Скласти математичну модель задачі комівояжера.
Розв’язати задачу за допомогою електронних таблиць Microsoft Excel.
Проінтерпретувати графічно отриманий розв’язок.
Задача 5.10
Розв’язок
математична модель задача комівояжер
Економіко-математична модель. Знайти такий план
обходу міст комівояжером, щоб:
Загальна довжина = План обходу * Матриця
відстаней Þ min
При обмеженнях:
Входять = 1 (в’їзд комівояжера в
місто);
$B$17:$G$17=1
Виходять = 1 (виїзд комівояжера з
міста);
$H$11:$H$16=1
Щоб виключити ситуацію одержання
ізольованих контурів, у модель задачі було запропоновано додати обмеження
зв’язаності, що дозволяє одержати повний контур обходу всіх міст шляхом
зв’язування 6 вузлів в один контур: Зв’язаність_вх_i-міста -
Зв’язаність_вих_j-міста +
+ 5 * Обхід_з_i_в_j-місто ≤ 4;
невідомі плану обходу двійкові
числа.
Реалізація в Excel.
У таблиці плану обходу в рядок
Входять уводимо формули суми по стовпцях, у стовпець Виходять уводимо формули
суми по рядках таблиці, у цільову клітинку (Н17) Довжина вводимо формулу:
=СУММПРОИЗВ(B3:G8;B11:G16)
У таблицю обмежень зв’язаності
вводимо формули
Зв’язаність_вх_i-міста -
Зв’язаність_вих_j-міста +
+(к-сть міст - 1)*Обхід_з_i_в_j-місто
≤ к-сть міст - 2,
в клітинку В21 вносимо ці дані:
=H21-B26+5*B12, так само продовжуємо і в інші чарунки заносити формули.
В чарунки В26:G26 транспортуємо
діапазон Н20:Н25, та після введення формули натискаємо Ctrl+Shift+Enter (для
роботи з масивами).
Запускаємо програму Поиск решений. У
вікні Параметры поиска решений встановлюємо перемикач на позицію Линейная
модель та Неотрицательные значения.
Висновок: таким чином, отримано
наступний план обходу міст
1Þ 5 Þ 2 Þ 3 Þ 6 Þ 4 Þ 1