Розв’язання задачі комівояжера

ДЕРЖАВНА МИТНА СЛУЖБА УКРАЇНИ

АКАДЕМІЯ МИТНОЇ СЛУЖБИ УКРАЇНИ

Контрольна робота

З ДИСЦИПЛІНИ:

«Економіко-математичне моделювання»

Варіант 10

Виконала:

Студентка гр. ЕО09-2

Зеленська Каріна

Перевірила:

Лебідь Оксана Юріївна

м. Дніпропетровськ

2011

Завдання 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