Assignment Problem

작업자 $i \in I$ 명에게 일 $j \in J$ 개의 일을 최적으로 할당하는 문제는 $I$에서 $J$로 가는 일대일 대응(bijection) $\sigma : I \to J$ 중에서 가장 비용이 적은 것을 찾는 문제이다.

작업자 $i$ 가 일 $j$를 처리하는 비용을 $c(i,j)$라고 최적의 할당은

이것을 그래프로 생각하면 $I$와 $J$ 에 대한 edge cost가 $c$인 complete bipartite graph가 되고 모든 정정이 참여해햐 함으로 cost 비용이 최소가 perfect matching M을 찾는 것이다.

작업자-일 배분 표

	$j_1$	$j_2$	$j_3$
$i_1$	3	8	9
$i_2$	4	12	7
$i_3$	4	8	5

위의 표를 최소의 비용으로 일대일 매칭을 해야한다. 여기서, Hungarian Algorithm을 사용한다.

Hungarian Algorithm (Intuitive Representation)

기본개념은 같은 행(작업자)에 일정한 비용을 더하거나 빼더라도 할당을 위한 결과는 바뀌지 않는다는 것이다. 열(일)에도 동일한 개념이 적용된다. 그렇다면 적당한 값을 행/열에 빼거나 더해서 일대일 대응에서 0이 나오도록 하면 최적으로 매칭일 될 수 있다.

먼저 각 행에서 최소값을 빼고 다음으로 각 열에서 최소값을 뺀다

각 열에서 최소값을 땐다

	$j_1$	$j_2$	$j_3$
$i_1$	0	5	6	-3
$i_2$	0	8	3	-4
$i_3$	0	4	1	-4

각 행에서 최소값을 땐다

	$j_1$	$j_2$	$j_3$
$i_1$	0	1	5	-3
$i_2$	0	4	2	-4
$i_3$	0	0	0	-4
	0	-4	-1

$i_3, j_1$이 모두 0을 가지므로 이를 벗어나기 위해 $i_1,i_1$에 1을 더빼준다

	$j_1$	$j_2$	$j_3$
$i_1$	-1	0	4	-3-1
$i_2$	-1	3	1	-4-1
$i_3$	0	0	0	-4
	0	-4	-1

음수가 있음으로 음수를 제거한다.

	$j_1$	$j_2$	$j_3$
$i_1$	0	0	4	-3-1
$i_2$	0	3	1	-4-1
$i_3$	1	0	0	-4
	+1	-4	-1

이제 모든 작업자와 일간의 매칭에서 0을 가지게 된다.

($i_1 \to j_2$ ), ($i_2 \to j_1$ ), ($i_3 \to j_3$ )

따라서, 최적의 비용은 다음과 같다

	$j_1$	$j_2$	$j_3$
$i_1$	3	8	9
$i_2$	4	12	7
$i_3$	4	8	5

($i_1 \to j_2$ )=8, ($i_2 \to j_1$ )=3, ($i_3 \to j_3$ )=5,