ДЕРЖАВНА МИТНА СЛУЖБА УКРАЇНИ
АКАДЕМІЯ митної служби України
Контрольна робота
з дисципліни:
«Економіко-математичне моделювання»
Варіант 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
