Алгоритм угорського методу

1. В матриці C вiднiмаємо від кожного елемента i -го рядка мінімальний елемент цього рядка (i=1,...,n).

2. Від кожного елемента j -го стовпця перетвореної матриці витрат вiднiмаємо його мінімальний елемент (j=1,...,n). В результаті виконання двох пунктів кожний рядок та кожний стовпець матриці витрат мають принаймні один нуль.

3. Проглядаємо послідовно рядки матриці витрат, починаючи з першого. Якщо рядок має лише один непозначений 0, позначаємо його позначкою * та закреслюємо (за допомогою позначки ^) решту нулів у цьому ж стовпцi. Нуль вважається позначеним, якщо він має позначку *. Повторюємо ці дії поки кожний рядок не буде мати непозначених нулів або буде мати їх принаймні два.

4. Дії п. 3 повторюємо для всіх стовпцiв матриці витрат.

5. Дії п.п. 3 та 4 повторюємо послідовно (якщо необхідно) поки не трапиться один з трьох можливих випадків:

І) кожний рядок має призначення (має 0 з позначкою *);

ІІ) є принаймні два непозначених нулі в деяких рядках i деяких стовпцях матриці витрат;

ІІІ) немає непозначених нулів i повне призначення ще не отримане (число нулів з позначкою * менше n).

6.У випадку i) задача розв’язана: xij, що відповідають 0 *, дорівнюють 1, решта – 0, кінець. У випадку ii) довільно вибираємо один з непозначених нулів, позначаємо його позначкою *, закреслюємо решту нулів в тому ж рядку i в тому ж стовпчику i повертаємося до п. 3. У випадку iii) переходимо до п. 7.

7. Позначаємо позначкою # рядки, для яких не отримане призначення (в яких немає нуля *). Такі рядки вважаємо позначеними, решту – непозначеними. Аналогiчно називаються i стовпчики матриці витрат.

8. Позначаємо позначкою # ще не позначенi стовпчики, які мають закреслений 0 (позначений позначкою ^) у позначених рядках.

9. Позначаємо позначкою # ще не позначенi рядки, які мають призначення (тобто 0*) у позначених стовпцях.

10. Повторюємо дії пунктів 8 і 9 доти, доки більше не можна буде позначити жодного рядка та стовпця матриці витрат.

11. Викреслюємо (за допомогою позначки &) непозначенi рядки i позначені стовпчики матриці витрат.

12. Знаходимо мінімальний невикреслений елемент матриці витрат, віднімаємо його від елементів кожного з невикреслених рядків, додаємо до елементів всіх викреслених стовпчикiв i переходимо до п. 3. При цьому позначки елементів матриці витрат (* та ^) втрачають свою силу.