Контрольная работа: Угорський метод рішення завдань про призначення

Перший етап. Переглядають невиділені стовпці С_k . Якщо серед них не виявиться нульових елементів, то переходять до третього етапу. Якщо ж невиділений нуль матриці С_k виявлений, то можливо один із двох випадків:

1) рядок, що містить невиділений нуль, містить також і нуль із зірочкою;

2) цей рядок не містить нуля із зірочкою.

У другому випадку переходимо відразу до другого етапу, відзначивши цей нуль штрихом.

У першому випадку цей невиділений нуль відзначають штрихом і виділяють рядок, у якій він утримується (знаком '+' праворуч від рядка). Переглядають цей рядок, знаходять нуль із зірочкою й знищують знак '+' виділення стовпця, у якому втримується даний нуль.

Далі переглядають цей стовпець (який уже став невиділеним) і відшукують у ньому невиділений нуль (або нулі), у якому він перебуває. Цей нуль відзначають штрихом і виділяють рядок, що містить такий нуль (або нулі). Потім переглядають цей рядок, відшукуючи в ній нуль із зірочкою.

Цей процес за кінцеве число кроків закінчується одним з наступних результатів:

1) всі нулі матриці С_k виділені, тобто перебувають у виділених рядках або стовпцях. При цьому переходять до третього етапу;

2) є такий невиділений нуль у рядку, де немає нуля із зірочкою. Тоді переходять до другого етапу, відзначивши цей нуль штрихом.

Другий етап. На цьому етапі будують наступний ланцюжок з нулів матриці С_k : вихідний нуль зі штрихом, нуль із зірочкою, розташований в одному стовпці з першим нулем зі штрихом в одному рядку з попереднім нулем із зірочкою й т.д. Отже, ланцюжок утвориться пересуванням від 0^' до 0^* по стовпці, від 0^* до 0^' по рядку й т.д.

Можна довести, що описаний алгоритм побудови ланцюжка однозначний і кінцевий, при цьому ланцюжок завжди починається й закінчується нулем зі штрихом.

Далі над елементами ланцюжка, що знаходяться на непарних місцях ( 0^' ) ставимо зірочки, знищуючи їх над парними елементами (0^* ). Потім знищуємо всі штрихи над елементами С_k і знаки виділення '+'. Кількість незалежних нулів буде збільшено на одиницю. На цьому (k+1)-а ітерація закінчена.

Третій етап. До цього етапу переходять після першого, якщо всі нулі матриці С_k виділені. У такому випадку серед невиділених елементів С_k вибирають мінімальний і позначають його h (h>0). Далі віднімають h із всіх елементів матриці С_k , розташованих у невиділених рядках і додають до всіх елементів, розташованим у виділених стовпцях. У результаті одержують нову матрицю С^' _k , еквівалентну С_k . Помітимо, що при такому перетворенні, всі нулі із зірочкою матриці С_k залишаються нулями й у С^' _k , крім того, у ній з'являються нові невиділені нулі. Тому переходять знову до першого етапу. Завершивши перший етап, залежно від його результату або переходять до другого етапу, або знову повертаються до третього етапу.

Після кінцевого числа повторень черговий перший етап обов'язково закінчиться переходом на другий етап. Після його виконання кількість незалежних нулів збільшиться на одиницю й (k+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*	4	0	84
0	60	26	10
57	66	33	0*
28	0*	26	12

Перша ітерація. Перший етап. Виділяємо знаком '+' перший, другий, і четвертий стовпці матриці З₀ , які містять 0^* .

Переглядаємо невиділений третій стовпець, знаходимо в ньому невиділений нуль ІЗ₁₃ = 0, відзначаємо його штрихом і виділяємо знаком '+' перший рядок. Переглядаємо цей рядок, знаходимо в ній елемент ІЗ₁₁ = 0^* і знищуємо знак виділення першого стовпця, що містить 0^* .

0*	4	0’	84
0	60	26	10
57	66	33	0*
28	0*	26	12

Шукаємо мінімальний елемент у невиділеній частині матриці З₀ (тобто елементи, які лежать у стовпцях і рядках, не відзначених знаком '+').

Друга ітерація. Перший етап. Переглядаючи всі невиділені елементи, знаходимо серед них невиділений нуль ІЗ₁₂ = 0, відзначаємо його знаком штрих та переходимо до другого етапу.

0*	4	0’	84 +
0’	60	26	10
57	66	33	0*
28	0*	26	12

Другий етап. Починаючи з елемента ІЗ₁₂ = 0^' , будуємо коло, рухаючись від нього по стовпці. Знаходимо нуль із зірочкою ІЗ₁₁ = 0^* , далі від нього рухаємося уздовж першого рядка й знаходимо 0^' (ІЗ₁₃ ).

0*	4	0’	84 +
0’	60	26	10
57	66	33	0*
28	0*	26	12