13주차1차시 복습 시작하겠습니다.
이번 시간에는 Assignment problem에 대해 배웠습니다.
*assignment problem(할당)
어느 에이전트에 어떤 과업을 부여해서 일을 시킬것인가
영업사원에게 어떤 지역을 담당하라고 시킬것인가 등등
이러한 여러 가지 의사결정 상황에서 각각의 역할들을 할당 시키는 것
(물류예제처럼 움직이는 것이 아닌 일종의 네트워크)
-한 에이전트에 한가지 과업만 부여가능합니다.
-최소화(비용,시간,불만) ,최대화(만족도,성과,이익)
마케팅리서치 회사에 현재 일을 할 수 있는 팀은 1,2,3 총 3개의 팀이 있으며 각각의 리더 이름으로 나타나있습니다.
클라이언트도 마찬가지로 1,2,3 이렇게 3군데가 있습니다(3개의 의뢰가 들어온 상황).
그리고 팀이 각각의 과업을 수행하는데에 필요한 시간도 위와같이 나와있습니다.(3번팀이 1번일을 할 때 걸리는
시간은 6일 이런식으로) 이제 문제는 한팀당 한가지 일밖에 못하는데 과연 어떤 팀이 어떤 일을 해야
업무에 걸리는 시간을 최소화 할 수 있을까,효율적일까 이 것이 문제입니다.(따라서 목적함수식은 최소화)
저번시간에 노드와 아크의 개념들을 충분히 배우고 이해했기 때문에 위의 그림이 어떤 것을
의미하는지 알 수 있었습니다. 이번 문제에서는 origin node 부분이 일을 하는 팀에 해당되고
,destination node 부분이 task에 해당된다고 생각하시면 될 것 같습니다. 저번예제와 마찬가지로
이번 문제도 아크가 모두 활성화 되어있기 때문에 경우의수가 총 9개라는 것도 알 수 있었습니다.
그리고 위와같이 각각의 일을 수행하는데에 필요한 시간도 볼 수 있습니다.
저번시간과 마찬가지로 공급하는 쪽은 작거나같다로, 수요하는 쪽은 같다로 설정을 해야합니다.
(채택이 되면 1,안되면 0)
이러한 정보들로 위와같이 목적함수식과 제약조건식들을 만들 수 있습니다.
클라이언트1의 제약조건식은 X11+X21+X31=1 이렇게 고쳐야합니다.
2,3번은 따로 고칠 필요가 없습니다. 의사결정변수는 총 9개이고 앞의 계수는 각각의 걸리는 시간을 나타냅니다.
마지막으로 ms60을 돌리기위해 이런식으로 식을 맞춰주면 됩니다.
(실제 이동하는건 아니지만 일과 사람을 연결)
우선 ms60을 이용하기 전에 간단하게 결과표를 먼저 보겠습니다.
각각의 팀들이 어느 일에 할당이 되었는지 일을 완료하는데에 몇일이 걸리는지를 볼 수 있었습니다.(총26일)
저번시간에도 말을 했지만 여기서도 마찬가지로 DP등등 이런 민감도분석을 기계적으로 해석 할 필요가 전혀 없습니다.
사실상 실질적으로는Assignment 모듈을 사용하고 이렇게 LP로는 하지않습니다.
하지만 LP의 개념적인 부분들도 필요하기 때문에 하는 것입니다.
그럼 ms60을 이용해서 직접 결과를 보겠습니다.
개념을 알기위해 LP모듈을 먼저 이용해보겠습니다.
아까 결과표에서 잠시 봤지만 마찬가지로 목적함수값은 26이 나왔습니다.
그리고 이번 문제에서는 reduced cost나 DP같은 부분에 크게 신경 쓰지않아도 무관하다고 배웠습니다
.(수학적의미 밖에 없는 부분들도 많음, 기계적으로 해석 X)
이번에는 Assignment 모듈을 이용해보겠습니다.
한눈에 봐도 LP보다 간편하다는 것을 알 수 있었습니다.
LP로 돌렸을때와 동일한 값이 나왔습니다.
어떤팀이 어떤 일에 할당이 되었는지, 걸리는 시간은 얼마인지 등등
필요한 정보들만 보여줘서 좋았습니다.
이번 시간에도 문제의 변형에 대해 알아보겠습니다.
에이전트랑 일의 숫자가 일치하지 않는 경우
이번시간에도 마찬가지로 에이전트>일(예를들어 팀은 4개인데 일은 3개) 이런경우는 작거나 같다이기 때문에
LP에서나 Assignment에서나 큰 문제가 없습니다. 하지만 에이전트보다 일이 더 많으면 Assignment에서는
간단하게 해결이 가능하지만 LP에서는 저번시간에 배웠던 것 처럼 가상의 더미를 만들어서 문제를
해결해야합니다.(가상의 노드 하나를 만들어 프로그램을 속이는 방법)
2,3번 충분히 가능 3번은 예를들어 3번팀이 1번일을 할 수가 없다라는 제약이
생길경우 X31=0 와 같은 제약조건을 추가시켜주면 됩니다. 하지만 이러한 경우는 LP에서만 가능합니다.
그럼 에이전트보다 일이 더 많은 경우를 Assignment모듈로 바로 실험해보겠습니다. (Agent3개,Task4개)
edit을 이용해 task를 늘려주었습니다.
역시 Assignment모듈을 이용하면 이러한 부분도 편하게 문제 해결이 가능하다는 것을 알 수 있었습니다.(2번 task는 채택X)
첫댓글 Assignment모듈이 훨 편하지~