![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Лекція 6. Алгоритм угорського методу для розв’язування задач про призначення
Постановка задачі. Нехай є Треба знайти множину
На величини
(кожний працівник призначається тільки на одну роботу)
(на кожну роботу призначається тільки один працівник). Цільова функція: максимізувати величину
Задача про призначення є частинним випадком як загальної ЗЛП, так і транспортної задачі. Умови (6.1) показують, що ця задача належить до класу бульових ЗЛП. Для розв’язування цієї задачі найбільш ефективним є метод, розроблений угорськими вченими і тому названий угорським методом, який застосовний і до транспортних задач загалом. Опишемо цей метод. Спочатку матриця 1. У кожному стовпчику знаходимо максимальний елемент. Нові значення
Цим досягається, що у кожному стовпчику з’явиться принаймні один нуль. 2. Від усіх елементів кожного рядка віднімаємо найменший елемент рядка:
Тепер у кожному рядку теж з’явиться принаймні один нуль. Ідея методу полягає в тому, щоб замість максимізації функції Умови (6.2) і (6.3) виконуються, якщо буде вибрана множина з n нулів так, щоб у кожному рядку і кожному стовпчику знаходився рівно один нуль. Опишемо алгоритм задачі про призначення. 1. Здійснимо перетворення матриці 2. Позначимо зірочкою (*) будь-який нуль у першому стовпчику; позначимо у другому стовпчику зірочкою будь-який нуль, який не лежить у рядку з попереднім 3. Підраховуємо кількість 4. Позначимо знаком „V” зверху стовпчики, в яких є Означення. Елементи, що знаходяться на перетині незайнятих рядка і стовпчика, назвемо незайнятими, решту – зайнятими. Переходимо до п. 5. 5. Знаходимо незайняті нулі. Якщо вони є, переходимо до п. 6, якщо немає – до п. 9. 6. Вибираємо перший із незайнятих нулів, перебираючи рядки зліва направо. Позначимо його штрихом (`). Якщо в його рядку немає 7. Знімаємо знак „ Позначимо знаком „ Переходимо до п. 5. 8. Починаючи з щойно позначеного Примітка. Ланцюжок може складатися лише з одного Знімаємо зірочки у Новий набір Знімемо всі позначки („ 9. (Незайнятих нулів немає). Знаходимо мінімальний елемент серед незайнятих. Нехай його величина дорівнює Ніякі позначки не знімаються. Нова матриця буде містити незайняті нулі. Переходимо до п. 6. 10. Фіксуємо індекси
тобто призначеними будуть Максимально можлива сума рейтингів становитиме:
Процес закінчено. Приклад 6.1. Нехай дана матриця
Ця матриця має вигляд (4.7). Якби можна було вибирати найбільші рейтинги стовпчиків, то їх сума становила б Робимо дії згідно з алгоритмом. У результаті виконання п. 1 маємо матрицю
Виконаємо п. 2.
Підраховуємо кількість зірочок у матриці (6.9). Оскільки їх менше, ніж Далі наведемо низку перетворень матриць після дії вказаних пунктів алгоритму. Матриця після виконання пп. 3, 4, 5, 6, 7, 5, 6, 7, 5:
У матриці (4.10) немає незайнятих нулів. Переходимо до п. 9. Знаходимо найменший незайнятий елемент. Легко бачити, що величина такого елемента
Додаємо
Перейшовши до п. 5, знаходимо незайнятий нуль в позиції (1, 5). У його рядку немає нуля з зірочкою, тому переходимо до п.8. Позначивши незайнятий нуль в позиції (1, 5) штрихом, намагаємося знайти ланцюжок, але в п’ятому стовпчику немає
Після виконання пп. 3, 4, 5, 6, 7, 5, 6, 7, 5, 6 матриця набуває вигляду:
Виконавши пп. 5 і 6, бачимо, що незайнятий нуль у позиції (5, 4) не має
Після виконання п. 8 матриця набуває вигляду:
У матриці (6.12) є Таким чином, тобто здійснені такі призначення: п’ятий робітник призначається на першу роботу, перший робітник – на другу роботу тощо. Решта Суму рейтингів (6.4) дістаємо, взявши відповідні рейтинги початкової матриці
Як бачимо, досягти величини
|