7.3.4. Задача про кільцевий маршрут

Зміст задачі про кільцевий маршрут: треба обійти т точок, у кожній з яких необхідно побувати тільки один раз; маршрут має бути кільцевим. Витрати на перехід від і-ї до -ї точки відомі і дорівнюють величинам . Знайти кільцевий маршрут з мінімальними сумарними витратами.

До цієї задачі можна звести задачі оптимального використання транспортних засобів (наприклад, бензозаправник, молокорозвізник та інше), знаходження послідовності обробки деталей верстатами, обробка замовлень агрегатами (чи цехами) з точки зору мінімізації простоїв агрегатів за причиною їх переналагодження та інші задачі повного обходу множини точок.

Якщо згідно з вимогами перехід від і-ї до -ї точки неможливий (тобто має місце заборона -зв’язку) то відповідне значення .

Математична модель задачі про кільцевий маршрут наступна:

• цільова функція

,

• о бмеження

– умова тільки одного входу та одного виходу з

точки;

– умова тільки двох станів змінних: 0 та 1;

– умова виключення петель з маршруту;

маршрут у вигляді замкнутого контуру.

За нашого часу найефективнішим методом розв’язування задачі є метод розгалужень і меж, який подалі розглядається.

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

Метод розгалужень і меж включає наступні етапи розв’язування:

• знаходження нижньої оцінки цільової функції для множини допустимих варіантів;

• складання можливих варіантів розгалужень пошуків кільцевих маршрутів;

• знаходження оцінок знайдених розгалужень маршрутів і вибір з них перспективного напрямку пошуку;

• складання продовження розгалуження перспективного напрямку допустимих варіантів;

• вибір оптимального варіанта кільцевого маршруту.

Вперше цей метод був застосований у 1960 р. до задач цілочислового програмування, у 1963 р. – відповідно до задачі кільцевого маршруту.

5. Метод розгалужень і меж

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

Розв’язування задачі методом розгалужень і меж здійснюється у такій послідовності (блок-схема показана на рис. 7.5).

1. Знаходження повністю зведеної матриці. Для цього у кожному і-му рядку початкової матриці вибирається мінімальний елемент і знаходяться нові значення

,

потім у одержаній матриці вибирається мінімальний елемент у кожній -й колонці і знаходяться нові значення

.

Наслідком такого перетворення є повністю зведена матриця , в якій у кожній -й колонці та кожному і-му рядку є хоча б один нульовий елемент. Для цієї матриці знаходиться величина

,

яка є нижньою межею значення цільової функції усіх допустимих варіантів кільцевих маршрутів.

2. Побудова напрямків, які належить оцінити згідно із значенням нижньої межі цільової функції. З цією метою для кожного елемента