Quantitative Analysis for Management, 13/e

9.4 Maximal-Flow Problem

The maximal-flow problem involves determining the maximum amount of material that can flow from one point (the source) to another (the sink) in a network. Examples of this type of problem include determining the maximum number of cars that can flow through a highway system, the maximum amount of a liquid that can flow through a series of pipes, the maximum number of cell-phone calls that can pass through a series of cell towers, and the maximum amount of data that can flow through a computer network.

To find the maximal flow from the source or start of a network to the sink or finish of that network, two common methods are used: linear programming and the maximal-flow technique. We will begin by presenting an example ...