Page 377 -
P. 377
MAXIMAL FLOW PROBLEM 357
Figure 8.15 The Management Scientist Solution for the Regional Computer Centre
Minimal Spanning Tree Problem
**** NETWORK DESCRIPTION ****
6 NODES AND 11 ARCS
ARC START NODE END NODE DISTANCE
--- ---------- -------- --------
1 1 2 20
2 1 3 40
3 1 4 30
4 1 5 50
5 1 6 40
6 2 5 40
7 3 4 10
8 3 5 30
9 3 6 30
10 4 6 20
11 5 6 40
MINIMAL SPANNING TREE
*********************
START NODE END NODE DISTANCE
---------- -------- --------
1 2 20
1 4 30
4 3 10
4 6 20
3 5 30
TOTAL LENGTH 110
8.3 Maximal Flow Problem
The objective in a maximal flow problem is to determine the maximum amount of
flow (vehicles, messages, fluid, etc.) that can enter and exit a network system in a
given period of time. In this problem, we attempt to transmit flow through all arcs of
the network as efficiently as possible. The amount of flow is limited due to capacity
restrictions on the various arcs of the network. For example, highway types limit
vehicle flow in a transportation system, while pipe sizes limit oil flow in an oil
distribution system. The maximum or upper limit on the flow in an arc is referred
to as the flow capacity of the arc. Even though we do not specify capacities for the
L. R. Ford and D. R. nodes, we do assume that the flow out of a node is equal to the flow into the node.
Fulkerson set out the As an example of the maximal flow problem, consider the road network system
procedure for solving the
maximal flow problem in passing through Glasgow, Scotland. The vehicle flow travelling west to east reaches a
1955. level of 15 000 vehicles per hour at peak times. Due to a summer highway
Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
