서울에서 부산까지 화물운송을 위한 최대 운송가능량 및 운송비가 아래와 … | [물류관리사] 16년 1회차 기출문제 상세 페이지

서울에서 내보낼 수 있는 최대 8단위를 단위비용이 낮은 경로부터 채우면 최소 총 운송비용은 70이 된다.
그림의 간선은 서울→1이 3(2), 서울→2가 3(2), 서울→3이 2(3)이고, 1→5가 3(1), 1-2가 2(2), 2→4가 4(1), 2-3이 3(2), 4→5가 3(6), 4→6이 4(3), 4→7이 2(2), 3→7이 2(3), 5→부산이 4(4), 6→부산이 4(3), 7→부산이 3(5)이다. 서울에서 나가는 용량 합이 3+3+2=8이므로 운송 가능량은 8단위로 묶인다.
서울-1-5-부산: 단위비용 2+1+4=7, 병목 용량 3 → $3 \times 7 = 21$
서울-2-4-6-부산: 단위비용 2+1+3+3=9, 병목 용량 3 → $3 \times 9 = 27$
서울-3-7-부산: 단위비용 3+3+5=11, 병목 용량 2 → $2 \times 11 = 22$
세 경로를 합하면 $21+27+22 = 70$ 이다. 서울-3에서 출발한 물량을 2를 거쳐 4로 우회시키면 단위비용이 12~13으로 올라가고 4→6 잔여용량도 1단위뿐이어서 더 싼 대안이 존재하지 않는다.