경영과학 13주차 2차시 & 14주차 2차시_Transshipment Problem

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

<시작 : Transshipment Problem>

이 케이스는 '환적 문제' 입니다.

환적 문제는 중간에 창고와 같이 환적하는 장소가 추가된 확장된 수송 문제 입니다.

환적 문제의 경우 일반적으로, 출발지 노드, 환적지 노드, 도착지 노드 총 3가지 타입의 노드로 구성되어 있습니다.

수송 문제와 마찬가지로 각각의 생산지에서의 생산량, 각각의 수요지에서의 수요량는 일반적으로 주어집니다.

환적 문제 역시 일반적으로 수송문 처럼 생산지에서 목적지까지 상품의 수송하는 비용을 최소화 하는 것이 목적이 됩니다.

상황 :

Ryan Electronics 가 현재 마주친 환적 문제에 대해 알아보도록 하겠습니다.

Ryan Electronics 는 Denver 와 Atlanta에 생산시설을 갖춘 전자제품 회사입니다.

두 생산지에서 생산된 제품은 Kansas City 혹은 Louisville 로 이동된 후, Detroit, Miami, Dallas, New Orleans 로 공급됩니다.

또한 각각의 노드에 대한 제약조건과 각각의 아크에 대한 변수가 필요합니다.

왜냐하면 이는 Transportation 문제와는 다르게 중간에 환적지 node가 얼마든지 갯수에 제한없이 존재할 수 있기 때문에

출발지 node 1,2,3,.. 그리고 도착지 node 1,2,3,... 으로 표시 할 수 없기 때문입니다.

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

<생산지와 생산량>

출발지	생산지	생산량
1	Denver	600
2	Atlanta	400
		합계 : 1000

<수요지와 수요량>

도착지	수요지	수요량
5	Detroit	200
6	Miami	150
7	Dallas	350
8	New Orleans	300
		합계 : 1000

<출발지-환적지 수송비>

출발지-환적지	생산지	환적지	수송비
x13	Denver	Kansas City	2
x14	Denver	Louisville	3
x23	Atlanta	Kansas City	3
x24	Atlanta	Louisville	1

<환적지-도착지 수송비>

환적지-도착지	환적지	도착지	수송비
x35	Kansas City	Detroit	2
x36	Kansas City	Miami	6
x37	Kansas City	Dallas	3
x38	Kansas City	New Orleans	6

환적지-도착지	환적지	도착지	수송비
x45	Louisville	Detroit	4
x46	Louisville	Miami	4
x47	Louisville	Dallas	6
x48	Louisville	New Orleans	5

위의 정리된 표와 함께 다음과 같이 환적지에서의 제약 조건을 추가적으로 고려해야 합니다.

이는 환적지에서의 출하되는 양은 입고되는 양이 같아야 한다는 것입니다.

이를 식으로 나타내면 이는 다음과 같으며 => out = in

이를 정리하면 식은 다음과 같습니다 => - in + out = 0

위의 경우를 통해 Kansas City 의 경우를 살펴보면 식은 다음과 같습니다.

x35 + x36 + x37 + x38 (출하되는 양) = x13 + x23 (입고되는 양)

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

따라 정리된 표와 환적지에서의 제약조건에 따라 식을 세우면 식을 다음과 같습니다.

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

s.t.

x13 + x14 <= 600

x23 + x24 <= 400

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

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

x35 +  x45 = 200

x36 + x46 = 150

x37 + x47 = 350

x38 + x48 = 300

목적함수식은 수송비를 최소화 하는 것입니다.

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

생산지에서의 생산량의 합계의 제한입니다.

x13 + x14 <= 600

x23 + x24 <= 400

환적지에서의 입고되는 양과 출하되는 양은 같아야 합니다.

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

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

수요지에서의 수요량을 만족시켜야 합니다.

x35 +  x45 = 200

x36 + x46 = 150

x37 + x47 = 350

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)  -1x13-1x23+1x35+1x36+1x37+1x38=0
       4)  -1x14-1x24+1x45+1x46+1x47+1x48=0
       5)  1x35+1x45=200
       6)  1x36+1x46=150
       7)  1x37+1x47=350
       8)  1x38+1x48=300

OPTIMAL SOLUTION

Objective Function Value =        5200.000

      Variable             Value             Reduced Costs   
   --------------     ---------------      ------------------ 
        x13                   550.000                   0.000
        x14                    50.000                   0.000
        x23                     0.000                   3.000
        x24                   400.000                   0.000
        x35                   200.000                   0.000
        x36                     0.000                   1.000
        x37                   350.000                   0.000
        x38                     0.000                   0.000
        x45                     0.000                   3.000
        x46                   150.000                   0.000
        x47                     0.000                   4.000
        x48                   300.000                   0.000


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

OBJECTIVE COEFFICIENT RANGES

   Variable       Lower Limit       Current Value     Upper Limit
 ------------   ---------------    ---------------  ---------------
     x13                  2.000              2.000            5.000
     x14                  1.000              3.000            3.000
     x23                  0.000              3.000   No Upper Limit
     x24         No Lower Limit              1.000            3.000
     x35         No Lower Limit              2.000            5.000
     x36                  5.000              6.000   No Upper Limit
     x37         No Lower Limit              3.000            7.000
     x38                  6.000              6.000   No Upper Limit
     x45                  1.000              4.000   No Upper Limit
     x46         No Lower Limit              4.000            5.000
     x47                  2.000              6.000   No Upper Limit
     x48         No Lower Limit              5.000            5.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                  0.000              0.000          550.000
       4                  0.000              0.000           50.000
       5                  0.000            200.000          200.000
       6                100.000            150.000          150.000
       7                  0.000            350.000          350.000
       8                250.000            300.000          300.000

목적함수 값에 따라 발생되는 최소 비용은 ＄5200 입니다.

이때 각 생산지에서 환적지로 보내야할 개수는 다음과 같습니다.

x13 : 550개 (출발지 : Denver, 환적지: Kansas City)

x14 : 50 개 (출발지 : Denver, 환적지: Louisville)

x24 : 400 개 (출발지 : Atlanta, 환적지: Louisville)

이때 각 환적지에서 목적지로 보내야할 개수는 다음과 같습니다.

- 환적지가 Kansas City 일 경우

x35 : 200 개 (환적지: Kansas City, 도착지 : Detroit)

x37 : 350 개 (환적지: Kansas City, 도착지 : Dallas)

- 환적지가 Louisville 일 경우

x46 : 150 개 (환적지: Louisville, 도착지 : Miami)

x48 : 300 개 (환적지: Louisville, 도착지 : New Orleans)

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

출발지	환적지	보내는 수량	각 수량의 비용	비용의 합계
Denver	Kansas City	550	＄2	＄1100
Denver	Louisville	50	＄3	＄150
Atlanta	Louisville	400	＄1	＄400
				＄1650

환적지	도착지	보내는 수량	각 수량의 비용	비용의 합계
Kansas City	Detroit	200	＄2	＄400
Kansas City	Dallas	350	＄3	＄1050
Louisville	Miami	150	＄4	＄600
Louisville	New Orleans	300	＄5	＄1500
				＄3550
＄1650 + ＄3550 = ＄5200

위의 결과 값을 토대로 이를 Network 형태로 나타내면 다음과 같습니다.

 위의 기본 문제에서 새로운 경로가 추가된 경우입니다.

Atlanta 에서 New Orleans 로 직접적으로 갈 수 있는 경로와, Dallas 에서 New Orleans로 갈 수 있는 경로가 열렸습니다.

따라 식에 변동이 생기며 변동되는 식만 정리하면 이는 다음과 같습니다.

기존의 목적함수 식에서 추가된 경로에 해당하는 변수를 추가해야 합니다.

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

       [+ 1*x78]

제약조건식에서 해당 경로에 해당하는 변수를 추가해야 합니다.

생산지에서 x28로 가는 경우를 추가해야 합니다.

x23 + x24 + x28<= 400

Dallas 에서 New Orleans로 가는 경우를 추가해야합니다.

x37 + x47 -x78= 350

New Orleans에서 Atlanta 에서 받는 경우와 Dallas 에서 받는 경우를 추가해야 합니다.

x38 + x48 + x28 + x78 = 300

따라 이를 추가하여 새롭게 완성된 식은 다음과 같습니다.

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

s.t.

x13 + x14 <= 600

x23 + x24 + x28<= 400

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

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

x35 +  x45 = 200

x36 + x46 = 150

x37 + x47 -x78= 350

x38 + x48 + x28 + x78 = 300

이를 MS60에 넣어 나온 결과값은 다음과 같습니다.

목적함수 값에 따라 발생되는 최소 비용은 ＄4600 입니다.

생산지에서 환적지로 가는 개수 와 비용

x13 : 600 개 => 600*2 = 1200

x24 : 150 개 => 150*1 = 150

누적 합계 : 1350

생산지에서 수요지로 가는 개수와 비용

x28 : 250 개 => 250*4 = 1000

누적 합계 : 2350

환적지에서 수요지로 가는 개수와 비용

x35 : 200 개 => 200*2 = 400

x37 : 400 개 => 400*3 = 1200

x46 : 150 개 => 150*4 = 600

누적 합계 : 4550

수요지에서 수요지로 가는 개수와 비용

x78 : 50 개 => 50*1 = 50

누적 합계 : 4600

이는 예제로 나온 경우와 Solution 이 다릅니다.

하지만 이 역시 Opitmal Objective Value 가 4600 인 것을 통해 Multiple Solution 인 것을 알 수 있습니다.

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

목적함수 값에 따라 발생되는 최소 비용은 ＄4600 

생산지에서 환적지로 가는 개수 와 비용

x13 : 550 개 => 550*2 = 1100

x14 : 50 개 => 50*3 = 150

x24 : 100 개 => 100*1 = 100

누적 합계 : 1350

생산지에서 수요지로 가는 개수와 비용

x28 : 300 개 => 300*4 = 1200

누적 합계 : 2550

환적지에서 수요지로 가는 개수와 비용

x35 : 200 개 => 200*2 = 400

x37 : 350 개 => 350*3 = 1050

x46 : 150 개 => 150*4 = 600

누적 합계 : 4600

위의 Multiple Solution을 Network 형태로 나타내면 다음과 같습니다.

수송 문제와 같이 환적 문제도 다음과 같이 문제의 변형이 가능합니다.

문제의 변형은 다음과 같습니다.

1. 총 공급량과 총 수요량이 같지 않은 경우

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

3. 해당 경로로 보낼 때 최소한의 양이 존재할 경우

4. 제한되는 경로가 있을 경우

문제의 변형을 하는 방법은 수송 문제와 동일하게 진행됩니다.

수송 문제와 환적 문제를 통해 실질적으로는 이동이 없는 경우에도 응용해서 이용이 가능합니다.

따라 제품 및 재고 문제를 이를 통해 해결하도록 하겠습니다.

상황 :

Contois Carpets 은 가정 및 사무실에서 사용되는 카펫을 제조하는 소규모 제조업체입니다.

회사에서는 향후 4분기의 생산량, 수요량, 생산원가, 재고유지비용을 측정하였습니다.

따라 생산량, 수요량, 생산원가 는 각각 다르지만 재고유지비용은 ＄0.25로 일정한 것으로 측정되었습니다.

이때 Contois Carpets은 4분기 동안 총 생산원가와 재고유지비용을 최소화 하기 위해

각 분기에 얼마만큼의 카펫을 생산할지 결정하고자 합니다.

측정된 생산량 ,수요량, 생산원가, 재고유지비용을 정리하면 이는 다음과 같습니다.

분기	제품 생산량 (제곱 야드 당)	제품 수요량 (제곱 야드 당)	생산 원가 (＄/제곱 야드 당)	재고유지비용 (＄/제곱 야드 당)
1	600	400	2	0.25
2	300	500	5	0.25
3	500	400	3	0.25
4	400	400	3	0.25
제품 생산량의 합 : 1800		제품 수요량의 합 : 1700

이를 Network 형태로 나타내면 이는 다음과 같습니다.

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

<각 분기당 생산량>

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

<각 분기당 수요량>

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

<각 분기당 생산원가>

분기-분기 (Node_num 기준으로)	분기	분기	생산원가
x15	1	1	2
x26	2	2	5
x37	3	3	3
x48	4	4	3

<각 분기당 재고유지비용>

분기-분기 (Node_num 기준으로)	분기(보관 시작)	분기(보관 끝)	재고유지비용
x56	1	2	＄0.25
x67	2	3	＄0.25
x78	3	4	＄0.25

위에 표와 함께 재고가 필요한 경우를 고려해야 하는데 이는 다음과 같습니다.

각 분기에서 받는 양 = 각 분기의 수요량 + 다음 분기로 이월될 재고 (+ 이전 분기에서 받은 재고)

1분기의 경우

x15 (각 분기에서 받는양) = 400 (각 분기의 수요량) + x56 (다음 분기로 이월될 재고)

x15 -x56 = 400

1분기 외 분기의 경우

x56 (이전 분기에서 받은 재고) + x26 (각 분기에서 받는양) = 500 (각 분기의 수요량) + x67 (다음 분기로 이월될 재고)

따라 위의 표와 재고가 필요한 경우를 고려하여 만들어지는 식은 다음과 같습니다.

MIN 2*x5 + 5*26 + 3*x37 + 3*x48 + 0.25*x56 + 0.25*x67 + 0.25*x78

s.t.

x15 <= 600

x26 <= 300

x37 <= 500

x48 <= 400

x15 -x56 = 400

x26 + x56 -x67 = 500

x37 +x67 -x78 = 400

x48 +x78 = 400

xij >= 0 (for all i and j)

목적함수식의 경우 최소의 비용을 구하는 것이 됩니다. (각 분기의 생산원가 + 이월될 경우의 재고유지비용)

MIN 2*x5 + 5*26 + 3*x37 + 3*x48 + 0.25*x56 + 0.25*x67 + 0.25*x78

제약조건식의 경우 다음과 같습니다.

최대 생산량은 넘을 수 없다.

x15 <= 600

x26 <= 300

x37 <= 500

x48 <= 400

각 분기에서 받는 양 = 각 분기의 수요량 + 다음 분기로 이월될 재고 (+이전 분기에서 받은 재고)

x15 -x56 = 400

x26 + x56 -x67 = 500

x37 +x67 -x78 = 400

x48 +x78 = 400

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

이를 실행시킨 결과 값은 다음과 같습니다.

최소 필요한 비용은 ＄5150 입니다.

이때 각 분기에 생산해야 되는 개수는 다음과 같습니다.

x15 : 600 개 (1분기 : 400개 해당 분기 수요량, 200개 보관)

x26 : 300 개 (2분기 : 300개 해당 분기 수요량)

x37 : 400 개 (3분기 : 400개 해당 분기 수요량)

x48 : 400 개 (4분기 : 400개 해당 분기 수요량)

이에 따른 가격은 다음과 같습니다.

-생산원가

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

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

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

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

누적 합계 : ＄5100

-재고유지비용

x56 : 200 개 => 200*0.25 = ＄50

누적합계 : ＄5150

[현승용]

마지막까지 마무리 하고 싶은거구나.