Chapter 10 – Distribution & Network Models
True / False
1. Whenever total supply is less than total demand in a transportation problem, the LP model does not determine how the
unsatisfied demand is handled.
a. True
b. False
2. Converting a transportation problem LP from cost minimization to profit maximization requires only changing the
objective function; the conversion does not affect the constraints.
a. True
b. False
3. A transportation problem with 3 sources and 4 destinations will have 7 decision variables.
a. True
b. False
4. If a transportation problem has four origins and five destinations, the LP formulation of the problem will have nine
constraints.
a. True
b. False
5. The capacitated transportation problem includes constraints which reflect limited capacity on a route.
a. True
b. False
6. When the number of agents exceeds the number of tasks in an assignment problem, one or more dummy tasks must be
introduced in the LP formulation or else the LP will not have a feasible solution.
a. True
b. False
Chapter 10 – Distribution & Network Models
7. A transshipment constraint must contain a variable for every arc entering or leaving the node.
a. True
b. False
8. The shortest-route problem is a special case of the transshipment problem.
a. True
b. False
9. Transshipment problem allows shipments both in and out of some nodes while transportation problems do not.
a. True
b. False
10. A dummy origin in a transportation problem is used when supply exceeds demand.
a. True
b. False
11. When a route in a transportation problem is unacceptable, the corresponding variable can be removed from the LP
formulation.
a. True
b. False
12. In the LP formulation of a maximal flow problem, a conservation-of-flow constraint ensures that an arc’s flow
capacity is not exceeded.
a. True
b. False
13. The maximal flow problem can be formulated as a capacitated transshipment problem.
a. True
b. False
Chapter 10 – Distribution & Network Models
14. The direction of flow in the shortest-route problem is always out of the origin node and into the destination node.
a. True
b. False
15. A transshipment problem is a generalization of the transportation problem in which certain nodes are neither supply
nodes nor destination nodes.
a. True
b. False
16. The assignment problem is a special case of the transportation problem in which all supply and demand values equal
one.
a. True
b. False
17. A transportation problem with 3 sources and 4 destinations will have 7 variables in the objective function.
a. True
b. False
18. Flow in a transportation network is limited to one direction.
a. True
b. False
19. In a transportation problem with total supply equal to total demand, if there are four origins and seven destinations,
and there is a unique optimal solution, the optimal solution will utilize 11 shipping routes.
a. True
b. False
20. In the general assignment problem, one agent can be assigned to several tasks.
Chapter 10 – Distribution & Network Models
a. True
b. False
21. In a capacitated transshipment problem, some or all of the transfer points are subject to capacity restrictions.
a. True
Multiple Choice
22. The problem which deals with the distribution of goods from several sources to several destinations is the
a. maximal flow problem
b. transportation problem
c. assignment problem
d. shortest-route problem
23. The parts of a network that represent the origins are
a. the capacities
b. the flows
c. the nodes
d. the arcs
24. The objective of the transportation problem is to
a. identify one origin that can satisfy total demand at the destinations and at the same time minimize total shipping
cost.
b. minimize the number of origins used to satisfy total demand at the destinations.
c. minimize the number of shipments necessary to satisfy total demand at the destinations.
d. minimize the cost of shipping products from several origins to several destinations.
25. The number of units shipped from origin i to destination j is represented by
a. xij.
b. xji.
c. cij.
d. cji.
Chapter 10 – Distribution & Network Models
26. Which of the following is not true regarding the linear programming formulation of a transportation problem?
a. Costs appear only in the objective function.
b. The number of variables is (number of origins) x (number of destinations).
c. The number of constraints is (number of origins) x (number of destinations).
d. The constraints’ left-hand side coefficients are either 0 or 1.
27. The difference between the transportation and assignment problems is that
a. total supply must equal total demand in the transportation problem
b. the number of origins must equal the number of destinations in the transportation problem
c. each supply and demand value is 1 in the assignment problem
d. there are many differences between the transportation and assignment problems
28. In the general linear programming model of the assignment problem,
a. one agent can do parts of several tasks.
b. one task can be done by several agents.
c. each agent is assigned to its own best task.
d. one agent is assigned to one and only one task.
29. The assignment problem is a special case of the
a. transportation problem.
b. transshipment problem.
c. maximal flow problem.
d. shortest-route problem.
30. Which of the following is not true regarding an LP model of the assignment problem?
a. Costs appear in the objective function only.
b. All constraints are of the ≥ form.
c. All constraint left-hand side coefficient values are 1.
d. All decision variable values are either 0 or 1.
Chapter 10 – Distribution & Network Models
31. The assignment problem constraint x31 + x32 + x33 + x34 ≤ 2 means
a. agent 3 can be assigned to 2 tasks.
b. agent 2 can be assigned to 3 tasks.
c. a mixture of agents 1, 2, 3, and 4 will be assigned to tasks.
d. there is no feasible solution.
32. Arcs in a transshipment problem
a. must connect every node to a transshipment node.
b. represent the cost of shipments.
c. indicate the direction of the flow.
d. All of the alternatives are correct.
33. Constraints in a transshipment problem
a. correspond to arcs.
b. include a variable for every arc.
c. require the sum of the shipments out of an origin node to equal supply.
d. All of the alternatives are correct.
34. In a transshipment problem, shipments
a. cannot occur between two origin nodes.
b. cannot occur between an origin node and a destination node.
c. cannot occur between a transshipment node and a destination node.
d. can occur between any two nodes.
35. Consider a shortest route problem in which a bank courier must travel between branches and the main operations
center. When represented with a network,
a. the branches are the arcs and the operations center is the node.
b. the branches are the nodes and the operations center is the source.
c. the branches and the operations center are all nodes and the streets are the arcs.
d. the branches are the network and the operations center is the node.
36. The shortest-route problem finds the shortest-route
a. from the source to the sink.
b. from the source to any other node.
Chapter 10 – Distribution & Network Models
c. from any node to any other node.
d. from any node to the sink.
37. Consider a maximal flow problem in which vehicle traffic entering a city is routed among several routes before
eventually leaving the city. When represented with a network,
a. the nodes represent stoplights.
b. the arcs represent one way streets.
c. the nodes represent locations where speed limits change.
d. None of the alternatives is correct.
38. We assume in the maximal flow problem that
a. the flow out of a node is equal to the flow into the node.
b. the source and sink nodes are at opposite ends of the network.
c. the number of arcs entering a node is equal to the number of arcs exiting the node.
d. None of the alternatives is correct.
39. If a transportation problem has four origins and five destinations, the LP formulation of the problem will have
a. 5 constraints
b. 9 constraints
c. 18 constraints
d. 20 constraints
40. Which of the following is not a characteristic of assignment problems?
a. costs appear in the objective function only
b. the RHS of all constraints is 1
c. the value of all decision variables is either 0 or 1
d. the signs of constraints are always <
41. The network flows into and out of demand nodes are what makes the production and inventory application modeled in
the textbook a
a. shortest-route model.
b. maximal flow model.
c. transportation model
d. transshipment model
Chapter 10 – Distribution & Network Models
Subjective Short Answer
42. Write the LP formulation for this transportation problem.
43. Draw the network for this transportation problem.
Min 2XAX + 3XAY + 5XAZ+ 9XBX + 12XBY + 10XBZ
s.t. XAX + XAY + XAZ ≤ 500
X BX + XBY + XBZ ≤ 400
XAX + XBX = 300
XAY + XBY = 300
XAZ + XBZ = 300
Xij ≥ 0
Chapter 10 – Distribution & Network Models
44. Canning Transport is to move goods from three factories to three distribution centers. Information about the move is
given below. Give the network model and the linear programming model for this problem.
Source Supply Destination Demand
A 200 X 50
B 100 Y 125
C 150 Z 125
Shipping costs are:
Destination
Source X Y Z
A 3 2 5
B 9 10 —
C 5 6 4
(Source B cannot ship to destination Z)
Chapter 10 – Distribution & Network Models
45. The following table shows the unit shipping cost between cities, the supply at each source city, and the demand at
each destination city. The Management Scientist solution is shown. Report the optimal solution.
Destination
Source Terre Haute Indianapolis Ft. Wayne South Bend Supply
St. Louis 8 6 12 9 100
Evansville 5 5 10 8 100
Bloomington 3 2 9 10 100
Demand 150 60 45 45
TRANSPORTATION PROBLEM
*****************************
OBJECTIVE: MINIMIZATION
SUMMARY OF ORIGIN SUPPLIES
********************************
ORIGIN SUPPLY
———– ———–
1 100
2 100
3 100
SUMMARY OF DESTINATION DEMANDS
***************************************
DESTINATION DEMAND
——————- ———–—
1 150
2 60
3 45
4 45
SUMMARY OF UNIT COST OR REVENUE DATA
*********************************************
FROM TO DESTINATION
ORIGIN 1 2 3 4
———– —– —– —– —–
1 8 6 12 9
2 5 5 10 8
3 3 2 9 10
OPTIMAL TRANSPORTATION SCHEDULE
****************************************
SHIP
FROM TO DESTINATION
Chapter 10 – Distribution & Network Models
ORIGIN 1 2 3 4
———– —– —– —– —–
1 0 10 45 45
2 100 0 0 0
3 50 50 0 0
TOTAL TRANSPORTATION COST OR REVENUE IS 1755
46. After some special presentations, the employees of the AV Center have to move projectors back to classrooms. The
table below indicates the buildings where the projectors are now (the sources), where they need to go (the destinations),
and a measure of the distance between sites.
Destination
Source Business Education Parsons Hall Holmstedt Hall Supply
Baker Hall 10 9 5 2 35
Tirey Hall 12 11 1 6 10
Arena 15 14 7 6 20
Demand 12 20 10 10
a. If you were going to write this as a linear programming model, how many decision variables would there be, and how
many constraints would there be?
The solution to this problem is shown below. Use it to answer the questions b – e.
TRANSPORTATION PROBLEM
*****************************
OPTIMAL TRANSPORTATION SCHEDULE
****************************************
FROM TO DESTINATION
FROM ORIGIN 1 2 3 4
——————- —— —— —— ——
1 12 20 0 3
2 0 0 10 0
3 0 0 0 7
TOTAL TRANSPORTATION COST OR REVENUE IS 358
NOTE: THE TOTAL SUPPLY EXCEEDS THE TOTAL DEMAND BY 13
ORIGIN EXCESS SUPPLY
———– ———————–
3 13
b. How many projectors are moved from Baker to Business?
c. How many projectors are moved from Tirey to Parsons?
d. How many projectors are moved from the Arena to Education?
e. Which site(s) has (have) projectors left?
Chapter 10 – Distribution & Network Models
47. Show both the network and the linear programming formulation for this assignment problem.
Task
Person A B C D
1 9 5 4 2
2 12 6 3 5
3 11 6 5 7
Chapter 10 – Distribution & Network Models
48. Draw the network for this assignment problem.
Min 10x1A + 12x1B + 15x1C + 25x1D + 11x2A + 14x2B + 19x2C + 32x2D
+ 18x3A + 21x3B + 23x3C + 29x3D + 15x4A + 20x4B + 26x4C + 28x4D
s.t. x1A + x1B + x1C + x1D = 1
x2A + x2B + x2C + x2D = 1
x3A + x3B + x3C + x3D = 1
x4A + x4B + x4C + x4D = 1
x1A + x2A + x3A + x4A = 1
x1B + x 2B + x3B + x4B = 1
x1C + x 2C + x3C + x4C = 1
x1D + x2D + x3D + x4D = 1
49. A professor has been contacted by four not-for-profit agencies that are willing to work with student consulting teams.
The agencies need help with such things as budgeting, information systems, coordinating volunteers, and forecasting.
Although each of the four student teams could work with any of the agencies, the professor feels that there is a difference
in the amount of time it would take each group to solve each problem. The professor’s estimate of the time, in days, is
given in the table below. Use the computer solution to see which team works with which project.
Projects
Team Budgeting Information Volunteers Forecasting
A 32 35 15 27
B 38 40 18 35
C 41 42 25 38
D 45 45 30 42
ASSIGNMENT PROBLEM
************************
Chapter 10 – Distribution & Network Models
OBJECTIVE: MINIMIZATION
SUMMARY OF UNIT COST OR REVENUE DATA
*********************************************
TASK
AGENT 1 2 3 4
———– —– —– —– —–
1 32 35 15 27
2 38 40 18 35
3 41 42 25 38
4 45 45 30 42
OPTIMAL ASSIGNMENTS COST/REVENUE
************************ ***************
ASSIGN AGENT 3 TO TASK 1 41
ASSIGN AGENT 4 TO TASK 2 45
ASSIGN AGENT 2 TO TASK 3 18
ASSIGN AGENT 1 TO TASK 4 27
——————————————- —–
TOTAL COST/REVENUE 131
50. Write the linear program for this transshipment problem.
Chapter 10 – Distribution & Network Models
51. Peaches are to be transported from three orchard regions to two canneries. Intermediate stops at a consolidation station
are possible.
Orchard Supply Station Cannery Capacity
Riverside 1200 Waterford Sanderson 2500
Sunny Slope 1500 Northside Millville 3000
Old Farm 2000
Shipment costs are shown in the table below. Where no cost is given, shipments are not possible. Where costs are shown,
shipments are possible in either direction. Draw the network model for this problem.
R SS OF W N S M
Riverside 1 5 3
Sunny Side 4 5
Old Farm 6 3
Waterford 2 2 4
Northside 5 9
Sanderson 2
Millville
52. RVW (Restored Volkswagens) buys 15 used VW’s at each of two car auctions each week held at different locations. It
then transports the cars to repair shops it contracts with. When they are restored to RVW’s specifications, RVW sells 10
each to three different used car lots. There are various costs associated with the average purchase and transportation prices
from each auction to each repair shop. Also there are transportation costs from the repair shops to the used car lots. RVW
is concerned with minimizing its total cost given the costs in the table below.
a. Given the costs below, draw a network representation for this problem.
Repair Shops Used Car Lots
S1 S2 L1 L2 L3
Auction 1 550 500 S1 250 300 500
Auction 2 600 450 S2 350 650 450