4주차 1차시 복습

[윤수정(행정)]

0-1 integer variables에서 flexibility를 제공할 수 있는 방법

w1+w2+w3=1이라고 제약조건을 세우면 셋 중에 꼭 1개는 채택되어야 하며 1개밖에 확장하지 못한다.

w1+w2+w3<1이라고 제약조건을 세우면 셋 중에 한개는 채택이 될 수도 아닐수도 있다. 확장을 하지 않아도 되고 한다면 1개만 가능하다

w1+w2+w3+w4+w5=2라는 제약조건이면 다섯 중 2개는 꼭 채택이 되어야한다. 

w1+w2+w3+w4+w5<2라는 제약조건이라면 다섯 중 2개가 채택이 될수도 한개만 채택될 수도 확장을 하지 않을 수도 있다.

W<P라는 제약조건일때 p=0이면 w=o이다. 하지만 p=1이면 w는 1일수도 0일수도 있다.

W=P라는 제약조건이면 p=0이면 w=0, p=1이면 w=1이다.

이렇게 제약조건의 작은변화가 최적해에 큰 영향을 준다는 것을 알 수 있다.

shortest route

1node부터 6node까지 가는 가장 짧은 거리를 구하는 것

구하는 것이 비용, 시간, 거리, 보험료라고 하면 minimization이고 고객만족도라고 하면 maximization이 된다. 다만 max가 되면 shortest route는 안되고 LP로만 최적해를 구할 수 있다. 

ms60의 shortest route로 구할 수도 있고 LP로 구할 수도 있다.

먼저 ms60의 shortest route module로 실습을 해보면

arc는 9개, node는 6개고 거리를 입력하고 시작하는 node를 1, 끝나는 node를 6으로하면 총 32거리의 1에서 3, 3에서 2, 2에서 4, 4에서 6으로 가는 shortest route를 구할 수 있다.

Lp를 이용하면

1node에서 2node를 가는것을 X12라고 표현하고 걸리는 거리를 25x12로 LP 제약조건식을 세울 수 있다. 그리고 같은 거리지만 2에서 3으로 가는 방향과, 3에서 2로 가는 방향을 x23, x32로 다르게 표현하여 나타낼 수 있다.

최소화식을 세우면 

Min 25x12+20x13+3x23+3x32+5x24+14x26+6x35+6x33+4x45+4x34+4x46+7x56

그리고 x12와 x13은 두 길이 같이 갈 수 없고 두 길중 하나는 무조건 지나가야한다. 그래서 x12+x13=1이라는 제약조건식이 추가된다.

나가는 방향 길과 들어가는 길이 두개이면 안되니까 flow out=flow in으로 제약조건식을 세운다.

node 2에는 x23+z24+x26=x12+x32+x42 -> x23+x24+x26-x12-x32-x42=0으로 세울 수 있다. 하지만 도착하는 6에서 돌아올 필요는 없으니깐 x62는 표함하지 않아도 된다.

다른 node들도 똑같이 세우면

node 3 x32+x35-x13-x23-x53=0

node 4 x42+x45+x46-x24-x54=0

node 5 x53+x54+x56-x35-x45=0

그리고 도착하는 node인 6에서 오는 길인 x26+x46+x56이 여러개 일 수는 없으니깐 x26+x46+x56=1이라는 제약조건을 세워야한다.

ms60으로 실습을 해보면

[현승용]

수작업으로도 계산 한번 해보면 도움이 될거다.