경영과학 13주차 1차시 복습

[윤수정(행정)]

assignment problem 할당문제; 어떤 일을 어떤 사람에게 할당시킬지 결정하는 것. 이를 수송의 네트워크처럼 생각하고 한 사람당 한 가지 일만 맡길 수 있음. 최소화라면 비용, 시간이고 최대화라면 고객만족도 성과 이익.

3명의 팀이있고 3가지 job이 있음. 이를 수송문제와 같이 그림을 그려 표현할 수 있다. 그리고 수송과는 달리 한팀에 한가지 일만 할당 할 수 있으니까 각각 origin과 destination에 한가지 씩 수요와 공급이 존재한다. 그리고 각 팀에서 일을 할당되는 것은 한가지보다 많이 할 수는 없으니까 1보다 작거나 같다로 조건을 세워야하고 클라이언트는 무조건 일을 한 팀이 맡아야하니까 =1로 조건을 세운다. 각 할당됐을 때 걸리는 시간을 계수로 놓고 시간이니까 최소화로 목적함수식을 세울 수 있다.

이를 LP와 Assignment를 이용해서 문제를 풀어볼 수 있다.

이를 통해 X12, X23, X31에 각각 1씩 일이 할당된 것을 확인할 수 있다.

Assignment를 이용하면

3이 1의 일을 맡고 1팀이 2고객 일을 맡고 2팀이 3고객의 일을 맡으며 총 소요 시간은 26시간이 소요됨을 알 수 있다.

Assignment에 생길 수 있는 문제가 있는데

1. client와 team의 숫자가 맞지 않는 경우

team의 숫자가 client보다 많은 경우에는 괜찮다. 제약조건 식이 작거나 같다이기에 한팀이 일을 맡지 않으면 된다.

하지만 반대로 team의 숫자가 client보다 적은 경우에는 불리한 일은 맡지 못하게된다.

2.maximization 만족도나 성과라면 maximization으로 바꾸면 된다.

3. 맡을 수 없는 일의 경우에는 X31=0이라는 조건식을 추가하면된다. 이는 assignment module에서는 할 수 없기에 LP를 이용.

그래서 client의 숫자가 더 많은 경우에는 Dummy를 세워서 LP를 통해 문제를 해결할 수 있다.

Assignment module을 이용해서 team이 더 많은 경우와 client가 더 많은 경우를 확인해보면

이렇게 해결할 수 있다.

LP로 client 수가 더 많을 때 dummy를 세워서 문제를 해결하는 경우를 확인해보면

task 4가 추가되면 제약조건7이 늘어나게 되고 solve해보면 infeasible solution이 나타난다.

이때 variable을 4개 더 추가하여 dummy를 이용한다. 그리고 dummy의 합이 1보다 작거나 같은 제약조건식을 추가한다.

이때 dummy에 할당된 D42를 통해 2 client의 일은 맡을 수 없음을 알 수 있다.

[현승용]

차분히 잘 하고 있구나.