Материал: 62_201
приведення по стовпцях дорівнює 4. Сумарна вартість приве дення заданої таблиці С по рядках і стовпцях становить 11. Це значення означає, що ми зменшили загальну вартість призна чення кандидатів на посади па 11, тому після одержання оста точного результату необхідно буде це значення додати.
Оскільки найбільші шанси на включення до результуючого призначення на вакантні посади мають у першу чергу ті канди дати, що принесуть найменшу шкоду, то розглянемо в таблиці елементи зі значеннями 0. Побудуємо дводольний граф, що складається лише з нульових ребер (мал. 115, а). Максимальна кількість призначень з нульовим коефіцієнтом шкідливості в задачі, до якої звелася задача про призначення, є аналогічною до побудови максимального паросполучення в отриманому дво дольному графі. Таке максимальне паросполучення зображене на малюнку 115,6.
Максимальне паросполучення на нульових ребрах можна побудувати із застосуванням алгоритму, який розглядався раніше в розділі «Основи теорії графів». Нагадаємо, що для ре алізації цього алгоритму необхідне використання двох маси вів: один містить опис наявності ребер між усіма вершинами графа, значеннями елементів якого є 0 і 1; другий - опис поточ ного стану включених до паросполучення прямих і відповідних їм зворотних ребер, значеннями елементів якого є - 1, 0, 1.
Для зручності наступних перетворень введемо додаткову інформацію у вигляді двох одновимірних масивів mark_n- (у = 1, 2, ..., т) і mark_mi (і = 1, 2, ..., п). У першому зберігатиме мо номер рядка і таблиці С, де знаходиться вибраний нами нульовий елемент ctp а в другому - номер стовпця j. Також бу демо запам'ятовувати сумарний коефіцієнт приведення табли ці L (правий нижній кут таблиці), на який було зменшено зна чення її елементів, а одночасно і сумарного значення шкідли вості призначення кандидатів на посади (мал. 116).
У результаті побудови максимального паросполучення на нульових ребрах визначимо нульові елементи таблиці с.. = 0*, що їм відповідають. Розміщення елементів си - 0* відповідає
7* |
195 |
розміщенню елементів xtj = 1, що визначені у класичному фор мулюванні задачі лінійного програмування про призначення.
Результат зробленого призначення відображений на малюн ку 116 у масивах markn і mark_m. Із вмісту цих масивів можна зробити висновок, що у максимальне паросполучення не ввійшли вершини 2 і 4'. Це саме ми спостерігаємо і на малюнку 115,6.
п |
\ |
1 |
2 |
3 |
4 |
5 |
marhjn |
1 |
|
2 |
2 |
6 |
4 |
0* |
5 |
2 |
|
5 |
6 |
8 |
4 |
0 |
0 |
3 |
|
0* |
5 |
1 |
0 |
1 |
1 |
4 |
|
1 |
3 |
0* |
0 |
3 |
3 |
5 |
|
1 |
0* |
7 |
6 |
0 |
2 |
markn |
|
3 |
5 |
4 |
0 |
1 |
L=ll |
Мал. 116
Вершини, які не беруть участі у паросполученні, називають ненасиченими, а решту - насиченими. Тож бачимо, що побудова не максимальне паросполучення (мал. 115,6) залишає ненасиче ними у верхній групі вершин (кандидати) одну вершину 2 і в нижній групі (посади) одну вершину 4'. Ненасичені вершини в дводольному графі на малюнку 115,6 виділено сірим кольором.
Ми не отримали повноцінної відповіді. Невже це остаточний результат? Мабуть, ні, оскільки не включено до розгляду велику кількість інших варіантів призначень. У таблиці, зображеній на малюнку 116, ще є достатня кількість призначень з низьким ко ефіцієнтом шкідливості. Для включення цих перспективних призначень необхідно збільшити кількість ребер у дводольному графі. Це дасть змогу збільшити і максимальне паросполучення. Для цього проведемо подальші перетворення таблиці.
Розглянемо елемент таблиці с2 5 . Він відповідає нульовому реб ру (2,5') у дводольному графі, яке не було включене до пароспо лучення. Цьому завадило вже на той час включене ребро (1,5'). Будемо казати, що насичена вершина 1 (вона ввійшла до паро сполучення) досяжна з ненасиченої вершини 2, яка не ввійшла до паросполучення, оскільки існує послідовність ребер (2,5') і (5',1), що дає змогу потрапити з вершини 2 у вершину 1. Слід зауважи ти також, що в цій послідовності ребер завжди чергуються ребра, які ввійшли до паросполучення з тими, що не ввійшли.
Можна припустити, що, включивши до розгляду інші «де шеві» ребра, що виходять з вершини 1, і замінивши одним з них ребро (1,5'), ми б змогли включити в паросполучення ребро (2,5'). Як бачимо з таблиці (мал. 115), такі ребра з «вагою» 2 є (1,1') і (1,2'). Але ми домовилися включати до паросполучення
196
ребра з нульовими значеннями. Тому виконаємо таку опера цію: від усіх значень елементів рядка з номером 1 віднімемо значення найменшого ненульового елемента. В результаті у нас з'являться нові нульові ребра, що виходитимуть з вершини 1, і з'явиться змога включити їх до розгляду. Разом з тим нульові елементи цього рядка, а в ньому є як мінімум один такий нульовий елемент (с2 5 = 0), перетворяться на від'ємне число. Оскільки ми розв'язуємо задачі лінійного програмування лише в області невід'ємних чисел, а також не можемо відкидати вже отримані нульові ребра, то необхідно в тих стовпцях таблиці, де c^ = 0, додати те саме мінімальне значення. Для нашого ви падку таким стовпцем є стовпець з номером 5.
Описана операція носить назву перетворення Егерварі. Обґрунтування її справедливості буде таким. Ми вже скориста лися тією властивістю задачі про призначення, що при змен шенні кожного рядка і стовпця таблиці на деякі числа резуль тат її розв'язання залишається таким самим, як і в початковій задачі. Ця властивість може бути застосована і в разі додаван ня деякого числа (або віднімання деякого від'ємного числа). Чи зміниться при цьому вартість остаточного призначення? Ні, оскільки на вже присутніх у паросполученнях ребрах вартість залишилася нульовою: ми спочатку відняли одне і те саме чис ло, а потім його додали. Тому на даному етапі поточна вартість призначення залишається без змін L = 11.
Проведемо описане вище перетворення на таблиці, зобра женій на малюнку 116. У масиві markjrn визначимо елементи зі значенням 0, що вказують на ненасичені вершини, тобто не задіяні у паросполученні. У нашому прикладі таким рядком є рядок з номером 2. Визначаємо позицію / першого нульового елемента в цьому рядку: j = 5. У масиві mark_n на п'ятій позиції знаходиться число 1, що вказує на номер рядка, який необхідно перетворювати. У нашому прикладі мінімальним ненульовим елементом у рядку 1 є число 2. Віднімемо його від ненульових елементів цього рядка. Від нульового елемента відні мати немає сенсу, оскільки потім до нього це число знову буде додаватися, і переходити при цьому в область від'ємних чисел також немає сенсу (мал. 117, а).
Тепер до стовпця 5, інформація про який знаходиться у mark_m1 (розглядається рядок з номером 1), додаємо число 2. Насправді додамо до всіх елементів, окрім с1 5 (мал. 117, б). Як бачимо, до старих нульових елементів додалися нові і це дає змогу поновити наші пошуки повноцінного призначення.
Однак отримано таблицю, у якій не у всіх рядках є хоча б по одному нульовому значенню: у рядку 2 всі елементи ненульові. Проблеми немає, приведемо отриману таблицю по рядках і стовп цях (мал. 117, в) і почнемо побудову максимального паросполу-
197
чення спочатку. Для нашого прикладу приведення відбувається лише по рядку під номером 2, який відмічено сірим кольором, і його вартість становить 2 (мал. 117,6). Таким чином, на поточний момент сумарна вартість приведення початкової таблиці L = 13.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
|
X |
1 |
2 |
3 |
4 |
5 |
|
га\ |
1 |
2 |
3 |
4 |
5 |
1 |
0 |
0 |
4 |
2 |
о_2 |
|
1 |
0 |
0 |
4 |
2 |
0 |
|
1 |
0 |
0 |
4 |
2 |
0 |
2 |
5 |
6 |
8 |
4 |
0 |
|
2 |
5 |
6 |
8 |
4 |
2 |
|
2 |
3 |
4 |
6 |
2 |
0 |
3 |
0 |
5 |
1 |
0 |
1 |
|
3 |
0 |
5 |
1 |
0 |
3 |
|
3 |
0 |
5 |
1 |
0 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
1 |
3 |
0 |
0 |
3 |
|
4 |
1 |
3 |
0 |
0 |
5 |
|
4 |
1 |
3 |
0 |
0 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
1 |
0 |
7 |
6 |
0 |
|
5 |
1 |
0 |
7 |
6 |
2 |
|
5 |
1 |
0 |
'7 |
6 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
а) |
|
|
|
|
|
|
б) |
Мал. 117 |
|
|
в) |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Приведення таблиці (мал. 117, в) зображено на малюнку 118, а. Нульовим елементам цієї таблиці відповідає граф, зображений на малюнку 118, б. Виконавши алгоритм побудови максималь ного паросполучення на цьому графі, отримаємо результат, зоб ражений на малюнку 118, в. Ця сама інформація відображена в масивах mark_n і mark_m на малюнку 118, а. Вміст цих масивів свідчить про те, що задача розв'язана і знайдене найменше за вартістю шкідливості (L = 13) призначення всіх кандидатів на вакантні посади, вартість якого позначена на кожному ребрі знайденого максимального паросполучення (мал. 118, в).
"\ |
т |
1 |
2 |
3 |
4 |
5 |
mark_m |
П |
^ \ |
|
|
|
|
|
|
|
1 |
0* |
0 |
4 |
2 |
0 |
1 |
|
2 |
3 |
4 |
6 |
2 |
0* |
5 |
|
3 |
0 |
5 |
1 |
0* |
3 |
4 |
|
4 |
1 |
3 |
0* |
0 |
5 |
3 |
|
5 |
1 |
0* |
7 |
6 |
2 |
2 |
markka |
1 |
5 |
4 |
3 |
2 |
L=13 |
|
|
|
|
|
|
|
|
|
а)
Варто детальніше розглянути умови завершення роботи ал горитму. У нашому прикладі все склалося ідеально: всі канди дати отримали запропоновані їм посади. Однак можливий і та-
198
кий випадок, коли всі кандидати претендують на одну і ту саму посаду. При цьому логічно призначити на неї того, хто най менш шкідливий, а решта кандидатів і посад залишаться віль ними. Тому обмежуватись ознакою завершення алгоритму, що гарантує зайнятість усіх кандидатів або всіх посад, не слід. Якою в цьому разі буде ознака завершеності алгоритму? Запро понуємо таку послідовність міркувань.
На кожній ітерації спочатку виконується приведення поточ ного стану таблиці коефіцієнтів шкідливості кандидатів на по сади. У разі появи в ній нових нульових елементів змінюється дводольний граф і може бути побудований новий варіант приз начення. А що може спровокувати зміни в цій таблиці? Тільки перетворення Егерварі, що виконується на її рядках та стовп цях. Тому можна підбити підсумок: умовою завершення алго ритму є відсутність результативного перетворення Егерварі в таблиці С.
Нарешті сформулюємо алгоритм визначення розв'язку за дачі про призначення у загальному вигляді.
1. Ввести початкові значення п, т елементів таблиці cij(i = 1, 2, ..., п; j = 1, 2, ..., т); визначити L = 0.
2.Привести таблицю С по рядках і стовпцях; сумарний ко ефіцієнт приведення додати до поточного значення L.
3.Побудувати максимальне паросполучення на нульових елементах таблиці С.
4. Визначити значення елементів масивів markn і markm.
5.З масиву mark_m визначити всі ненасичені вершини, що відповідають кандидатам на вакантні посади; з масиву markn визначити насичені вершини, які є досяжними з ненасичених вершин.
6.Виконати перетворення Егерварі в рядках і стовпцях, що відповідають визначеним досяжним вершинам.
7.Якщо перетворення Егерварі змінило поточний стан еле ментів таблиці С, то перейти до п. 2.
8.Завершити алгоритм.
Реалізуємо основну частину алгоритму у вигляді Pascalпрограми.
L := 0; nm := n + m; |
|
{Ініціалізація результату! роботи програми.} |
r e p e at |
|
{Організація ітерацій виконання алгоритму.} |
for І := 1 t o n d o mark_m[i] := 0; |
{Ініціалізація масиву тагкт.) |
|
for j := 1 to m do mark_n[j] := 0; |
{Ініціалізація масиву тагк_п.} |
|
reduce; |
{Приведення масиву С і обчислення L:=L + тіп.} |
|
maximummatching; {Побудова максимального паросполучення на нульових ребрах.}
for і :- 1 to nm do |
{Обробка масиву поточних призначень f.} |
for j := 1 to nm do |
|
if f A [ i , j] > 0 then |
{Якщо існує призначення, то занесення інформації} |
199