Розділ 2. Основи математичного моделювання ремонтно-консерваційних операції
Робота бригад, що підтримують рух у багатьох підрозділах на шахті кам'яного вугілля (ШКВ), характеризується просторовим розподілом місць реалізації завдань спеціалістами. Кожне завдання складається з операції транспортування і технологічної операції. Операція транспортування виникає з того факту, що оператор мусить дійти до відділу, в якому має виконати вказане завдання. Натомість технологічна операція - це об'єднання робіт, які виконуються оператором, ціллю якого є реалізація визначеного завдання. Операція транспортування і технологічна операція мають визначений нормований час на виконання. Не враховуючи обмежень, які є наявними в практиці, управління працею однієї бригади у багатьох виробничих відділах можна звести до так званої проблеми багатьох комівояжерів.
2.1. Комплекс операцій як об'єкт дослідження
Комівояжер має справи в N місцях. Відомі відстані між усіма місцями. Також відоме початкове розміщення комівояжера (наприклад місце під номером 0). Тепер можна поставити запитання: якою дорогою повинен поїхати комівояжер, щоб повернувшись до місця з номером 0 проїхати найменшу відстань. Під фразою "якою дорогою" ми маємо на увазі порядок місць, які відвідує комівояжер для завершення своїх справ.
Під відстанню між місцями розуміємо відстань в кілометрах, тривалість подорожі між цими місцями або кошти на подорож. В останньому випадку, визначення оптимальної траси полягає в зведенні до мінімуму усіх коштів на подорож. Таким чином можемо шукати найкоротшу, найшвидшу або найдешевшу трасу. Припустимо при цьому, що відстань між будь-якими двома місцями не є більшою за довжину будь-якого шляху, що поєднує ці ж місця, але проходить через інші місця. Це припущення лише здається таким, що завжди справджується.
Побудуємо зважений граф, вершинами якого є місця. Кожну пару місць поєднаємо дугами. Кожній дузі надаємо вагу, яка дорівнює відстані між місцями, що відповідають вершинам, які в свою чергу є краями цієї дуги. В такий спосіб отримуємо повний граф, який має стільки вершин, скільки місць має відвідати комівояжер (враховуємо і те місце, з якого комівояжер розпочав подорож). Відвідини усіх місць відповідають циклу, який проходить через кожну вершину даного графа лише раз. Такий цикл називається циклом Гамільтона. В повному графі шукаємо цикл Гамільтона з мінімальною сумою дуг. Довільний повний граф містить щонайменше один цикл Гамільтона. Так як граф має скінчену кількість вершин, то в сукупності циклів Гамільтона існує такий (не завжди один), що містить мінімальну суму ваг дуг.
Існує багато алгоритмів розв'язування цього завдання. Усі мають один основний недолік. Вони вимагають аналізу дуже великої кількості випадків, а також час їх виконання може бути дуже довгим. Невеликий приріст кількості місць тягне за собою відносно великий ріст кількості випадків для розв'язання і, тим самим, довший час на роботу алгоритму. Один з можливих алгоритмів полягає в обчисленні цілої довжини усіх циклів Гамільтона, які існують в даному графі. Однак, це дуже складно виконати вже при кількості місць трохи більшій за п'ять. Наприклад, для 20 місць кількість циклів Гамільтона в повному графі з 20 вершинами складає 19!/2 циклів, тобто близько 6 млн.
Час розв'язання проблеми комівояжера можна зменшити застосовуючи один із відомих наближених алгоритмів, які не вимагають розв'язку аж такої великої кількості випадків. Але такі алгоритми не завжди знаходять оптимальні розв'язки. Створена ними траса може бути значно довшою від найкоротшої. Використання наближених алгоритмів пов'язане з необхідністю вибору поміж швидкістю знаходження і якістю знайденого розв'язку. Як правило, приймається, що результат роботи такого алгоритму не може бути гіршим за оптимальний не більш ніж на певну встановлену величину.
За таких припущень, можна побачити аналогію між комівояжером і оператором бригади підтримки руху на шахті. Переміщення комівояжера відповідає переміщенню оператора між виробничими відділами. Час, що необхідний для завершення справ комівояжера, відповідає часу на виконання технологічної операції оператора бригади підтримки руху. Комівояжер повинен вибрати таку дорогу, щоб з найменшим часом повернутися до місця, з якого розпочав поїздку. Аналогічно, оператор бригади підтримки руху повинен пройти почергово через відділи, щоб з найменшим часом повернутися на поверхню.
Вказування на аналогію проблеми комівояжера і оператора бригади підтримки руху має істотне методичне значення. Проблема комівояжера є науково складною проблемою - стосовно розрахунків для великих N. Звідси робимо висновок, що управління бригадами підтримки руху мусить базуватись на комп'ютерному моделюванні і обчисленнях.
Представлені розв'язки можна розширити на багатьох комівояжерів. Така проблема багатьох комівояжерів полягає в тому, що M комівояжерів одночасно вирушають з місця з номером 0 і проїжджають через N місць. В кожному місці залагоджує справи лише один комівояжер. Після завершення всіх справ кожен комівояжер повертається до місця з номером 0. Завдання полягає у знайденні такої дороги для кожного комівояжера, щоб останній з них повернувся до місця з номером 0 якнайшвидше.
Оскільки кількість можливих варіантів доріг для комівояжерів (навіть для одного) є дуже великою, проблема багатьох комівояжерів є ще більш складною. Таким чином, управління бригадою підтримки руху на шахті кам'яного вугілля є складною проблемою. Для її вирішення належить розробити відповідний алгоритм, для використання в комп'ютерних обчисленнях.
Якщо потрібно, щоб останній комівояжер повернувся до місця з номером 0 перед закінченням визначеного часу, то необхідно розв'язати проблему багаторазово, для різної кількості комівояжерів. Таким чином, можна визначити мінімальну кількість комівояжерів M, необхідних для вирішення справ перед закінченням певного терміну. Аналогічно до цієї ситуації можна визначити мінімальну кількість операторів бригад