Chapter 10 – Distribution & Network Models
b. Formulate this problem as a transshipment linear programming model.
53. Consider the network below. Formulate the LP for finding the shortest-route path from node 1 to node 7.
Chapter 10 – Distribution & Network Models
54. Consider the following shortest-route problem involving six cities with the distances given. Draw the network for this
problem and formulate the LP for finding the shortest distance from City 1 to City 6.
Path Distance
1 to 2 3
1 to 3 2
2 to 4 4
2 to 5 5
3 to 4 3
3 to 5 7
4 to 6 6
5 to 6 2
Chapter 10 – Distribution & Network Models
55. A beer distributor needs to plan how to make deliveries from its warehouse (Node 1) to a supermarket (Node 7), as
shown in the network below. Develop the LP formulation for finding the shortest route from the warehouse to the
supermarket.
Chapter 10 – Distribution & Network Models
56. Consider the following shortest-route problem involving seven cities. The distances between the cities are given
below. Draw the network model for this problem and formulate the LP for finding the shortest route from City 1 to City 7.
Path Distance
1 to 2 6
1 to 3 10
1 to 4 7
2 to 3 4
2 to 5 5
3 to 4 5
3 to 5 2
3 to 6 4
4 to 6 8
5 to 7 7
6 to 7 5
Chapter 10 – Distribution & Network Models
57. The network below shows the flows possible between pairs of six locations. Formulate an LP to find the maximal flow
possible from Node 1 to Node 6.
58. A network of railway lines connects the main lines entering and leaving a city. Speed limits, track reconstruction, and
train length restrictions lead to the flow diagram below, where the numbers represent how many cars can pass per hour.
Formulate an LP to find the maximal flow in cars per hour from Node 1 to Node F.
Chapter 10 – Distribution & Network Models
59. Fodak must schedule its production of camera film for the first four months of the year. Film demand (in 1,000s of
rolls) in January, February, March and April is expected to be 300, 500, 650 and 400, respectively. Fodak’s production
capacity is 500 thousand rolls of film per month. The film business is highly competitive, so Fodak cannot afford to lose
sales or keep its customers waiting. Meeting month i ‘s demand with month i +1’s production is unacceptable.
Chapter 10 – Distribution & Network Models
Film produced in month i can be used to meet demand in month i or can be held in inventory to meet demand in month i
+1 or month i +2 (but not later due to the film’s limited shelflife). There is no film in inventory at the start of January.
The film’s production and delivery cost per thousand rolls will be $500 in January and February. This cost will increase to
$600 in March and April due to a new labor contract. Any film put in inventory requires additional transport costing $100
per thousand rolls. It costs $50 per thousand rolls to hold film in inventory from one month to the next.
a. Modeling this problem as a transshipment problem, draw the network representation.
b. Formulate and solve this problem as a linear program.
Chapter 10 – Distribution & Network Models
60. Find the maximal flow from node 1 to node 7 in the following network.
Chapter 10 – Distribution & Network Models
61. A foreman is trying to assign crews to produce the maximum number of parts per hour of a certain product. He has
three crews and four possible work centers. The estimated number of parts per hour for each crew at each work center is
summarized below. Solve for the optimal assignment of crews to work centers.
Work Center
WC1 WC2 WC3 WC4
Crew A 15 20 18 30
Crew B 20 22 26 30
Crew C 25 26 27 30
Chapter 10 – Distribution & Network Models
62. A plant manager for a sporting goods manufacturer is in charge of assigning the manufacture of four new aluminum
products to four different departments. Because of varying expertise and workloads, the different departments can
produce the new products at various rates. If only one product is to be produced by each department and the daily output
rates are given in the table below, which department should manufacture which product to maximize total daily product
output? (Note: Department 1 does not have the facilities to produce golf clubs.)
Department Baseball
Bats Tennis
Rackets Golf
Clubs Racquetball
Rackets
1 100 60 X 80
2 100 80 140 100
3 110 75 150 120
4 85 50 100 75
Formulate this assignment problem as a linear program.
Chapter 10 – Distribution & Network Models
63. A clothing distributor has four warehouses which serve four large cities. Each warehouse has a monthly capacity of
5,000 blue jeans. They are considering using a transportation LP approach to match demand and capacity. The following
table provides data on their shipping cost, capacity, and demand constraints on a per-month basis. Develop a linear
programming model for this problem.
Warehouse City E City F City G City H
A .53 .21 .52 .41
B .31 .38 .41 .29
C .56 .32 .54 .33
D .42 .55 .34 .52
City Demand 2,000 3,000 3,500 5,500
64. A computer manufacturing company wants to develop a monthly plan for shipping finished products from three of its
manufacturing facilities to three regional warehouses. It is thinking about using a transportation LP formulation to exactly
match capacities and requirements. Data on transportation costs (in dollars per unit), capacities, and requirements are
given below.
Chapter 10 – Distribution & Network Models
Warehouse
Plant 1 2 3 Capacities
A 2.41 1.63 2.09 4,000
B 3.18 5.62 1.74 6,000
C 4.12 3.16 3.09 3,000
Requirement 8,000 2,000 3,000
a. How many variables are involved in the LP formulation?
b. How many constraints are there in this problem?
c. What is the constraint corresponding to Plant B?
d. What is the constraint corresponding to Warehouse 3?
65. A large book publisher has five manuscripts that must be edited as soon as possible. Five editors are available for
doing the work, however their working times on the various manuscripts will differ based on their backgrounds and
interests. The publisher wants to use an assignment method to determine who does what manuscript. Estimates of editing
times (in hours) for each manuscript by each editor are:
Editor
Manuscript Uley Vargas Way York Zee
A 12 8 10 16 13
B 9 10 14 13 9
C 17 14 9 18 12
D 15 7 11 9 18
E 12 18 22 11 27
Develop the LP formulation for this problem.
Chapter 10 – Distribution & Network Models
66. A Japanese Company is trying to decide between two alternative locations, C and D, for making their new wrist
cellular telephone using the LP transportation method. They currently have two factories, A and B, working 24 hours per
day but cannot keep up with demand. Costs are on a per-unit basis. Monthly data relating locations with centers of
demand are:
Demand Centers Factory
Factories U.S. Canada Mexico Output
Existing A .12 .38 .65 8,000
Existing B .23 .16 .23 5,000
Proposed C .20 .26 .37 5,000
Proposed D .18 .31 .34 5,000
Min. Demand 6,000 6,000 6,000
Formulate two transportation LPs, one including Proposed C factory and the other including Proposed D factory, that
could be solved to determine the lower-cost choice of new factories.
67. The Emerald Valley Country Club has three tractors that are used for cutting grass. Each is of a different size and has
different capabilities. The largest tractor cuts fairways and other large areas very efficiently, but has trouble around
bunkers and trees. The smallest tractor cuts very quickly around small objects but takes more time on the open expanses
of grass. The middle-sized tractor operates as a compromise between the other two. The 18-hole golf course is divided
into three parts for cutting purposes: holes 1‑6; holes 7‑12; and holes 13‑18. The club wants to determine which tractor
should be assigned to which part of the course so as to minimize total cutting time. The table shows cutting times (in
minutes) for the tractors in each of the three sections of the golf course:
Chapter 10 – Distribution & Network Models
Section of Course
Tractor 1‑6 7‑12 13‑18
Large 270 473 512
Medium 386 395 483
Small 456 409 476
Formulate this assignment problem as an LP.
Essay
68. Explain how the general linear programming model of the assignment problem can be modified to handle problems
involving a maximization function, unacceptable assignments, and supply not equally demand.
69. Define the variables and constraints necessary in the LP formulation of the transshipment problem.
70. Explain what adjustments can be made to the transportation linear program when there are unacceptable routes.
71. Is it a coincidence to obtain integer solutions to network problems? Explain.
72. How is the assignment linear program different from the transportation model?
73. Define the variables and constraints necessary in the LP formulation of the maximal flow problem.
Chapter 10 – Distribution & Network Models
74. How is the shortest-route problem like the transshipment problem?