<p>경영과학 11주차 2차시 때 다뤘던 예제를 12주차 2차시 수업에선 기존 틀에서 변형을 하면서 풀이하였습니다.</p><p> </p><p>11주차 2차시 복습에서 다뤘던 예제의 목적함수는</p><p>MIN 3X11+2X12+7X13+6X14+7X21+5X22+2X23+3X24+2X31+5X32+4X33+5X34 이였고</p><div class="imagegridblock" data-ke-type="imageGrid"><div class="image-container"><span data-url="https://t1.daumcdn.net/cafeattach/G7Le/2925476ea598e990e8042d3a8e1ddab331ab3182" data-origin-width="688" data-origin-height="169" style="width:57.94%; margin-right: 10px;"><img src="https://t1.daumcdn.net/cafeattach/G7Le/2925476ea598e990e8042d3a8e1ddab331ab3182" class="txc-image-grid"></span><span data-url="https://t1.daumcdn.net/cafeattach/G7Le/65f177859b4db76d8a8524ca02240c62b45483f8" data-origin-width="600" data-origin-height="203" style="width:42.06%; "><img src="https://t1.daumcdn.net/cafeattach/G7Le/65f177859b4db76d8a8524ca02240c62b45483f8" class="txc-image-grid"></span></div></div><p>위에 나와있는 표는 총 7개에 해당하는 제약조건들입니다.</p><p> </p><div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/4736370eb7f295785981a2aec51c8f169ba8d8e2" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/4736370eb7f295785981a2aec51c8f169ba8d8e2" data-origin-width="612" data-origin-height="641"></div><p>위의 목적함수와 제약조건식을 ms60 프로그램을 이용하여 돌리고 난 후의 output표입니다.</p><p> </p><p>저희는 12주차 2차시 수업에서 문제를 접근하는 방법을 조금 더 확대하여 보았습니다.</p><p>총 4가지 케이스를 하나하나 짚어가며 다루어보겠습니다.</p><p> </p><p><span data-ke-size="size18"><b>1. 공급의 합과 수요의 합이 일치하지 않는 경우</b></span></p><p> </p><p>1-1 공급>수요</p><p> </p><p>이 경우에는 RHS값의 증가 이외에  수송자체에 문제가 생기지는 않습니다. 다만 공급할 수 있는 양이 수요보다 많기 때문에 <=인 제약조건에 여유변수가 생깁니다.</p><p> </p><p>1-2 공급<수요</p><p> </p><p>이 경우는 공급할 수 있는 양이 수요를 충족시켜주지 못하며 infeasible하게 돼서 optimal solution을 도출하지 못하게 됩니다. 이는 또 'LP로 문제를 해결하는 경우'와 '수송 모듈로 문제를 해결하는 경우'로 나눠볼 수가 있겠는데 우선 LP로 문제를 해결해보겠습니다. 저희는 LP에서 Dummy변수를 이용하여 시스템을 조작해보았습니다.</p><p>여기서 Lexington demand의 수요는 1500-> 2000으로 가정하게됩니다. </p><p> </p><div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/2c2a09ae49c01b47467b6bc83bba84a18e578b0e" class="txc-image" width="523" height="468" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/2c2a09ae49c01b47467b6bc83bba84a18e578b0e" data-origin-width="777" data-origin-height="696"></div><p>이런식으로 Dummy 변수(D41,D42,D43,D44)가 추가되고, </p><p>목적함수식이 MIN 3X11+2X12+7X13+6X14+7X21+5X22+2X23+3X24+2X31+5X32+4X33+5X34+0D41+0D42+0D43+0D44와 같이 실제 존재하는 노드가 아니라 계수가 0으로서 존재하게 되고  추가/변경된 제약조건은</p><p> </p><p><공급지 노드></p><p>D41+D42+D43+D44<=500 제약조건이 추가되었고</p><p> </p><p><수요지 노드></p><div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/bb5b6984f3d1df2333adbd60bfff8ba0f139c9fb" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/bb5b6984f3d1df2333adbd60bfff8ba0f139c9fb" data-origin-width="777" data-origin-height="247"></div><p> </p><p>위 표와같이 제약조건이 변경되었습니다.   Lexington demand의 수요 1500-> 2000</p><p> </p><p>따라서 MS60 프로그램을 돌려보면 아래와 같은 결과가 나오게 됩니다.</p><div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/9188f271de7b4fa04dc455e2173982ff028372ee" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/9188f271de7b4fa04dc455e2173982ff028372ee" data-origin-width="613" data-origin-height="633"></div><p>목적함수값은 38000으로 처음의 39500보다 낮아지게 되었으며 그 이유는 1번수요지에서 확인 할 수 있는데 X11+X21+X31+D41의 합이 6000이지만 D41은 Dummy변수이므로 사실 1번수요지에서 500만큼 수요를 못채운 것으로 확인 할 수 있습니다. </p><p> </p><p>다음으로 수송모듈을 이용해서 문제를 해결하게되면</p><div class="imagegridblock" data-ke-type="imageGrid"><div class="image-container"><span data-url="https://t1.daumcdn.net/cafeattach/G7Le/70ad4260fc741a7e7d8d2dcd9974a3391179940a" data-origin-width="400" data-origin-height="232" style="width:42.41%; margin-right: 10px;"><img src="https://t1.daumcdn.net/cafeattach/G7Le/70ad4260fc741a7e7d8d2dcd9974a3391179940a" class="txc-image-grid"></span><span data-url="https://t1.daumcdn.net/cafeattach/G7Le/069ab0a968da5591d90020e488d483ffea94ff0e" data-origin-width="391" data-origin-height="167" style="width:57.59%; "><img src="https://t1.daumcdn.net/cafeattach/G7Le/069ab0a968da5591d90020e488d483ffea94ff0e" class="txc-image-grid"></span></div></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/5756a327daab16abd4faba3674d6f0690998c918" class="txc-image" width="466" height="529" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/5756a327daab16abd4faba3674d6f0690998c918" data-origin-width="625" data-origin-height="710"></div><p>이런식으로 공급량이 수요량에 비해 충분하지 않을 때 정보메세지창이 뜨고 메세지창의 확인버튼을 누르게되면 어느 수요지에서 얼마만큼 공급이 안됐는지 명확하게 확인이 가능하게 됩니다.</p><p> </p><p> </p><p> </p><p><span data-ke-size="size18"><b>2. 최대화 문제로 바꾸어 보기<br></b></span></p><div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/G7Le/713d1db34650ad37fe2ea32878a28664ef336d97" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/G7Le/713d1db34650ad37fe2ea32878a28664ef336d97" data-origin-width="622" data-origin-height="692"></div><p>본래 네트워크 플로우 다이어그램에서 노드에 있는 숫자를 단위당 수송비용이 아니라, 단위당 가치로 가정하고 최대화 문제로 취급하였을 때 목적함수값 80500이라는 값이 나옴을 알 수 있습니다. 또한 최적해로 채택된 아크와 그 숫자가 MIN문제와 다름을 알 수 있습니다.</p><p> </p><p><span data-ke-size="size18"><b>3. 루트의 최소충족량이 생기는 경우</b></span></p><div class="imagegridblock" data-ke-type="imageGrid"><div class="image-container"><span data-url="https://t1.daumcdn.net/cafeattach/G7Le/b21241d02b89e2150facf997ceb6ff87c914eca5" data-origin-width="612" data-origin-height="641" style="width:51.88%; margin-right: 10px;"><img src="https://t1.daumcdn.net/cafeattach/G7Le/b21241d02b89e2150facf997ceb6ff87c914eca5" class="txc-image-grid"></span><span data-url="https://t1.daumcdn.net/cafeattach/G7Le/90d610d3f617ef39da3f766579888f65d27ed4f5" data-origin-width="620" data-origin-height="700" style="width:48.12%; "><img src="https://t1.daumcdn.net/cafeattach/G7Le/90d610d3f617ef39da3f766579888f65d27ed4f5" class="txc-image-grid"></span></div></div><p>X11의 아크에 최소 4000개의 물품을 실어야 한다는 가정으로 X11>=4000의 제약조건을 추가하고 프로그램을 돌려보았습니다. MIN문제임에 불구하고 비용이 2000만큼 올라서 39500 -> 41500이 비용을 최소화했을 때 나오는 값입니다. 이는 X11>=4000의 제약조건이 해당 제약조건이 없었을 때에 비해서 비용 최소화에 기여하지 못함을 의미하기도 합니다.</p><p> </p><p><span data-ke-size="size18"><b>4. 루트가 금지된 경우</b></span></p><p> </p><p>루트가 지형적으로 불리한 루트이거나 수송을 하는데 있어 어려움이 있는 루트일 경우 그에 해당하는 특정 아크를 막을 수 있고 만약 X23 아크를 금지시켰다고 가정하고 프로그램을 돌려보겠습니다.</p><div class="imagegridblock" data-ke-type="imageGrid"><div class="image-container"><span data-url="https://t1.daumcdn.net/cafeattach/G7Le/618ef7f05b38f1bb033f41d1d0c46f98da814c44" data-origin-width="612" data-origin-height="641" style="width:49.80%; margin-right: 10px;"><img src="https://t1.daumcdn.net/cafeattach/G7Le/618ef7f05b38f1bb033f41d1d0c46f98da814c44" class="txc-image-grid"></span><span data-url="https://t1.daumcdn.net/cafeattach/G7Le/0b31dce04bc4c6337693f8d4241fd55276868c55" data-origin-width="615" data-origin-height="639" style="width:50.20%; "><img src="https://t1.daumcdn.net/cafeattach/G7Le/0b31dce04bc4c6337693f8d4241fd55276868c55" class="txc-image-grid"></span></div></div><p>X23 아크를 금지시켰더니 수송 비용이 39500 -> 52000으로 12500만큼 크게 증가하였음을 알 수 있습니다. 이러한 결과는 X23 아크가 정상적으로 운행이 될 수 있다면 수송 비용을 최소화하는데 있어 크게 기여할 수 있음을 의미하기도 합니다.</p><p> </p><p> </p>
<!-- -->
첫댓글 차분히 잘 하고 있구나.