The maximum flow problem is again structured on a network;
but here the arc capacities, or upper bounds, are the only
relevant parameters. The problem is to find the maximum
flow possible from some given source node to a given sink
node. A network model is in Fig. 17. All arc costs are zero,
but the cost on the arc leaving the sink is set to -1. Since
the goal of the optimization is to minimize cost, the maximum
flow possible is delivered to the sink node.
Figure 17. Network model for the maximum flow problem.
The solution to the example is in
Fig. 18. The maximum flow from node 1 to node 8 is 30 and the
flows that yield this flow are shown on the figure. The heavy
arcs on the figure are called the minimal cut. These arcs are
the bottlenecks that are restricting the maximum flow. The fact
that the sum of the capacities of the arcs on the minimal cut
equals the maximum flow is a famous theorem of network theory
called the max flow - min cut theorem. The arcs on the minimum
cut can be identified using sensitivity analysis.
Figure 18. Solution. Maximum flow = 30.
Operations Research Models and Methods
Internet
by Paul A. Jensen
Copyright 2004 - All rights reserved
