Chapter 6 – Distribution and Network Models
——————————————-
—–
TOTAL COST/REVENUE
131
Assignment problem
50. Write the linear program for this transshipment problem.
Transshipment problem
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
Chapter 6 – Distribution and Network Models
Old Farm
6
3
Waterford
2
2
4
Northside
5
9
Sanderson
2
Millville
Transshipment problem
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
b. Formulate this problem as a transshipment linear programming model.
Chapter 6 – Distribution and Network Models
53. Consider the network below. Formulate the LP for finding the shortest-route path from node 1 to node 7.
Chapter 6 – Distribution and Network Models
Shortest-route problem
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 6 – Distribution and 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.
Shortest-route problem
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
Shortest-route problem
Chapter 6 – Distribution and 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.
Chapter 6 – Distribution and Network Models
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 6 – Distribution and Network Models
Maximal flow problem
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.
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.
b.
Define the decision variables:
Define objective:
Chapter 6 – Distribution and Network Models
60. Find the maximal flow from node 1 to node 7 in the following network.
Define the constraints:
Objective Function Value = 1045000.000
Production and inventory application
Chapter 6 – Distribution and Network Models
Chapter 6 – Distribution and 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
1.000
2.000
2.000
1.000
0.000
1.000
3.000
3.000
2.000
2.000
5.000
5.000
Chapter 6 – Distribution and 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.
Assignment problem
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.
Total Parts Per Hour
Assignment problem
Chapter 6 – Distribution and Network Models
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.
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?
Chapter 6 – Distribution and Network Models
65. 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.
66. Define the variables and constraints necessary in the LP formulation of the transshipment problem.
67. Explain what adjustments can be made to the transportation linear program when there are unacceptable routes.
68. Is it a coincidence to obtain integer solutions to network problems? Explain.
69. How is the assignment linear program different from the transportation model?
70. Define the variables and constraints necessary in the LP formulation of the maximal flow problem.
71. How is the shortest-route problem like the transshipment problem?