# The lines connecting certain pairs of nodes always allow travel in either direction.

1) WACO manufactures high-tech bicycles at two factories, one in Troy and one in Denver. The Troy factory can produce up to 150 bicycles per day, and the Denver factory can produce up to 200 bicycles per day. Bicycles are shipped by air to customers in Los Angeles and Boston. The customers in each city require 130 bicycles per day. Because of the deregulation of air fares, WACO believes that it may be cheaper to first fly some bicycles to New York or Chicago and then fly them to their final destinations. The costs of flying a bicycle are shown in the table below. WACO wants to minimize the total cost of shipping the required bicycles to its customers.

To

From? Troy Denver New York Chicago Los Angeles Boston

Troy $0 — $8 $13 $25 $28

Denver — $0 $15 $12 $26 $25

New York — — $0 $6 $16 $17

Chicago — — — $0 $14 $16

Los Angeles — — — — $0 —

Boston — — — — — $0

The following are feasible and optimal distribution routes, EXCEPT

a) New York->Los Angeles

b) Denver-Boston

c) New York->New York

d) Memphis->Chicago

2) Which of the following is not an assumption of a shortest path problem?

a) The lines connecting certain pairs of nodes always allow travel in either direction.

b) Associated with each link or arc is a nonnegative number called its length.

c) A path through the network must be chosen going from the origin to the destination.

d) The objective is to find a shortest path from the origin to the destination.

e) None of the above.

3) Which of the following is not an assumption of a maximum flow problem?

a) All flow through the network originates at one node, called the source.

b) If a node is not the source or the sink then it is a transshipment node.

c) Flow can move toward the sink and away from the sink.

d) The maximum amount of flow through an arc is given by the capacity of the arc.

e) The objective is to maximize the total amount of flow from the source to the sink.

4) Which of the following could be the subject of a maximum flow problem?

Products

a) Oil

b) Vehicles

c) All of the above

d) None of the above

5) What is the objective of a maximum flow problem?

a) Maximize the amount flowing through a network.

b) Maximize the profit of the network.

c) Maximize the routes being used.

d) Maximize the amount produced at the origin.

e) None of the above.

6) WACO manufactures high-tech bicycles at two factories, one in Troy and one in Denver. The Troy factory can produce up to 150 bicycles per day, and the Denver factory can produce up to 200 bicycles per day. Bicycles are shipped by air to customers in Los Angeles and Boston. The customers in each city require 130 bicycles per day. Because of the deregulation of air fares, WACO believes that it may be cheaper to first fly some bicycles to New York or Chicago and then fly them to their final destinations. The costs of flying a bicycle are shown in the table below. WACO wants to minimize the total cost of shipping the required bicycles to its customers.

To

From? Troy Denver New York Chicago Los Angeles Boston

Troy $0 — $8 $13 $25 $28

Denver — $0 $15 $12 $26 $25

New York — — $0 $6 $16 $17

Chicago — — — $0 $14 $16

Los Angeles — — — — $0 —

Boston — — — — — $0

The only cities that will have a surplus of bicycles are,

a) Memphis and New York

b) Memphis and Denver

c) New York and Chicago

d) New York and Denver

7) In a shortest path problem, when “real travel” through a network can end at more than one node:

a) an arc with length 0 is inserted.

b) the problem cannot be solved.

c) a dummy destination is needed.

d) c only.

e) a and c only.