경영의사결정론 4주차 복습

[강경훈(경영)]

이번 4주차에서는 Shortest-Route(최단경로)와 Maximal Flow(최대흐름관리) 문제를 다루어 보았습니다.

먼저 Shortest-Route(최단경로)란 말 그대로 가장 빠르게 가는 경로가 어디냐를 찾는 문제입니다.

예시 문제를 보면 동그라미가 node는 지점을 의미하고 arc는 경로를 의미합니다.

Gorman’s office라는 node1에서 최종 목적지 node6으로 이동하려고 합니다.

node1->node2로 가는데 25mile이란 거리를 가야하고 이 것을 목적함수식으로 X12으로 세워서 진행 할 것입니다.

X23은 node2->node3으로 가는데 3mile을 가야 합니다. 반대로 X32는 node3->node2로 가는 것도 3mile이 걸린 다는 것을 그림에서 볼 수 있습니다.

그림1)

이 그림을 보고 목적함수식을 쓰면 밑에처럼 나오는데 X21과 X31이 없는 이유는 굳이 node2,3까지 왔는데 다시 출발지로 돌아가야할 이유가 없기 때문에 목적함수식에 없는 것이고, 마찬가지로 X62,X64.X65도 최종 목적지에 도착했는데 굳이 돌아가야 할 필요가 없기 때문에 목적함수식에 없는 것을 알 수 있습니다.

그림2)

그림3)

밑에는 In put과 Out put을 나타내는 표입니다.

Out put=In put을 넘기면 Out put-In put=0이 됩니다.

밑에 표에 Node2의 X23+X24+X26은 나간 것들이고 –X12-X32-X42는 뒤에 숫자가 2라는 공통점을 보면 알 수 있듯이 모두 2번 Node로 들어온 것입니다. 나머지도 똑같이 이해 할 수 있었습니다.

그림4)

마지막 X12+X13=1은 node2든 node3으로 가든 무조건 둘 중 한 명만 한 곳에는 꼭 가야 한다는 것이고, X26+X46+X56=1은 node2든 node4든 node5 셋 중에 한 곳에서는 무조건 node6으로 꼭 가야 한다는 것을 뜻 합니다.

그림5)

위에서 말한 내용을 밑에 제약조건식으로 나타 낼 수 있습니다. 이것을 MS60으로 프로그램으로 돌릴 때 integer로 돌리든 binary로 돌리든 상관 없이 값을 구할 수 있습니다. 왜냐하면 제약조건식의 앞에 계수가 없기 때문입니다.

그림6)

이제 MS60으로 시뮬레이션을 돌려 보겠습니다.

그림7)

그림8)

그림9)

먼저 Integer로 돌렸을 때 X13->X32->X24->X46으로 가는 경로가 최소한의 mile로 가는 경로인 것을 알 수 있고 총 32mile을 갔다는 것을 알 수 있습니다. 그 다음 binary로 돌려보았을 때도 마찬가지의 값을 알 수 있다는 것을 알 수 있었습니다.

그림10)

그림11)

이번엔 새로운 Shortest-Route 모듈로 돌려 보았습니다.

먼저 node는 총 6곳이라서 6으로 하고, 선형모듈로 돌릴 때는 Arcs가 13개로 시뮬레이션을 돌리는데 최단경로 모듈은 X23, X32처럼 왔다갔다 하는 것을 빼고 9곳으로 넣는 것을 알 수 있었습니다.

그림12)

그림13)

이렇게 값을 넣고 Solve를 누르면 시작점에서 도착점을 지정하라는 것이 뜹니다. 우리는 1번에서 6번 node로 가기때문에 1, 6을 입력해 주었습니다.

그림14)

그 결과 선형모듈과 마찬가지로 X13->X32->X24->X46으로 가는 경로가 최단 거리이며 총 32mile를 간다는 것을 알 수 있습니다. 선형모듈보다 간편하게 입력해도 되고, 결과 값을 한 눈에 쉽게 이해 할 수 있다는 장점이 있는 것 같습니다!

이제는 두 번째 Maximal flow(최대 흐름) 문제를 다뤄보았습니다.

이번 예제는 1번 node에서 7번 노드까지 흘러가는 자동차들의 최대값을 알아 내기 위한 예제입니다. 밑에 그림에서 node1->node2로 가는데 arc가 5란 것은 시간당 자동차가 5000대가 흘러간다는 뜻입니다. 또한, 이것을 목적함수식에서 X12로 표현 할 수 있습니다.

그림15)

이번 문제도 Shortest route(최단거리)문제와 마찬가지로 밑에 표는 Out put=In put을 넘기면 Out put-In put=0이 되기 때문에 node1의 X12+X13+X14-X71=0이란 X12,X13,X14는 node1번에서 다른 node로 나가는 차들이고 X71은 node7번에서 node1번으로 들어오는 차량을 뜻합니다.

그림16)

밑에 그림에서 X12≤5는 node1->node2로 가는 차량이 5000대가 넘지 못한다는 것을 뜻합니다. X13≤6는 node1->node3로 가는 차량이 6000대가 넘지 못한다는 것을 뜻합니다.

그림17)

이제 우리의 MS60을 돌려보겠습니다.

그림18)

그림19)

그림20)

그림21)

그림22)

직접 계산해본 결과 node6은 node7로 보낼 수 있는 양이 7000대이기 때문에 총 node6으로 8000대가 왔지만 7000대만 보낼 수 있기 때문에 node6에서 node5로 1000대 만큼 보내줬다는 것을 알 수 있었습니다.

위에있는 그림은 직접 MS60을 돌려본 것이고 밑에는 값은 책에 나와있는 표입니다. 둘 다 optimal solution이 될 수 있다는 것을 알 수 있습니다. 이 표를 보고 총 14000대의 차량이 흘러 가고 흘러온 14000대의 차량이 다시 node7번에서 node1번으로 14000대 차량이 흘러 간다는 것을 이해 할 수 있었습니다.

이번엔 여기서 더 나아가 허석우학생과 장정호학생이 다른 부분에서 잘 써주어서 저는 Maximal Flow부분을 좀 더 깊게 학습해보았습니다. arc경로를 두개 더 추가해서 MS60으로 이 복잡한 문제를 더 복잡하게 만들어서 푸는게 과연 될 것인가라는 생각으로 장난식으로 돌려보았습니다.

그림23)

그림24)

그림25)

그 결과 MS60에서 node4에서 node3으로 1000대만큼 더 보내주는 것을 볼 수 있었고, 다른 부분에서도 경로가 조금씩 바뀐 것을 확인할 수 있었습니다! 이런식으로 복잡한 문제도 MS60은 풀 수 있구나 라는 것을 알 수 있었습니다.

[현승용]

성실하게 차근 차근 개념을 본인 것으로 만들어가면 된단다.