# Assignment Problem 할당문제
: 다양한 의사결정 상황에서 발생하며 비용, 시간의 최소화나 이익의 최대화와 같이
명시된 목표를 최적화 할 과제를 찾는다.
직업-기계, 에이전트-직무, 영업사원-영업지원 등 누구에게 무엇을 할당하고 어떻게 배분할 것인가를 다루는 문제이다.
한 명의 에이전트에 하나의 과제가 할당된다. (이는 필수가 아님) 즉, 꼭 1일 필요는 없다.
( 만약 2라면 한 프로젝트 리더가 두 가지의 프로젝트를 동시에 할 수 있다는 뜻.
이러한 변형은 Assignment에서는 O, Linear Program 에서는 X)
이는 수송문제와 마찬가지로 네트워크 모형으로 나타낼 수 있다.
Assignment Problem 예제
프로젝트 리더를 각 3명의 고객에게 할당, 배분해야한다.
프로젝트 리더는 한 명당 한명의 고객에 할당된다.
다음은 예상 프로젝트 완료 하는데에 걸리는 시간을 나타낸 표이다.
우리는 프로젝트를 완료하는 데 소비되는 시간을 최소화하는 것을 목표로 한다.
이를 한눈에 보기 쉬운 네트워크 모형으로 나타낸다면 다음과 같다.
origin node : 프로젝트 리더
destination node : 고객
arc : 프로젝트 리더에게 할당되는 고객(직무) , 각 arc는 직무를 완료하는데 걸리는 시간을 나타내고 있음
우리는 프로젝트 완료 시간을 최소화하는 것이 목적이기 때문에
다음과 같이 목적함수식과 6개의 제약조건식을 설정할 수 있다.
< 목적함수식 >
: Min 10X11+15X12+9X13+9X21+18X22+5X23+6X31+14X32+3X33
< 조건제약식 >
- 수요 제약조건식
X11+X12+X13 ≤ 1
X21+X22+X23 ≤ 1
X31+X32+X33 ≤ 1
- 공급 제약조건식
X11+X21+X31 = 1
X21+X22+X33 = 1
X31+X32+X33 = 1
이를 MS60에 대입하면 다음과 같은 결과가 나타난다.
목적함수값(최소화 시킨 완료시간)은 26(일)이라는 결과가 나왔다.
채택되지 않은 것은 할당되지 않음을 의미하며, 채택된 것은 할당되었다는 의미이다.
할당문제 역시 특수한 모형 Assignment Module로 나타낼 수 있다.
이와 같이 Assignment module은 Linear Program보다 간결하고 한 눈에 보기 쉽다.
만약 고객이 한 명 더 들어나서 수요량이 공급량을 초과한다면 어떤 결과가 나올지 알아보기 위해
변수의 계수를 임의로 6,2,5라고 지정하여 실험해보겠다.
목적함수값 (소요시간)은 26일에서 15일로 감소했지만 고객 2는 할당되지 못한다.
즉, Task가 하나 더 많기 때문에 Task1개는 실질적으로 해내지 못한다는 의미이다.
이는 고객2를 할당하는 것보다 고객4를 할당하는 것이 소요시간을 최소화하는 데에 더 효율적이라고 판단되었기 때문이다.
여기서 어떤 팀이 두 고객의 프로젝트를 처리할 수 있다면 이 문제는 해결될 것이다.
+ 할당문제도 수송문제와 마찬가지로 공급량이 수요량을 초과하면 문제가 되지 않지만,
수요량이 공급량을 초과할 시에는 Infeasible이라는 결과가 나온다.
공급량이 수요량을 초과할 때에는 가장 목적에 부합하는 팀만 배치하고 비교적 뒤처지는 팀은 배치하지 않으면 되기 때문에
문제가 되지 않지만, 수요량이 공급량을 초과할 때에는 Infeasible의 결과가 나온다.