Угорський метод

Лаболаторна робота з дослідження операцій aka методи оптимізації

В цій статті я хочу розказати про розв’язування задачі про виконавців угорським методом. Тут буде тільки відповідь на запитання: “Як розв’язати задачу”, а не “Чому і як цей метод працює?”. Записано на семінарі в Богдана Валерійовича Довгая.

Умова задачі:

ми маємо n завдань, і n виконавців. При чому кожен виконавець для свого завдання хоче певний розмір зарплати. Потрібно поділити завдання між виконавцями з мінімальними витратами. Крім того один виконавець має робити одне завдання. Не більше і не менше. Запишемо витрати i-того виконавця на j-ту роботу як C_i,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 нулів (кількість виконавців і робіт), то ці нулі показують кому яку роботу дати. В нас позначено тільки чотири нулі, тому розв’язок не оптимальний. З матрицею потрібно робити перетворення.

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

2. Позначимо стовпчики в яких в позначених рядочках є викреслений нуль.
   

   		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
   		#

3. Позначимо рядочки, де в позначених стовпчках є позначений нулик.
   

   #		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] X_i,j*C_i,j. Тобто тільки тих де X ненульове. В нас Z(X)=3+8+4+6+4=25.

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

Advertisements