 |
Метод розгалужень і меж
|
|
|
|
Цей метод ґрунтується на твердженні, що оптимальний план задачі про кільцевий маршрут з початковою матрицею збігається з оптимальним планом задачі для повністю зведеної матриці.
Розв’язування задачі методом розгалужень і меж здійснюється у такій послідовності (блок-схема показана на рис. 7.5).
1. Знаходження повністю зведеної матриці. Для цього у кожному і -му рядку початкової матриці 
вибирається мінімальний елемент 
і знаходяться нові значення
,
потім у одержаній матриці вибирається мінімальний елемент у кожній 
-й колонці і знаходяться нові значення
.
Наслідком такого перетворення є повністю зведена матриця , в якій у кожній -й колонці та кожному і -му рядку є хоча б один нульовий елемент. Для цієї матриці знаходиться величина
,
яка є нижньою межею значення цільової функції усіх допустимих варіантів кільцевих маршрутів.
2. Побудова напрямків, які належить оцінити згідно із значенням нижньої межі цільової функції. З цією метою для кожного елемента 
 |
ні
ні
так
|
- дуг
з
|
 | |||
 | |||
Рис.7.5
знаходиться його оцінка
,
не враховуючи елемент , для якого знаходиться оцінка; величина цієї оцінки дорівнює сумі мінімального елемента з і -го рядка та мінімального елемента з -ї колонки. З усіх знайдених 
вибирається максимальне, яке вказує на 
-дугу, що повинна подалі розглядатися у процесі побудови послідовності 
кільцевого маршруту.
Вибрана -дуга включається до дерева-графа за двома напрямками (рис.7.6).
─ 
входить до послідовності ;
─ 
не повинна входити до послідовності (позначається як 
).
|
|
|
Рис.7.6
3. Знаходження оцінки межі 
усіх допустимих кільцевих маршрутів з включенням - дуги наступним чином.
У повністю зведеній матриці виключається і –й рядок та -а колонка, потім в одержаній таким чином матриці один з елементів прирівнюється до М: цей елемент має виключати локальні цикли при подальшому конструюванні послідовності . Наприклад, при т = 5 та частковій послідовності 
треба виключити дугу (31), тобто 
.
Одержана матриця знову перетворюється на повністю зведену матрицю, потім знаходиться оцінка -дуги:
Нижня межа оцінки цільової функції для всіх послідовностей з включенням -дуги дорівнює
.
Величина а записується до вершини -дуги дерева-графа послідовності. Матриця 
, яка одержана після цих перетворень знову готова для подальшого розвитку послідовності з -тою дугою, починаючи з п.2.
4. Знаходження оцінки нижньої межі 
усіх допустимих кільцевих маршрутів без включення -ї дуги виконується наступним чином.
У повністю зведеній матриці , знайденої за п.2, проводиться заборона елемента 
для вибраної -дуги. Потім така матриця перетворюється на повністю зведену і знаходиться оцінка
.
Нижня межа оцінки цільової функції для усіх послідовностей без -ї дуги дорівнює
.
Величина записується до вершини -дуги дерева-графа послідовності. Матриця після таких перетворень знову готова для подальшого розвитку послідовності без -дуги, починаючи з п.2.
5. Знаходження подальшого розвитку знайдених послідовностей . Якщо 
, то подальший розвиток ведеться з матриці , одержаної у п.3. Якщо 
, - то з матриці з п.4.
Процес побудови напрямків ведеться до моменту, коли матриця стане розміром (2х2).
6. Складання усіх -дуг у неперервну послідовність, яка відображує кільцевий маршрут.
Для цього з матриці (2х2) вибираються дві дуги, для яких , потім цими дугами доповнюється одержана послідовність 
.
Починаючи з будь-якої дуги послідовності формується кільцевий маршрут.
|
|
|
Загальний вид дерева-графа зображений на рис.7.7.
а а а
(), ()
Рис. 7.7
Приклад
Згідно з початковою матрицею знайти кільцевий маршрут постачання готової продукції від заводу до трьох баз призначення з мінімізацією загальної відстані пробігу автотранспорту.
Завод, який постачає готову продукцію, відображується у матриці першою точкою.
Початкова матриця має вигляд:
| Х | ||||
| Х | ||||
| Х | ||||
| Х |
Процес розв’язування задачі такий.
По кожному рядку знаходимо 
та перетворюємо початкову матрицю на матрицю, зведену за рядками: 
. Потім по кожній колонці знаходимо 
і перетворюємо знайдену матрицю на повністю зведену: 
. Така матриця має наступний вигляд:
 3
| ||||
| Х | 04 | |||
| Х | 0 
| 0 
| ||
0 
| Х | |||
| 0
| 0
| Х |
Початкове значення нижньої межі усіх кільцевих маршрутів дорівнює
.
Для кожного нульового елемента цієї матриці знаходимо його оцінку (не враховуючи самого нульового елемента):
Вибір максимальної оцінки 
(можна вибрати і 
, яка показує на варіант розгляду двох напрямків дерева-графа з дугою (13) (рис. 7.8).
92
 |
Рис.7.8
Для наочності процесу розв’язування наведемо кінцевий дерево-граф прикладу (рис. 7.9).
|
92 96 96
98
|
96 96 96
 |  |  | |||||||
 |  |
100 98
Рис.7.9
Згідно з вибором дуги (13) з матриці виключається перший рядок та третя колонка, елемент , тому що він може подалі дати частковий кільцевий маршрут. Така матриця має вигляд:
| Х | |||
| Х | |||
| Х |
Потім цю матрицю перетворюємо на повністю зведену: 
:
 1
| |||
| 02 | Х | 00 | |
| Х | 00 | 00 | |
| 02 | Х |
Знаходимо нижню межу маршрутів з включенням дуги (13):
Згідно з одержаною матрицею знаходимо оцінки для кожного нульового елемента
і вибираємо за максимальною величиною дугу (21), яка включається до складу послідовності 
Потім виключається другий рядок та перша колонка, тобто 
, тому що набір послідовності 
з дугою (32) може дати надалі частковий кільцевий маршрут. Така матриця має вигляд:
|
|
|
| Х | ||
| Х |
Одержана матриця має розмір (2х2). Таким чином, послідовність доповнюється дугами (34) та (42), а оцінка нижньої межі не змінюється, тому що ця матриця є повністю зведеною.
Отже, 
та 
.
З набору знайдених дуг послідовності 
будується кільцевий маршрут 
, який має значення цільової функції 
= 96.
Другий розвиток знаходження варіантів розв’язку задачі виконуємо тоді, коли дуга (13) не увійшла до послідовності .
Для цього у відповідній матриці змінюємо 
та перетворюємо її до повністю зведеної:
| Х | Х | |||
| Х | ||||
| Х | ||||
| Х |
| Х | Х | |||
| Х | ||||
| Х | ||||
| Х |
Таким чином, цей напрямок пошуку рівноцінний з першим напрямком пошуку; тому, щоб знайти інші варіанти розв’язку, доцільно також розглянути і цей напрямок.
Знаходяться оцінки нульових елементів:
Отже, вибирається дуга (31), а , та виключаються третій рядок і перша колонка. Така матриця має вигляд:
| Х | |||
| Х | |||
| Х |
Зрозуміло, що таку послідовність треба розглядати подалі.
З цієї матриці знаходимо
та по послідовності 
включаємо дугу (І2).
Потім виключаємо перший рядок та другу колонку 
, тому що послідовність має вигляд (312). Така матриця має вигляд:
| Х | ||
| Х |
Ця матриця повністю зведена, 
і має розмір (2Х2). До включаються дуги (24) та (43) і будується кільцевий маршрут 
Третій напрямок пошуку є з дугою (
), для якої будується наступна матриця:
| Х | Х | ||
| Х | |||
| Х |
Одержана матриця перетворюється на повністю зведену і знаходиться нижня межа оцінки
.
Цей напрямок має вищу оцінку, тому подалі він не розглядається.
Перевіряємо інші напрямки пошуку.
|
|
|
Напрямок 3 (
) має наступну матрицю:
| Х | Х | |||
| Х | ||||
| Х | Х | |||
| Х |
Цей напрямок також має вищу оцінку: 
Тому подалі він не розглядається.
Перевіримо напрямок з (13) (
), для якого маємо наступну матрицю:
| Х | Х | ||
| Х | |||
| Х |
Для цього напрямку 
і цей напрямок також подалі не розглядається.
Висновки
1. Згідно з особливостями цілочислових задач розроблено спеціальні методи їх розв’язування, включаючи методи відтинання та комбінаторні методи.
2. Алгоритм Гоморі можна використовувати для розв’язування як частково цілочислових (1-й алгоритм), так і повністю цілочислових лінійних задач (2-й алгоритм).
3. Задача про призначення є частковим випадком Т – задачі, тому іноді її можна розв’язувати як транспортну задачу.
4. Алгоритм угорського методу можна використовувати для розв’язування задач з бульовими змінними.
5. Метод розгалужень і меж є методом покрокового конструювання розв’язування задач з бульовими змінними.
Контрольні запитання
1. Який зміст економічних явищ з цілочисловими змінними?
2. Наведіть конкретні прикладні задачі, що належать до
─ лінійних цілочислових задач;
─ задач про призначення;
─ задач про кільцевий маршрут.
3. Як будується додаткове обмеження у першому алгоритмі Гоморі?
4. Чи можливо, щоб елементи 
були від’ємні при використанні угорського методу?
5. Чому задачу про призначення можна розв’язувати методом потенціалів?
6. Яка принципова різниця задач про призначення та про кільцевий маршрут?
7. У чому основна ідея угорського методу?
8. Що таке повністю зведена матриця?
9. Які основні етапи методу розгалужень і меж?
|
|
|
