Розв’язання задачі комівояжера
ДЕРЖАВНА МИТНА СЛУЖБА УКРАЇНИ
АКАДЕМІЯ МИТНОЇ СЛУЖБИ УКРАЇНИ
Контрольна робота
З ДИСЦИПЛІНИ:
«Економіко-математичне моделювання»
Варіант 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
Больше работ по теме:
Контрольная работа
Ряды распределения и динамики
Контрольная работа
Сетевое планирование и управление. Построение сетевых моделей
Контрольная работа
Основы управления качеством продукции лесозаготовительной и деревообрабатывающей промышленности
Контрольная работа
Основы управления организацией
Контрольная работа
Предмет: Менеджмент
Тип работы: Контрольная работа
Новости образования
22 Июля 2016 16:26
Более 70 представителей крупных вузов АСЕАН подтвердили участие в форуме во Владивостоке
22 Июля 2016 12:51
Абызов: публикация первичных статсведений снизит бюрократическую нагрузку на школы
22 Июля 2016 11:53
В Чечне свыше 200 школьников сдали ЕГЭ с результатом свыше 90 баллов - министр
22 Июля 2016 05:36
Замглавы Минобрнауки РФ: задача сократить число людей с высшим образованием не стоит
21 Июля 2016 20:19
КОНТАКТНЫЙ EMAIL: [email protected]
Скачать реферат © 2017 | Пользовательское соглашение
ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ