경영과학 11주차 2차시 때 다뤘던 예제를 12주차 2차시 수업에선 기존 틀에서 변형을 하면서 풀이하였습니다.
11주차 2차시 복습에서 다뤘던 예제의 목적함수는
MIN 3X11+2X12+7X13+6X14+7X21+5X22+2X23+3X24+2X31+5X32+4X33+5X34 이였고
위에 나와있는 표는 총 7개에 해당하는 제약조건들입니다.
위의 목적함수와 제약조건식을 ms60 프로그램을 이용하여 돌리고 난 후의 output표입니다.
저희는 12주차 2차시 수업에서 문제를 접근하는 방법을 조금 더 확대하여 보았습니다.
총 4가지 케이스를 하나하나 짚어가며 다루어보겠습니다.
1. 공급의 합과 수요의 합이 일치하지 않는 경우
1-1 공급>수요
이 경우에는 RHS값의 증가 이외에 수송자체에 문제가 생기지는 않습니다. 다만 공급할 수 있는 양이 수요보다 많기 때문에 <=인 제약조건에 여유변수가 생깁니다.
1-2 공급<수요
이 경우는 공급할 수 있는 양이 수요를 충족시켜주지 못하며 infeasible하게 돼서 optimal solution을 도출하지 못하게 됩니다. 이는 또 'LP로 문제를 해결하는 경우'와 '수송 모듈로 문제를 해결하는 경우'로 나눠볼 수가 있겠는데 우선 LP로 문제를 해결해보겠습니다. 저희는 LP에서 Dummy변수를 이용하여 시스템을 조작해보았습니다.
여기서 Lexington demand의 수요는 1500-> 2000으로 가정하게됩니다.
이런식으로 Dummy 변수(D41,D42,D43,D44)가 추가되고,
목적함수식이 MIN 3X11+2X12+7X13+6X14+7X21+5X22+2X23+3X24+2X31+5X32+4X33+5X34+0D41+0D42+0D43+0D44와 같이 실제 존재하는 노드가 아니라 계수가 0으로서 존재하게 되고 추가/변경된 제약조건은
<공급지 노드>
D41+D42+D43+D44<=500 제약조건이 추가되었고
<수요지 노드>
위 표와같이 제약조건이 변경되었습니다. Lexington demand의 수요 1500-> 2000
따라서 MS60 프로그램을 돌려보면 아래와 같은 결과가 나오게 됩니다.
목적함수값은 38000으로 처음의 39500보다 낮아지게 되었으며 그 이유는 1번수요지에서 확인 할 수 있는데 X11+X21+X31+D41의 합이 6000이지만 D41은 Dummy변수이므로 사실 1번수요지에서 500만큼 수요를 못채운 것으로 확인 할 수 있습니다.
다음으로 수송모듈을 이용해서 문제를 해결하게되면
이런식으로 공급량이 수요량에 비해 충분하지 않을 때 정보메세지창이 뜨고 메세지창의 확인버튼을 누르게되면 어느 수요지에서 얼마만큼 공급이 안됐는지 명확하게 확인이 가능하게 됩니다.
2. 최대화 문제로 바꾸어 보기
본래 네트워크 플로우 다이어그램에서 노드에 있는 숫자를 단위당 수송비용이 아니라, 단위당 가치로 가정하고 최대화 문제로 취급하였을 때 목적함수값 80500이라는 값이 나옴을 알 수 있습니다. 또한 최적해로 채택된 아크와 그 숫자가 MIN문제와 다름을 알 수 있습니다.
3. 루트의 최소충족량이 생기는 경우
X11의 아크에 최소 4000개의 물품을 실어야 한다는 가정으로 X11>=4000의 제약조건을 추가하고 프로그램을 돌려보았습니다. MIN문제임에 불구하고 비용이 2000만큼 올라서 39500 -> 41500이 비용을 최소화했을 때 나오는 값입니다. 이는 X11>=4000의 제약조건이 해당 제약조건이 없었을 때에 비해서 비용 최소화에 기여하지 못함을 의미하기도 합니다.
4. 루트가 금지된 경우
루트가 지형적으로 불리한 루트이거나 수송을 하는데 있어 어려움이 있는 루트일 경우 그에 해당하는 특정 아크를 막을 수 있고 만약 X23 아크를 금지시켰다고 가정하고 프로그램을 돌려보겠습니다.
X23 아크를 금지시켰더니 수송 비용이 39500 -> 52000으로 12500만큼 크게 증가하였음을 알 수 있습니다. 이러한 결과는 X23 아크가 정상적으로 운행이 될 수 있다면 수송 비용을 최소화하는데 있어 크게 기여할 수 있음을 의미하기도 합니다.
첫댓글 차분히 잘 하고 있구나.