Page 300 -

280 CHAPTER 7 TRANSPORTATION, ASSIGNMENT AND TRANSSHIPMENT PROBLEMS

We have spent the last few chapters looking in detail at linear programming. We
have seen that LP can be applied to a wide variety of optimization problems.
However, there are certain types of optimization problems that are worth looking
at separately. In this chapter we will look at a particular group of optimization
problems referred to as network flow problems. These typically relate to applications
involving transportation, assignment and transshipment models. As we shall see,
network flow problems are readily solved using LP. However, because of the special
mathematical structure of network flow problems, special solution algorithms have
been developed that we shall also consider.

Transportation Problem: A Network Model and a Linear
7.1
Programming Formulation

The transportation problem arises frequently in planning for the distribution of
goods and services from several supply locations to several demand locations.
Typically, the quantity of goods available at each supply location (or origin) is
limited, and the quantity of goods needed at each of several demand locations
(or destinations) is known. The usual objective in a transportation problem is to
minimize the cost of shipping goods from the origins to the destinations.
We’ll illustrate by considering a transportation problem faced by Foster Elec-
tronics. Amongst other things, the company manufactures memory cards that are
used in digital cameras. These are manufactured at three different plants: in the
Czech Republic, in Brazil and in China. The production capacity for each plant over
the next three-month planning period is shown below:

Origin Plant Three-Month Production Capacity (units)
1 Czech Republic 5 000
2 Brazil 6 000
3 China 2 500
Total 13 500
The transportation
problem was first The firm distributes its products through four distribution centres located in Boston,
formulated by
F. L. Hitchcock in 1941 Dubai, Singapore and London; the three-month forecast of demand for each of the
who also proposed a distribution centres is as follows:
solution procedure
similar to the general
Simplex method. Destination Distribution Centre Three-Month Demand Forecast (units)
Independently
T. C. Koopmans looked 1 Boston 6 000
on the same problem in 2 Dubai 4 000
connection with his work 3 Singapore 2 000
as a member of the Joint
Shipping Board. The 4 London 1 500
problem is frequently Total 13 500
referred to as the
Hitchcock–Koopmans
problem.
Management would like to determine how much of its production should be
shipped from each manufacturing plant to each distribution centre. Figure 7.1 shows
graphically the 12 distribution routes Foster can use. Such a graph is called a network;
the circles are referred to as nodes and the lines connecting the nodes as arcs.Each
origin or destination is represented by a node, and each possible shipping route is

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.