13주차 1차시 수업에서는 할당문제에 해당하는 예제를 학습해보았습니다.
수송문제와 비슷하게 네트워크 흐름을 통하여 풀게되는 또 다른 문제 유형 중에 하나이고, '누구에게 무엇을 어떻게/얼마나 할당할 것인가?'를 해결해야 하는 문제가 됩니다. 이번 예제에서는 Flwoe 마케팅 회사가 어떤 에이전트(Agent)에게 고객(Clinet)을 할당할 것인가에 대한 문제를 해결해야 합니다.
현재 회사는 3명에 달하는 고객을 각 부서 팀장들에게 할당시키려고 하고 각 고객은 1명의 팀장에게만 연결이 되어야합니다.
또한 프로젝트 완료 시간(days)는 위 표에 나타나있으며 고객 간의 우선순위와 상관없이 단지 비용을 최소화(MIN) 할 수 있는 방향으로 1:1 할당을 해주어야 합니다.
위에 나타난 표를 네트워크 흐름 다이어그램으로 나타내게 되면 아래와 같습니다.
이 할당문제의 네트워크 흐름표도 수송문제와 유사하게 문제를 접근해 볼 수 있는데 팀장/고객 노드(node) 옆에 적혀져있는 숫자는 공급/수요를 의미하게 됩니다. 공급이 3 수요가 3으로서 공급=수요를 확인할 수가 있고 프로젝트 수행시간이 표시되어있는 총 9개의 아크(arc)를 확인해볼 수 있습니다. 즉 의사결정변수는 9개로 설정 할 수 있다는 의미이고 앞의 12주차 수업의 예제에서 의사결정변수를 설정하였던 것처럼 X11,X12,......X33과 같이 나타내어 줍니다.(앞의 1은 origin node, 뒤의 1은 destination node)
그렇게해서 목적함수식은 아래와 같이 만들어지게 됩니다.
그리고 제약조건식은 총 6개이고, 공급에 의한 제약조건식이 3개, 수요에 의한 제약조건식이 3개가 됩니다.
공급에 의한 제약조건식은 부호를 <=로 설정해주게 됩니다. (1보다 클수가 없음)
이렇게 목적함수식, 제약조건들을 정리하고 ms60 프로그램으로 옮긴 후 돌려보게되면 다음과 같습니다.
프로젝트 완료 시간에 관한 값이 26으로 나오게 되었고, 시간을 가장 최소화하는 방법으로 3명의 고객을 3명의 팀장 중 1명이 1명씩 담당하였을 때 나올 수 있는 최적의 값입니다. 최적해로서 채택된 해는 X12,X23,X31이 있고 채택된 해는 '1', 채택되지 않은 해는 '0'으로 나타나게 됩니다. 또한 이 할당문제같은 경우에도 주어진 조건 내에서 현실세계에 적용할 수 있는 최적의 '방안' 자체를 찾는 것에 목적이 있기 때문에 LP에서 확인 할 수 있는 RC나 D.P 등등의 산술적인 값들은 현실적으로 보았을 때 생각하지 않아도 되는 부분입니다.
그리고 할당문제 또한 전용 모듈을 지니고 있는데 전용 모듈을 가지고 돌려보니 아래와 같았습니다.
어떤 고객에게 어떤 팀장이 할당이 되었고 프로젝트에 든 시간에 관한 비용이 총 얼만큼 들었는지만 명료하게 확인 할 수 있습니다.
이렇게 기본적 관점에서 문제를 해결해보았는데 저희는 수송문제를 다뤘을때처럼 시야를 조금 더 넓혀서 생각해보았습니다.
여러가지 상황들을 생각해보고 변형시켜 보았는데 그 중에서 중요하다고 생각되는 것 2가지만 실험해보겠습니다.
1. 공급의 합과 수요의 합이 일치하지 않는 경우
<공급>수요>
위와 같은 경우에는 만약 1번에 해당하는 팀장이 2개의 프로젝트를 수행할 수 있다고 했을 때 총 공급은 4 / 수요는 3이 되는데, 원래 공급 3 / 수요 3 상태에서 공급(할 수 있는)량만 늘어났기 때문에 해당 문제를 해결하는데 있어서는 어려움이 없습니다.
<공급<수요>
수요가 늘게 된다는 의미는 고객(clinet)가 늘게 된다는 의미이고 만약 수요가 1만큼 증가하게 되면 네트워크 흐름표 상 아래와 같이 나타날 수 있을 것입니다.
기존 팀장1/팀장2/팀장3에 있어서 고객4에 대해 프로젝트에 걸리는 시간을 임의로 각각 6/7/10으로 정해주었습니다.
그러나 해당 데이터를 MS60 프로그램에 입력 후 돌려보게되면 infeasible region이라고 뜨게 되면서 최적안을 도출하지 못하게 됩니다. 따라서 저희는 Dummy변수를 사용하여 문제를 해결해보겠습니다.
아래의 그림은 'Dummy변수를 네트워크 흐름표에 집어넣었을 때 어떻게 될까'를 도식화 해본 것 입니다.
이렇게 되었을때 추가된 결정변수는 D41,D42,D43,D44이고 추가/변경된 제약조건은 다음과 같습니다.
<공급에 의한 제약조건>
D41+D42+D43+D44<=1
<수요에 의한 제약조건>
X11+X21+X31+D41=1
X12+X22+X32+D42=1
X13+X23+X33+D43=1
X14+X24+X34+D44=1
이렇게 추가/변경된 사항을 데이터에 입력 후 프로그램을 돌려주게 되면 아래와 같습니다.
현재 Dummy변수에 해당되는 것 중에 D42가 최적해로 1이 채택이 된 것을 확인했을 때 공급이 1만큼 부족하다. 즉 고객에게 할당시켜줄 팀장이 1명만큼 부족하다는 것을 알 수 있게 됩니다. 그리고 프로젝트에 걸린 시간의 값이 26->15로 크게 줄었는데 이는 물론 현재 수요만큼 공급이 되진 못하였으나 '2번고객에게 할당되어 걸리는 시간보다 4번고객에게 할당되어 걸리는 시간이 더 매력적(시간이 적게 든다)이다.'라고 판단이 되어 이러한 결괏값이 나타난 것으로 확인할 수 있겠습니다.
그리고 공급3/수요4일때 할당 전용 모듈로 돌려보았을 때의 결과입니다.
2. 루트에 제약이 걸린 경우
만약에 2번 팀장이 3번 고객에게 할당되지 못하는(프로젝트를 수행하지 못하는)경우가 생긴다고 가정해보고 문제를 해결해보겠습니다. 그렇다면 의사결정변수인 X23이 0이된다는 소리고 즉 해당 루트는 없는 루트라고 생각할 수 있게 됩니다.
따라서 의사결정변수에서 X23을 제외시키고 프로그램을 실행하게 되면 아래와 같습니다.
프로그램 실행결과 결괏값이 26에서 27로 1만큼 올랐는데 이는 X23에 해당하는 아크(arc)가 만약 있었더라면, 즉 2번 팀장이 3번고객에게 할당될 수 있었더라면 프로젝트에 걸리는 시간을 최소화할 수 있었다는 것을 의미합니다. X12는 최적의 루트로서 변동이없고 본래 X23 X31이 채택되었는데, X23이 제외되고나서 X21 X33이 채택되게 되었습니다.
그리고 해당 경우에는 할당 모듈로 문제를 해결할 수 없습니다. 왜냐하면 수송문제와 마찬가지로 표준 모형(공급=수요)이외의 경우에는 세부적인 제약조건을 설정할 수 없기 때문입니다.
첫댓글 이제 다 와간다. 마지막까지 잘 해내거라.