경영과학 15주차 1차시 복습_Transshipment Problem (2)

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

<시작 : Transshipment Problem (2)>

다음과 같은 문제를 Transshipment 로 해결하였다.

그렇다면 이를 어떻게 Transportation으로 해결할 수 있을까?

1. 먼저 Transportation 의 경우 존재할 수 없는 부분을 제거해준다.

2. Tranportation에 맞게 Orgin 과 Destination Node의 숫자를 변경해준다

3. Transportation 형식으로 변경하기 위해 지워진 길이 아예 사라져서는 안된다. 

따라 이를 다시 Transportation의 형식을 반영해준다.

(단, 해당 문제에서는 시간의 흐름에 따라 이월되는 경우이다. 이는 미래 분기에서 과거 분기로 줄 수 없음을 제한해야 한다.)

위의 그림의 정보를 이제 다음과 같이 정리 할 수 있다.

<생산 분기와 생산량>

Node_num	생산 분기	생산량
1	1	600
2	2	300
3	3	500
4	4	400
		합계 : 1800

<수요량과 수요분기>

Node_num	수요 분기	수요량
1	1	400
2	2	500
3	3	400
4	4	400
		합계 : 1700

<생산분기-수요분기 생산비>

생산 분기-수요 분기	생산 분기	수요 분기	생산비
x11	1	1	2
x12	1	2	2.25
x13	1	3	2.50
x14	1	4	2.75
x22	2	2	5
x23	2	3	5.25
x24	2	4	5.50
x33	3	3	3
x34	3	4	3.25
x44	4	4	3

 위에 따라 식을 세우면 식은 다음과 같습니다.

MIN 2*x11 + 2.25*x12 + 2.50*x13 + 2.75*x14 + 5*x22 + 5.25*x23 + 5.50*x24 + 3*x33 + 3.25*x34 + 3*x44

s.t.

x11 + x12 + x13 + x14 <= 600

x22 + x23 + x24 <= 300

x33 + x34 <= 500

x44 <= 400

x11 = 400

x12 + x22 = 500

x13 + x23 + x33 = 400

x14 + x24 + x34 + x44 = 400

xij >= 0 (for all i & j)

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

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

최소 비용은 ＄5150 입니다.

각 생산분기-수요분기의 개수는 다음과 같습니다.

x11 = 400 개 (생산 분기 : 1, 수요 분기 : 1)

x12 = 200 개 (생산 분기 : 1, 수요 분기 : 2)

x22 = 300 개 (생산 분기 : 2, 수요 분기 : 2)

x33 = 400 개 (생산 분기 : 3, 수요 분기 : 3)

x44 = 400 개 (생산 분기 : 4, 수요 분기 : 4)

이에 따른 비용은 다음과 같습니다.

x11 = 400 개 => 400*2 = ＄800

x12 = 200 개 => 200*2.25 = ＄450

x22 = 300 개 => 300*5 = ＄1500

x33 = 400 개 => 400*3 = ＄1200

x44 = 400 개 => 400*3 = ＄1200

합계 : ＄5150

이는 기존의 transshipment와 동일한 결과를 보인다는 것을 알 수 있습니다.

<문제의 변형 中 총 공급량과 총 수요량이 같지 않을 경우>

Transshipment의 변형 中 총 공급량과 총 수요량이 같지 않을 경우 입니다.

이때는 기존의 Transportation의 Linear Programming 에서 dummy 를 이용한 것 처럼

Transshipment 역시 dummy를 이용하여야 합니다.

이때의 식은 다음과 같습니다.

MIN    2*x13 + 3*x14 + 3*x23 + 1*x24 +(+0*d93 + 0*d94)

       + 2*x35 + 6*x36 + 3*x37 + 6*x38 + 4*x45 + 4*x46 + 6*x47 + 5*x48 

s.t.

x13 + x14 <= 600

x23 + x24 <= 400

d93 + d94 <= 50

-x13 -x23 -d93 + x35 + x36 + x37 + x38 = 0

-x14 -x24 -d94 + x45 + x46 + x47 + x48 = 0

x35 +  x45 = 200

x36 + x46 = 150

x37 + x47 = 400

x38 + x48 = 300

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

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

LINEAR PROGRAMMING PROBLEM

MIN 2x13+3x14+3x23+1x24+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48

     S.T.

       1)  1x13+1x14<600
       2)  1x23+1x24<400
       3)  1d93+1d94<50
       4)  -1x13-1x23-1d93+1x35+1x36+1x37+1x38=0
       5)  -1x14-1x24-1d94+1x45+1x46+1x47+1x48=0
       6)  1x35+1x45=200
       7)  1x36+1x46=150
       8)  1x37+1x47=400
       9)  1x38+1x48=300

OPTIMAL SOLUTION

Objective Function Value =        5300.000

      Variable             Value             Reduced Costs   
   --------------     ---------------      ------------------ 
        x13                   600.000                   0.000
        x14                     0.000                   1.000
        x23                     0.000                   2.000
        x24                   400.000                   0.000
        d93                     0.000                   0.000
        d94                    50.000                   0.000
        x35                   200.000                   0.000
        x36                     0.000                   2.000
        x37                   400.000                   0.000
        x38                     0.000                   1.000
        x45                     0.000                   2.000
        x46                   150.000                   0.000
        x47                     0.000                   3.000
        x48                   300.000                   0.000


     Constraint        Slack/Surplus           Dual Prices    
   --------------     ---------------      ------------------
         1                      0.000                   0.000
         2                      0.000                   1.000
         3                      0.000                   2.000
         4                      0.000                   2.000
         5                      0.000                   2.000
         6                      0.000                  -4.000
         7                      0.000                  -6.000
         8                      0.000                  -5.000
         9                      0.000                  -7.000

OBJECTIVE COEFFICIENT RANGES

   Variable       Lower Limit       Current Value     Upper Limit
 ------------   ---------------    ---------------  ---------------
     x13                  1.000              2.000            3.000
     x14                  2.000              3.000   No Upper Limit
     x23                  1.000              3.000   No Upper Limit
     x24         No Lower Limit              1.000            2.000
     d93                 -1.000              0.000            1.000
     d94                 -1.000              0.000            1.000
     x35         No Lower Limit              2.000            4.000
     x36                  4.000              6.000   No Upper Limit
     x37         No Lower Limit              3.000            6.000
     x38                  5.000              6.000   No Upper Limit
     x45                  2.000              4.000   No Upper Limit
     x46         No Lower Limit              4.000            6.000
     x47                  3.000              6.000   No Upper Limit
     x48         No Lower Limit              5.000            6.000


RIGHT HAND SIDE RANGES

  Constraint      Lower Limit       Current Value     Upper Limit
 ------------   ---------------    ---------------  ---------------
       1                600.000            600.000   No Upper Limit
       2                400.000            400.000          450.000
       3                 50.000             50.000          650.000
       4                  0.000              0.000          600.000
       5                  0.000              0.000           50.000
       6                  0.000            200.000          200.000
       7                100.000            150.000          150.000
       8                  0.000            400.000          400.000
       9                250.000            300.000          300.000

총 비용은 ＄5300 이 발생하였습니다. 

하지만 이는 실제 값이 아닌 것을 유의하여야 합니다.

왜냐하면 처음 dummy가 환적지로 갈 경우의 비용은 차감되었지만,

환적지에서 수요지로 갈 때의 dummy 의 가격은 차감이 되지 않았기 때문입니다.

따라 각각의 개수와 dummy의 흐름을 따라가 보도록 하겠습니다.

이때 각각에 보내진 개수는 다음과 같습니다.

x13 : 600 개

x24 : 400 개

d94 : 50 개

x35 : 200 개

x37 : 400 개

x46 : 150 개

x48 : 300 개

이때 dummy의 경우 4번 환적지로만 흘러갔습니다. 따라 3번 환적지를 거쳐가는 경우는 제외해줍니다.

x24 : 400 개

d94 : 50 개

x46 : 150 개

x48 : 300 개

이제 이 상태에서 각각의 비용 中 4번 환적지에서 출고된 경우의 비용을 확인해줍니다.

x46 의 경우 개당 ＄4의 운송비가 발생되고

x48 의 경우 개당 ＄5의 운송비가 발생됩니다

즉 개당 가격은 x48 > x46 인 것을 알 수 있습니다.

우리의 목적은 비용을 최소화 하는 경우 입니다.

따라 x48 개수 300개에서 50개를 차감시켜야만 실제 가격을 구할 수 있습니다.

(만약 이 경우가 수익이라서 최대를 구한다면, x46에서 50개를 차감시켜야 합니다)

dummy가 제거되지 않았을 때 입니다.

x13 : 600 개 => 600*2 = ＄1200

x24 : 400 개 => 400*1 =＄400

d94 : 50 개 => 50*0 = ＄0

x35 : 200 개 => 200*2 = ＄400

x37 : 400 개 => 400*3 = ＄1200

x46 : 150 개 => 150*4 = ＄600

x48 : 300 개 => 300*5 = ＄1500

합계 : ＄5300

dummy가 제거되었을 경우 입니다.

x13 : 600 개 => 600*2 = ＄1200

x24 : 400 개 => 400*1 =＄400

x35 : 200 개 => 200*2 = ＄400

x37 : 400 개 => 400*3 = ＄1200

x46 : 150 개 => 150*4 = ＄600

x48 : 250 개 => 250*5 = ＄1250

합계 : ＄5050

＄250 만큼 비용이 차감되었습니다.

따라 Transshipment Problem 일때,

dummy 가 있다면 해당 dummy 의 흐름을 따라 차감되지 않은 가격이 없는지 확인하는 절차가 추가적으로 필요합니다.

[현승용]

막판에 한꺼번에 게시글을 올린건 아쉽지만 수고 많았다.