네트워크 문제: 최대 흐름 역량 파악

네트워크 모델에서 마지막으로 고려해야 할 사항은 바로 최대 흐름 문제이다. 이런 문제는 개념적으로 그동안 보아왔던 것과 매우 다르다. 네트워크 시스템의 역량을 조사하여 최대 흐름을 파악할 수 있다. 역량이란 최대 생산량을 의미한다. 예를 들어 파이프에서 얼마나 많은 양의 물을 보낼 수 있는지가 있다. 정유 회사 문제 위 경우에서의 최대 생산량이 무엇일까? 원유 생산지에서 정제소 까지 가는 데에 요구되는 각각의 비용이 arc에 써있고, 1부터 6까지 가는 것은 그동안 해온 문제다. 그동안은 비용을 최소화 하는 방식을 고려했다면, 이제는 비용을 고려할 필요가 없다. 알고자 하는 것은 노드 1에서 6까지 보낼 수 있는 최대 량이다.예를 들어서 X12, X24, X46이 각각 3이라면 X16은 9가 아니라 3이다. 최종적으로 도착한 양이 중요하기 때문이다. 위 문제에서 6개의 노드가 있으므로 6개의 제약조건이 있고, 8개의 arc가 있고, 이는 8개의 역량 한계점이 있다는 것을 의미한다. ...