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 and demonstrating the use of linear programming for this type of problem.
Example
Waukesha, a small town in Wisconsin, is in the process of developing a road system for the downtown area. Bill Blackstone, one of the city planners, would like to determine the maximum number of cars that can flow through the town from west to east. The road network is shown in Figure 9.4. The streets are indicated by their respective arcs. For example, the arc from node 1 to node 2 is arc 1–2. The arc in the reverse direction (from node 2 to node 1) is arc 2–1. The numbers by the nodes indicate the maximum number of cars (in hundreds of cars per hour) that can flow from the various nodes along the respective arcs. The maximum flow along arc 1–2 is 3, while the flow along arc 1–3 is 10. The city planners would like to know the capacity of the current road system in the west-to-east direction.
Figure 9.4 Road Network for Waukesha Maximal-Flow Example
The maximal-flow problem can be modeled as a linear program. This type of problem may be viewed as a special type of transshipment problem with one source, one destination, and a number of transshipment points. The number shipped through the network would be called the flow. The objective is to maximize the flow through the network. There are two types of constraints. The first set of constraints restricts the amount of flow on any arc to the capacity of that arc. The second set of constraints indicates that the amount of flow out of a node will equal the amount of flow into that node. These are the same as the transshipment constraints in the transshipment problem.
The variables are defined as:
One additional arc will be added to the network, and this arc will go from the sink (node 6) back to the source (node 1). The flow along this arc represents the total flow in the network. The first set of constraints in the linear program consists of the maximum flows along each arc in each direction. These flows are grouped together based on the node from which the flow originates. The last six constraints are restricting the flow out of a node to equal the flow into a node (i.e., the flow into a node minus the flow out of that node must equal zero). The linear program is
subject to
The problem is now ready to solve using the linear programming module QM for Windows or using Solver in Excel 2016. However, Program 9.6 illustrates the solution found using Excel QM. To obtain this, from the Excel QM ribbon, select Network Analysis as LP and then choose Maximal Flow. In the initialization window that opens, you enter the number of nodes (6) and click OK. A worksheet is developed as seen in Program 9.6. Enter the data for the arc capacities, and then click Solver from the Data ribbon. Click Solve from the Solver input window, and the results (flows) are put into the worksheet.
