1
Managerial Decision Modeling w/ Spreadsheets, 3e (Balakrishnan/Render/Stair)
Chapter 5 Transportation, Assignment, and Network Models
5.1 Chapter Questions
1) Which of the following is NOT a network flow model?
A) Transportation model
B) Assignment model
C) Product mix model
D) Shortest-path model
E) Minimal-spanning tree model
2) Which of the following models determines the path through the network that connects all the points?
A) Transportation model
B) Assignment model
C) Product mix model
D) Shortest-path model
E) Minimal-spanning tree model
Use the information below to answer the following questions.
Consider the following maximal flow problem where node 1 is the source and node 6 is the destination.
3) Refer to the figure. What is the objective function?
A) Max X16
B) Min X16
C) Max X61
D) Min X61
E) Max X26 + X56
4) Refer to the figure. What is the constraint associated with node 6?
A) X46 + X56 = 0
B) X46 + X56 = 1
C) X46 + X56 – X61 = 1
D) X46 + X56 – X61 = -1
E) X46 + X56 – X61 = 0
5) Refer to the figure. What is the maximum capacity associated with arc X61?
A) +1
B) -1
C) 0
D) +∞
E) –∞
6) Refer to the figure. What is the constraint associated with node 1?
A) -X12 – X13 = 1
B) X61 – X12 – X13 = -1
C) X61 – X12 – X13 = 1
D) X61 – X12 – X13 = 0
E) X61 – X12 – X13 = ∞
7) Refer to the figure. What is the constraint associated with node 2?
A) X12 – X24 = 0
B) X12 – X32 – X24 = 0
C) X12 + X32 – X24 = 1
D) X12 – X32 + X24 = 0
E) X12 + X32 – X24 = 0
8) Which of the following statements concerning the transshipment model are FALSE?
A) A supply node is one where the total flow into the node is less than the total flow out of the node.
B) A transshipment node is one where the total flow into the node equals the total flow of the node.
C) The flow balance for a demand node should show a positive RHS value.
D) The flow balance for a transshipment node should show a negative RHS value.
E) The flow balance for a supply node should show a negative RHS value.
Use the information below to answer the following questions.
Consider the following shortest path problem where node 1 is the starting node and node 6 is the
destination node.
9) Refer to the figure. What is the constraint associated with node 1?
A) X21+ X31 – X12 – X13 = -1
B) X21 + X31 – X12 – X13 = +1
C) + X31– X12 – X13 = 0
D) X12 + X13 = 0
E) -X12 + X13 = -1
10) Refer to the figure. What is the constraint associated with node 6?
A) X64 + X65 – X46 – X56 = +1
B) X64 + X65 – X46 – X56 = 0
C) X46 + X56 – X64 – X65 = +1
D) -X64 – X65 = -1
E) -X46 + X56 = 0
11) Refer to the figure. Excluding the non-negativity constraint, this model has:
A) 6 decision variables
B) 7 decision variables
C) 8 decision variables including the dummy arc
D) 5 decision variables
E) none of the above
12) What is the constraint associated with job A for the following assignment problem?
Machine
1 2 3
A $3 $4 $2
Job B $1 $3 $5
C $6 $4 $2
Let Xij = 1 if job i is assigned to machine j, otherwise 0.
A) 3XA1 + 4XA2 + 2XA3 = 1
B) 3XA1 + 4XA2 + 2XA3 = 0
C) 3XA1 + 4XA2 + 2XA3 = -1
D) XA1 + XA2 + XA3 = -1
E) -XA1 – XA2 – XA3 = -1
13) What is the constraint associated with machine 2 for the following assignment problem?
Machine
1 2 3
A $3 $4 $2
Job B $1 $3 $5
C $6 $4 $2
Let Xij = 1 if job i is assigned to machine j, otherwise 0.
A) XA2 + XB2 + XC2 = +1
B) XA2 + XB2 + XC2 = 0
C) XA2 + XB2 + XC2 = -1
D) 4XA2 + 3XB2 + 4XC2 = +1
E) 4XA2 + 3XB2 + 4XC2 = -1
14) Consider the following transshipment problem. The shipping cost per unit between nodes 1 and 2 is
$10, while the shipping cost per unit between nodes 2 and 3 is $12. What is the objective function?
A) Min X12 + X23
B) Max X12 + X23
C) Min 10X12 + 12X13
D) Min -10X12 – 12X13
E) Max 10X12 + 12X23
15) In an unbalanced transportation problem where total supply exceeds total demand, the supply
constraints will typically have “≥” inequalities.
16) In an unbalanced transportation problem where total demand exceeds total supply, the demand
constraints will typically have “≤” inequalities.
17) All supply and demand quantities in an assignment model equal one unit.
18) In a maximal flow problem, each node in the network is associated with a decision variable.
19) In a maximal flow problem, if node 1 is the source and node 2 is the destination, the objective
function of the LP problem is to maximize the flow along arc X12 .
20) In a maximal flow problem, the right-hand side of the flow balance constraints equals 1.
21) The starting node of the shortest path problem has a supply value of -1.
22) The objective function of an assignment problem may be either maximization or minimization.
23) In a maximal flow problem, all the net flows are typically zeros.
24) Every node in a network flow problem has a decision variable associated with it.
25) In a maximal flow problem, the flow capacity on the dummy arc connecting the destination node to
the source node should be set to a very large value.
26) An assignment model has three jobs and four machines. This problem would be referred to as a
balanced assignment problem.
27) It is possible to solve small assignment problems by enumerating all possible outcomes rather than
modeling them as linear programming problems.
8
28) In a transshipment problem, nodes are considered as either pure supply nodes or pure demand nodes.
30) The addition of constraints other than supply and demand constraints may cause the optimal solution
in network flow models to no longer be integers.
5.2 Excel Problems
Use this information for the following questions.
The following network describes the hourly volume of traffic that can flow between various
communities in Dover County. Assume traffic can flow in both directions between each community at
the same rate. What is the maximum flow of cars between Communities 1 and 6 in one hour?
1) Refer to the network above. Formulate this problem as a linear programming problem.
2) Refer fo the network above and its associated Excel solution shown below.
What values would you enter in the Solver Parameter dialog box for the Excel spreadsheet model?
Set Target Cell:
By Changing Cells:
Subject to the Constraints:
3) Refer fo the network above and its associated Excel solution shown below.
a. What equation should be entered in cell H4?
b. What equation should be entered in cell B10?
c. What equation should be entered in cell B25?
12
Use this information to answer the following questions.
Bob Jenkins needs to drive from City 1 to City 7 and would like to find the shortest route between the
two. The road system with the distance in miles between cities is shown in the network below. What
cities should he travel through to minimize his distance?
Refer to the following Excel spreadsheet model.
13
4) Refer to the network above and its associated spreadsheet. What values would you enter in the Solver
Parameter dialog box for the Excel spreadsheet model?
Set Target Cell:
By Changing Cells:
Subject to the Constraints:
5) Refer to the network above and its associated spreadsheet.
a. What equation should be entered in cell B23?
b. What equation should be entered in cell B27?
c. What equation should be entered in cell I4?
Use this information for the following questions.
Neki Sports Company manufacturers treadmills in factories located in Pittsburgh and Kansas City.
These are shipped to regional distribution centers in Chicago, Phoenix, and Philadelphia. Ultimately
they are delivered to supply houses in New York and Los Angeles. The available supplies at the
factories, demands at the final destinations, and shipping costs are illustrated in the table below.
6) Refer to the information above. Formulate this problem as a linear programming problem.
7) Refer to the information above. Using Excel, determine how many units should be shipped for all
possible origin and destination points (final or intermediate) in the distribution network in order to
minimize shipping costs.