Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Лекція 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) дістаємо, взявши відповідні рейтинги початкової матриці :

.

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




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







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.