Угорський метод рішення завдань про призначення
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
?жок утвориться пересуванням від 0 до 0* по стовпці, від 0* до 0 по рядку й т.д.
Можна довести, що описаний алгоритм побудови ланцюжка однозначний і кінцевий, при цьому ланцюжок завжди починається й закінчується нулем зі штрихом.
Далі над елементами ланцюжка, що знаходяться на непарних місцях ( 0 ) ставимо зірочки, знищуючи їх над парними елементами (0*). Потім знищуємо всі штрихи над елементами Сk і знаки виділення +. Кількість незалежних нулів буде збільшено на одиницю. На цьому (k+1)-а ітерація закінчена.
Третій етап. До цього етапу переходять після першого, якщо всі нулі матриці Сk виділені. У такому випадку серед невиділених елементів Сk вибирають мінімальний і позначають його h (h>0). Далі віднімають h із всіх елементів матриці Сk, розташованих у невиділених рядках і додають до всіх елементів, розташованим у виділених стовпцях. У результаті одержують нову матрицю Сk, еквівалентну Сk. Помітимо, що при такому перетворенні, всі нулі із зірочкою матриці Сk залишаються нулями й у Сk, крім того, у ній зявляються нові невиділені нулі. Тому переходять знову до першого етапу. Завершивши перший етап, залежно від його результату або переходять до другого етапу, або знову повертаються до третього етапу.
Після кінцевого числа повторень черговий перший етап обовязково закінчиться переходом на другий етап. Після його виконання кількість незалежних нулів збільшиться на одиницю й (k+1)-а ітерація буде закінчена.
3 Приклад розвязання задачі за допомогою угорського методу
Вирішити завдання про призначення з наступною матрицею:
Операціії
Обладнання12341378583
25761661316162587445823275
При рішенні завдання використаємо наступні позначення:
Знак виділення +, що підлягає знищенню, обводимо кружком; коло, як і раніше, указуємо стрілками.
Попередній етап. Відшукуємо максимальний елемент першого стовпця - 73. Віднімаємо з нього всі елементи цього стовпця. Аналогічно для одержання другого, третього й четвертого стовпців нової матриці віднімаємо всі елементи цих стовпців від 82, 58, і 87 відповідно. Одержимо матрицю С(C~C).
040841676422657663302802612
Тому що в кожному рядку С крім другого є нуль, то віднімаємо лише мінімальний елемент другого рядку (16) від усіх елементів цього рядку і отримуємо матрицю З0 ~ С і на цьому процес приведення матриці закінчується.
Далі шукаємо й відзначаємо знаком * незалежні нулі в З0, починаючи з першого рядка.
0*408406026105766330*280*2612
Перша ітерація. Перший етап. Виділяємо знаком + перший, другий, і четвертий стовпці матриці З0, які містять 0*.
Переглядаємо невиділений третій стовпець, знаходимо в ньому невиділений нуль ІЗ13 = 0, відзначаємо його штрихом і виділяємо знаком + перший рядок. Переглядаємо цей рядок, знаходимо в ній елемент ІЗ11 = 0* і знищуємо знак виділення першого стовпця, що містить 0*.
0*4084 0602610 5766330* 280*2612Шукаємо мінімальний елемент у невиділеній частині матриці З0 (тобто елементи, які лежать у стовпцях і рядках, не відзначених знаком +).
Друга ітерація. Перший етап. Переглядаючи всі невиділені елементи, знаходимо серед них невиділений нуль ІЗ12 = 0, відзначаємо його знаком штрих та переходимо до другого етапу.
0*4084 + 06026105766330*280*2612
Другий етап. Починаючи з елемента ІЗ12 = 0, будуємо коло, рухаючись від нього по стовпці. Знаходимо нуль із зірочкою ІЗ11= 0*, далі від нього рухаємося уздовж першого рядка й знаходимо 0(ІЗ13).
0*4 084 + 0602610 5766330* 280*2612
Таким чином, коло побудоване: 021-0*11-013. Заміняємо штрих на зірочку й знищуємо зірочки над парними елементами кола, а також всі знаки виділення стовпців і рядків. Після цієї ітерації кількість незалежних нулів (0*) стало дорівнювати 4 (розмірності матриці З) і тому алгоритм закінчує роботу. Шукані елементи призначення відповідають позиціям незалежних нулів матриці З3 (тобто 0*).
040*840*602610 5766330* 280*2612
Висновок
Відповідне значення цільової функції:
F = C12+C24+C31+C43 = 57+82+58+87=284
Література
1. Системы автоматизированного проектирования. В 9-ти кн.Учебное пособие для вузов. Под редакцией Норенкова И.П. М.: Высш. шк., 1986.
2. Норенков И.П. Введение в автоматизированное проектирование технических устройств и систем. Учебное пособие для вузов. - М.: Высш. шк., 1986.
3. П. Шеннен и др. Математика и САПР. т.1. М.: Мир, 1988.
4. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984.
5.Системы автоматизированного проектирования в радиоэлектронике. Справочник. М.: Радио и связь, 1986.
6. Погребной В.К. О декомпозиции графов на классы изоморфных подграфов. В кн.: Вопросы программирования и автоматизации проектирования. Изд. ТГУ, 1979, с. 82-96.
7. Петренко А.И. Основы автоматизации проектирования. К.: Техника, 1982. - 295 с.
8. Ильин В.Н.. Основы автоматизации схемотехнического проектирования. Г.: Энергия, 1979. - 392 с.
9. Демидович Б.П., Марон И.А. Основы вычислительной математики. Г.: Изд-во Наука, 1966. - 664 с.
10.Разевиг В.Д. Система сквозного проектирования электронных устройств DesignLab 8.0.- М.: Изд-во Солон,1999. - 698 с.