Ui - Uj + nXj < n -1 (i = 1, n, j = 1, n, І Ф j),
де ui, Uj - невід'ємні цілочислові змінні, які в процесі розв'язання
задачі набуватимуть значень порядкових номерів міст за оптимальним маршрутом прямування комівояжера.
У результаті математична модель має такий вигляд
n n
z = Т.Т.СуХу -> min, i ф j;
Z xij =1 (j =1, n, i * j);
i=1
£ Xj = 1 (i = 1, n, i Ф j);
Xj = {0; 1} (i = 1, n, j = 1, n);
Ui - Uj + nXjj < n -1 (i = 1, n, j = 1, n, i Ф j).
До задачі "комівояжера" зводиться також багато інших практично важливих задач: перевезення пошти або певних товарів у місті; перевірка або інспекція підприємств та установ; з'єднання пунктів лініями газопостачання або зв'язку тощо.
Введення умови цілочисельності в задачу лінійного програмування призводить до ускладнення розв'язання таких задач, оскільки за таких умов точкою екстремуму може виявитись будь-яка точка багатокутника розв'язків. Ці обставини обумовлюють необхідність використання спеціальних методів розв'язання названих задач.
Методи розв'язання задач цілочислового програмування можна поділити на три групи.
• Методи відтинання. При використанні цих методів розв'язок задачі лінійного програмування без урахування вимог цілочисельності уточнюється за рахунок розширення кількості обмежень, обумовлених вимогами цілочисельності.
• Комбінаторні методи. Ці методи базуються на ідеї цілеспрямованого перебирання всіх допустимих цілочислових розв'язків з відсіюванням множин неперспективних допустимих розв'язків.
• Наближені методи. Вони, як правило, дозволяють знайти наближений розв'язок задачі за меншого обсягу обчислень та спрощення відповідних алгоритмів.
Висновки
• 1. Поняття "модель" може бути визначено як умовний образ об'єкта чи процесу, що відображає його основні властивості й використовується під час дослідження. Модель є лише спрощеним відображенням реальних подій, обставин та ситуацій, що відбуваються в системі управління.
• 2. На етапах економіко-математичного моделювання: створюється модель, яка описує реальний об'єкт чи процес: здійснюється аналіз побудованої моделі: отримані результати дослідження моделі переносяться на реальну систему та перевіряється їх адекватність: аналізуються отримані результати і приймається відповідне рішення.
Сторінки
В нашій електронній бібліотеці ви можете безкоштовно і без реєстрації прочитати «Прийняття управлінських рішень» автора Автор невідомий на телефоні, Android, iPhone, iPads. Зараз ви знаходитесь в розділі „Задачі лінійного цілочислового програмування“ на сторінці 3. Приємного читання.
