shortest route 정리

[천주은(경영)]

해당그림에서 1번부터 6번까지 가는 min 거리를 알아내는 것이 목표이다.

min은 거리만 있는 것이 아니라 시간이 될 수도 있고, 비용이 될 수도 있다.

arc는 경로 node는 위치를 나타낸다.

만약 x12라면 node1에서 node2로 이동한다는 것을 의미한다.

해당 그림에서의 의사결정 변수는 x12, x13, x23, x32, x24, x42, x26, x35, x53, x45, x54, x46, x56 이다.

node 2로 들어오지 않았으면 다시 나가지 못한다는 것은 flow in flow out이라 한다.

즉, node2에 대한 제약조건은 x23+x24+x26-x12-x32-x42=0이 되는 것이다.

모든 변수는 0 or 1이 된다.

이를 토대로 MS60에 기입하면

이렇게 되고, 0-1 binary를 선택하면 

이러한 결과가 나온다. 이를 토대로 그림을 그려보면

최단거리는 32이고, 13->32->24->46을 거쳐 6번에 도달한다.

그림에 나와있는 것처럼 손으로 직접 해결할 수도 있는데

(어디에서 와서ㅣ얼만큼 왔는지)를 적어서 탈락 선정을 반복하면 손으로도 최단거리를 찾을 수 있다. 

-> node가 많을 경우 손으로 하는 것은 적절하지 않음

[현승용]

한학기 수고 했다.