4-1 Shortest Route Problem

[이재학(경영)]

먼저, MS60을 적용하기 전에 최단경로문제에 대한 성질을 완전히 이해해야 경로가 바뀌어도 헷갈리지 않고 목적함수와 제약조건을 정확히 구할 수 있을 거 같아 정리를 하였습니다.

2번, 다시 출발지로 돌아 올 수 없다. 즉 X(i,j)에서 IN인 j가 1이 될 수 없다는 뜻입니다.

또한 3번, 목적지에서 다시 나갈 수 없습니다. 즉 X(i,j)에서 Out인 i가 6이 될 수 없습니다.

이 두 가지 경우가 아니면 다른 Node 사이는 왕복이 가능합니다. 왕복은 출발지와 도착지에서만 안됩니다.

5번이 가장 중요합니다 Flow out=Flow in 즉 Flow out-Flow in=0 이며

해석하면 들어왔기 때문에 나가는 것이 가능하며 들어왔으면 반드시 나가야한다는 뜻이기도 합니다. 나가지 않으면 그 Node에서갇혀 있을 것입니다.

X(1,2) + X(1,3) = 1이 되어야 하는데 그 근거는 1번 성질입니다. 왜냐하면 다시 출발지로 들어올 수 없는데 출발지에서 무조건 Node 2 혹은 Node 3으로 갔을 것입니다. Node 2로 갔으면 X(1,2)=1이며 그러면 X(1,3)=0이 되어야 합니다. Node 3으로 갔으면 그 반대이고 그러면 Node 2로 가든 3으로 가든 무조건 X(1,2)+X(1,3)=1입니다.

X(2,6)+X(4,6)+X(5,6)=1도 3번 성질을 이용해서 이해하면 되겠습니다.

---

<MS60 적용>

모든 Variables=0 or 1

최단 경로 : 1 - 3 - 2 - 4 - 6 / 최단 거리 : 32(Miles)

Variables가 많으므로 실수하지 않게 입력하는 것이 중요합니다.

저 같은 경우는 먼저 등호를 6개 입력하고 맨 끝에 순서대로 1,0,0,0,0,1 입력을 내놓고

Variable 입력한 순서대로 찾아가면서 1 or -1를 입력하였습니다. 그러니 덜 헷갈렸던 거 같습니다.

---

<MS60 - 5. Shortest Route Module>

Node : 6개

ARCS(경로) : 9개

5. Shortest Route를 이용하면 Constraints를 설정할 필요 없이 간단하게 구할 수 있다.

[현승용]

자세한 과정 및 설명이 아주 좋아요~ ^^