경의론 shortest route 정리

[장정호(경영)]

우리는 어떠한 공정등에서 다양한 경로가있을 때 최적의 효율성을위해서 시간이 작게걸리는 의사결정을 하는 것이 효율성을 높일 수 있습니다. 위의 문제는 1번에서 시작하여 6번을 최종목적지로 할 때 어떤 경로로 가는 것이 시간이 제일 적게걸리는지를 알아보는 문제입니다.

먼저 이 문제는 MS 60을 사용하여 ILP의 방식으로도 풀 수 있고 shortest-route problem으로도 풀 수 있습니다.

1-1 ILP를 이용

ILP를 이용할때는 Note1~6에 대한 제약식을 세워줘야 합니다.

식을 세울 때 1번노드와 6번노드는 시작지와 종착지이기 떄문에 무조건 하나는 선택되서 나아가야하기 때문에 1이 나와야 합니다. 2~5번 노드는 flow out(보내는 것)-flow in(들어오는 것) 이 0이 되도록 식을 세워주면 됩니다.

가령 2번노드의 경우에는 2번에서 보낼 수 있는 노드(flow out)은 3번,4번,6번이 되고 2번으로 들어 올 수 있는 노드(flow in)는 1번,3번,4번이 되기 때문에

x23+x24+x26-x12-x32-x42= 0 이런식으로 식을 세워주면 됩니다. 식을 다 세우면 아래와 같습니다.

이를 바탕으로 해찾기를 실행할 때 전부 0or1을 사용하여 해찾기를하면 아래와 같은 결과가나옵니다.

이 결과를 보았을 때 1->3->2->4->6 번 순서로 간다면 총 32의 시간이 걸리고 이것이 제일 최단시간이라는 것을 알 수 있습니다.

1-2 shortest route를 이용

위에서 만들어본 ILP는 직접 하나하나 경로를 찾는 것 보다는 비교적 적은 시간을 소모하지만 노드가 늘어날수록 제약식이 많아져서 식을 세우는데 어려움이 있을 수 있습니다.이를 보완하기 위해서 이번에는 shortest route를 이용하여 풀어보도록 하겠습니다.

shortest route는 처음에 노드와 아크를 지정해주어야 하는데 우리가 풀어볼 문제의 노드는 6개 아크는 9개이므로 6과 9를 입력 해 줍니다.

이후 제약식을 세우는 것은 노드의 시작점과 끝점을 기록하고 그사이의 거리를 기록하면 됩니다. 가령 2번에서 4번노드를 갈 때의 거리가 5라면 start에는 2를 end에는 4를 distance에는 5를 입력해 주면 됩니다.

이렇게 식을 세우고 나서 해찾기를하면 아래와 같은 결과가 나옵니다.

앞에서 사용해보았던 ILP와 비교해서 똑같이 1->3->2->4->6번 경로를 이용하면 32의 거리가 나오며 이것이 최단경로라는 것을 알 수 있습니다.

1-3 직접 풀어보기

간단한 경로찾기문제라면 직접 손으로 하나씩 경로를 계산할 수 있습니다.

2번을 가기위해서는 1번에서 출발하여 25의거리 [1ㅣ25], 3번에서 출발하여 23 [3ㅣ23(20+3)]의 두가지 경로가 있습니다. 이후 6번까지 가기위해서는 경로를 살펴본다면 [2ㅣ37],[4ㅣ32],[5ㅣ33] 등이 있습니다. 직접 이렇게 풀어보아도 1->3->2->4->6번 노드를 거쳐서 이동한다면 32가 나오며 이것이 최단경로라는 것을 알 수 있습니다.

변형문제

이렇게 7번노드를 하나 더 만든다면 노드는 7개 아크는 11개가 존재하게 됩니다. 이것을 shortest route로 식을 세우면 아래와 같습니다.

이에 식과 해찾기는 아래와 같습니다.

.

1-3에서 구한 1번에서 5번까지의 최단경로 [3ㅣ26]에서 5만큼을 더한 31과 1번에서 6번까지의 최단경로 [4ㅣ32]에서 10을더한 42중 31이 최단경로가 나오는 것이 나오는걸 확인할 수 있었습니다.

2.A minimal spanning tree

우리는 어떠한 작업을 할 때 최소한의 비용이나 시간을 염두해야합니다 가령 보기처럼 5개의 장소에 각자 한번씩은 존력을 공급해 주어야 한다면 1에서 5까지 모든선을 연결하는것이아닌 1-2,1-3,1-4,1-5 4곳만 선을 연결해 준다면 5곳 모두에게 전력이 갈 수있습니다.

지금부터 직접 문제를 풀어보는방법과 ms60을 사용하여 해결하는 두가지방법을 풀이하겠습니다.

2-1 직접풀기

1-2,1-4,3-4,4-6,3-5 번을 통과하면 110을 사용하며 최소한의 길이로 모든곳을 지나갈 수 있었습니다.

이번에는 시작점을 5번에서 부터 시작해보겠습니다.

5번에서부터 출발하여도 1번에서 출발한것과 같은 경로가 나오는것이 확인가능합니다.

2-2 MS60을 이용

위 그림에서 노드는 6개 아크는 11개이므로 ms60에서 minimal spanning tree를 선택하고 1에서 2를갈때는 20 1에서 4를갈때는 30 이런식으로 전부 식을 입력해줍니다.

식과 해찾기는 다음과 같습니다.

ms60을 사용하여도 직접 그렸던것과 같이 1-2,1-4,3-4,4-6,3-5를 지나가며 110의 길이가 소요되는 것을 알 수 있습니다.

4주차 정리: 4주차는 기존의 다른 교수님께 배운 운영관리에서 네트워크 기법인 AOA기법이 많이 생각나는 파트였습니다. 그때도 노드와 아크를 처음접하였는데 운영관리를 수강할 때에도 직접 하나하나 그려가면서 풀었던 기억이납니다. MS60에서 ILP도 분명 잘 만들어진 프로그램이지만 이렇게 식이 많아질수록 분명한 한계점이 나타나는 것 같습니다. shortest route,Minimal spanning tree등을 이용하면 ILP로 식을 세우는것보다 시간도 절약되고 정답도 정확하게 찾을 수 있을 것 같습니다!!

[현승용]

어떤수업에서 AOA(Activity on Arrow, Arc)는 말을 들었던 모양이구나. 그냥 그 자체로 노드와 아크로 구성되는 네트워크 구조와 각각 연결관계를 칭하는 의미란다. 아마도 제조업의 공정관리에서 설명을 들었나본데, 우리가 5주차부터 다루는 PERT/CPM에서 확실한 개념으로 더욱 폭넓고 다양하게 활용하게 될거란다.
스스로 실험도 해가며 복습을 차분히 잘했네~ ^^

[장정호(경영)]

네 교수님 aoa랑 aon을배웠는데 따로 모듈이 있는지 몰랐습니다 5주차도 열심히 하겠습니다!!