ISSUES 382

b) In cu between three directed cycles . After identifying an and it may be affordable to replace it in a year or two. The following
undirected cycle that includes all nodes . table provides the total net discounted costs associated with the
c) Identify a set of square arcs that form a spanning tree s ion . purchase of the tractor (purchase price minus sales value of the tractor
d ) Use the process presented in Figure 9.3 to build a tree one arc at a in use plus operating and maintenance costs) at the end of year i and if
time until you have a spanning tree. Then repeat the process to replaced at the end of year j (where the present moment is year 0) .
obtain another spanning tree. [Do not duplicate the spanning tree
identified in part c ).] j
9.3- 1. Read the reference article that describes in detail the IO study 1 2 3
summarized in the application box presented in section 9.3. Briefly
describe which network optimization model was applied in that study. 0 $13 0 00 $28 000 $48 000
List the different financial benefits certain and other types that resulted Yo 1 $17 000 $33 000
2 $20 000
from that study.
9.4- 2. You must take a car trip to a city that you have never ca has
visited. Study a map to determine the shortest route to your The problem is determining when (if any) you should replace The
destination. Depending on the route you choose, there are five other tractor should be replaced to minimize the total cost over the three
cities (named A, B, C, D, E) that you can pass through along the way . years.
The PLA It does not show the miles of each road that are a direct a) Formulate this as a shortest path problem .
connection between two cities without another intervening. These b) Use the somewhat rhythm described in section 9.3 to solve this
figures are summarized in the following table, where a dash indicates shortest path problem.
that there is no direct connection without passing through other cities. C c ) Formulate and solve the model in a spreadsheet .

Miles between adjacent cities 9.3- 4. *

Use the algorithm described in section 9.3 to find find the
Destinatio shortest path through networks a ) and b ) , in which the numbers
TO b c d AND
City n represent the actual distances between the running nodes teeth.
Origin 40 60 50
— — —
TO 10 — 70 — —
b 20 55 40 —
c — 50 —

d 10 60
AND 80

(Destinati
on)

a) Formulate this as a shortest route problem when drawing a

network where the nodes are cities, the arcs are roads , and the
numbers are the distance in miles.
b) Use the algorithm described in section 9.3 to solve this shortest
path problem.
C c ) Formulate and solve a spreadsheet model for this problem .
d ) If each number in the table represents your cost (in dollars) of
driving from one city to the next, do you get the minimum-cost
route with your answer to part b ) or c )?
e ) If each number in the table represents your time ( in minutes ) to
drive from one city to the next , do you obtain the minimum time
route with the answer in part b ) or c )?
9.4- 5. Formulate the shortest path problem as one of pro Linear
9.3-3. A local airline plans to buy a new tractor to move the train of grading .
cars that carry and bring luggage from planes that land at a small
9.5- 6. A Speedy Airlines flight is about to take off from Seattle
airport that is in full swing. not growth. Within three years a new
nonstop to London. There is some flexibility in choosing the precise
mechanized baggage transport system will be installed, so there will
route, depending on weather conditions. The following network
be no need to the tractor will stop. However, it will have a heavy
scribes the possible routes considered, where SE and LN are Seattle
workload and operation and maintenance costs will increase quickly
383 CHAPTER 9 NETWORK OPTIMIZATION MODELS

and London, respectively, and the other nodes represent various Normal
$5 million — — —
locations. gar is inter media s . Break $9 million $10 million $14 million $6 million
Priority $14 million $15 million $19 million $9 million

Management wishes to determine the level at which each of the four

stages should be performed to minimize the total time to meal.
cialization of the product subject to budget constraints. a ) Formulate
this as a shortest path problem.
b ) Use the algorithm described in section 9.3 to solve it.

9.4- 1. * Reconsider the networks shown in Problem 9.3-4. Use the

The wind along each arc considerably affects flight time, and therefore algorithm described in section 9.4 to find the minimum spanning tree for
fuel consumption. Based on the current weather report, flight times (in each of them.
hours) are displayed next to the arcs. Due to the high cost of fuel, the 9.5- 2. The Wirehouse lumber company will cut down trees in eight
administration has adopted the policy of choosing the route that areas of the same area. But first you must develop a system of dirt
minimizes the total flight time. roads to access any area from any other. The distance (in miles)
a) What plays the role of “distances” in the interpretation of this between each pair of zones is:
problem?
b) Use the algorithm described in section 9.3 to solve this shortest
path problem. Distance between zone pairs
C c ) Formulate and solve the model in a spreadsheet. 1 2 3 4 5 6 7 8

9.3- 7. Quick Company has found out that a competitor plans to 1 — 1.3 2.1 0.9 0.7 1.8 2.0 1.5
launch a new type of product with very large potential sales. des. 2 1.3 — 0.9 1.8 1.2 2.6 2.3 1.1
Quick has been working on a similar product scheduled to come out 3 2.1 0.9 — 2.6 1.7 2.5 1.9 1.0
within 20 months. However, the research is almost finished and now Zone 4 0.9 1.8 2.6 — 0.7 1.6 1.5 0.9
5 0.7 1.2 1.7 0.7 0.9 1.1 0.8
the management wants to launch the product more quickly to face the —

6 1.8 2.6 2.5 1.6 0.9 — 0.6 1.0

competition.
7 2.0 2.3 1.9 1.5 1.1 0.6 — 0.5
Four independent stages must be overcome that include what is 8 1.5 1.1 1.0 0.9 0.8 1.0 0.5 —
missing from the investigation that is currently being carried out at a
normal pace. However, each stage can be performed at a priority or
concentration level to speed completion and these are the only levels The problem is to determine the pairs of zones between which
considered in the last three stages. The times required for each level roads must be built to connect them all with a minimum total road
are shown in the following table. (The times in parentheses length.
corresponding to the normal level have been removed because they are a) Describe how this problem fits the description of the pro
too long.) Minimum spanning tree problem.
b) Use the algorithm described in section 9.4 to solve it.

Time 9.4- 3. Premiere Bank has decided to connect computer terminals

from each branch to the central computer of its headquarters through
Start of
special telephone lines with telecommunication devices. nications. It is
production and
Remaining
not necessary for a branch office's telephone line to be directly
Developme Manufacturing distribution
Level research nt system design connected to the head office. The connection can be indirect through
another branch that is connected (directly or indirectly) to the
Normal 5 months (4 months ) (7 months ) (4 months ) headquarters. The only requirement is that there be some route that
Break 4 months 3 months 5 months 2 months connects all the branches to the head office.
Priority 2 months 2 months 3 months 1 month
The charge for special telephone lines is directly proportional to
the wired distance, where the distance (in miles) between each pair of
The administration has allocated $50 million for the four stages. offices is:
The cost (in millions of dollars) of each phase at the different levels
under consideration is:
Distance between pairs of offices
Cost Major S.1 S.2 S.3 S.4 S.5
Start of
Main office — 190 70 115 270 160
production Branch 1 190 100 110 215 50
and —
Remaining Manufacturing Branch 2 70 100 — 140 120 220
Level research Development system design distribution Branch 3 115 110 140 — 175 80
Branch 4 270 215 120 175 — 310
Branch 5 160 50 220 80 310
—
 ISSUES 384

Management wants to determine which pairs of branches to connect origin, destination, and transshipment nodes, and plot the
connect directly with the special telephone lines so that all are complete network showing the capacity of each arc.
connected (directly or indirectly) to the headquarters office with a b) Use the rising path algorithm presented in Section 9.5 to solve this
minimum total cost. problem.
a ) Explain how this problem fits the description of the problem. C c ) Formulate and solve the model in a spreadsheet.
Minimum spanning tree problem.
9.5- 4. The Texago Corporation has four oil fields, four three
b ) Use the algorithm described in section 9.4 to solve this problem.
refineries and four distribution centers. A strong strike in the transport
*
9.5- 1. For the network shown below, use the rising path algorithm industry has considerably reduced the ca Texago's ability to ship oil
described in section 9.5 to find the flow pattern that provides the from its fields to refineries and derived products to distribution
maximum flow from the source node to the destination node, given that centers. Use units in thousands of barrels of crude oil (and its
the capacity through the arc that goes from node i to node j is the equivalent in production). refined cough); The following tables show
closest number to node i of the arc between these nodes. Show your the maximum number of units that can be sent per day from each field
work. to each refinery and from these to each distribution center.

Refinery
saint
N. Orleans Charleston seattle
Field Louis

Texas 11 7 2 8
California 5 4 8 7
Alaska 7 3 12 6
Midwest 8 9 4 15

Center of distribution

Refinery Pittsburgh atlanta Kansas City San Francisco

9.5- 2. Formulate the maximum flow problem as a linear N. Orleans 5 9 6 4
programming problem. Charleston 8 7 9 5
seattle 4 6 7 8
9.5- 3. The following diagram describes an aqueduct system that
saint Louis 12 11 9 7
originates in three rivers (Rl, R2 and R3) and ends in a city. te (node
T), where the other nodes are union points of the system. Texago management wants to develop a plan to determine mine
how many units to ship from each oil field to each refinery and from
each refinery to each distribution center so that the total number of
units arriving at the distribution centers is maximized.
a) Sketch a plan showing the location of the fields, refi Texago
factories and distribution centers. Aggregate the flow of crude oil
and petroleum products through the distribution network.
b) Draw the network again, aligning the field nodes in one column,
the refinery nodes in another, and the cens in a third. distribution
systems. Then add arcs to show the possible flow.
c) Modify the network from part b ) to formulate this problem as a
maximum flow problem with only one source, one destination,
and one layer. city of each arch.
Use units of thousands of acre-feet; The following tables show d ) Use the rising path algorithm from Section 9.5 to solve the
the maximum amount of water that can be pumped through each maximum flow problem.
aqueduct each day. C e ) Formulate and solve the model in a spreadsheet.

F omA FromA
9.5-5. A track of the Eura Railroad system runs from Faireparc, the
FromA largest industrial city, to Portstown, the largest port city. This route is
From B TO b c
h d
AN
D F Of T frequently used by both passenger expresses and freight trains.
R1 130 115 — TO 110 85 — d 220
Expresses are carefully scheduled and have priority over slower
R2 70 90 110 b 130 95 85 AND 330 freight trains (it's a European railroad), so the freight train must exit
R3 140 120 c 130 160 F 240 onto a side track when a passenger train is scheduled to pass it. Freight
— —
service needs to be increased, so the problem is scheduling trains in a
The water commission wants to determine the plan that maximizes the way that maximizes the number of trains. grouper that can be sent
flow of water into the city. every day without interfering with fixed express schedules.
a) Formulate this problem as a maximum flow problem; Identify an
Consecutive freight trains must maintain a different schedules of
at least 0.1 hour; this unit of time is used po to program them, so the
385 CHAPTER 9 NETWORK OPTIMIZATION MODELS

day's itinerary indicates the po relative position of each freight train at Store
times 0.0, 0.1, 0.2, . . . , 23.9. There are S side tracks between Center of
Faireparc and Portstown, which are long enough to receive n i freight distribution 1 2
trains ( i 5 1, . . . , S ). It takes t i units of time (rounded to an integer)
for a freight train to travel from side track i to i 1 1—with t 5 time Factory 1 3 7 — 80
0
Factory 2 4 9 70
required to go from Faireparc to track 1 and t S is the time from the S —

frontage road to Portstown. A freight train is allowed to pass or leave Center of distribution 2 4
the side track i ( i 5 0, 1, . . . , S ) at time j ( j 5 0.0, 0.1, . . . , 23.9) if, as
scheduled, an express will not reach it before reaching the side track i 1 Assignment 60 90
1 (let di ij 5 1 if it will reach it and di ij 5 0 if not). A freight train is also
required to wait if there is no room on the next side tracks, before an a) Formulate the network representation of this problem as a
express overtakes it. minimum cost flow problem.
Formulate this problem as a maximum flow problem and identify b) Formulate a linear programming model for this problem.
each node (not including source or destination) and each arc with the
flow capacity for the network representation of the problem. ( Tip : 9.6- 4. Reconsider Problem 9.3-3. Now formulate this problem as a
Use a different set of nodes for each of the 240 times pos.) minimum cost flow problem and show its representation. appropriate
networking.
9.5- 6. Consider the maximum flow problem shown in the following
network, where A is the source node and F is the demand node, while 9.6- 5. Makonsel is a comprehensive company that produces goods
the capacities are the numbers shown next to the directed arcs. and sells them in its own stores. After the goods are produced, they are
placed in two warehouses until the stores need them. Trucks are used
to transport the goods to the warehouses and then to the three stores.
Use a full truck load as a unit; the next one The table shows the
monthly production of each plant, its transportation cost per load sent
to each warehouse and the maximum quantity that can be sent per
month to each one.

TO Shipping unit cost Shipping capacity

Of Store Store Store Store

a ) Use the rising path algorithm described in section 9.5 to solve this 1 2 1 2 Production
problem. Floor 1 $1 1 75 $1 580 375 450 600
C b ) Formulate and solve a spreadsheet model for this problem. Floor 2 $1 430 $1 700 525 600 900

9.6- 1. Read the article that describes in detail the IO study

summarized in the application box in section 9.6. Bre vely describe The following table contains the monthly demand for each store (
how the minimum cost flow model can be applied to this study. T ), the cost of transportation by truck from each warehouse, and the
Briefly describe how network optimization models were applied to quantity maximum amount that can be sent per month from each one.
this study. Then list the different financial and other benefits that said
study showed.
TO
9.6- 2. Reconsider the maximum flow problem presented in Problem Shipping unit cost Shipping capacity
9.5-6. Formulate this problem as a minimum cost flow problem, and Of T1 T2 T3 T1 T2 T3
add the arc A → F. Use F 5 20.
Warehouse 1 $1 370 $1 505 $1 490 300 450 300
9.6- 3. A company will manufacture the same new product in two Warehouse 2 $1 190 $1 210 $1 240 375 450 225
plants and then ship it to two warehouses. Factory 1 can ship an
Demand 450 $600 $450 450 600 450
unlimited quantity by rail only to warehouse 1, while after factory 2
can send an unlimited quantity for the same ma route only to
warehouse 2. However, separate freight trucks can be used to ship up
Management wishes to determine a distribution plan—no number of
to 50 units from each factory to a distribution center from which up to
loads sent per month from each plant to each warehouse and from each
50 units can be shipped to each warehouse. The following table shows
of these to each store—so that the total transportation cost is
the unit shipping cost of each alternative along with the quantities that
minimized.
will be produced in the factories and the quantities needed in the
warehouses.

Of TO Unit shipping cost Production

 ISSUES 386

a) Draw a network that describes the company's distribution network. purchasing costs (including shipping charges) and shipping costs from
Identify the source, transshipment and demand nodes in it. warehouses to factories.
b) Formulate this problem as a minimum cost flow problem and enter a) Draw a network that describes the network of Audio providers file.
all the necessary data. Identify the supply, transshipment and transportation nodes in it.
C c ) Formulate and solve a spreadsheet model. command.
C d ) Use a computer to solve this problem without using Excel. b) Formulate this problem as a minimum cost flow problem, with all
9.6- 6. The Audiofile company produces portable sound devices. the necessary data on the network. Additionally, include a dummy
However, the administration has decided to outsource the production. demand node that receives (at no cost) unused capacity from
tion of the speakers necessary for said sound devices. There are three suppliers.
providers. Their prices for each shipment of 1,000 speakers are shown C c ) Formulate and solve the model in a spreadsheet.
in the following table. C d ) Use a computer to solve the problem without using Excel.
Supplier Price 9.7-1. Consider the minimum cost flow problem presented in the
D
following figure, where the values of b i (net flows generated) are
1 $22 500 given at the nodes, the values of c ij (cost per unit flow rate) are given
2 $22 700
in the arcs and the values of u ij (arc capacities) are found between
3 $22 300
nodes C and D. Perform this task manually.
a ) Obtain an initial BF solution by solving the tree expansion bowl
Additionally, each supplier will charge a shipping cost. Each shipment
feasible with the basic arcs A → B , C → E , D → E and C → A (an
will arrive at one of the company's two warehouses. Each provider has
inverted arc), in which one of the arcs
its own formula to calculate this cost based on miles re sum of
runs to the warehouse. These formulas and the mileage data are
shown below.

Supplier Shipping charge

1 $300 + 40¢/mile
2 $200 + 50¢/mile
3 $500 + 20¢/mile

Supplier Warehouse 1 Warehouse 2

1 1,600 miles 1,400 miles

2 1,500 miles 1,600 miles
3 2,000 miles 1,000 miles nonbasics ( C → B ) is also an inverted arc. Show the resulting
network (include b i , c ij , and u ij ) in the same format as above—
When one of the two factories requires a shipment of speakers except that you must use dashed lines to draw the nonbasic arcs—
to liven up the dances, it hires a truck to bring them from the and add the flows in parentheses next to the arcs.
factory. warehouses. The cost per shipment is presented in the Use the optimality test to verify that this initial BF solution is
following column na, along with the number of shipments per
b optimal and that multiple optimal solutions exist. Perform an
month required by each plant. ) iteration of the network simplex method to find the other optimal
BF solution and use these results to identify the other optimal
Unit cost per shipment solutions that are not BF solutions.
Factory 1 Factory 2 Now consider the following BF solution.
c
Warehouse 1 $200 $700 )
Warehouse 2 $400 $500
basic bow Flow Non-basic bow
Monthly demand 10 6
A—D 20 A—B
B—C 10 A—C
Each supplier can supply up to 10 shipments per month; but due EC 10 B—D
to transportation limitations, each can ship a maximum of only 6 OF 20
shipments per month to each warehouse. By way of
Similarly, each warehouse can send up to 6 shipments per month to network method. Identify the incoming basic arc, the outgoing one,
each factory. and the next BF solution, but do not continue.
Now, management wants to develop a monthly plan to determine
9.7- 2. Reconsider the minimum cost flow problem introduced in
how many shipments (if any) to order from each pro. supervisor, how
Problem 9.6-2.
many of them should go to each warehouse and how many shipments
each warehouse should send to each factory. The objective is to
minimize the From this BF solution, apply an iteration of the simplex