Розв’язання задачі комівояжера
Складання математичної моделі задачі комівояжера. Її розв'язок за допомогою електронних таблиць Microsoft Excel. Знаходження оптимального плану обходу міст комівояжером за заданими критеріями. Інтерпретація графічно отриманого розв’язку даної задачі.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | украинский |
| Дата добавления | 24.09.2014 |
| Размер файла | 244,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Размещено на http://www.allbest.ru
ДЕРЖАВНА МИТНА СЛУЖБА УКРАЇНИ
АКАДЕМІЯ МИТНОЇ СЛУЖБИ УКРАЇНИ
Контрольна робота
З ДИСЦИПЛІНИ:
«Економіко-математичне моделювання»
Варіант 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
Размещено на Allbest.ru
Подобные документы
Складання математичної моделі задачі забезпечення приросту капіталу. Її рішення за допомогою електронних таблиць Microsoft Excel. Облік максимальної величини сподіваної норми прибутку. Оцінка структури оптимального портфеля. Аналіз отриманого розв’язку.
контрольная работа [390,5 K], добавлен 24.09.2014Розробка програмного комплексу для розв’язання задачі цілочисельного програмування типу "Задача комівояжера". Класифікація задач дослідження операцій. Вибір методу розв’язання транспортної задачі; алгоритмічне і програмне забезпечення, тести і документи.
курсовая работа [807,7 K], добавлен 07.12.2013Розробка математичної моделі задачі заміни устаткування та її розв'язання за допомогою електронних таблиць Microsoft Excel. Визначення оптимальної стратегії експлуатації устаткування, щоб сумарні витрати були мінімальними. Економіко-математична модель.
задача [271,3 K], добавлен 24.09.2014Складання математичної моделі задачі. Побудова симплексної таблиці. Розв’язок задачі лінійного програмування симплексним методом. Рішення двоїстої задачі та складання матриці. Знаходження графічним методом екстремумів функцій, визначеній нерівностями.
контрольная работа [239,0 K], добавлен 28.03.2011Поняття та сутність запасів на виробництві та управління ними. Обчислення загальних витрат на купівлю товару. Розв’язок задачі за допомогою електронних таблиць Microsoft Excel. Аналіз можливості зменшення витрат при збільшенні бюджету на закупівлю.
контрольная работа [651,4 K], добавлен 24.09.2014Методика та головні етапи складання математичної моделі рішення заданої задачі, її елементи: цільові функції, обчислення. Розв’язок задачі за допомогою методу Гоморі: алгоритм програми, ітерації. Розрахунок задачі методом "Розгалуджень та обмежень".
курсовая работа [88,1 K], добавлен 31.08.2014Побудування математичної моделі задачі. Розв'язання задачі за допомогою лінійного програмування та симплексним методом. Наявність негативних коефіцієнтів в індексному рядку. Основний алгоритм симплексного методу. Оптимальний план двоїстої задачі.
контрольная работа [274,8 K], добавлен 28.03.2011Побудова математичної моделі плану перевезення зерна на елеватори, який мінімізує транспортні витрати. Розв’язок задачі симплексним методом. Знаходження графічним методом екстремумів функцій, визначеній нерівностями. Порядок рішення транспортної задачі.
контрольная работа [326,2 K], добавлен 28.03.2011Розробка математичної моделі задачі оптимізації, розв’язання її засобами "Пошук рішення" в MS Excel. Класичні методи дослідження функцій на оптимум. Графічне розв’язання задачі лінійного програмування. Метод штучного базису. Двоїстий симплекс-метод.
контрольная работа [755,6 K], добавлен 26.12.2011Побудова математичної моделі плану виробництва, який забезпечує найбільший прибуток. Розв’язок задачі симплекс-методом, графічна перевірка оптимальних результатів. Складання опорного плану транспортної задачі. Пошук екстремумів функцій графічним методом.
контрольная работа [286,4 K], добавлен 28.03.2011
