"justify"> Всі ефективні (скорочуючі повний перебір) методи розв'язання задачі комівояжера - методи евристичні. У більшості евристичних методів знаходиться не найефективніший маршрут, а наближене рішення. Найчастіше затребувані так звані any-time алгоритми, тобто поступово поліпшують деякий поточне наближене рішення.
Існує також постановки, в яких завдання комівояжера стає NP-повною. Зазвичай такі постановки виглядають наступним чином: чи існує на заданому графі G такий обхід, що його вартість не перевищує X. Часто на ній проводять обкатку нових підходів до евристичному скороченню повного перебору.
На практиці застосовуються різні модифікації більш ефективних методів: метод гілок і меж і метод генетичних алгоритмів, а також алгоритм мурашиної колонії.
1.5 NP-складні завдання
У теорії алгоритмів класом NP (від англ. non-deterministic polynomial) називають безліч алгоритмів, час роботи яких істотно залежить від розміру вхідних даних. У той же час, якщо надати алгоритмом деякі додаткові відомості (так званих свідків рішення), то він зможе досить швидко (за час, не перевершує многочлена від розміру даних) вирішити задачу.
Багато задач на графах відносять до класу NP-повних задач.
1.6 Транспортна задача
Транспортна задача (Завдання Монжа-Канторовича) - завдання про оптимальному плані перевезень продукту з пунктів відправлення в пункти споживання. Розробка та застосування оптимальних схем вантажних потоків дозволяють знизити витрати на перевезення. Транспортна задача є з теорії складності обчислень NP-складною.
Коли сумарний обсяг пропозицій (вантажів, що стоять в пунктах відправлення) НЕ дорівнює загальному обсягу попиту на товари (вантажі), запитувані пунктами споживання, транспортна задача називається незбалансованою.
1.7 Постановка завдання
Транспортна задача (класична) - завдання про оптимальному плані перевезень однорідного продукту з однорідних пунктів наявності в однорідні пункти споживання на однорідних транспортних засобах (зумовленості кількості) зі статичними даними і лінеарному підході (це основні умови задачі).
Для класичної транспортної задачі виділяють два типи завдань: критерій вартості (досягнення мінімуму витрат на перевезення) або відстаней і критерій часу (затрачається мінімум часу на перевезення).
1.8 Історія пошуку методів вирішення
Проблема була вперше формалізована французьким математиком Гаспаром Монжем в 1781. Основне просування було зроблено на полях під час Великої Вітчизняної війни радянським математиком і економістом Леонідом Канторовичем. Тому іноді ця проблема називається Транспортної завданням Монжа-Канторовича.
1.9 Методи рішення
Класичну трансп?? ртную завдання можна вирішити симплекс-методом, але є й інші підходи.
Наприклад, спочатку шукається опорний план за допомогою одного з нижче перерахованих методів:
· «північно-західного кута»,
· «найменшого елемента»,
· подвійного переваги,
· апроксимацією Фогеля
А вже потім за допомогою теорії графів шукається оптимальний шлях.
Розглядається дводольний граф, в якому пункти виробництва перебувають у верхній частці, а пункти споживання - у нижній. Пункти виробництва і споживання попарно з'єднуються ребрами нескінченної пропускної здатності і ціни за одиницю потоку C ij.
До верхньої частці штучно приєднується витік. Пропускна здатність ребер з витоку в кожен пункт виробництва дорівнює запасу продукту в цьому пункті. Ціна за одиницю потоку у цих ребер дорівнює 0.
Аналогічно до нижньої частці приєднується стік. Пропускна здатність ребер з кожного пункту споживання в сток дорівнює потреби в продукті в цьому пункті. Ціна за одиницю потоку у цих ребер теж дорівнює 0.
Далі вирішується завдання знаходження максимального потоку мінімальної вартості (mincost maxflow). Її рішення аналогічно знаходженню максимального потоку в алгоритмі Форда-Фалкерсона. Тільки замість найкоротшого доповнюючого потоку шукається найдешевший. Відповідно, в цій подзадаче використовується не пошук в ширину, а алгоритм Беллмана-Форда. При поверненні потоку вартість вважається негативною.
Алгоритм mincost maxflow можна запускати і відразу - без знаходження опорного плану. Але в цьому випадку процес вирішення буде трохи більш довгим. Виконання алгоритму mincost maxflo...
