загрузка...
загрузка...
На головну

заключні зауваження

  1. XII. ЗАКЛЮЧНІ ПОЛОЖЕННЯ
  2. АДАПТИВНЕ КЕРІВНИЦТВО. Заключні ЗАУВАЖЕННЯ
  3. Адаптивне керівництво. заключні зауваження
  4. Вступні зауваження
  5. Вступні зауваження
  6. вступні зауваження
  7. Вступні зауваження

Слід зазначити, що завдання комівояжера є комбінаторної завданням, оскільки число можливих маршрутів експоненціально залежить від числа міст. Дане завдання належить до класу так званих NP-повних задач. Було показано, що численний клас комбінаторних задач є класом еквівалентних завдань, де еквівалентність розуміється в тому сенсі, що або всі вони можуть бути вирішені за допомогою алгоритмів, що мають поліноміальну складність обчислень, або жодна з них не може бути вирішена за допомогою таких алгоритмів. Дана група завдань утворює клас NP-повних задач. І. нарешті, завдання комівояжера не може бути безпосередньо сформульована і вирішена як завдання лінійного програмування. Вона відноситься до класу потокових завдань в силу історично сформованої зв'язку між методами їх вирішення і в силу її графічного представлення як завдання про оптимальний маршрут.

Ряд завдань, що представляють собою різновид завдання комівояжера, був поставлений і вирішений з метою дослідити маршрути руху людей або перевезення товарів. Однак розгляд цих прикладних задач відсуває на другий план одну важливу особливість завдання комівояжера. Основна відмінність між завданням комівояжера і іншими завданнями про найкоротший шлях полягає в тому, що в першій з них потрібно існування орієнтованого циклу, в який рівно один раз входять всі вузли мережі. Іншими важливими додатками завдання комівояжера є завдання складання розкладів.

додаткова література

1. Ю. М. Єрмолаєв та ін. Математичні методи дослідження операцій. Київ: "Вища школа", 1979 г.

2. Д. Філліпс, А. Гарсіа-Діас. Методи аналізу мереж. М.: Мир, 1984 р

3. Н. М. Губін та ін. Економіко-математичні методи і моделі в плануванні і управлінні в галузі зв'язку. М .: Радио и связь, 1993 р



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15

Теорема про максимальний потік і мінімальному розрізі | Ізоморфізм і гомеоморфизм графів. | Дерева і деревовидних | Матричні уявлення мереж | Постановка задачі | Алгоритм рішення (алгоритм Дейкстри) | приклад рішення | Приклади економічних задач, що зводяться до задачі про найкоротшою ланцюга | Алгоритм рішення (алгоритм Літтла) |

загрузка...
© um.co.ua - учбові матеріали та реферати