Угорський метод
Угорський метод
Лаболаторна робота з дослідження операцій aka методи оптимізації
В цій статті я хочу розказати про розв’язування задачі про виконавців угорським методом. Тут буде тільки відповідь на запитання: “Як розв’язати задачу”, а не “Чому і як цей метод працює?”. Записано на семінарі в Богдана Валерійовича Довгая.
Умова задачі:
ми маємо n завдань, і n виконавців. При чому кожен виконавець для свого завдання хоче певний розмір зарплати. Потрібно поділити завдання між виконавцями з мінімальними витратами. Крім того один виконавець має робити одне завдання. Не більше і не менше. Запишемо витрати i-того виконавця на j-ту роботу як Ci,j. Наприклад:
![]() |
3 | 10 | 5 | 9 | 16 | ![]() |
||
6 | 8 | 11 | 8 | 18 | ||||
7 | 13 | 10 | 3 | 4 | ||||
5 | 9 | 6 | 21 | 12 | ||||
5 | 4 | 12 | 6 | 13 |
Розв’язок:
Знаходимо мінімальний елемент кожного рядка:
![]() |
3 | 10 | 5 | 9 | 16 | ![]() |
3 | |
6 | 8 | 11 | 8 | 18 | 6 | |||
7 | 13 | 10 | 3 | 4 | 3 | |||
5 | 9 | 6 | 21 | 12 | 5 | |||
5 | 4 | 12 | 6 | 13 | 4 |
І віднімаємо від кожного елементу рядка:
![]() |
0 | 7 | 2 | 6 | 13 | ![]() |
||
0 | 2 | 5 | 2 | 12 | ||||
4 | 10 | 7 | 0 | 1 | ||||
0 | 4 | 1 | 16 | 7 | ||||
1 | 0 | 7 | 2 | 9 |
Далі таке саме робимо для стовпців. Наша мета – зробити хоча б один нуль в кожному рядку і кожному стовпцю:
![]() |
0 | 7 | 2 | 6 | 13 | ![]() |
||
0 | 2 | 5 | 2 | 12 | ||||
4 | 10 | 7 | 0 | 1 | ||||
0 | 4 | 1 | 16 | 7 | ||||
1 | 0 | 7 | 2 | 9 | ||||
|
||||||||
0 | 0 | 1 | 0 | 1 |
Отримуємо:
![]() |
0 | 7 | 1 | 6 | 12 | ![]() |
||
0 | 2 | 4 | 2 | 11 | ||||
4 | 10 | 6 | 0 | 0 | ||||
0 | 4 | 0 | 16 | 6 | ||||
1 | 0 | 6 | 2 | 8 | ||||
Тепер підготовчий етап пройдено. Можна розставляти позначки. Позначки розставляються за таким правилом: “Якщо в рядку є єдиний непозначений нуль, то позначаємо його (символ *). Всі нулі того стовпчика який щойно позначили – викреслюємо (символ ^)”.
![]() |
0* | 7 | 1 | 6 | 12 | ![]() |
||
0^ | 2 | 4 | 2 | 11 | ||||
4 | 10 | 6 | 0 | 0 | ||||
0^ | 4 | 0* | 16 | 6 | ||||
1 | 0* | 6 | 2 | 8 |
Таке саме робимо для стовпців, тобто “Якщо в стовпці є єдиний непозначений нуль, то позначаємо його. Всі нулі того рядка який щойно позначили – викреслюємо”.
![]() |
0* | 7 | 1 | 6 | 12 | ![]() |
||
0^ | 2 | 4 | 2 | 11 | ||||
4 | 10 | 6 | 0* | 0^ | ||||
0^ | 4 | 0* | 16 | 6 | ||||
1 | 0* | 6 | 2 | 8 |
Тепер рахуємо скільки нулів позначено. Якщо позначено 5 нулів (кількість виконавців і робіт), то ці нулі показують кому яку роботу дати. В нас позначено тільки чотири нулі, тому розв’язок не оптимальний. З матрицею потрібно робити перетворення.
- Позначимо символом # (“дієз”) рядки, в яких є непозначені нулі (без *).
0* 7 1 6 12 # 0^ 2 4 2 11 4 10 6 0* 0^ 0^ 4 0* 16 6 1 0* 6 2 8 - Позначимо стовпчики в яких в позначених рядочках є викреслений нуль.
0* 7 1 6 12 # 0^ 2 4 2 11 4 10 6 0* 0^ 0^ 4 0* 16 6 1 0* 6 2 8 # - Позначимо рядочки, де в позначених стовпчках є позначений нулик.
# 0* 7 1 6 12 # 0^ 2 4 2 11 4 10 6 0* 0^ 0^ 4 0* 16 6 1 0* 6 2 8 #
Тепер викреслюємо непозначені рядки і позначені стовпчики. Але я краще просто підкреслю те що має залишитись.
# | ![]() |
0* | 7 | 1 | 6 | 12 | ![]() |
|
# | 0^ | 2 | 4 | 2 | 11 | |||
4 | 10 | 6 | 0* | 0^ | ||||
0^ | 4 | 0* | 16 | 6 | ||||
1 | 0* | 6 | 2 | 8 | ||||
# |
Серед невикреслених (читай “підкреслених”) рядків шукаємо мінімальний емент. В нас він дорівнює 1. Віднімаємо його від невикреслених рядків,
![]() |
-1 | 6 | 0 | 5 | 11 | ![]() |
||
-1 | 1 | 3 | 1 | 10 | ||||
4 | 10 | 6 | 0 | 0 | ||||
0 | 4 | 0 | 16 | 6 | ||||
1 | 0 | 6 | 2 | 8 |
і додаємо до викреслених стовпчиків. (Важливо, щоб усі елементи залишились додатніми). В нашому випадку додаємо в перший стовпчик.
![]() |
0 | 6 | 0 | 5 | 11 | ![]() |
||
0 | 1 | 3 | 1 | 10 | ||||
5 | 10 | 6 | 0 | 0 | ||||
1 | 4 | 0 | 16 | 6 | ||||
2 | 0 | 6 | 2 | 8 |
В нашій новій матриці знову починаємо позначати нулі. Якщо їх буде п’ять завершимо роботу.
# | ![]() |
0^ | 6 | 0^ | 5 | 11 | ![]() |
|
# | 0* | 1 | 3 | 1 | 10 | |||
5 | 10 | 6 | 0* | 0^ | ||||
# | 1 | 4 | 0* | 16 | 6 | |||
2 | 0* | 6 | 2 | 8 | ||||
# | # |
Позначених нулів знову чотири, тому віднімаємо 1 (мінімальний невикреслений елемент) від невикреслених рядків і додаємо в викреслені стовпчики. З новою матрицею знов продовжимо позначення
![]() |
0* | 5 | 0^ | 4 | 10 | ![]() |
||
0^ | 0^ | 3 | 0* | 9 | ||||
6 | 10 | 7 | 0^ | 0* | ||||
1 | 3 | 0* | 15 | 5 | ||||
3 | 0* | 7 | 2 | 8 |
Опа. В нас 5 позначених нулів. При чому в кожному рядку і кожному стовпці лише один позначений нуль. Наприклад позначений нуль в першому стовпці першого рядка означає, що першому виконавцю будем давати першу роботу. І так далі. Тепер записуємо матрицю розв’язку X. В ній якщо і-тому робітнику дають j-те завдання то елемент в і-тому рядку і j-тому стовпці буде містити одиничку. Всі інші елементи нульові. Отже X:
![]() |
1 | 0 | 0 | 0 | 0 | ![]() |
||
0 | 0 | 0 | 1 | 0 | ||||
0 | 0 | 0 | 0 | 1 | ||||
0 | 0 | 1 | 0 | 0 | ||||
0 | 1 | 0 | 0 | 0 | ||||
І звісно насамкінець обчислюємо цільову функцію (витрати). Для цього знаходимо суму всіх елементів по i,j=[1..n] Xi,j*Ci,j. Тобто тільки тих де X ненульове. В нас Z(X)=3+8+4+6+4=25.
Уточнення, зауваження, і повідомлення про помилки пишіть в коментарях.
Згадав предмет “методи оптимізації” – дуже любив лабораторні роботи з цього предмету – особливо задачу про комівояжера.
illusions
22 Травня, 2009 at 11:39
Дуже гарно дякую, сильно помогло, коли запрограмовував на Delphi
Sandy
5 Травня, 2012 at 17:41
Дякую, дуже приємно знати.
bunyk
5 Травня, 2012 at 19:25