Навигация
Приклад розв’язання задачі за допомогою угорського методу
10215
знаков
8
таблиц
1
изображение
3 Приклад розв’язання задачі за допомогою угорського методу
Вирішити завдання про призначення з наступною матрицею:
| Операціії Обладнання | 1 | 2 | 3 | 4 |
| 1 | 3 | 78 | 58 | 3 |
| 2 | 57 | 6 | 16 | 61 |
| 3 | 16 | 16 | 25 | 87 |
| 4 | 45 | 82 | 32 | 75 |
При рішенні завдання використаємо наступні позначення:
Знак виділення '+', що підлягає знищенню, обводимо кружком; коло, як і раніше, указуємо стрілками.
Попередній етап. Відшукуємо максимальний елемент першого стовпця - 73. Віднімаємо з нього всі елементи цього стовпця. Аналогічно для одержання другого, третього й четвертого стовпців нової матриці віднімаємо всі елементи цих стовпців від 82, 58, і 87 відповідно. Одержимо матрицю С'(C'~C).
0 | 4 | 0 | 84 |
| 16 | 76 | 42 | 26 |
| 57 | 66 | 33 | 0 |
| 28 | 0 | 26 | 12 |
Тому що в кожному рядку С' крім другого є нуль, то віднімаємо лише мінімальний елемент другого рядку (16) від усіх елементів цього рядку і отримуємо матрицю З0 ~ С' і на цьому процес приведення матриці закінчується.
Далі шукаємо й відзначаємо знаком '*' незалежні нулі в З0, починаючи з першого рядка.
| 0* | 4 | 0 | 84 |
| 0 | 60 | 26 | 10 |
| 57 | 66 | 33 | 0* |
| 28 | 0* | 26 | 12 |
Перша ітерація. Перший етап. Виділяємо знаком '+' перший, другий, і четвертий стовпці матриці З0, які містять 0*.
Переглядаємо невиділений третій стовпець, знаходимо в ньому невиділений нуль ІЗ13 = 0, відзначаємо його штрихом і виділяємо знаком '+' перший рядок. Переглядаємо цей рядок, знаходимо в ній елемент ІЗ11 = 0* і знищуємо знак виділення першого стовпця, що містить 0*.
| 0* | 4 | 0’ | 84 |
| 0 | 60 | 26 | 10 |
| 57 | 66 | 33 | 0* |
| 28 | 0* | 26 | 12 |
Шукаємо мінімальний елемент у невиділеній частині матриці З0 (тобто елементи, які лежать у стовпцях і рядках, не відзначених знаком '+').
Друга ітерація. Перший етап. Переглядаючи всі невиділені елементи, знаходимо серед них невиділений нуль ІЗ12 = 0, відзначаємо його знаком штрих та переходимо до другого етапу.
| 0* | 4 | 0’ | 84 + |
| 0’ | 60 | 26 | 10 |
| 57 | 66 | 33 | 0* |
| 28 | 0* | 26 | 12 |
Другий етап. Починаючи з елемента ІЗ12 = 0', будуємо коло, рухаючись від нього по стовпці. Знаходимо нуль із зірочкою ІЗ11= 0*, далі від нього рухаємося уздовж першого рядка й знаходимо 0'(ІЗ13).
| 0* | 4 | 0’ | 84 + |
| 0’ | 60 | 26 | 10 |
| 57 | 66 | 33 | 0* |
| 28 | 0* | 26 | 12 |
Таким чином, коло побудоване: 0'21-0*11-0'13. Заміняємо штрих на зірочку й знищуємо зірочки над парними елементами кола, а також всі знаки виділення стовпців і рядків. Після цієї ітерації кількість незалежних нулів (0*) стало дорівнювати 4 (розмірності матриці З) і тому алгоритм закінчує роботу. Шукані елементи призначення відповідають позиціям незалежних нулів матриці З3 (тобто 0*).
| 0’ | 4 | 0* | 84 |
| 0* | 60 | 26 | 10 |
| 57 | 66 | 33 | 0* |
| 28 | 0* | 26 | 12 |
Висновок
Відповідне значення цільової функції:
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 с.
Похожие работы
... «сподвижників», Петро Могила цим підніс Україну до небувалого культурного розвитку. В цей час Україна почала випромінювати своїми церковними і культурними досягненнями на ввесь православний світ, а насамперед на Молдавію і Волощину. Назагал про Петра Могилу, як особу, знасмо мало, нам доводиться говорити про його творчість; його біографія це частина історії української православної церкви. 4) ...
... Починає розвиватися та набувати радикальних форм націоналізм, серед косовських албанців. Сербська влада намагалася вести боротьбу з ними, але безрезультатно. Албано – сербські протиріччя починають набувати гострих форм, які в майбутньому грозили перетворитися у збройні сутички. РОЗДІЛ 2. ВИНИКНЕННЯ ТА РОЗВИТОК АЛБАНО – СЕРБСЬКИХ ПРОТИРІЧ 2.1 Загострення албано – сербських протиріч, в другій ...
... пошуку. Побудований нами приклад показав, що для рішення задач із вимогою цілочисленності необхідно розглянути особливі методи оптимізації; і, крім того, ми бачимо, що оптимальне рішення задач цілочисленного програмування не обов'язково належить границі багатогранника (багатокутника) умов, що було характерно для задач лінійного програмування. 2. Теоретичні основи методів відсікання Запишемо ...
... блоку, як і, у свою чергу, країни Антанти у передвоєнні роки. Тема 6. Україна на міжнародній арені в період національної революції 1917-1920 рр. (4 год.). 1. Становлення міжнародних відносин України в період Центральної Ради 27 лютого 1917 р. в Росії перемогла Лютнева демократична революція. Влада в Росії перейшла до Тимчасового уряду. 3-4 березня 1917 р. в Києві було організовано ...
0 комментариев