Завдання № 2

Завдання розраховано на виконання протягом двох практичних занять – 4 години.

Мета роботи: визначення оптимальних кільцевих маршрутів об’їзду пунктів, з яких поступили заявки на надання певного виду послуг. Визначення оптимального кільцевого маршруту, який забезпечить мінімізацію витрат на надання послуг.

Вихідні дані представлені в додатку 1 за 10 варіантами. Номер варіанту вибирається по останній цифрі студентського квитка чи задається викладачем.

Методичні вказівки до рішення завдання № 2 Побудова кільцевих маршрутів

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

Труднощі вибору оптимального кільцевого маршруту випливають із необхідності перебору великої кількості можливих варіантів (рішень). Так, наприклад, для об'їзду 6 пунктів може бути побудовано 120 різних варіантів кільцевих маршрутів. Якщо кількість пунктів, включених у маршрут, буде дорівнювати 10, то число можливих варіантів збільшиться до 362 880. У загальному виді число можливих варіантів побудови кільцевих маршрутів складе (n - 1)!, де n – число пунктів у маршруті.

Завдання подібного типу відомі в літературі як завдання "комівояжера". У цей час відомо кілька способів їхнього вирішення.

Побудова кільцевого маршруту за допомогою методу «гілок і границь»

Розглянутий метод, запропонований американськими математиками Дж. Літлом, К. Мурті, Д. Суіні й К. Керелом, є найбільш зручним способом побудови оптимального кільцевого маршруту. Метод полягає в тому, що вся безліч припустимих рішень завдання розбивається на послідовно зменшувані підмножини за допомогою процедури розгалуження. У результаті знаходиться послідовність об'їзду пунктів (маршрут), довжина якого менше будь-якого іншого можливого варіанта. Цей кільцевий маршрут вважається оптимальним. Під «довжиною» будемо розуміти той показник, за яким формується критерій оптимальності – власне довжину маршруту, час об’їзду маршруту, витрати на об’їзд маршруту тощо. В даному завданні під довжиною будемо розуміти час руху між підпунктами.

Послідовність рішення завдання за допомогою цього методу розглянемо на конкретному прикладі.

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

У ряді випадків витрати часу на рух між тими самими об'єктами в прямому й зворотному напрямках можуть бути неоднакові. Це можна пояснити особливостями рельєфу місцевості й іншими конкретними умовами. У нашому випадку ми будемо зневажати такими умовами й витрати часу на рух між тими самими об'єктами в прямому й зворотному напрямках будемо вважати однаковими. Вихідні дані будуть представлені в матриці (табл. 2.1). Приймемо число об'єктів (пунктів обходу n = 5). Позначимо матрицю вихідних даних В.

Таблиця 2.1

Матриця В – Вихідні дані

Пункти початку руху	Пункти кінця руху
	1	2	3	4	5
1	∞	13	10	13	12
2	13	∞	4	4	6
3	10	4	∞	3	5
4	13	4	3	∞	2
5	12	6	5	2	∞

Матриця В має квадратну форму. Кількість рядків і стовпців дорівнює 5 (по кількості об'єктів). Кожний рядок визначає пункти початку руху, а кожний стовпець – пункти кінця руху. У клітках матриці записуються витрати часу на рух між пунктами. Так, наприклад, витрати часу на рух від пункту 1 до пункту 5 становить 12 од. Ця величина записується в клітці першого рядка п'ятого стовпця матриці. Як ми вже відзначали, ці величини можуть позначати й відстань між пунктами (наприклад, у кілометрах).

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

Обчислювальні операції по методу «гілок і границь» включають наступні етапи.

Етап 1. Одержання приведеної матриці («приведення» вихідної матриці В).

Для приведення матриці В виконуються операції приведення по рядках і стовпцям.

Для приведення по рядках у кожному рядку вибирається мінімальний елемент. У першому рядку мінімальним елементом буде 10, у другому – 4, у третьому – 3, у четвертому – 2 й у п'ятому – 2. Ці мінімальні елементи (константи приведення) зручно записати з правого боку матриці. Константи приведення віднімаються від елементів відповідних рядків (табл. 2.2). У табл. 2.2 надано приведення вихідної матриці по рядках.

Таблиця 2.2

Приведення вихідної матриці В по рядках

Пункти початку руху	Пункти кінця руху
	1	2	3	4	5
1	∞	13 3	10 0	13 3	12 2	10
2	13 9	∞	4 0	4 0	6 2	4
3	10 7	4 1	∞	3 0	5 2	3
4	13 11	4 2	3 1	∞	2 0	2
5	12 10	6 4	5 3	2 0	∞	2

Таблиця 2.3