Лекція 6. Алгоритм угорського методу для розв’язування задач про призначення

Постановка задачі. Нехай є робіт і робітників або пристроїв для виконання цих робіт. Задана матриця , де – рейтинг (міра корисності) -го робітника (пристрою) під час виконання -ї роботи.

Треба знайти множину ,

де величина

(6.1)

На величини накладаються умови:

(6.2)

(кожний працівник призначається тільки на одну роботу)

(6.3)

(на кожну роботу призначається тільки один працівник).

Цільова функція: максимізувати величину :

.

(6.4)

Задача про призначення є частинним випадком як загальної ЗЛП, так і транспортної задачі. Умови (6.1) показують, що ця задача належить до класу бульових ЗЛП.

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

Опишемо цей метод.

Спочатку матриця підлягає двом перетворенням.

1. У кожному стовпчику знаходимо максимальний елемент. Нові значення елементів матриці дорівнюють різниці між максимальним і поточним значеннями елементів

.

(6.5)

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

2. Від усіх елементів кожного рядка віднімаємо найменший елемент рядка:

.

(6.6)

Тепер у кожному рядку теж з’явиться принаймні один нуль.

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

Умови (6.2) і (6.3) виконуються, якщо буде вибрана множина з n нулів так, щоб у кожному рядку і кожному стовпчику знаходився рівно один нуль.

Опишемо алгоритм задачі про призначення.

1. Здійснимо перетворення матриці у , як показано вище згідно з формулами (6.5) і (6.6).

2. Позначимо зірочкою (*) будь-який нуль у першому стовпчику; позначимо у другому стовпчику зірочкою будь-який нуль, який не лежить у рядку з попереднім ; продовжуємо цей процес так, щоб у жодному рядку не було більше одного . Переходимо до п. 3.

3. Підраховуємо кількість . Якщо вона дорівнює , процес закінчено; переходимо до п. 10, інакше переходимо до п. 4.

4. Позначимо знаком „V” зверху стовпчики, в яких є , і вважаємо ці стовпчики зайнятими. У ході процесу з’являться також і зайняті рядки.

Означення. Елементи, що знаходяться на перетині незайнятих рядка і стовпчика, назвемо незайнятими, решту – зайнятими.

Переходимо до п. 5.

5. Знаходимо незайняті нулі. Якщо вони є, переходимо до п. 6, якщо немає – до п. 9.

6. Вибираємо перший із незайнятих нулів, перебираючи рядки зліва направо. Позначимо його штрихом (`). Якщо в його рядку немає , то переходимо до п.8, а якщо є, переходимо до п. 7.

7. Знімаємо знак „ ” (позначаємо „ ”) і вважаємо знову незайнятим стовпчик, у якому знаходиться , що лежить у тому самому рядку, що й позначений щойно .

Позначимо знаком „ ” рядок, у якому знаходиться цей , і вважаємо цей рядок зайнятим.

Переходимо до п. 5.

8. Починаючи з щойно позначеного , будуємо ланцюжок з нулів: від даного по стовпчику до , від нього по рядку – до наступного , далі по стовпчику до і т.д. Ланцюжок виявиться незамкнутим і буде закінчуватися на .

Примітка. Ланцюжок може складатися лише з одного .

Знімаємо зірочки у , що належать ланцюжкові, і заміняємо зірочками штрихи у , що належать ланцюжкові.

Новий набір буде мати на один елемент більше ніж попередній.

Знімемо всі позначки („ ”, „ ”, „`”), крім зірочок, і переходимо до п. 3.

9. (Незайнятих нулів немає). Знаходимо мінімальний елемент серед незайнятих. Нехай його величина дорівнює . Віднімаємо величину від усіх незайнятих рядків, а потім додаємо цю величину до усіх зайнятих стовпчиків.

Ніякі позначки не знімаються.

Нова матриця буде містити незайняті нулі.

Переходимо до п. 6.

10. Фіксуємо індекси , де знаходяться нулі із зірочками. Позначимо множину таких індексів через . Тоді маємо:

тобто призначеними будуть з індексами, що відповідають позиціям нулів із зірочками.

Максимально можлива сума рейтингів становитиме:

.

Процес закінчено.

Приклад 6.1. Нехай дана матриця , де . Кожен -й рядок відповідає -й роботі; -й стовпчик відповідає -му робітникові.

.

(6.7)

Ця матриця має вигляд (4.7).

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

Робимо дії згідно з алгоритмом.

У результаті виконання п. 1 маємо матрицю (6.8)

; .

(6.8)

Виконаємо п. 2.

.

(6.9)

Підраховуємо кількість зірочок у матриці (6.9). Оскільки їх менше, ніж , виконуємо наступні дії.

Далі наведемо низку перетворень матриць після дії вказаних пунктів алгоритму. Матриця після виконання пп. 3, 4, 5, 6, 7, 5, 6, 7, 5:

(6.10)

У матриці (4.10) немає незайнятих нулів. Переходимо до п. 9. Знаходимо найменший незайнятий елемент. Легко бачити, що величина такого елемента (наприклад, елемент (1, 5)). Віднімаємо його від усіх елементів незайнятих рядків:

(6.11)

Додаємо до елементів зайнятих стовпчиків матриці (6.11):

Перейшовши до п. 5, знаходимо незайнятий нуль в позиції (1, 5). У його рядку немає нуля з зірочкою, тому переходимо до п.8. Позначивши незайнятий нуль в позиції (1, 5) штрихом, намагаємося знайти ланцюжок, але в п’ятому стовпчику немає , тому у позиції (1, 5) є першим і останнім елементом ланцюжка. Знімемо з нього позначку (’) і замінимо її на (*). Знявши всі позначки, крім (*), маємо:

Після виконання пп. 3, 4, 5, 6, 7, 5, 6, 7, 5, 6 матриця набуває вигляду:

Виконавши пп. 5 і 6, бачимо, що незайнятий нуль у позиції (5, 4) не має у своєму рядку, тому будуємо ланцюжок, як показано далі:

Після виконання п. 8 матриця набуває вигляду:

.

(6.12)

У матриці (6.12) є нулів із зірочками. Задача розв’язана. Ненульові є ті , які відповідають індексам у матриці (6.12).

Таким чином, ,

тобто здійснені такі призначення: п’ятий робітник призначається на першу роботу, перший робітник – на другу роботу тощо. Решта .

Суму рейтингів (6.4) дістаємо, взявши відповідні рейтинги початкової матриці :

.

Як бачимо, досягти величини чи не вдається.