출발지에서 도착지까지 파이프라인을 통해 가스를 보낼 경우 보낼 수 있는… | [물류관리사] 23년 1회차 기출문제 상세 페이지

파이프라인 용량 제약 아래 출발지에서 도착지로 보낼 수 있는 최대 가스량은 16톤이다.
그림의 링크 용량은 출발지→a 10, 출발지→b 12, a→c 6, a→d 5, a→b 6, b→d 10, c→도착지 12, d→e 14, d→f 3, e→f 7, f→도착지 15이다. 도착지로 들어오는 링크는 c→도착지와 f→도착지 둘뿐이므로 이 둘의 실제 유입량이 답을 결정한다.
c로 들어오는 링크는 a→c(6) 하나뿐이라 c 경유 유량은 최대 6톤이고, f로 들어오는 링크는 d→f(3)와 e→f(7)이며 e는 d→e를 통해서만 공급받으므로 f 경유 유량은 최대 3+7=10톤이다. 따라서 상한은 6+10=16톤이다.
이 상한은 실제로 달성된다. 출발지→a 6, a→c 6, c→도착지 6으로 6톤을 보내고, 출발지→b 10, b→d 10에 이어 d→f 3과 d→e 7, e→f 7로 f에 10톤을 모아 f→도착지 10톤(용량 15 이내)을 흘리면 모든 용량을 만족하면서 합계 16톤이 도착지에 도달한다.