경영과학 11주차 2차시 & 12주차 2차시_Transportation Problem

<시작 : Transportation Problem><div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/a7e606926be78ef1659a504b48f9fe2c03d69487_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/a7e606926be78ef1659a504b48f9fe2c03d69487_re_1655573881223" data-origin-width="723" data-origin-height="422"></div>이 모델들은 network flow 란 LP 중 특수한 경우입니다.예시로는 공급망 문제, 수송 문제, 환적 문제, 할당 문제, 최단 경로 문제, 흐름 최대량 문제 등이 있습니다.각각의 경우에 network 형태로 어떻게 문제가 진행되는지 보여주고 프로그램으로 해결법을 제시하도록 합니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/08374d3ec519229f6629a356c2d0b41a1da37b7e_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/08374d3ec519229f6629a356c2d0b41a1da37b7e_re_1655573881223" data-origin-width="713" data-origin-height="344"></div>공급망 문제는 제품의 생산 및 배포와 관련된 연결 상황의 문제를 설명합니다.일반적으로 공급망의 경우 최소의 비용으로 모든 고객의 요구를 만족시키는 방향으로 설계되어 있습니다.따라 공급망에 대해 결정할 경우 제품을 어디에서 생산할지, 얼마를 생산할지, 어디로 보내야 할지 등의 결정을 내리게 됩니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/3bbb801b50dd04cb3048e6cebb0c78c9fc4d0e82_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/3bbb801b50dd04cb3048e6cebb0c78c9fc4d0e82_re_1655573881223" data-origin-width="726" data-origin-height="397"></div>수송 문제는물건을 공급할 수 있는 생산지가 여러 장소이며,상품 및 서비스를 받을 수요지가 여러 장소 일 때 이를 계획하기 위해 주로 사용됩니다. 각각의 생산지에서 생산 할 수 있는 상품의 개수, 각각의 수요지에서 필요한 상품의 개수는 일반적으로 주어집니다. 일반적으로 생산지에서 목적지까지 상품의 수송하는 비용을 최소화하는 것이 목적이 됩니다. <div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/679c28ddce6f663694d5d1a26fdc42c1036c8665_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/679c28ddce6f663694d5d1a26fdc42c1036c8665_re_1655573881223" data-origin-width="666" data-origin-height="152"></div>상황 :Foster Genrator가 현재 마주친 수송 문제에 대해 알아보도록 하겠습니다.이 문제는 3개의 공장(생산지)에서 4개의 유통센터(수요지)로 제품을 수송하는 문제입니다. <div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/af6cfa87da3c16fae49963c6d6651b46b4f7b4c5_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/af6cfa87da3c16fae49963c6d6651b46b4f7b4c5_re_1655573881223" data-origin-width="1125" data-origin-height="648"></div>문제를 네트워크 형태로 나타내면 위와 같습니다. 이러한 그래프의 형태를 '네트워크' 라고 부릅니다.각각의 원을 'Node' 라고 부르고, 각각의 연결된 선을 'arcs' 라고 부릅니다.node에서 또 다른 node로 흘러가는 방향(출발지에서 도착지까지)은 화살표로 표시됩니다. 위의 그림의 정보를 다음과 같이 정리할 수 있습니다. <생산지와 생산량><div class="table-wrap"><table data-ke-type="table" data-ke-align="alignCenter" style="width: 100%;" border="1"><tbody><tr><td style="width: 33.3333%;">출발지</td><td style="width: 33.3333%;">생산지</td><td style="width: 33.3333%;">생산량</td></tr><tr><td style="width: 33.3333%;">1</td><td style="width: 33.3333%;">Cleveland</td><td style="width: 33.3333%;">5,000</td></tr><tr><td style="width: 33.3333%;">2</td><td style="width: 33.3333%;">Bedford</td><td style="width: 33.3333%;">6,000</td></tr><tr><td style="width: 33.3333%;">3</td><td style="width: 33.3333%;">York</td><td style="width: 33.3333%;">2,500</td></tr><tr><td style="width: 66.6666%;" colspan="2"></td><td style="width: 33.3333%;">합계 : 13,500</td></tr></tbody></table></div><수요지와 수요량><div class="table-wrap"><table data-ke-type="table" data-ke-align="alignCenter" style="width: 100%;" border="1"><tbody><tr><td style="width: 33.3333%;">도착지</td><td style="width: 33.3333%;">수요지</td><td style="width: 33.3333%;">수요량</td></tr><tr><td style="width: 33.3333%;">1</td><td style="width: 33.3333%;">Boston</td><td style="width: 33.3333%;">6,000</td></tr><tr><td style="width: 33.3333%;">2</td><td style="width: 33.3333%;">Chicago</td><td style="width: 33.3333%;">4,000</td></tr><tr><td style="width: 33.3333%;">3</td><td style="width: 33.3333%;">St. Louis</td><td style="width: 33.3333%;">2,000</td></tr><tr><td style="width: 33.3333%;">4</td><td style="width: 33.3333%;">Lexington</td><td style="width: 33.3333%;">1,500</td></tr><tr><td style="width: 66.6666%;" colspan="2"></td><td style="width: 33.3333%;">합계 : 13,500</td></tr></tbody></table></div><출발지-수요지 수송비><div class="table-wrap"><table data-ke-type="table" data-ke-align="alignCenter" style="width: 100%; height: 90px;" border="1"><tbody><tr style="height: 18px;"><td style="width: 25%; height: 18px;">출발지-도착지</td><td style="width: 25%; height: 18px;">생산지</td><td style="width: 25%; height: 18px;">수요지</td><td style="width: 25%; height: 18px;">수송비</td></tr><tr style="height: 18px;"><td style="width: 25%; height: 18px;">x11</td><td style="width: 25%; height: 18px;">Cleveland</td><td style="width: 25%; height: 18px;">Boston</td><td style="width: 25%; height: 18px;">3</td></tr><tr style="height: 18px;"><td style="width: 25%; height: 18px;">x12</td><td style="width: 25%; height: 18px;">Cleveland</td><td style="width: 25%; height: 18px;">Chicago</td><td style="width: 25%; height: 18px;">2</td></tr><tr style="height: 18px;"><td style="width: 25%; height: 18px;">x13</td><td style="width: 25%; height: 18px;">Cleveland</td><td style="width: 25%; height: 18px;">St. Louis</td><td style="width: 25%; height: 18px;">7</td></tr><tr style="height: 18px;"><td style="width: 25%; height: 18px;">x14</td><td style="width: 25%; height: 18px;">Cleveland</td><td style="width: 25%; height: 18px;">Lexington</td><td style="width: 25%; height: 18px;">6</td></tr></tbody></table></div><div class="table-wrap"><table data-ke-type="table" data-ke-align="alignLeft" style="width: 100%;" border="1"><tbody><tr><td style="width: 25%;">출발지-도착지</td><td style="width: 25%;">생산지</td><td style="width: 25%;">수요지</td><td style="width: 25%;">수송비</td></tr><tr><td style="width: 25%;">x21</td><td style="width: 25%;">Bedford</td><td style="width: 25%;">Boston</td><td style="width: 25%;">7</td></tr><tr><td style="width: 25%;">x22</td><td style="width: 25%;">Bedford</td><td style="width: 25%;">Chicago</td><td style="width: 25%;">5</td></tr><tr><td style="width: 25%;">x23</td><td style="width: 25%;">Bedford</td><td style="width: 25%;">St. Louis</td><td style="width: 25%;">2</td></tr><tr><td style="width: 25%;">x24</td><td style="width: 25%;">Bedford</td><td style="width: 25%;">Lexington</td><td style="width: 25%;">3</td></tr></tbody></table></div><div class="table-wrap"><table data-ke-type="table" data-ke-align="alignLeft" style="width: 100%;" border="1"><tbody><tr><td style="width: 25%;">출발지-도착지</td><td style="width: 25%;">생산지</td><td style="width: 25%;">수요지</td><td style="width: 25%;">수송비</td></tr><tr><td style="width: 25%;">x31</td><td style="width: 25%;">York</td><td style="width: 25%;">Boston</td><td style="width: 25%;">2</td></tr><tr><td style="width: 25%;">x32</td><td style="width: 25%;">York</td><td style="width: 25%;">Chicago</td><td style="width: 25%;">5</td></tr><tr><td style="width: 25%;">x33</td><td style="width: 25%;">York</td><td style="width: 25%;">St. Louis</td><td style="width: 25%;">4</td></tr><tr><td style="width: 25%;">x34</td><td style="width: 25%;">York</td><td style="width: 25%;">Lexington</td><td style="width: 25%;">5</td></tr></tbody></table></div>위에 따라 식을 세우면 식은 다음과 같습니다 MIN 3*x11 + 2*x12 + 7*x13 + 6*x14 + 7*x21 + 5*x22 + 2*x23 + 3*x24 + 2*x31 + 5*x32 + 4*x33 + 5*x34 s.t  x11 + x12 + x13 + x14 <= 5000 x21 + x22 + x23 + x24 <= 6000x31 + x32 + x33 + x34 <= 2500x11 + x21 + x31 = 6000x12 + x22 + x32 = 4000x13 + x23 + x33 = 2000x14 + x24 + x34 = 1500xij >= 0 (i = 1,2,3, & j = 1,2,3,4) 이를 MS60의 'Linear Pragramming' 에 넣으면 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/38845140c03d7f42a98144cc75144fad3daf1530_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/38845140c03d7f42a98144cc75144fad3daf1530_re_1655573881223" data-origin-width="1281" data-origin-height="262"></div>위의 결과는 다음과 같다. LINEAR PROGRAMMING PROBLEM MIN 3x11+2x12+7x13+6x14+7x21+5x22+2x23+3x24+2x31+5x32+4x33+5x34      S.T.        1)  1x11+1x12+1x13+1x14<5000        2)  1x21+1x22+1x23+1x24<6000        3)  1x31+1x32+1x33+1x34<2500        4)  1x11+1x21+1x31=6000        5)  1x12+1x22+1x32=4000        6)  1x13+1x23+1x33=2000        7)  1x14+1x24+1x34=1500 OPTIMAL SOLUTION Objective Function Value =       39500.000       Variable             Value             Reduced Costs       --------------     ---------------      ------------------          x11                  3500.000                   0.000         x12                  1500.000                   0.000         x13                     0.000                   8.000         x14                     0.000                   6.000         x21                     0.000                   1.000         x22                  2500.000                   0.000         x23                  2000.000                   0.000         x24                  1500.000                   0.000         x31                  2500.000                   0.000         x32                     0.000                   4.000         x33                     0.000                   6.000         x34                     0.000                   6.000      Constraint        Slack/Surplus           Dual Prices        --------------     ---------------      ------------------          1                      0.000                   3.000          2                      0.000                   0.000          3                      0.000                   4.000          4                      0.000                  -6.000          5                      0.000                  -5.000          6                      0.000                  -2.000          7                      0.000                  -3.000 OBJECTIVE COEFFICIENT RANGES    Variable       Lower Limit       Current Value     Upper Limit  ------------   ---------------    ---------------  ---------------      x11                 -1.000              3.000            4.000      x12                  1.000              2.000            5.000      x13                 -1.000              7.000   No Upper Limit      x14                  0.000              6.000   No Upper Limit      x21                  6.000              7.000   No Upper Limit      x22                  2.000              5.000            6.000      x23         No Lower Limit              2.000            8.000      x24         No Lower Limit              3.000            9.000      x31         No Lower Limit              2.000            6.000      x32                  1.000              5.000   No Upper Limit      x33                 -2.000              4.000   No Upper Limit      x34                 -1.000              5.000   No Upper Limit RIGHT HAND SIDE RANGES   Constraint      Lower Limit       Current Value     Upper Limit  ------------   ---------------    ---------------  ---------------        1               5000.000           5000.000         7500.000        2               6000.000           6000.000   No Upper Limit        3               2500.000           2500.000         5000.000        4               3500.000           6000.000         6000.000        5               1500.000           4000.000         4000.000        6                  0.000           2000.000         2000.000        7                  0.000           1500.000         1500.000 목적함수 값에 따라 발생되는 최소 비용은 ＄39500 입니다. 이때 각 생산지에서 수요지로 보내야할 개수는 다음과 같습니다.x11 : 3500 개 (출발지 : Cleveland, 도착지 : Boston)x12 : 1500 개 (출발지 : Cleveland, 도착지 : Chicago)x22 : 2500 개 (출발지 : Bedford, 도착지 : Chicago)x23 : 2000 개 (출발지 : Bedford, 도착지 : St. Louis)x24 : 1500 개 (출발지 : Bedford, 도착지 : Lexington)x31 : 2500 개 (출발지 : York, 도착지 : Boston)<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/6d82a13d81a2d8732f202d61d16b1a95a32c9d6a_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/6d82a13d81a2d8732f202d61d16b1a95a32c9d6a_re_1655573881223" data-origin-width="682" data-origin-height="297"></div>위의 결과를 다시 표로 정리하면 이는 다음과 같습니다.<div class="table-wrap"><table data-ke-type="table" data-ke-align="alignCenter" style="width: 100%; height: 144px;" border="1"><tbody><tr style="height: 18px;"><td style="width: 20%; height: 18px;">출발지</td><td style="width: 20%; height: 18px;">도착지</td><td style="width: 20%; height: 18px;">보내는 수량</td><td style="width: 20%; height: 18px;">각 수량의 비용</td><td style="width: 20%; height: 18px;">비용의 합계</td></tr><tr style="height: 18px;"><td style="width: 20%; height: 18px;">Cleveland</td><td style="width: 20%; height: 18px;">Boston</td><td style="width: 20%; height: 18px;">3500</td><td style="width: 20%; height: 18px;">＄3</td><td style="width: 20%; height: 18px;">＄10,500</td></tr><tr style="height: 18px;"><td style="width: 20%; height: 18px;">Cleveland</td><td style="width: 20%; height: 18px;">Chicago</td><td style="width: 20%; height: 18px;">1500</td><td style="width: 20%; height: 18px;">＄2</td><td style="width: 20%; height: 18px;">＄3,000</td></tr><tr style="height: 18px;"><td style="width: 20%; height: 18px;">Bedford</td><td style="width: 20%; height: 18px;">Chicago</td><td style="width: 20%; height: 18px;">2500</td><td style="width: 20%; height: 18px;">＄5</td><td style="width: 20%; height: 18px;">＄12,500</td></tr><tr style="height: 18px;"><td style="width: 20%; height: 18px;">Bedford</td><td style="width: 20%; height: 18px;">St. Louis</td><td style="width: 20%; height: 18px;">2000</td><td style="width: 20%; height: 18px;">＄2</td><td style="width: 20%; height: 18px;">＄4,000</td></tr><tr style="height: 18px;"><td style="width: 20%; height: 18px;">Bedford</td><td style="width: 20%; height: 18px;">Lexington</td><td style="width: 20%; height: 18px;">1500</td><td style="width: 20%; height: 18px;">＄3</td><td style="width: 20%; height: 18px;">＄4,500</td></tr><tr style="height: 18px;"><td style="width: 20%; height: 18px;">York</td><td style="width: 20%; height: 18px;">Boston</td><td style="width: 20%; height: 18px;">2500</td><td style="width: 20%; height: 18px;">＄2</td><td style="width: 20%; height: 18px;">＄5,000</td></tr><tr style="height: 18px;"><td style="width: 80%; height: 18px;" colspan="4"></td><td style="width: 20%; height: 18px;">＄39,500</td></tr></tbody></table></div>이를 MS60의 'Transportation' 에 넣으면 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/be662d1c8802cec7489087674ae9d23c15f15ffd_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/be662d1c8802cec7489087674ae9d23c15f15ffd_re_1655573881223" data-origin-width="402" data-origin-height="161"></div>이에 대한 결과는 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/bff8959ec42ba5da67c7e07248cd62f553517582_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/bff8959ec42ba5da67c7e07248cd62f553517582_re_1655573881223" data-origin-width="425" data-origin-height="201"></div>결과 값은 앞서 살펴본 Linear Programming 과 동일한 것을 알 수 있습니다. 최소 비용 : ＄39500x11 : 3500 개 (출발지 : Cleveland, 도착지 : Boston)x12 : 1500 개 (출발지 : Cleveland, 도착지 : Chicago)x22 : 2500 개 (출발지 : Bedford, 도착지 : Chicago)x23 : 2000 개 (출발지 : Bedford, 도착지 : St. Louis)x24 : 1500 개 (출발지 : Bedford, 도착지 : Lexington)x31 : 2500 개 (출발지 : York, 도착지 : Boston) 위의 Linear Programming 과 Transportation 의 결과 값을 토대로 이를 Network 형태로 나타내면 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/28cbfb0caf814425d2401a44bf9de5cf930078d8_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/28cbfb0caf814425d2401a44bf9de5cf930078d8_re_1655573881223" data-origin-width="1088" data-origin-height="647"></div><문제의 변형><div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/96f4ef8b5348b547926e5f51a41cd796613030b7_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/96f4ef8b5348b547926e5f51a41cd796613030b7_re_1655573881223" data-origin-width="983" data-origin-height="298"></div>Foster Genarator의 문제는 기본적인 수송 문제의 상황을 보여줍니다. 문제의 변형은 다음과 같이 가능합니다. 1. 총 공급량이 총 수요량과 같지 않은 경우2. 목적 함수를 최대화 할 경우3. 해당 경로로 보낼 때 최소한의 양이 존재할 경우4. 제한되는 경로가 있을 경우 이를 차례대로 살펴보도록 하겠습니다. 1. 총 공급량이 총 수요량과 같지 않은 경우 총 공급량과 총 수요량이 같지 않은 경우는 또 다시 2가지의 경우를 생각해 볼 수 있습니다.1. 총 공급량 > 총 수요량  /  2. 총 공급량 < 총 수요량 1-1. 총 공급량 > 총 수요량의 경우 위의 기본 문제에서 York 의 공급량을 2500 에서 3500 으로 증가시켰습니다. Transportation 으로 나타내면 이는 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/75f4f49fdb024550d289e331dc37387dd3c842ab_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/75f4f49fdb024550d289e331dc37387dd3c842ab_re_1655573881223" data-origin-width="399" data-origin-height="150"></div>결과 값은 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/b424e0ecf34e133c99b271e3b174a1fe292eb513_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/b424e0ecf34e133c99b271e3b174a1fe292eb513_re_1655573881223" data-origin-width="464" data-origin-height="306"></div>총 비용은 35500이 발생하며, Bedford 에서 1000개의 여분이 발생된 것을 확인할 수 있습니다. Linear Programming으로 나타내면 결과 값은 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/f523b8946df544ae69408794d32380726d227684_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/f523b8946df544ae69408794d32380726d227684_re_1655573881223" data-origin-width="510" data-origin-height="535"></div>이 역시 총 비용은 35500이 발생되며, Beford 에서 1000개의 여분이 발생한 것을 알 수 있습니다. 1-2. 총 공급량 < 총 수요량의 경우 위의 기본 문제에서 York 의 공급량을 2500 에서 1500 으로 감소시켰습니다. Transportation 으로 나타내면 이는 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/d52e46d9ee89ed2377e261ef41f76ed316f7d9f3_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/d52e46d9ee89ed2377e261ef41f76ed316f7d9f3_re_1655573881223" data-origin-width="420" data-origin-height="159"></div>경고가 발생하며, 총 수요량보다 총 공급량이 1000개가 부족하다고 알려줍니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/adbd750ad00ebde6a03b8eaf6feace72db516bac_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/adbd750ad00ebde6a03b8eaf6feace72db516bac_re_1655573881223" data-origin-width="416" data-origin-height="189"></div>결과 값은 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/be8a38bbaccfdf5e9a719e206e96287bb9375a1d_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/be8a38bbaccfdf5e9a719e206e96287bb9375a1d_re_1655573881223" data-origin-width="464" data-origin-height="299"></div>총 비용은 37500이 발생하며, Boston 에서 1000개의 수요가 부족하다고 알려줍니다. Linear Programming으로 나타내면 결과 값은 다음과 같습니다. 모든 것은 동일하게 한 뒤 York 의 공급량만 1500으로 감소시켰습니다.이를 MS60으로 나타내면 이는 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/0afc6ad5cf2c067f92c08a995e7f3f041de34128_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/0afc6ad5cf2c067f92c08a995e7f3f041de34128_re_1655573881223" data-origin-width="1019" data-origin-height="265"></div>하지만 이 경우에는 Input 과 Output 의 값이 동일하지 않기에 오류가 발생됩니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/fe35e5a0f8f708fd4180f22aedd19149ae11bccf_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/fe35e5a0f8f708fd4180f22aedd19149ae11bccf_re_1655573881223" data-origin-width="215" data-origin-height="165"></div>따라 이를 해결하기 위해서는 Dummy가 필요합니다.Dummy 란 실제로는 존재하지 않지만 있는 것처럼 넣은 자료를 의미합니다.따라 부족한 공급량을 Dummy 로 할당시키면 결과값을 구할 수 있습니다. 따라 이를 식으로 나타내면 다음과 같습니다. MIN    3*x11 + 2*x12 + 7*x13 + 6*x14 + 7*x21 + 5*x22 + 2*x23 + 3*x24 + 2*x31 + 5*x32 + 4*x33 + 5*x34       (+0*d11 +0*d12 + 0*d13 + 0*d14) s.t  x11 + x12 + x13 + x14 <= 5000 x21 + x22 + x23 + x24 <= 6000x31 + x32 + x33 + x34 <= 1500d11 + d12 + d13 + d14 <= 1000x11 + x21 + x31 + d11 = 6000x12 + x22 + x32 + d12 = 4000x13 + x23 + x33 + d13 = 2000x14 + x24 + x34 + d14 = 1500xij >= 0 (i = 1,2,3, & j = 1,2,3,4) , d1j >= 0 (j = 1,2,3,4) 최소 비용을 구하는 것이기에 변함없이 MIN 문제 입니다.MIN 3*x11 + .... + (+0*d11 +0*d12 + 0*d13 + 0*d14) 를 통해 Dummy 부분이 추가 되었습니다.하지만 이는 dummy 이기에 실제 값에 영향을 미치면 안되기에 생략해도 되는 부분입니다. d11 + d12 + d13 + d14 <= 1000부족한 공급량인 1000만큼 dummy 에 할당되었습니다. x11 + x21 + x31 + d11 = 6000x12 + x22 + x32 + d12 = 4000x13 + x23 + x33 + d13 = 2000x14 + x24 + x34 + d14 = 1500dummy 가 각각의 수요지를 나타내는 제약조건에 추가되었습니다. 이의 결과값은 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/c88a35e7b039f3fffce4f3559a9c12a095ef3a90_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/c88a35e7b039f3fffce4f3559a9c12a095ef3a90_re_1655573881223" data-origin-width="510" data-origin-height="623"></div>역시 총 비용은 37500이 발생합니다. 또한 Dummy 가 공급한 수요지가 Boston 인것을 통해 Boston 에서 1000개가 부족한 것을 알 수 있습니다. 2. 목적 함수를 최대화 할 경우 위의 기본 문제에서 같은 동일한 값들을 갖고 있지만 비용이 아닌 수익일 경우를 보도록 하겠습니다. Transportation 으로 나타내면 값은 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/19cb8de00fb54cd6e3f635329627329110daec40_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/19cb8de00fb54cd6e3f635329627329110daec40_re_1655573881223" data-origin-width="420" data-origin-height="193"></div>총 수익은 80500이 발생한 것과 x12 : 1500 개 (출발지 : Cleveland, 도착지 : Chicago)x13 : 2000 개 (출발지 : Cleveland, 도착지 : St. Louis)x14 : 1500 개 (출발지 : Cleveland, 도착지 : Lexington)x21 : 6000 개 (출발지 : Bedford, 도착지 : Boston)x32 : 2500 개 (출발지 : York, 도착지 : Chicago) 다음과 같이 할당이 된 것을 알 수 있습니다. Linear Programming으로 나타내면 결과는 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/890f6d98ee7d766086f0afbdfa01f550e8fd6356_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/890f6d98ee7d766086f0afbdfa01f550e8fd6356_re_1655573881223" data-origin-width="510" data-origin-height="537"></div>이 역시 위와 동일하게 총 수익은 80500이 발생한 것과 x12 : 1500 개 (출발지 : Cleveland, 도착지 : Chicago)x13 : 2000 개 (출발지 : Cleveland, 도착지 : St. Louis)x14 : 1500 개 (출발지 : Cleveland, 도착지 : Lexington)x21 : 6000 개 (출발지 : Bedford, 도착지 : Boston)x32 : 2500 개 (출발지 : York, 도착지 : Chicago) 다음과 같이 할당이 된 것을 알 수 있습니다. 3. 해당 경로로 보낼 때 최소한의 양이 존재할 경우 해당 경로로 보낼 때 최소한의 양이 존재할 경우의 Transportation 로는 해결할 수 없습니다.따라 Linear Programming 으로만 해결하도록 하겠습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/1782f3ea98a2c6b446e881022175d3562a0b192e_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/1782f3ea98a2c6b446e881022175d3562a0b192e_re_1655573881223" data-origin-width="586" data-origin-height="327"></div>기본적인 문제에서는 x13(출발지 : Cleveland, 도착지 : St. Louis) 가 채택되지 못했습니다. 따라 최소한 x13에 1000개를 할당하도록 하겠습니다. 따라 제약조건식으로 아래의 식을 추가시켜주면 됩니다.x13 >= 1000  위의 제약조건을 추가하여 나올 결과는 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/dd1b87db150e8ad9af9c9fab9743d6078a3cf642_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/dd1b87db150e8ad9af9c9fab9743d6078a3cf642_re_1655573881223" data-origin-width="628" data-origin-height="567"></div>발생되는 최소 비용은 ＄47500 로 기존의 ＄39500에서 ＄8000 증가했습니다. 이때 각 생산지에서 수요지로 보내야할 개수를 살펴보면 이는 다음과 같습니다.x11 : 3500 개 (출발지 : Cleveland, 도착지 : Boston)x12 : 500 개 (출발지 : Cleveland, 도착지 : Chicago)x13 : 1000 개 (출발지 : Cleveland, 도착지 : St. Louis)x22 : 3500 개 (출발지 : Bedford, 도착지 : Chicago)x23 : 1000 개 (출발지 : Bedford, 도착지 : St. Louis)x24 : 1500 개 (출발지 : Bedford, 도착지 : Lexington)x31 : 2500 개 (출발지 : York, 도착지 : Boston) 4. 제한되는 경로가 있을 경우 해당 경로로 보낼 때 제한되는 경로가 존재할 경우의 Transportation 로는 해결할 수 없습니다.따라 Linear Programming 으로만 해결하도록 하겠습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/1782f3ea98a2c6b446e881022175d3562a0b192e_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/1782f3ea98a2c6b446e881022175d3562a0b192e_re_1655573881223" data-origin-width="586" data-origin-height="327"></div>기본적인 문제에서는 x11(출발지 : Cleveland, 도착지 : Boston) 으로 향하는 물량이 가장 많은 것을 알 수 있습니다.따라 x11의 경로를 제한시켜보도록 하겠습니다. 다음과 같은 기존의 제약 조건식에서x11 + x21 + x31  = 6000다음과 같이x11의 경로만 제거해주면 됩니다.x21 + x31 = 6000 위의 제약조건을 적용한 결과 값은 다음과 같습니다.<div class="figure-img" data-ke-type="image" data-ke-style="alignLeft" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/f62c609d721f1f46be19d35a25202cdc3ab9fada_re_1655573881223" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/f62c609d721f1f46be19d35a25202cdc3ab9fada_re_1655573881223" data-origin-width="633" data-origin-height="538"></div>발생되는 최소 비용은 ＄49000 로 기존의 ＄39500에서 ＄9500 증가했습니다. 이때 각 생산지에서 수요지로 보내야할 개수를 살펴보면 이는 다음과 같습니다.x12 : 4000 개 (출발지 : Cleveland, 도착지 : Chicago)x14 : 1000 개 (출발지 : Cleveland, 도착지 : Lexington)x21 : 3500 개 (출발지 : Bedford, 도착지 : Boston)x23 : 2000 개 (출발지 : Bedford, 도착지 : St. Louis)x24 : 500 개 (출발지 : Bedford, 도착지 : Lexington)x31 : 2500 개 (출발지 : York, 도착지 : Boston) <결론>기본적인 상황에서는 Transportation 이 더 편리하지만,그 외의 경로에 관한 제약이 있을 경우에는 Linear Programming 이 편리한 것을 알 수 있었습니다.