CHAPTER 4
NETWORK MODELS
TRUE/FALSE QUESTIONS
1. In a problem formulated as a standard transportation model, if
all the source/destination quantities are integer-valued, the set of
solution variables is guaranteed to be integer-valued as well.
2. The optimal total shipping cost in a minimization
transportation model is $622, and the reduced cost from source node
1 to destination node 6 is $6. This implies that if one were to
deviate from the optimal solution by shipping one unit from node 1
to node 6, the new minimum total shipping cost would be $628.
3. If a general linear programming problem can also be formulated
as a network problem, the network formulation is generally
preferable because of easier model input and a quicker solution
4. Minimal spanning tree problems do not lend themselves to a
5. In addressing and solving a maximal flow problem, flow
capacities between adjacent nodes must be equal in both directions.
6. A map of the United States can be drawn as a network with each
state represented by a node and arcs connecting each pair of states
7. Transshipment, assignment, shortest path, and traveling
8. In network flow models, all arcs are generally assumed to be
directed. In connectivity models, all arcs are generally assumed to
10. For a network of n nodes, a spanning tree contains n – 1 arcs.
11. The objective function of a transportation model is to
12. A bi-directional arc in a shortest path problem can be modeled
13. An optimal maximum flow solution will involve positive flow on
14. You can solve the traveling salesman problem by selecting a
15. A minimal spanning tree connects all nodes in a minimal total
MULTIPLE CHOICE QUESTIONS
1. In the standard assignment problem where, for example, workers
are being assigned tasks, which of the following situations would
preclude the application of the assignment approach (the Hungarian
algorithm)?
a. A worker may be assigned to more than one job.
b. A worker may be unable to perform a certain job.
c. The number of workers does not equal the number of jobs.
d. Workers may perform fractional parts of jobs.
2. In a problem formulated as a standard transportation model,
where there are m sources and n destinations, the number of arcs
(routes) in an optimal solution need be:
a. m * n.
b. m + n.
c. no less than (m * n) – 1.
d. no greater than (m + n) – 1.
3. The assumptions underlying the application of the basic
transportation model do not include:
a. any node may represent either a source or a destination.
b. unit shipping costs may be constant or declining (i.e.,
quantity discounts) but not increasing with volume.
c. all shipments must occur in the same time frame.
d. shipments may not be sent back from a destination to a
source.
4. In a standard transportation model, each objective function
coefficient represents the:
a. total cost of shipping from a source to a destination
node.
b. fixed cost of utilizing the route between a source and
destination node.
c. unit cost of shipping from a source to a destination
node.
d. negative “unit cost” of not using the route between a
source and a destination node.
5. A city needs to design and build a completely new storm
drainage system. The excess rainwater runoff in each neighborhood
is to be channeled to a suburban reservoir. The appropriate network
model would most likely be:
a. transportation/transshipment.
b. shortest path.
c. minimal spanning tree.
d. maximal flow.
6. A transportation model has been selected to represent the
production schedule of a product to meet demand over a twelve month
planning horizon with 12 production nodes, on each of which is
defined the production capacity for each month, and 12 demand nodes,
on each of which is defined the demand for each month. If goods can
be stored a maximum of 3 months, which of the following statements
is not true?
a. There should be no arc from production node 1 to demand
node 5.
b. There should be no arc from production node 5 to demand
node 1.
c. There will be no feasible solution if demand in any one
month cannot exceed the production capacity for that
month.
d. There will be no feasible solution if the total demand
of the first m months cannot exceed the total production
capacity for the first m months.
7. In which of the following network models is it not possible to
“ship” both in and out of a given node?
a. Transshipment
b. Traveling salesman
c. Maximal flow
d. Assignment
8. A model which matches salespeople to retail customers based on
estimated profit potential of each salesperson-retail customer
match, where each salesperson is to be matched with at most 25
retail customers, could be modeled as which network models?
a. Either as a shortest path or a traveling salesman model.
b. Either as a minimal spanning tree or a maximal flow
model.
c. Either as a maximization assignment model or a
maximization transportation model.
d. Either as a capacitated transshipment model or a direct
enumeration model.
9. A car dealership uses its van to drive its service customers
to their jobs. If the dealership van has five people who need to be
taken to work, what network algorithm should be used in order to
minimize the distance the van must travel in order to accomplish
this task?
a. Shortest path
b. Minimal spanning tree
c. Traveling salesman
d. Transportation
10. In a minimal spanning tree problem:
a. If node 1 is connected to node 3, which is connected to
node 5, the shorted path from node 1 to node 5 is 1-3-5.
b. The optimal solution is found by adding arcs of least
distance until all nodes are connected.
c. The arcs between nodes 1 and 5, between nodes 1 and 9,
between nodes 3 and 5, and between nodes 5 and 9 cannot
all be included in the optimal solution.
d. The solution will include n arcs.
11. In a shortest path model:
a. The arc between nodes A and B must have the same value
as the arc between arc B and A.
b. The goal is to find the minimum distance between the
start node and the terminal node.
c. Negative arc distances are not prohibited.
d. Unidirectional arcs are permitted.
12. In a maximal flow problem:
a. Multiple sources may be accommodated, but multiple sinks
may not.
b. Arc capacities must be the same in either direction.
c. There are several different linear programming
formulations for the model.
d. The connected arcs may contain no cycles.
13. The optimal solution to an assignment model can be obtained by
solving the problem as each of the following models except:
a. a traveling salesman model.
b. a transportation model.
c. a binary integer programming model.
d. a linear programming model.
14. A B-1 bomber must fly through a choice of “safe areas,”
deliver its bombing payload, and return to its home base using
minimum fuel. Which network model would be the most appropriate
representation?
a. Shortest path
b. Minimal spanning tree
c. Traveling salesman
d. Transportation
15. An environmental impact report for a proposed new industrial
center complex must include the total amount of sewage that can be
pumped through existing pipes. Which network model would be the
most appropriate representation?
a. Shortest path
b. Minimal spanning tree
c. Traveling salesman
d. Maximal flow
16. Which statement is not true?
a. The Ford-Fulkerson method solves the maximal flow
problem by finding the minimum cut.
b. The minimum cut will provide an optimal solution to the
maximal flow problem.
c. The maximal flow equals the sum of the capacities of the
minimum cut.
d. The flows on all arcs on the minimum cut will be at
their upper bounds.
17. Which of the following is not an algorithm for solving the
assignment model?
a. Transportation model
b. Dynamic programming
c. The Hungarian algorithm
d. The Dijkstra algorithm
18. Which of the following is true about an intermediate node in a
transshipment problem?
a. The net flow out must be zero.
b. The node must connect to at least one supply node and at
least one demand node.
c. The number of arcs connected to supply nodes must be
less than or equal to the number of arcs connected to
demand nodes.
d. The total capacity of outbound arcs must equal the total
capacity of inbound arcs.
19. Which of the following cannot model a blocked route on a
transportation model?
a. A very large objective coefficient.
b. A constraint on shipment equal to zero.
c. Excluding the cell from the list of changing cells in
the Excel Solver parameters.
d. Assigning an objective function coefficient of zero.
20. Two nodes are said to be connected if what exists?
a. An arc between them.
b. A path between them.
c. A network containing both nodes.
d. A cycle between them.
SHORT ANSWER QUESTIONS
1. The optimal solution to a standard linear programming problem
need have no more non-zero-valued decision variables than there are
linear constraints. The standard balanced transportation model, in
which total supply equals total demand, has one linear constraint
restricting the amount shipped from each of the m source nodes and
one linear constraint restricting shipments into each of the n
demand nodes. For this model, which is simply a special case of
linear programming, the number of non-zero-valued decision variables
in the optimal solution need be no more than one less than the total
number of linear constraints. Why?
2. In formulating a transportation model using a balanced format
in which total supply must equal total demand, indicate how to model
each of the following unusual circumstances:
3. Name the two types of nodes in a network flow model.
4. Network connectivity models solve what type of problem?
5. Network flow models are integer linear programming models.
Why, then, would we prefer using a linear programming model? Does
the linear programming model give an optimal solution?
6. What is the term for a path from a node that returns to the
same node without including any arc more than once?
7. In a transportation model, how are shadow prices interpreted
for supply nodes? For demand nodes?
8. Identify the four parts of a maximal flow problem.
9. The Greedy algorithms for solving the minimal spanning tree
problem require selecting the remaining arc with the smallest cost
unless what is true?
10. Describe two Greedy algorithms for solving the minimal
spanning tree problem.
FORMULATION/SOLUTION/ANALYSIS QUESTIONS
1. SnowDevil produces snowboards at its factories in Reno and
Tahoe with weekly outputs of 30 and 20 units, respectively. This
commodity is to be transported to three regional warehouse
locations, Warehouses 1, 2, and 3, which have weekly requirements of
10, 15, and 25 units, respectively. Unit shipping costs are:
From Reno to Warehouses 1, 2, and 3 respectively: 8, 7, and 6.
From Tahoe to Warehouses 1, 2, and 3 respectively: 5, 9, and 4.
2. Consider the problem faced by SnowDevil in problem 1. Suppose
the next week Tahoe can produce only 15 units.
A. How would the linear programming formulation be modified to
account for this development?
B. What necessarily must be true about the total number of
snowboards received at the warehouses?
C. Given the answer to Part B, what is the “real life” problem
being solved by this model?
D. Suppose the decision has been made that no warehouse is to
receive less than two fewer snowboards than requested. How could
the linear programming formulation be modified to reflect this
condition? How could the transportation network be modified to
reflect this condition?
3. As part of a work-study program, Winslow Graphics has agreed
to have 5 internship students from the Communications Department of
the local university spend one day each during the next week in its
labs participating in the development of magazine layouts for a
variety of products. Since these internship students are in their
final year of a master’s degree program, they possess significant
skills, and Winslow feels it would benefit by having the maximum
total number of student hours during the week. Each student was
asked for his availability in terms of maximum number of continuous
hours for each day during the coming week.
Monday
Tuesday
Thursday
Friday
Arturo
4
5
6
7
Jill
3
7
2
9
Kyle
2
3
0
8
Thuy
0
5
3
4
Tiffany
5
9
2
4
A. Determine the schedule that gives the most benefit to Winslow
Graphics.
B. Suppose each intern could work two additional hours on Monday.
What would be the new optimal solution? Suppose Arturo’s schedule
C. What would be the effect of increasing Tiffany’s availability
on Monday to 7 hours? Decreasing Thuy’s hours on Friday to 2?
4. Suppose in problem 3 that over the 15 week semester each of
the five interns must spend 12 dates each at Winslow Graphics with
no two interns being at Winslow on the same day. Assume that
student availability will not change from week to week over the
semester.
A. How could a transportation model be used to solve for the set
of assignments of interns over the 15 week period that would most
benefit Winslow Graphics?
B. Solve for the optimal assignments.
5. The Department of Defense (DOD) is conducting weapons tests in
an isolated part of the Nevada desert. At one particular site, the
DOD has six structures that are in proximity to the blast area and
must be evacuated to an observation area at times when testing is
done. The blast area lies in a combination of flat and mountainous
A. How long will it take a person to evacuate from the blast site
to the observation area?
B. If all sites, including the blast site, are given the notice
to evacuate to the observation area at 0600 hours, at what time can
the blast proceed?
6. Consider the DOD blast area represented by the network for
problem 5. The DOD would like to eliminate the need for 4-wheel
A. If the time estimates on the graph were determined by assuming
that 4-wheel drive vehicles average 30 miles per hour over each
path, what is the minimum amount of taxpayer money needed to pave
B. If only the paved roads found in part A are to be used, speeds
on those roads average 60 miles per hour, and notice is given to
evacuate to the observation area at 0600 hours, at what time can the
blast proceed?
7. A nightwatchman must make his rounds to four areas of a plant
each hour. When he reaches an area, he inspects it and punches a
timeclock to verify his inspection. After visiting all four areas,
he returns to the lobby and watches television.
A. Given the times between locations in minutes in the table
below, in which order should he inspect the areas if his objective
is to maximize his television time?
B. His favorite one-hour television show, Nightwatchman, Man of
Mystery, starts at 9:00 PM. How much of this show will he get to
C. At what time will he check into each area if he starts his
rounds at 9:00 from the lobby?
8. Cajun Oil Company operates pipelines for transporting oil from
its source in the Gulf of Mexico to storage facilities located on
the mainland in Louisiana. Before reaching the storage facilities,
the oil must pass through one or more pumping stations. The network
below gives the maximum amount that can be transported in pipes
between sites in thousands of gallons per hour.
A. Assuming a 24 hour per day operation, what is the maximum
volume of oil that can be pumped from the source to the storage
B. Where are the bottlenecks in the network?
9. In a given transportation problem involving cost minimization,
there are three sources, with outputs of 10, 18, and 17,
respectively. There are four destinations, with demands of 14, 11 9
and 6, respectively.
A. Using Excel, define the problem. What is the Excel formula
for the cell with the objective function value?
(
B. What values are entered into the Solver Parameters dialogue
box in the field “By Changing Cells”? “Subject to the Constraints”?
(
C. What is the solution?
10. The sensitivity report from problem 9 is given below. The
“Reduced Gradient” column contains reduced costs, and the “Lagrange
Multiplier” column contains shadow prices.
A. If this a unique solution? How do you know?
B. Source 2 has the ability to ship 18 units, but only shipped
13. What does this mean in real world terms?
C. The reduced cost for shipment from Source 1 to Destination 4
is $4. Give two interpretations.
D. The LaGrange Multiplier for Source 1 is –3. What does this
mean?
E. The LaGrange Multiplier for Destination 4 is $5. What does
this mean?