Types of Network Flow Problems
A number of practical decision problems in
business fall into a category known as
Network Flow Problems.
The Network Flow Problems share a common
characteristic and can
be described or displayed in a graphical form
known as a Network.
Types of Network Flow Problems
This chapter focuses on several types of network flow problems:
- Transshipment problems
- Shortest Path problems
- Maximal Flow problems
- Transportation/Assignment problems
- Generalized network flow problems
- Minimum Spanning Tree problem
- The Transportation Problem
The Transportation Problem
The Bavarian Motor Company (BMC) manufactures expensive luxury cars in
Hamburg, Germany, and exports cars to sell in the United States. The exported cars
are shipped from Hamburg to ports in Newark, New Jersey and Jacksonville, Florida.
From these ports, the cars are transported by rail or truck to distributors located in
Boston, Massachusetts; Columbus, Ohio; Atlanta, Georgia; Richmond, Virginia; and
Mobile, Alabama.
Figure 5.1 shows the possible shipping routes available to the company along with
the transportation cost for shipping each car along the indicated path. Currently,
200 cars are available at the port in Newark and 300 are available in Jacksonville.
The numbers of cars needed by the distributors in Boston, Columbus, Atlanta,
Richmond, and Mobile are 100, 60, 170, 80, and 70, respectively. BMC wants to
determine the least costly way of transporting cars from the ports in Newark and
Jacksonville to the cities where they are needed.
