경영과학 13주차 1차시_Assignment Problem

[최승현(스마트헬스케어)]

<시작 : Assignment Problem>

이 케이스는 '할당 문제' 입니다.

할당 문제는 다양한 의사 결정 상황에서 발생합니다.

해당 문제가 발생되는 일반적인 상황은 다음과 같습니다.

(기계에 작업을 할당할 때, 에이전트에 작업을 할당할 때, 판매 직원에게 판매 영역을 결정할 때, 계약자에게 입찰할 때 등)

할당 문제의 특징은 하나의 작업에 하나의 에이전트가 할당되는 것입니다.

특히 비용 최소화, 시간 최소화, 수익 최대화 등에서 최적의 결과를 도출할 때 사용됩니다.

이제 할당 문제의 하나의 케이스에 대해서 살펴보도록 하겠습니다

상황 :

3명의 신규 고객으로부터 Fowle Marketing Research 는  시장 조사를 의뢰 받았습니다.

- 회사는 각 클라이언트 (과제)에 프로젝트 리더 (에이전트) 를 할당해야 하는 상황입니다.

- 각 세 명의 후보자는 다른 클라이언트는 존재하지 않으며, 이들을 각 프로젝트의 리더로 선정해야 합니다.

- 각 시장 조사를 끝나는데 걸리는 시간은 각각의 경험과 능력에 따라 달라집니다.

- 세 프로젝트의 우선 순위는 거의 차이가 없으며, CEO는 최대한 빠르게 끝내는 것을 원합니다.

- 하나의 프로젝트에는 한 명만 할당이 가능합니다. 

Fowle의 경영진은 모든 프로젝트에 인원을 배치했을 때, 각각의 상황에 따른 결과를 추정한 후 최종 결정을 하고자 합니다.

3명의 프로젝트 리더와 3명의 고객일 경우,  총 9가지의 경우의 수가 발생합니다. 이는 다음과 같습니다.

		Client
Project Leader	1	2	3
1. Terry	10	15	9
2. Carle	9	18	5
3. McClymonds	6	14	3

위와 같은 상황을 네트워크 형태로 나타내면 이는 다음과 같습니다.

이를 식으로 세우면 식은 다음과 같습니다.

Min 10*x11 + 15*x12 + 9*x13 + 9*x21 + 18*x22 + 5*x23 + 6*x31 + 14*x32 + 3*x33

s.t.

x11 + x12 + x13 <= 1

x21 + x22 + x23 <= 1

x31 + x32 + x33 <= 1

x11 + x21 + x31 = 1

x12 + x22 + x32 = 1

x13 + x23 + x33 =1

xij >= 0 (for i = 1,2,3, and j = 1,2,3)

-목적함수식

Min 10*x11 + 15*x12 + 9*x13 + 9*x21 + 18*x22 + 5*x23 + 6*x31 + 14*x32 + 3*x33

발생되는 시간을 최소화하는 것이기에 목적함수식은 각 시간의 합이 최소화가 목적이 되는 것이므로 식은 위와 같습니다.

-제약조건식

x11 + x12 + x13 <= 1 // x21 + x22 + x23 <= 1 // x31 + x32 + x33 <= 1 

각자 하나의 업무에만 할당 될 수 있습니다.

x11 + x21 + x31 = 1 // x12 + x22 + x32 = 1 // x13 + x23 + x33 =1

하나의 업무에는 한 명 만 할당 될 수 있습니다.

이를 MS60의 'Linear Programming' 에 넣으면 다음과 같습니다.

위의 식의 결과는 다음과 같습니다.

LINEAR PROGRAMMING PROBLEM

MIN 10x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33

     S.T.

       1)  1x11+1x12+1x13<1
       2)  1x21+1x22+1x23<1
       3)  1x31+1x32+1x33<1
       4)  1x11+1x21+1x31=1
       5)  1x12+1x22+1x32=1
       6)  1x13+1x23+1x33=1

OPTIMAL SOLUTION

Objective Function Value =          26.000

      Variable             Value             Reduced Costs   
   --------------     ---------------      ------------------ 
        x11                     0.000                   0.000
        x12                     1.000                   0.000
        x13                     0.000                   3.000
        x21                     0.000                   0.000
        x22                     0.000                   4.000
        x23                     1.000                   0.000
        x31                     1.000                   0.000
        x32                     0.000                   3.000
        x33                     0.000                   1.000


     Constraint        Slack/Surplus           Dual Prices    
   --------------     ---------------      ------------------
         1                      0.000                   0.000
         2                      0.000                   1.000
         3                      0.000                   4.000
         4                      0.000                 -10.000
         5                      0.000                 -15.000
         6                      0.000                  -6.000

OBJECTIVE COEFFICIENT RANGES

   Variable       Lower Limit       Current Value     Upper Limit
 ------------   ---------------    ---------------  ---------------
     x11                  9.000             10.000           13.000
     x12         No Lower Limit             15.000           18.000
     x13                  6.000              9.000   No Upper Limit
     x21                  8.000              9.000           10.000
     x22                 14.000             18.000   No Upper Limit
     x23         No Lower Limit              5.000            6.000
     x31         No Lower Limit              6.000            7.000
     x32                 11.000             14.000   No Upper Limit
     x33                  2.000              3.000   No Upper Limit


RIGHT HAND SIDE RANGES

  Constraint      Lower Limit       Current Value     Upper Limit
 ------------   ---------------    ---------------  ---------------
       1                  1.000              1.000   No Upper Limit
       2                  1.000              1.000            1.000
       3                  1.000              1.000            1.000
       4                  1.000              1.000            1.000
       5                  0.000              1.000            1.000
       6                  1.000              1.000            1.000

목적함수 값은 26으로 최소 26일이 걸린다는 것을 의미합니다.

이때 X12, X23, X31 이 채택된 것을 통해, Terry-2client, Carle-3client, McClymonds-1client 가 할당된 것을 알 수 있습니다.

이를 Assignmnet 에 넣으면 다음과 같습니다.

이의 결과는 다음과 같습니다.

최소 시간은 동일하게 26시간, 그리고 이 역시 동일하게 X12, X23, X31이 채택된 것을 통해,

Terry-2client, Carle-3client, McClymonds-1client 가 할당된 것을 알 수 있습니다.

이를 표로 정리하면 이는 다음과 같습니다.

<문제의 변형>

할당 문제의 특별한 경우는 수송 문제의 특별한 경우로 볼 수 있기에

할당 문제에서의 특수한 상황은 수송 문제의 특수한 상황과 비슷합니다.

문제의 변형은 다음과 같이 가능합니다.

1. 총 에이전트(공급량)의 수가 총 업무(수요량)의 양이 같지 않은 경우

2. 목적 함수를 최대화할 경우

3. 제한되는 업무가 있을 경우

이를 차례대로 살펴보도록 하겠습니다.

1. 총 에이전트(공급량)의 수가 총 업무(수요량)의 양이 같지 않은 경우

총 에이전트(공급량)의 수가 총 업무(수요량)의 양이 같지 않은 경우는 또 다시 2가지의 경우를 생각해 볼 수 있습니다.

1. 총 에이전트의 수 > 총 업무의 양 / 2. 총 에이전트의 수 < 총 업무의 양

1-1. 총 에이전트의 수 > 총 업무의 양

위의 기본 문제에서 에이전트를 한 명 추가하겠습니다.

	Client
Project Leader	1	2	3
1. Terry	10	15	9
2. Carle	9	18	5
3. McClymonds	6	14	3
4. Jack	7	16	4

이를 식으로 세우면 식은 다음과 같습니다.

기존의 목적함수식에 Jack을 추가해줍니다.

Min     10*x11 + 15*x12 + 9*x13 + 9*x21 + 18*x22 + 5*x23 + 6*x31 + 14*x32 + 3*x33

       + 7*x41+16*x42+4*x43

제약 조건식에는 

Jack 이 업무를 할당받았을 경우의 제약 조건식

x41 + x42 + x43 <= 1

그리고 

각 업무에 다음과 같은 형태로 Jack이 할당 받을 경우를 추가해 줍니다.

x11 + x21 + x31 + x41= 1

이에 완성된 식은 다음과 같습니다.

Min     10*x11 + 15*x12 + 9*x13 + 9*x21 + 18*x22 + 5*x23 + 6*x31 + 14*x32 + 3*x33

       + 7*x41+16*x42+4*x43

s.t.

x11 + x12 + x13 <= 1

x21 + x22 + x23 <= 1

x31 + x32 + x33 <= 1

x41 + x42 + x43 <= 1

x11 + x21 + x31 +x 41 = 1

x12 + x22 + x32 + x42 = 1

x13 + x23 + x33 + x43 =1

xij >= 0 (for i = 1,2,3,4 and j = 1,2,3)

결과 값은 다음과 같습니다.

최소 25일이 필요하며, 

이때 x12, x31, x43 이 채택된 것을 통해, Terry-2client, McClymonds-1client, , Jack-3client 이 할당 받았고

Carle 가 업무를 할당받지 못한 것을 알 수 있습니다.

이를 Assignment 로 나타내면 이는 다음과 같습니다.

이에 대한 결과값은 다음과 같습니다.

최소 25일이 필요하며, 

이때 x12, x33, x41 이 채택된 것을 통해, Terry-2client, McClymonds-3client, , Jack-1client 이 할당 받았고

Carle 가 업무를 할당받지 못한 것을 알 수 있으며, 위와 같은 25일이 걸리지만 이는 Multiple Solution 인 것을 알 수 있습니다.

1-2. 총 에이전트의 수 < 총 업무의 양

위의 기본 문제에서 업무를 하나 추가시켰습니다.

	Client
Project Leader	1	2	3	4
1. Terry	10	15	9	10
2. Carle	9	18	5	8
3. McClymonds	6	14	3	7

이를 Assignment 로 나타내면 이는 다음과 같습니다.

이에 대한 결과값은 다음과 같습니다.

총 21 일이 요구되며, 

이때 x11, x24, x33이 할당된것을 통해 2번 고객의 업무를 하지 못했다고 알려줍니다.

Linear Programming으로 나타내면 이는 다음과 같습니다.

하지만 이 경우에는 Input 과 Output 의 값이 동일하지 않기에 오류가 발생됩니다. 

따라 이를 해결하기 위해서는 앞서 수송 문제와 같이 Dummy 가 필요합니다.

수송 문제와 같이 부족한 인원을 Dummy로 할당시키면 결과 값을 얻을 수 있습니다.

이를 식으로 나타내면 다음과 같습니다.

Min     10*x11 + 15*x12 + 9*x13 + 4*x14 + 9*x21 + 18*x22 + 5*x23 + 8*x24 + 6*x31 + 14*x32 + 3*x33 + 7*x34

       (+ 0*d11 + 0*d12 + 0*d13 + 0*d14) 

s.t.

x11 + x12 + x13 + x14 <= 1

x21 + x22 + x23 + x14 <= 1

x31 + x32 + x33 + x14 <= 1

d11 + d12 + d13 + d14 <= 1

x11 + x21 + x31 + d11 = 1

x12 + x22 + x32 + d12 = 1

x13 + x23 + x33 + d13 =1

x14 + x24 + x34 + d14 =1

xij >= 0 (for i = 1,2,3,4 and j = 1,2,3,4)

MIN 10*x11 + .... + (+0*d11 +0*d12 + 0*d13 + 0*d14) 를 통해 Dummy 부분이 추가 되었습니다.

하지만 이는 dummy 이기에 실제 값에 영향을 미치면 안되기에 생략해도 되는 부분입니다.

d11 + d12 + d13 + d14 <= 1

부족한 인원인 1만큼 dummy 에 할당되었습니다.

x11 + x21 + x31 + d11 = 1

x12 + x22 + x32 + d12 = 1

x13 + x23 + x33 + d13 =1

x14 + x24 + x34 + d14 =1

dummy가 각각의 업무의 제약조건에 추가되었습니다.

이의 결과 값은 다음과 같습니다.

총 21 일이 요구되며,

이때 x11, x24, x33, d2 를 통해 dummy 가 2번의 업무를 할당 받음으로 2번 고객의 업무를 하지 못하는 것을 알 수 있습니다.

2. 목적 함수를 최대화할 경우

위의 기본 문제에서 동일한 값을 갖고 있지만 걸리는 시간이 아닌 수익일 경우로 가장하겠습니다..

Assignment 로 나타내면 이는 다음과 같습니다.

총 수익은 33이 발생한 것과

이때 x13, x22, x31 에 할당된 것 을 통해 Terry-3Client, Carle-2Client, McClymonds-1Client 에 할당된 것을 알 수 있습니다.

이를 Linear Programming 으로 나타내면 결과값은 다음과 같습니다.

이 역시 동일하게 총 수익은 33이 발생한 것과

이때 x13, x22, x31 에 할당된 것 을 통해 Terry-3Client, Carle-2Client, McClymonds-1Client 에 할당된 것을 알 수 있습니다.

3. 제한되는 업무가 있을 경우

기본적인 문제에서 최소 시간은 26시간,

X12, X23, X31이 채택된 것을 통해 Terry-2client, Carle-3client, McClymonds-1client 가 할당된 것을 알 수 있습니다.

따라 기존의 채택되었던 x23을 제한시키도록 하겠습니다.

다음과 같은 기존의 제약 조건식에서

x13 + x23 + x33  =1

다음과 같이 x23의 항목만 제거해주면 됩니다. 

위의 제약조건을 적용한 결과 값은 다음과 같습니다.

발생되는 최소 시간은 27시간으로 기존의 26시간으로 1시간 증가했습니다.

X12, X21, X33이 채택된 것을 통해 Terry-2client, Carle-1client, McClymonds-3client 가 할당된 것을 알 수 있습니다.

[현승용]

거의 다 와 가는구나.