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

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

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

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

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

Таблиця 2.1

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

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

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

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

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

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

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

Таблиця 2.2

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

Таблиця 2.3

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

Для приведення матриці по стовпцях у кожному стовпці табл. 2.2 знаходиться мінімальний елемент (константи приведення по стовпцях). Ці мінімальні елементи записуються під матрицею. Вони віднімаються з елементів відповідних стовпців (табл. 2.3 – приведення матриці по стовпцях).

Матриця, яка приведена по рядках і стовпцях, показана в табл. 2.4.

Таблиця 2.4

Матриця В, приведена по рядках і стовпцях

Сума констант приведення складе:

.

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

Етап 2. Організація процесу розгалуження.

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

,

,

,

,

,

,

,

.

Приведена матриця В із зазначеними для елементів представлена в табл. 2.5.

Таблиця 2.5

Приведена матриця В із зазначеними

Розгалуження повинне здійснюватися по дугах , що мають найбільше значення в приведеній матриці В (табл. 2.5).

Найбільші значення мають і . Для розгалуження можна використати як дугу (4,5), так і дугу (5,4). Скористаємося дугою (4,5). Позначимо всі варіанти, що включають у маршрут дугу 4,5 через (4,5), а варіанти, що не включають дугу 4,5 через . Перший етап розгалуження показаний на рис. 2.1.

Рис. 2.1. Перший етап розгалуження

На рис. 2.1 початковій вершині (вона позначена «Усі цикли») відповідає оцінка «29», яка отримана як сума констант приведення – , що визначає нижню границю, тобто мінімальне значення можливих витрат по циклу.

Виберемо цикли, що включають гілку (4,5). Нижня границя варіанта, що виключає використання дуги (4,5) (ліва гілка дерева) визначається як сума нижньої границі всіх циклів плюс : 29+3=32. Рядок 4 і стовпець 5 матриці (табл. 2.5) викреслюються (табл. 2.6). Не викреслені рядки і стовпці утворять нову матрицю, у якій у клітці (5,4) варто поставити «∞», тому що включення дуги (4,5) у маршрут виключає використання в маршруті дуги (5,4). Нова матриця показана в табл. 2.7. Відзначимо, що при викреслюванні рядків і стовпців нумерація рядків і стовпців, що залишилися, зберігається колишньою.

Таблиця 2.6

Процес виключення рядків

Пункти початку руху	Пункти кінця руху
	∞				2
		∞
			∞
4				∞
					∞

Після одержання розгалуження й відповідного перетворення матриці В знову виконуються етап 1 - одержання нової приведеної матриці В, і етап 2 - організація процесу розгалуження.

Етапи 1 й 2 повторюються до одержання рішення завдання - побудови оптимального кільцевого маршруту.

Для приведення нової матриці визначаються константи приведення по рядках (цифри з правої сторони матриці, табл. 2.7).

Таблиця 2.7

Приведена матриця з константами

Матриця, після її приведення по рядках, показана в табл. 2.8.

Таблиця 2.8

Матриця, після її приведення по рядках

Кожен стовпець матриці містить не менш одного нуля. Це виключає необхідність приведення матриці по стовпцях. Сума констант приведення . Нижня границя варіанта, що включає дугу (4,5) (права гілка дерева), визначається як сума нижньої границі всіх циклів плюс (див. рис. 2.1). Для наступного розгалуження дерева по правій гілці визначається для нової приведеної матриці (табл. 2.8):

,

,

,

,

,

,

,

,

.

Максимальне значення має . Рядок 1 і стовпець 3 в матриці викреслюються (табл. 2.9).

Таблиця 2.9

Нова приведена матриця

Пункти початку руху	Пункти кінця руху
1	∞		0
		∞
			∞
				∞

Дуга (1,3) включається в маршрут, що виключає використання дуги (3,1). У клітку (3,1) записується (табл. 2.10).

Таблиця 2.10

Нова приведена матриця

Наступне розгалуження правої частини дерева з використанням дуги (1,3) показане на рис. 2.2.

Помітимо, що при оцінці циклів, що включають дугу (1,3) треба до попередньої оцінки (32) додати суму констант приведення ().

При оцінці циклів, що не включають дугу (), до попередньої оцінки (32) додається (2).

Рис. 2.2. Останнє розгалуження правої частини дерева

Як видно з табл. 2.10, сума констант приведення дорівнює 0 (). Нижня границя варіантів з використанням дуги (1,3) дорівнює 32+0=32, а нижня границя варіантів, що виключають дугу (1,3), дорівнює 34.

Отже, подальше розгалуження варто проводити по правій частині дерева.

Отримана матриця (табл. 2.10) не має потреби в приведенні, тому що в кожному рядку й кожному стовпці є не менш одного нуля.

Сума констант приведення дорівнює нулю.

Значення нової матриці показані в табл. 2.11.

Наступне розгалуження приводить до варіантів, що включають дугу (3,1) (мал. 2.3). Включення дуги (3,1) виключає використання дуги (1,3). У новій матриці (табл. 2.11) у клітці (1,3) проставляється «∞».

Таблиця 2.11

Матриця, після виключення дуги (1,3)

Максимальне значення мають , тобто розгалуження можна здійснювати по дузі (2,4) або по дузі (5,1). Виберемо дугу (2,4).

Нове розгалуження по дугам (2,4) і () з оцінкою циклів представлене на рис. 2.3.

Рис. 2.3. Наступне розгалуження правої частини дерева

Викреслимо рядок 2 і стовпець 4 з матриці В. Одержуємо табл. 2.12.

Таблиця 2.12

Матриця, після виключення гілки (2,4)

Сума константи приведення для цієї матриці дорівнює 0.

Розраховані значення показані в правому верхньому куті матриці.

Як бачимо, розгалуження повинне здійснюватися або по дузі (3,2), або по дузі (5,1). Цей крок є останнім, тому здійснюється вибір одночасно двох дуг – (3,2) і (5,1). Виконаємо оцінку отриманого результату (рис. 2.4).

Рис. 2.4. Останнє розгалуження

Як бачимо, відповідно до рішення (рис. 2.4) у цикл увійшли наступні дуги: (1,3), (2,4), (3,2), (5,1). Оцінка циклу – 32 од.

Побудуємо отриманий цикл (рис. 2.5) і з використанням вихідної матриці В (табл. 2.1) одержимо сумарне значення часу Т (відстані L) переміщення по дугах циклу:

Т (L) = 12+2+4+4+10 = 32.

Рис. 2.5. Оптимальний маршрут (цикл)

Таким чином, отримане значення Т (L) = 32 од. відповідає оптимальному рішенню (32 од.), отриманому методом «гілок і границь».

Відзначимо, що у випадку, коли на якомусь із кроків розгалуження оцінка циклу виявляється вище, ніж та, котра відповідала напрямку розгалуження, виключеному як безперспективне на попередніх кроках, здійснюється повернення до цього напрямку. Наприклад, нехай на рис. 2.4 на розгалуженні по дузі (2,4) отримана оцінка не 32 од., а 33 од. Тоді цей напрямок пошуку не продовжується, а здійснюється повернення на крок, де здійснюється розгалуження по напрямку з оцінкою 32 од. (оскільки ця оцінка менше, ніж 33 од.).

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

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

Завдання № 3

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

Мета роботи: визначення показників роботи системи обслуговування (відновлення роботи обладнання, яке потребує ремонту) як системи масового обслуговування, визначення параметрів системи аварійного відновлення.

Таблиця 3.1

Вихідні дані

Остання цифра № студентського квитка
Число одиниць устаткування,
Число каналів обслуговування,
Передостання цифра № студентського квитка
Інтенсивність відмов, , 1/год	0,03	0,04	0,07	0,02	0,06	0,04	0,05	0,03	0,04	0,05
Інтенсивність відновлення, , 1/год	0,06	0,09	0,18	0,05	0,15	0,1	0,13	0,07	0,12	0,2

Поиск по сайту: