4주차 2차시 복습

[윤수정(행정)]

maximal flow

공사중인 고속도로에 혼잡함을 줄이기 위해 흘러가는 양 곧 들어오는 차를 신호등으로 컨트롤하여 공사 끝나는 구간으로 움직이게 한다.

가변적이기 때문에 LP를 이용해서 해결해야한다.

node1에서 node7까지 가는 최대 차량 수를 구하기 위해 flow out=flow in을 적용해서 node 7에서 나가는 차량을 node1로 다시 돌아오는 것으로 설정하고 이를 최대화하는 식을 세울 수 있다. Max x71

그리고 node1에서 시작하는 길을 한번만 지나가야하니깐 x12+x13+x14=x71가 되야한다. 

각 노드마다 flow out=flow in을 적용해서 제약조건식을 세울 수 있다.

그리고 flow capacity가 각 arc마다 다르니깐 각 arc는 최대 flow capacity보다 작거나 같다는 제약조건식을 세울 수 있다.

이를 ms60을 integer

LP를 이용해서 풀면

[현승용]

차분히 해나가면 된단다.