|
|||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Лекція 6. Алгоритм угорського методу для розв’язування задач про призначенняПостановка задачі. Нехай є робіт і робітників або пристроїв для виконання цих робіт. Задана матриця , де – рейтинг (міра корисності) -го робітника (пристрою) під час виконання -ї роботи. Треба знайти множину ,
На величини накладаються умови:
(кожний працівник призначається тільки на одну роботу)
(на кожну роботу призначається тільки один працівник). Цільова функція: максимізувати величину :
Задача про призначення є частинним випадком як загальної ЗЛП, так і транспортної задачі. Умови (6.1) показують, що ця задача належить до класу бульових ЗЛП. Для розв’язування цієї задачі найбільш ефективним є метод, розроблений угорськими вченими і тому названий угорським методом, який застосовний і до транспортних задач загалом. Опишемо цей метод. Спочатку матриця підлягає двом перетворенням. 1. У кожному стовпчику знаходимо максимальний елемент. Нові значення елементів матриці дорівнюють різниці між максимальним і поточним значеннями елементів
Цим досягається, що у кожному стовпчику з’явиться принаймні один нуль. 2. Від усіх елементів кожного рядка віднімаємо найменший елемент рядка:
Тепер у кожному рядку теж з’явиться принаймні один нуль. Ідея методу полягає в тому, щоб замість максимізації функції знайти множину елементів матриці з мінімальною, тобто нульовою сумою. Умови (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. Нехай дана матриця , де . Кожен -й рядок відповідає -й роботі; -й стовпчик відповідає -му робітникові.
Ця матриця має вигляд (4.7). Якби можна було вибирати найбільші рейтинги стовпчиків, то їх сума становила б , для рядків . Робимо дії згідно з алгоритмом. У результаті виконання п. 1 маємо матрицю (6.8)
Виконаємо п. 2.
Підраховуємо кількість зірочок у матриці (6.9). Оскільки їх менше, ніж , виконуємо наступні дії. Далі наведемо низку перетворень матриць після дії вказаних пунктів алгоритму. Матриця після виконання пп. 3, 4, 5, 6, 7, 5, 6, 7, 5:
У матриці (4.10) немає незайнятих нулів. Переходимо до п. 9. Знаходимо найменший незайнятий елемент. Легко бачити, що величина такого елемента (наприклад, елемент (1,5)). Віднімаємо його від усіх елементів незайнятих рядків:
Додаємо до елементів зайнятих стовпчиків матриці (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.4) дістаємо, взявши відповідні рейтинги початкової матриці : . Як бачимо, досягти величини чи не вдається. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.008 сек.) |