Quantitative Analysis BA 452 Supplemental Questions 6 This document contains practice questions that supplement homework questions and review questions for Lessons II-1 and II-2. This document first identifies the learning objectives of solving supplemental questions. The document then lists 36 questions. Four of those questions (questions 7, 11, 15, and 19) are like the questions in Homework 6. Finally, the document answers all questions except the homework questions. All questions can be helpful except questions 29 to 36. Questions marked with an asterisk * are similar to review questions. Tip: Supplemental questions are grouped into sets of similar type. Once you have mastered the questions in a set, you can skip the rest of the questions in that set.
1
Quantitative Analysis BA 452 Supplemental Questions 6
Objectives By working through the homework questions and the supplemental questions, you will: 1.
Be able to identify the special features of the transportation problem.
2.
Become familiar with the types of problems that can be solved by applying a transportation model.
3.
Be able to develop network and linear programming models of the transportation problem.
4.
Know how to handle the cases of (1) unequal supply and demand, (2) unacceptable routes, and (3) maximization objective for a transportation problem.
5.
Be able to identify the special features of the assignment problem.
6.
Become familiar with the types of problems that can be solved by applying an assignment model.
7.
Be able to develop network and linear programming models of the assignment problem.
8.
Be familiar with the special features of the transshipment problem.
9.
Become familiar with the types of problems that can be solved by applying a transshipment model.
10
Be able to develop network and linear programming models of the transshipment problem.
11.
Know the basic characteristics of the shortest route problem.
12.
Be able to develop a linear programming model and solve the shortest route problem. 2
Quantitative Analysis BA 452 Supplemental Questions 6 13.
Know the basic characteristics of the maximal flow problem.
14.
Be able to develop a linear programming model and solve the maximal flow problem.
15.
Know how to structure and solve a production and inventory problem as a transshipment problem.
16.
Understand the following : network flow problem transportation problem origin destination transshipment problem
shortest route source node sink node assignment problem
3
Quantitative Analysis BA 452 Supplemental Questions 6
Supplemental Questions 6 1. A company imports goods at two ports: Philadelphia and New Orleans. Shipments of one product are made to customers in Atlanta, Dallas, Columbus, and Boston. For the next planning period, the supplies at each port, customer demands, and shipping costs per case from each port to each customer are as follows: Customers Port Atlanta Dallas Columbus Boston Port Supply Philadelphia 2 6 6 2 5000 New Orleans 1 2 5 7 3000 Demand 1400 3200 2000 1400 Develop a network representation of the distribution system (transportation problem). 2. Consider the following network representation of a transportation problem:
The supplies, demands, and transportation costs per unit are shown on the network. a. Develop a linear programming model for this problem; be sure to define the variables in your model. b. Solve the linear program to determine the optimal solution.
4
Quantitative Analysis BA 452 Supplemental Questions 6 3. Tri-County Utilities, Inc., supplies natural gas to customers in a three-county area. The company purchases natural gas from two companies: Southern Gas and Northwest Gas. Demand forecasts for the coming winter season are Hamilton County, 400 units; Butler County, 200 units; and Clermont County, 300 units. Contracts to provide the following quantities have been written: Southern Gas, 500 units; and Northwest Gas, 400 units. Distribution cost for the counties vary, depending upon the location of the suppliers. The distribution costs per unit (in thousands of dollars) are as follows: To From Hamilton Butler Clermont Southern Gas 10 20 15 Northwest Gas 12 15 18 a. Develop a network representation of this problem. b. Develop a linear programming model that can be used to determine the plan that will minimize the total distribution costs. c. Describe the distribution plan and show the total distribution cost. d. Recent residential and industrial growth in Butler County has the potential for increasing demand by as much as 100 units. Which supplier should Tri-County contract with to supply the additional capacity? 4. Arnoff Enterprises manufactures the central processing unit (U) for a line of personal computers. The Us are manufactured in Seattle, Columbus, and New York and shipped to warehouses in Pittsburgh, Mobile, Denver, Los Angeles, and Washington, D.C., for further distribution. The following table shows the number of Us available at each plant, the number of Us required by each warehouse, and the shipping costs (dollars per unit):
Plant Seattle Columbus New York Us Required
Pittsburgh 10 2 1 3000
Mobile 20 10 20 5000
Warehouse Denver 5 8 7 4000
Los Angeles 9 30 10 6000
Washington 10 6 4 3000
Us Available 9000 4000 8000 21,000
a. Develop a network representation of this problem. b. Determine the amount that should be shipped from each plant to each warehouse to minimize the total shipping cost. c. The Pittsburgh warehouse just increased its order by 1000 units, and Arnoff authorized the Columbus plant to increase its production by 1000 units. Will this production increase lead to an increase or decrease in total shipping costs? Solve for the new optimal solution.
5
Quantitative Analysis BA 452 Supplemental Questions 6 5. Premier Consulting’s two consultants, Avery and Baker, can be scheduled to work for clients up to a maximum of 160 hours each over the next four weeks. A third consultant, Campbell, has some istrative assignments already planned and is available for clients up to a maximum of 140 hours over the next four weeks. The company has four clients with projects in process. The estimated hourly requirements for each of the clients over the four-week period are Client Hours A 180 B 75 C 100 D 85 Hourly rates vary for the consultant-client combination and are based on several factors, including project type and the consultant’s experience. The rates (dollars per hour) for each consultantclient combination are as follows: Client Consultant A B C D Avery 100 125 115 100 Baker 120 135 115 120 Campbell 155 150 140 130 a. Develop a network representation of the problem. b. Formulate the problem as a linear program, with the optimal solution providing the hours each consultant should be scheduled for each client to maximize the consulting firm’s billings. What is the schedule and what is the total billing? c. New information shows that Avery doesn’t have the experience to be scheduled for client B. If this consulting assignment is not permitted, what impact does it have on total billings? What is the revised schedule? 6. Klein Chemicals, Inc., produces a special oil-based material that is currently in short supply. Four of Klein’s customers have already placed orders that together exceed the combined capacity of Klein’s two plants. Klein’s management faces the problem of deciding how many units it should supply to each customer. Because the four customers are in different industries, different prices can be charged because of the various industry pricing structures. However, slightly different production costs at the two plants and varying transportation cost between the plants and customers make a “sell to the highest bidder” strategy unacceptable. After considering price, production costs, and transportation costs, Klein established the following profit per unit for each plant-customer alternative: Customer Plant D-1 D-2 D-3 Clifton Springs $32 $34 $32 Danville $34 $30 $28 The plant capacities and customer orders are as follows: Plant Capacity (units) Distributor Orders (units) Clifton Springs 5000 D1: 2000 D2: 5000 Danville 3000 D3: 3000 D4: 2000
D-4 $40 $38
How many units should each plant produce for each customer in order to maximize profits? Which customer demands will not be met? Show your network model and linear programming formulation.
6
Quantitative Analysis BA 452 Supplemental Questions 6 7. Forbelt Corporation has a one-year contract to supply motors for all refrigerators produced by the Ice Age Corporation. Ice Age manufactures the refrigerators at four locations around the country: Boston, Dallas, Los Angeles, and St. Paul. Plans call for the following number (in thousands) of refrigerators to be produced at each location: Boston 50 Dallas 70 Los Angeles 60 St. Paul 80 Forbelt’s three plants are capable of producing the motors. The plants and production capacities (in thousands) are Denver 100 Atlanta 100 Chicago 150 Because of varying production and transportation costs, the profit that Forbelt earns on each lot of 1000 units depends on which plant produced the lot and which destination it was shipped to. The following table gives the ing department estimates of the profit per unit (shipments will be made in lots of 1000 units): Shipped To Produced At Boston Dallas Los Angeles St. Paul Denver 7 11 8 13 Atlanta 20 17 12 10 Chicago 8 18 13 16 With profit maximization as a criterion, Forbelt’s management wants to determine how many motors should be produced at each plant and how many motors should be shipped from each plant to each destination. a. Develop a network representation of this problem. b. Find the optimal solution. 8. The Ace Manufacturing Company has orders for three similar products: Product Orders (units) A 2000 B 500 C 1200 Three machines are available for the manufacturing operations. All three machines can produce all the products at the same production rate. However, due to varying defect percentages of each product on each machine, the unit costs of the products vary depending on the machine used. Machine capacities for the next week, and the unit costs, are as follows: Machine Capacity (units) Machine Product 1 1500 1 A B C 2 1500 2 $1.00 $1.20 $0.90 3 1000 3 $1.30 $1.40 $1.20 $1.10 $1.00 $1.20 Use the transportation model to develop the minimum cost production schedule for the products and machines. Show the linear programming formulation.
7
Quantitative Analysis BA 452 Supplemental Questions 6 9. Scott and Associates, Inc., is an ing firm that has three new clients. Project leaders will be assigned to the three clients. Based on the different backgrounds and experiences of the leaders, the various leader-client assignments differ in of projected completion times. The possible assignments and the estimated completion times in days are as follows:
Client Project Leader Jackson Ellis Smith
1 2 3 10 16 32 14 22 40 22 24 34 a. Develop a network representation of this problem. b. Formulate the problem as a linear program, and solve. What is the total time required? 10. CarpetPlus sells and installs floor covering for commercial buildings. Brad Sweeney, a CarpetPlus executive, was just awarded the contract for five jobs. Brad must now assign a CarpetPlus installation crew to each of the five jobs. Because the commission Brad will earn depends on the profit CarpetPlus makes, Brad would like to determine an assignment that will minimize total installation costs. Currently, five installation crews are available for assignment. Each crew is identified by a color code, which aids in tracking of job progress on a large white board. The following table shows the costs (in hundreds of dollars) for each crew to complete each of the five jobs:
Job 1 2 3 4 5 Red 30 44 38 47 31 Crew White 25 32 45 44 25 Blue 23 40 37 39 29 Green 26 38 37 45 28 Brown 26 34 44 43 28 a. Develop a network representation of the problem. b. Formulate and solve a linear programming model to determine the minimum cost assignment. 11. A local television station plans to drop four Friday evening programs at the end of the season. Steve Botuchis, the station manager, developed a list of six potential replacement programs. Estimates of the advertising revenue (in dollars) that can be expected for each of the new programs in the four vacated time slots are as follows. Mr. Botuchis asked you to find the assignment of programs to time slots that will maximize total advertising revenue.
Home Improvement World News NASCAR Live Wall Street Today Hollywood Briefings Ramundo & Son
5:00-5:30 P.M. 5000 7500 8500 7000 7000 6000
5:30- 6:00 P.M. 3000 8000 5000 6000 8000 4000
8
7:00- 7:30 P.M. 6000 7000 6500 6500 3000 4500
8:00- 8:30 P.M. 4000 5500 8000 5000 6000 7000
Quantitative Analysis BA 452 Supplemental Questions 6 12. The U.S. Cable Company uses a distribution system with five distribution centers and eight customer zones. Each customer zone is assigned a sole source supplier; each customer zone receives all of its cable products from the same distribution center. In an effort to balance demand and workload at the distribution centers, the company’s vice president of logistics specified that distribution centers may not be assigned more than three customer zones. The following table shows the five distribution centers and cost of supplying each customer zone (in thousands of dollars):
Distribution Centers Plano Nashville Flagstaff Springfield Boulder
Customer Zones Los Chicago Columbus Atlanta Newark Kansas Denver Dallas Angeles City 70 47 22 53 98 21 27 13 75 38 19 58 90 34 40 26 15 78 37 82 111 40 29 32 60 23 8 39 82 36 32 45 45 40 29 75 86 25 11 37 a. Determine the assignment of customer zones to distribution centers that will minimize cost. b. Which distribution centers, if any, are not used? c. Suppose that each distribution center is limited to a maximum of two customer zones. How does this constraint change the assignment and the cost of supplying customer zones?
13. United Express Service (UES) uses large quantities of packaging materials as its four distribution hubs. After screening potential suppliers, UES identified six vendors that can provide packaging materials that will satisfy its quality standards. UES asked each of the six vendors to submit bids to satisfy annual demand at each of its four distribution hubs over the next year. The following table lists the bids received (in thousands of dollars). UES wants to ensure that each of the distribution hubs is serviced by a different vendor. Which bids should UES accept, and which vendors should UES select to supply each distribution hub?
Bidder Martine products Schmidt Materials Miller Containers D&J Burns Larbes Furnishings Lawler Depot
1 190 150 210 170 220
2 175 235 225 185 190
270
200
Distribution Hub 3 125 155 135 190 140 130
9
4 230 220 260 280 240 260
Quantitative Analysis BA 452 Supplemental Questions 6 14. The quantitative methods department head at a major Midwestern university will be scheduling faculty to teach courses during the coming autumn term. Four core courses need to be covered. The four courses are at the UG, MBA, MS, and Ph.D. levels. Four professors will be assigned to the courses, with each professor receiving one of the courses. Student evaluations of professors are available from previous . Based on a rating scale of 4 (excellent), 3 (very good), 2 (average), 1 (fair), and 0 (poor), the average student evaluations for each professor are shown. Professor D does not have a Ph.D. and cannot be assigned to teach the Ph.D.-level course. If the department head makes teaching assignments based on maximizing the student evaluation ratings over all four courses, what staffing assignments should be made?
Professor A B C D
UG 2.8 3.2 3.3 3.2
Course MBA 2.2 3.0 3.2 2.8
MS 3.3 3.6 3.5 2.5
Ph.D. 3.0 3.6 3.5 -
15. A market research film’s three clients each requested that the firm conduct a sample survey. Four available statisticians can be assigned to these three projects; however, all four statisticians are busy, and therefore each can handle only one client. The following data show the number of hours required for each statistician to complete each job; the differences in time are based on experience and ability of the statisticians.
Statistician 1 2 3 4
Client A B C 150 210 270 170 230 220 180 230 225 160 240 230 a. Formulate and solve a linear programming model for this problem. b. Suppose that the time statistician 4 needs to complete the job for client A is increased from 160 to 165 hours. What effect will this change have on the solution? c. Suppose that the time statistician 4 needs to complete the job for client A is decreased to 140 hours. What effect will this change have on the solution? d. Suppose that the time statistician 3 needs to complete the job for client B increases to 250 hours. What effect will this change have on the solution?
10
Quantitative Analysis BA 452 Supplemental Questions 6 16. Hatcher Enterprises uses a chemical called Rbase in production operations at five divisions. Only six suppliers of Rbase meet Hatcher’s quality control standards. All six suppliers can produce Rbase in sufficient quantities to accommodate the needs of each division. The quantity of Rbase needed by each Hatcher division and the price per gallon charged by each supplier are as follows: Demand Division (1000s of gallons) 1 40 2 45 3 50 4 35 5 45 Price Per Gallons ($) 12.60 14.00 10.20 14.20 12.00 13.00
Supplier 1 2 3 4 5 6
The cost per gallon (in dollars) for shipping from each supplier to each division is provided in the following table: Supplier Division 1 2 3 4 5 6 2.75 2.50 3.15 2.80 2.75 2.75 1 0.80 0.20 5.40 1.20 3.40 1.00 2 4.70 2.60 5.30 2.80 6.00 5.60 3 2.60 1.80 4.40 2.40 5.00 2.80 4 3.40 0.40 5.00 1.20 2.60 3.60 5 Hatcher believes in spreading its business among suppliers so that the company will be less affected by supplier problems (e.g., labor strikes or resource availability). Company policy requires that each division have a separate supplier. a. For each supplier-division combination, compute the total cost of supplying the division’s demand. b. Determine the optimal assignment of suppliers to divisions.
11
Quantitative Analysis BA 452 Supplemental Questions 6 17. The distribution system for the Herman Company consists of three plants, two warehouses, and four customers. Plant capacities and shipping costs per unit (in dollars) from each plant to each warehouse are as follows: Warehouse Plant 1 2 Capacity 1 4 7 450 2 8 5 600 3 5 6 380 Customer demand and shipping costs per unit (in dollars) from each warehouse to each customer are Customer Warehouse 1 2 3 4 6 4 8 4 1 3 6 7 7 2 30 300 300 400 Demand a. Develop a network representation of this problem. b. Formulate a linear programming model of the problem. c. Solve the linear program to determine the optimal shipping plan. 18. Refer to Problem 17. Suppose that shipments between the two warehouses are permitted at $2 per unit and that direct shipments can be made from plant 3 to customer 4 at a cost of $7 per unit. a. Develop a network representation of this problem. b. Formulate a linear programming model of this problem. c. Solve the linear program to determine the optimal shipping plan.
12
Quantitative Analysis BA 452 Supplemental Questions 6 19. Adirondack Paper Mills, Inc., operates paper plants in Augusta, Maine, and Tupper Lake, New York. Warehouse facilities are located in Albany, New York, and Portsmouth, New Hampshire. Distributors are located in Boston, New York, and Philadelphia. The plant capacities and distributor demands for the next month are as follows: Plant Augusta Tupper
Capacity (units) 300 100
Distributor Boston New York Philadelphia
Demand (units) 150 100 150
The unit transportation costs (in dollars) for shipments from the two plants to the two warehouses and from the two warehouses to the three distributors are as follows:
a. Draw the network representation of the Adirondack Paper Mills problem. b. Formulate the Adirondack Paper Mills problem as a linear programming problem. c. Solve the linear program to determine the minimum cost shipping schedule for the problem.
13
Quantitative Analysis BA 452 Supplemental Questions 6 20. The Moore & Harman Company is in the business of buying and selling grain. An important aspect of the company’s business is arranging for the purchased grain to be shipped to customers. If the company can keep freight costs low, profitability will improve. The company recently purchased three rail cars of grain at Muncie, Indiana; six rail cars at Brazil, Indiana; and five rail cars at Xenia, Ohio. Twelve carloads of grain have been sold. The locations and the amount sold at each location are as follows:
All shipments must be routed through either Louisville of Cincinnati. Shown are the shipping costs per bushel (incents) from the origins to Louisville and Cincinnati and the costs per bushel to ship from Louisville and Cincinnati to the destinations.
Determine a shipping schedule that will minimize the freight costs necessary to satisfy demand. Which (if any) rail cars of grain must be held at the origin until buyers can be found?
14
Quantitative Analysis BA 452 Supplemental Questions 6 21. The following linear programming formulation is for a transshipment problem:
Show the network representation of this problem. 22. A rental car company has an imbalance of cars at seven of its locations. The following network shows the locations of concern (the nodes) and the cost to move a car between locations. A positive number by a node indicates an excess supply at the node, and a negative number indicates an excess demand.
a. Develop a linear programming model of this problem. b. Solve the model formulated in part (a) to determine how the cars should be redistributed among the locations.
15
Quantitative Analysis BA 452 Supplemental Questions 6 23. Find the shortest route from node 1 to node 7 in the network shown.
24. In the original Gorman Construction Company problem, we found the shortest distance from the office (node 1) to the construction site located at node 6. Because some of the roads are highways and others are city streets, the shortest-distance routes between the office and the construction site may not necessarily provide the quickest of shortest-time route. Shown here is the Gorman road network with travel time rather than distance. Find the shortest route from Gorman’s office to the construction site at node 6 if the objective is to minimize travel time rather than distance.
16
Quantitative Analysis BA 452 Supplemental Questions 6 25. CARD, Cleveland Area Rapid Delivery, operates a delivery service in the Cleveland metropolitan area. Most of CARD’s business involves rapid delivery of documents and parcels between offices during the business day. CARD promotes its ability to make fast and on-time deliveries anywhere in the metropolitan area. When a customer calls with a delivery request, CARD quotes a guaranteed delivery time. The following network shows the street routes available. The numbers above each arc indicate the travel time in minutes between the two locations. a. Develop a linear programming model that can be used to find the minimum time required to make a delivery from location 1 to location 6. b. How long does it take to make a delivery form location 1 to location6? c. Assume that it is now 1:00P.M. CARD just received a request for a pickup at location 1, and the closest CARD courier is 8 minutes away from location 1. If CARD provides a 20% safety margin in guaranteeing a delivery time, what is the guaranteed delivery time if the package picked up at location 1 is to be delivered to location 6?
17
Quantitative Analysis BA 452 Supplemental Questions 6 26. Morgan Trucking Company operates a special pickup and delivery service between Chicago and six other cities located in a four-state area. When Morgan receives a request for service, it dispatches a truck from Chicago to the city requesting service as soon as possible. With both fast service and minimum travel costs as objectives for Morgan, it is important that the dispatched truck take the shortest route from Chicago to the specified city. Assume that the following network (not drawn to scale) with distances given in miles represents the highway network for this problem. Find the shortest-route distance from Chicago to node 6.
27. City Cab Company identified 10 primary pickup and drop locations for cab riders in New York City. In an effort to minimize travel time and improve customer service and the utilization of the company’s fleet of cabs, management would like the cab drivers to take the shortest route between locations whenever possible. Using the following network of roads and streets, what is the route a driver beginning at location 1 should take to reach location 10? The travel times in minutes are shown on the arcs of the network. Note that there are two one-way streets with the direction shown by the arrows.
18
Quantitative Analysis BA 452 Supplemental Questions 6 28. The five nodes in the following network represent points one year apart over a four-year period. Each node indicates a time when a decision is made to keep or replace a firm’s computer equipment. If a decision is made to replace the equipment, a decision must also be made as to how long the new equipment will be used. The arc from node 0 to node 1 represents the decision to keep the current equipment one year and replace it at the end of the year. The arc from node 0 to node 2 represents the decision to keep the current equipment two years and replace it at the end of year 2. The numbers above the arcs indicate the total cost associated with the equipment replacement decisions. These costs include discounted purchase price, trade-in value, operating costs, and maintenance costs. Use a shortest-route model to determine the minimum cost equipment replacement policy for the four-year period.
29. The north-south highway system ing through Albany, New York, can accommodate the capacities shown:
Can the highway system accommodate a north-south flow of 10,000 vehicles per hour?
19
Quantitative Analysis BA 452 Supplemental Questions 6 30. If the Albany highway system described in Problem 29 has revised flow capacities as shown in the following network, what is the maximal flow in vehicles per hour through the system? How many vehicles per hour must travel over each road (arc) to obtain this maximal flow?
31. A long-distance telephone company uses a fiber-optic network to transmit phone calls and other information between locations. Calls are carried through cable lines and switching nodes. A portion of the company’s transmission network is shown here. The numbers above each arc show the capacity in thousands of messages that can be transmitted over that branch of the network.
To keep up with the volume of information transmitted between origin and destination points, use the network to determine the maximum number of messages that may be sent from a city located at node 1 to a city located at node 7.
20
Quantitative Analysis BA 452 Supplemental Questions 6 32. The High-Price Oil Company owns a pipeline network that is used to convey oil from its source to several storage locations. A portion of the network is as follows:
Due to the varying pipe sizes, the flow capacities vary. By selectively opening and closing sections of the pipeline network, the firm can supply any of the storage locations. a. If the firm wants to fully utilize the system capacity to supply storage location 7, how long will it take to satisfy a location 7 demand of 1000,000 gallons? What is the maximal flow for this pipeline system? b. If a break occurs on line 2-3 and it is closed down, what is the maximal flow for the system? How long will it take to transmit 100,000 gallons to location 7? 33. For the following highway network system, determine the maximal flow in vehicles per hour.
The highway commission is considering adding highway section 3-4 to permit a flow of 2000 vehicles per hour or, at an additional cost, a flow of 3000 vehicles per hour. What is your recommendation for the 3-4 arc of the network?
21
Quantitative Analysis BA 452 Supplemental Questions 6 34. A chemical processing plant has a network of pipes that are used to transfer liquid chemical products from one part of the plant to another. The following pipe network has pipe flow capacities in gallons per minute as shown. What is the maximum flow capacity for the system if the company wishes to transfer as much liquid chemical as possible from location 1 to location 9? How much of the chemical will flow through the section of pipe from node 3 to node 5?
35. Refer to the Contois Carpets problem for which the network representation is shown in Figure 6.20. Suppose that Contois has a beginning inventory of 50 yards of carpet and requires an inventory of 50 yards of carpet and requires an inventory of 100 yards at the end of quarter 4. a. Develop a network representation of this modified problem. b. Develop a linear programming model and solve for optimal solution. 36. Sanders Fishing Supply of Naples, Florida, manufactures a variety of fishing equipment that it sells throughout the United States. For the next three months, Sanders estimates demand for a particular product at 150, 250, and 300 units, respectively. Sanders can supply the demand by producing on regular time or overtime. Because of other commitments and anticipated cost increase in month 3, the production capacities in units and the production costs per unit are as follows:
Inventory may be carried from one month to the next, but the cost is $20 per unit per month. For example, regular production from month 1 used to meet demand in month 2 would cost Sander $50 + $20 = $70 per unit. This same month 1 production used to meet demand in month 3 would cosr Sanders $50 + 2($20) = $90 per unit. a. Develop a network representation of this production scheduling problem as a transportation problem. (Hint: Use six origin nodes; the supply for origin node 1 is the maximum that can be produced in month 1 on regular time, and so on.) b. Develop a linear programming model that can be used to schedule regular and overtime production for each of the three months. c. What is the production schedule, how many units are carried in inventory each month, and what is the total cost? d. Is there any unused production capacity? If so, where?
22
Quantitative Analysis BA 452 Supplemental Questions 6
Answers to Supplemental Questions 6 1.
The network model is shown. Atlanta
1400
Dallas
3200
Columbus
2000
Boston
1400
2 5000
6
Phila.
6 2
1 2 3000
New Orleans
5 7
23
Quantitative Analysis BA 452 Supplemental Questions 6 2.
a. Let
x11 : Amount shipped from Jefferson City to Des Moines x12 : Amount shipped from Jefferson City to Kansas City • • • 9x12 Min 14x11 + + 7x13 + 8x21 + 10x22 + s.t. x11 x12 x13 + + x21 + x22 + x11 x21 + x12 x22 + x13 + x11, x12, x13, x21, x22, x23, ≥ 0
b.
Optimal Solution: Amount 5 15 10 20
Jefferson City - Des Moines Jefferson City - Kansas City Jefferson City - St. Louis Omaha - Des Moines Total
24
Cost 70 135 70 160 435
5x23 ≤ x23 ≤ = = x23 =
30 20 25 15 10
Quantitative Analysis BA 452 Supplemental Questions 6 3.
a.
b.
Let xij = amount shipped from supply node i to demand node j. Min s.t.
10x11
+
20x12
+
15x13
x11
+
x12
+
x13
x11
+
+ x12
12x21 + 15x22 + 18x23
x21 + x21 +
x13
x22 + x22 +
≤ x23 ≤ = = x23 =
500 400 400 200 300
xij ≥ 0 for all i, j c.
Optimal Solution Amount 200 300 200 200
Southern - Hamilton Southern - Clermont Northwest - Hamilton Northwest - Butler Total Cost d.
Cost $ 2000 4500 2400 3000 $11,900
To answer this question the simplest approach is to increase the Butler County demand to 300 and to increase the supply by 100 at both Southern Gas and Northwest Gas. The new optimal solution is: Amount 300 300 100 300
Southern - Hamilton Southern - Clermont Northwest - Hamilton Northwest - Butler Total Cost
Cost $ 3000 4500 1200 4500 $13,200
From the new solution we see that Tri-County should contract with Southern Gas for the additional 100 units. 25
Quantitative Analysis BA 452 Supplemental Questions 6 4.
a.
b.
The linear programming formulation and optimal solution are shown. The first two letters of the variable name identify the “from” node and the second two letters identify the “to” node.
LINEAR PROGRAMMING PROBLEM MIN 10SEPI + 20SEMO + 5SEDE + 9SELA + 10SEWA + 2COPI + 10COMO + 8CODE + 30COLA + 6COWA + 1NYPI + 20NYMO + 7NYDE + 10NYLA + 4NYWA
S.T. 1)
SEPI + SEMO + SEDE + SELA + SEWA <= 9000
26
Quantitative Analysis BA 452 Supplemental Questions 6 2) 3) 4) 5) 6) 7) 8)
COPI NYPI SEPI SEMO SEDE SELA SEWA
+ + + + + + +
COMO NYMO COPI COMO CODE COLA COWA
+ + + + + + +
CODE NYDE NYPI NYMO NYDE NYLA NYWA
+ + = = = = =
COLA + COWA <= 4000 NYLA + NYWA <= 8000 3000 5000 4000 6000 3000
OPTIMAL SOLUTION Optimal Objective Value 150000.00000 Variable
Reduced Cost
SEPI
0.00000
10.00000
SEMO
0.00000
1.00000
SEDE
4000.00000
0.00000
SELA
5000.00000
0.00000
SEWA
0.00000
7.00000
COPI
0.00000
11.00000
COMO
4000.00000
0.00000
CODE
0.00000
12.00000
COLA
0.00000
30.00000
COWA
0.00000
12.00000
NYPI
3000.00000
0.00000
NYMO
1000.00000
0.00000
NYDE
0.00000
1.00000
NYLA
1000.00000
0.00000
NYWA
3000.00000
0.00000
Constraint
c.
Value
Slack/Surplus
Dual Value
1
0.00000
-1.00000
2
0.00000
-10.00000
3
0.00000
0.00000
4
0.00000
1.00000
5
0.00000
20.00000
6
0.00000
6.00000
7
0.00000
10.00000
8
0.00000
4.00000
The new optimal solution actually shows a decrease of $9000 in shipping cost. It is summarized.
27
Quantitative Analysis BA 452 Supplemental Questions 6 Optimal Solution
Units
Seattle - Denver Seattle - Los Angeles Columbus - Mobile New York - Pittsburgh New York - Los Angeles New York - Washington
4000 5000 5000 4000 1000 3000
28
Cost $ 20,000 45,000 50,000 4,000 10,000 12,000 Total: $141,000
Quantitative Analysis BA 452 Supplemental Questions 6 5.
a.
b.
Let xij = number of hours from consultant i assigned to client j.
Max 100x11 + 125x12 + 115x13 s.t. + 120x24 + 155x31 x11 + x12 + x13 x21 x11
+ x12
+ 100x14 + 120x21 + 150x32 + 140x33 x14 + x22 + x23 + x31 x21 x31 + x + 22 x13 x23 + x14
+ 135x22 + 115x23 + 130x34 + +
x24 x32 +
+
x32 +
+
xij ≥ 0 for all i, j
29
x24
≤ ≤ x33 + x34 ≤ = = x33 = + x34 =
160 160 140 180 75 100 85
Quantitative Analysis BA 452 Supplemental Questions 6 Optimal Solution Hours Assigned 40 100 40 35 85 140
Avery - Client B Avery - Client C Baker - Client A Baker - Client B Baker - Client D Campbell - Client A Total Billing c.
Billing $ 5,000 11,500 4,800 4,725 10,200 21,700 $57,925
New Optimal Solution Hours Assigned 40 100 75 85 140
Avery - Client A Avery - Client C Baker - Client B Baker - Client D Campbell - Client A Total Billing
30
Billing $ 4,000 11,500 10,125 10,200 21,700 $57,525
Quantitative Analysis BA 452 Supplemental Questions 6 6.
The network model, the linear programming formulation, and the optimal solution are shown. Note that the third constraint corresponds to the dummy origin. The variables x31, x32, x33, and x34 are the amounts shipped out of the dummy origin; they do not appear in the objective function since they are given a coefficient of zero. Demand
Supply
D1
2000
D2
5000
D3
3000
D4
2000
32
5000
34
C.S.
32 40 34 30 3000
D.
28 38 0 0
4000
0
Dum
0
Note: Dummy origin has supply of 4000. Max
32x11 + 34x12 + 32x13 + 40x14 + 34x21 + 30x22 + 28x23 + 38x24
s.t. x11 +
x12 +
x13 +
x31 + x11
+
x14
x32 +
x21
x12
+ +
x21 +
x22 +
x33 +
x34
+ +
x24
x31
x22
x13
x23 +
x32
x23
x14
+ +
x24
xij ≥ 0 for all i, j
31
x33 +
x34
≤
5000
≤
3000
≤
4000
=
2000
=
5000
=
3000
= 2000
Dummy
Quantitative Analysis BA 452 Supplemental Questions 6
Optimal Solution
Units
Clifton Springs - D2 Clifton Springs - D4 Danville - D1 Danville - D4
4000 $136,000 1000 40,000 2000 68,000 1000 38,000 Total Cost: $282,000
Customer 2 demand has a shortfall of 1000 Customer 3 demand of 3000 is not satisfied.
32
Cost
Quantitative Analysis BA 452 Supplemental Questions 6 7.
a.
My answer to this homework 1question 50 Boston will go here. To 7find your answer, you 1 may want to study 11 the answers to some 100 of the similarDenverquestions. 8 13
2 Dallas
20
70
17 100
2 Atlanta
12 10
3 Los Angeles
8
60
18 3 150
13
Chicago 16 4 St. Paul
b.
80
There are alternative optimal solutions. Solution #1
Solution # 2
Denver to St. Paul: 10 Atlanta to Boston: 50 Atlanta to Dallas: 50 Chicago to Dallas: 20 Chicago to Los Angeles: 60 Chicago to St. Paul: 70
Denver to St. Paul: 10 Atlanta to Boston: 50 Atlanta to Los Angeles: 50 Chicago to Dallas: 70 Chicago to Los Angeles: 10 Chicago to St. Paul: 70
Total Profit: $4240 If solution #1 is used, Forbelt should produce 10 motors at Denver, 100 motors at Atlanta, and 150 motors at Chicago. There will be idle capacity for 90 motors at Denver. If solution #2 is used, Forbelt should adopt the same production schedule but a modified shipping schedule.
33
Quantitative Analysis BA 452 Supplemental Questions 6 8.
The linear programming formulation and optimal solution are shown. x1A Let = Units of product A on machine 1 x1B = Units of product B on machine 1 • • • x3C = Units of product C on machine 3
Min
x1A + 1.2x1B + 0.9x1C + 1.3x2A + 1.4x2B + 1.2x2C + 1.1x3A + x3B + 1.2x3C
s.t. x1A +
x1B +
x1C x2A +
x2B +
x2C x3A + x3B +
x1A
+
x2A
x1B
+ +
x3A
x2B
x1C
+ x3B +
x2C
+
xij ≥ 0 for all i, j
Optimal Solution 1-A 1-C 2-A 3-A 3-B
Units
Cost
300 1200 1200 500 500
$ 300 1080 1560 550 500 Total: $3990
Note: There is an unused capacity of 300 units on machine 2.
34
≤
1500
≤
1500
x3C ≤
1000
=
2000
=
500
x3C =
1200
Quantitative Analysis BA 452 Supplemental Questions 6 9.
a.
b. Min 10x11 + 16x12 + 32x13 + 14x21 + 22x22 + 40x23 + 22x31 + 24x32 + 34x33 s.t. x11 + x12 + x13 x21 + x22 + x23 x31 + x32 + x33 x11 + x21 + x31 x12 + x22 + x32 x13 x + 23 + x33 xij ≥ 0 for all i, j Solution x12 = 1, x21 = 1, x33 = 1 Total completion time = 64
35
≤ ≤ ≤ = = =
1 1 1 1 1 1
Quantitative Analysis BA 452 Supplemental Questions 6 10. a.
b. Min s.t.
30x11 x11
x11
+ 44x12 + x21
+ x12
+ 38x13
x12 + + x22 x31 + x41 x21 + + x22 x13 + x14
x13 + x32 + x51 x31 + x23 + x15
+ 47x14 + x23 + x42 + + x32 + x24 +
x14 + x33 + x52 x41 + x33 + x25
+ 31x15 + x24 + x43 + + x42 + x34 +
x15 + x34 + x53 x51 + x43 + x35
+ 25x21
+
x25 + x44 +
x35 + x45 x54 + x55
x52 + x44 +
x53 + x54 x45 + x55
+ 28x55 ≤ ≤ ≤ ≤ ≤ = = = = =
1 1 1 1 1 1 1 1 1 1
xij ≥ 0, i = 1, 2,.., 5; j = 1, 2,.., 5 Optimal Solution: Green to Job 1 Brown to Job 2 Red to Job 3 Blue to Job 4 White to Job 5
$26 34 38 39 25 $162
Since the data is in hundreds of dollars, the total installation cost for the 5 contracts is $16,200.
36
Quantitative Analysis BA 452 Supplemental Questions 6 11.
This can be formulated as a linear program with a maximization objective function. There are 24 variables, one for each program/time slot combination. There are 10 constraints, 6 for the potential programs and 4 for the time slots.
My answer to this homework question will Optimal go Solution: here. To find your answer, you Live 5:00 – 5:30 p.m. mayNASCAR want to study the answers to some Hollywood Briefings 5:30 – 6:00 p.m. World News 7:00 – 7:30 p.m. Ramundo & Son 8:00 – 8:30 p.m. of the similar questions. Total expected advertising revenue = $30,500
37
Quantitative Analysis BA 452 Supplemental Questions 6 12. a.
This is the variation of the assignment problem in which multiple assignments are possible. Each distribution center may be assigned up to 3 customer zones. The linear programming model of this problem has 40 variables (one for each combination of distribution center and customer zone). It has 13 constraints. There are 5 supply (≤ 3) constraints and 8 demand (= 1) constraints. The optimal solution is given below.
Plano: Flagstaff: Springfield: Boulder:
Assignments Kansas City, Dallas Los Angeles Chicago, Columbus, Atlanta Newark, Denver Total Cost -
Cost ($1000s) 34 15 70 97 $216
b.
The Nashville distribution center is not used.
c.
All the distribution centers are used. Columbus is switched from Springfield to Nashville. Total cost increases by $11,000 to $227,000.
38
Quantitative Analysis BA 452 Supplemental Questions 6 13.
A linear programming formulation and the optimal solution are given. For the decision variables, xij, we let the first subscript correspond to the supplier and the second subscript correspond to the distribution hub. Thus, xij = 1 if supplier i is awarded the bid to supply hub j and xij = 0 if supplier i is not awarded the bid to supply hub j. Min 190x11 +175x12 + 125x13 + 230x14 + 150x21 + 235x22 + 155x23 + 220x24 + 210x31 + 225x32 + 135x33 +260x34 + 170x41 + 185x42 + 190x43 + 280x44 + 220x51 + 190x52 + 140x53 + 240x54 + 270x61 + 200x62 + 130x63 + 260x64 s.t. x11 + x12 + x13 + x14 ≤ 1 + x21 + x22 + x23 + x24 ≤ 1 x31 + x32 + x33 + x34 ≤ 1 x41 + x42 + x43 + x44 ≤ 1 x51 + x52 + x53 + x54 ≤ 1 x61 + x62 + x63 + x64 ≤ 1 x11 + x21 + x31 + x41 + x51 + x61 = 1 x12 + x22 + x32 + x42 + x52 + x62 = 1 x13 + x23 + x33 + x43 + x53 + x63 = 1 x14 + x24 + x34 + x44 + x45 + x46 = 1 xij ≥ 0 for all i, j Bid
Optimal Solution Martin – Hub 2 Schmidt Materials – Hub 4 D&J Burns – Hub 1 Lawler Depot – Hub 3
14.
175 220 170 130 695
A linear programming formulation of this problem can be developed as follows. Let the first letter of each variable name represent the professor and the second two the course. Note that a DPH variable is not created because the assignment is unacceptable.
Max 2.8AUG
+ 2.2AMB
+ 3.3AMS
+ 3.0APH
+
+ +
AMS BMB CUG
+ + +
CUG BMB AMS
+ + +
+ 3.2BUG
+
···
+ 2.5DMS
s.t. AUG
AUG
+
AMB BUG
BUG AMB
+ +
APH BMS CMB DUG DUG CMB BMS APH
+ + +
BPH CMS DMB
+ +
H DMS
+ + +
DMB CMS BPH
+ +
DMS H
All Variables ≥ 0 Optimal Solution: A to MS course B to Ph.D. course C to MBA course D to Undergraduate course Max Total Rating 39
Rating 3.3 3.6 3.2 3.2 13.3
≤ ≤ ≤ ≤ = = = =
1 1 1 1 1 1 1 1
Quantitative Analysis BA 452 Supplemental Questions 6 15. a.
My answer to this homework question 210x12 + 270x13 Min 150x11 + 170x21 + + 220x23 22 will go+ here. To 230x find your answer, you 180x31 225x33 + + 230x32 + 160x41 + 240x42 230x43 + answers + some may want to study the to s.t. x11 +similar x12 + questions. x13 ≤ 1 of the x x x + + ≤ 1 21
x11
22 x31
+x21 x12
+
+x31 +x22
x13
+x32 +x23
23 x32 + x41 + +x41 +x42 +x33
x33 x42 +
+x43
≤ x43 ≤ = = =
1 1 1 1 1
xij ≥ for all i, j Optimal Solution: x12 = 1, x23 = 1, x41 = 1 Total hours required: 590 Note: statistician 3 is not assigned. b.
The solution will not change, but the total hours required will increase by 5. This is the extra time required for statistician 4 to complete the job for client A.
c.
The solution will not change, but the total time required will decrease by 20 hours.
d.
The solution will not change; statistician 3 will not be assigned. Note that this occurs because increasing the time for statistician 3 makes statistician 3 an even less attractive candidate for assignment.
40
Quantitative Analysis BA 452 Supplemental Questions 6 16. a.
The total cost is the sum of the purchase cost and the transportation cost. We show the calculation for Division 1 - Supplier 1 and present the result for the other Division-Supplier combinations. Division 1 - Supplier 1 Purchase cost (40,000 x $12.60) Transportation Cost (40,000 x $2.75) Total Cost:
$504,000 110,000 $614,000
Cost Matrix ($1,000s) Supplier 1
2
3
4
5
6
1
614
660
534
680
590
630
2
603
639
702
693
693
630
3
865
830
775
850
900
930
4
532
553
511
581
595
553
5
720
648
684
693
657
747
Division
b.
Optimal Solution: Supplier 1 - Division 2 Supplier 2 - Division 5 Supplier 3 - Division 3 Supplier 5 - Division 1 Supplier 6 - Division 4
$ 603 648 775 590 553 Total $3,169
41
Quantitative Analysis BA 452 Supplemental Questions 6 17. a.
Network Model Demand
Supply 1 P1
450
300
7 C2
300
8 C3
300
9 C4
400
4 6 7
4
4 W1
8 4
8
2 P2
600
6 C1
5
3 6 5 W2
5 380
7
6
3 P3
7
b. & c. The linear programming formulation and solution are shown. LINEAR PROGRAMMING PROBLEM MIN 4X14 + 7X15 + 8X24 + 5X25 + 5X34 + 6X35 + 6X46 + 4X47 + 8X48 + 4X49 + 3X56 + 6X57 + 7X58 + 7X59 S.T. 1) 2) 3) 4) 5) 6) 7) 8) 9)
X14 X24 X34 X46 X56 X46 X47 X48 X49
+ + + + + + + + +
X15 X25 X35 X47 X57 X56 X57 X58 X59
<= 450 <= 600 < 380 + X48 + X49 - X14 - X24 - X34 = 0 + X58 + X59 - X15 - X25 - X35 = 0 = 300 = 300 = 300 = 400
42
Quantitative Analysis BA 452 Supplemental Questions 6 OPTIMAL SOLUTION Optimal Objective Value 11850.00000 Variable
Value
Reduced Cost
X14
450.00000
0.00000
X15
0.00000
2.00000
X24
0.00000
4.00000
X25
600.00000
0.00000
X34
250.00000
0.00000
X35
0.00000
0.00000
X46
0.00000
2.00000
X47
300.00000
0.00000
X48
0.00000
0.00000
X49
400.00000
0.00000
X56
300.00000
0.00000
X57
0.00000
3.00000
X58
300.00000
0.00000
X59
0.00000
4.00000
Constraint
Slack/Surplus
Dual Value
1
0.00000
-1.00000
2
0.00000
-1.00000
3
130.00000
0.00000
4
0.00000
9.00000
5
0.00000
9.00000
6
0.00000
13.00000
7
0.00000
9.00000
8
0.00000
5.00000
9
0.00000
6.00000
There is an excess capacity of 130 units at plant 3.
43
Quantitative Analysis BA 452 Supplemental Questions 6 18. a.
Three arcs must be added to the network model in problem 23a. The new network is shown. Demand
Supply 1 P1
450
300
7 C2
300
8 C3
300
9 C4
400
4 6 7
4
4 W1
8 4
8
2 P2
600
6 C1
5
2
2
3 6
5 W2
5 380
7
6
3 P3
7
7
b.&c. The linear programming formulation and optimal solution follow: LINEAR PROGRAMMING PROBLEM MIN 4X14 + 7X15 + 8X24 + 5X25 + 5X34 + 6X35 + 6X46 + 4X47 + 8X48 + 4X49 + 3X56 + 6X57 + 7X58 + 7X59 + 7X39 + 2X45 + 2X54 S.T. 1) 2) 3) 4) 5) 6) 7) 8) 9)
X14 X24 X34 X45 X54 X46 X47 X48 X39
+ + + + + + + + +
X15 X25 X35 X46 X56 X56 X57 X58 X49
<= 450 <= 600 + X39 <= 380 + X47 + X48 + X49 - X14 - X24 - X34 - X54 = 0 + X57 + X58 + X59 - X15 - X25 - X35 - X45 = 0 = 300 = 300 = 300 + X59 = 400
44
Quantitative Analysis BA 452 Supplemental Questions 6 OPTIMAL SOLUTION Optimal Objective Value 11220.00000 Variable
Value
Reduced Cost
X14
320.00000
0.00000
X15
0.00000
2.00000
X24
0.00000
4.00000
X25
600.00000
0.00000
X34
0.00000
2.00000
X35
0.00000
2.00000
X46
0.00000
2.00000
X47
300.00000
0.00000
X48
0.00000
0.00000
X49
20.00000
0.00000
X56
300.00000
0.00000
X57
0.00000
3.00000
X58
300.00000
0.00000
X59
0.00000
4.00000
X39
380.00000
0.00000
X45
0.00000
1.00000
X54
0.00000
3.00000
Constraint
Slack/Surplus
Dual Value
1
130.00000
0.00000
2
0.00000
0.00000
3
0.00000
-1.00000
4
0.00000
8.00000
5
0.00000
8.00000
6
0.00000
12.00000
7
0.00000
8.00000
8
0.00000
4.00000
9
0.00000
5.00000
The value of the solution here is $630 less than the value of the solution for problem 23. The new shipping route from plant 3 to customer 4 has helped (x39 = 380). There is now excess capacity of 130 units at plant 1.
45
Quantitative Analysis BA 452 Supplemental Questions 6 19. a.
My answer to this homework question 5 Boston 150 will go here. To find your answer, you 8 1 3 7 Augusta 300 want Albany answers 5 may to study the to some 5 6 of the similar questions. 7 NewYork 100 5
3 2 Tupper Lake
100
4 Portsmouth
4
6 10 7 Philadelphia
150
b. Min s.t.
7x13 + 5x14 + 3x23 + 4x24 + 8x35 + 5x36 + 7x37 + 5x45 + 6x46 + 10x47 x13
+
x14
-x13
-
x23 x23
x14
+ x24 + x35
+ x36
+ x37
- x24
+ x45 + x45
x35 + x36
xij ≥ 0 for all i and j Optimal Solution:
Variable x13 x14 x23 x24 x35 x36 x37 x45 x46 x47
Value 50 250 100 0 0 0 150 150 100 0
Objective Function: 4300
46
+
x47
+
x47
+ x46 x37
c.
+ x46
≤ ≤ = = = = =
300 100 0 0 150 100 150
Quantitative Analysis BA 452 Supplemental Questions 6 20.
A linear programming model is Min 8x14 + 6x15 + 3x24 + 8x25 + 9x34 + 3x35 + 44x46 + 34x47 + 34x48 + 32x49 + 57x56 + 35x57 + 28x58 + 24x59 s.t. ≤ 3
x14 + x15
≤ 6
x24 + x25
≤ 5
x34 + x35 - x24
-x 14 - x15
- x34 - x25
+
x46 +
x47 +
x48 +
- x35 x46 x47
+
x56 +
+
x56 x57
x59 = 0
= 4 + x58
x49 xij ≥ 0 for all i, j
x57 + x58 +
= 2 +
x48
47
= 0
x49
= 3 +
x59 = 3
Quantitative Analysis BA 452 Supplemental Questions 6 Optimal Solution
Units Shipped Muncie to Cincinnati Cincinnati to Concord Brazil to Louisville Louisville to Macon Louisville to Greenwood Xenia to Cincinnati Cincinnati to Chatham
Cost 1 3 6 2 4 5 3
Two rail cars must be held at Muncie until a buyer is found.
48
6 84 18 88 136 15 72 419
Quantitative Analysis BA 452 Supplemental Questions 6 21.
The positive numbers by nodes indicate the amount of supply at that node. The negative numbers by nodes indicate the amount of demand at the node. 22. a. Min 20x12 + 25x15 + 30x25 + 45x27 + 20x31 + 35x36 + 30x42 + 25x53 + 15x54 + 28x56 + 12x67 + 27x74 s.t. x31
x12 -
-
x31 + x53 +
x54 +
= 8
x15 x25 +
x27
x36 -
x53
x56 -
-
x12
-
b.
xij ≥ 0 for all i, j x12 = 0 x53 x15 = 0 x54 x25 = 8 x56 x27 = 0 x67 x31 = 8 x74 x36 = 0 x56 x42 = 3
= = = = = =
x27 -
x54 +
x74
x15
x25
5 0 5 0 6 5
Total cost of redistributing cars = $917
49
x67
= 5 = 3
-
-
x36 + x74 -
x42 x42
= 3 = 2
x56 -
x67 = 5 = 6
Quantitative Analysis BA 452 Supplemental Questions 6 23.
Origin – Node 1 Transshipment Nodes 2 to 5 Destination – Node 7 The linear program will have 14 variables for the arcs and 7 constraints for the nodes.
1 if the arc from node i to node j is on the shortest route Let xij = 0 otherwise Min 7 x12 + 9 x13 + 18 x14 + 3 x23 + 5 x25 + 3 x32 + 4 x35 + 3 x46 + 5 x52 + 4 x53 + 2 x56
+6 x57 + 2 x65 + 3 x67 s.t. Flow Out
Flow In
Node 1
x12 + x13 + x14
Node 2
− x12 − x32 − x52 − x13 − x23 − x53 − x14 − x25 − x35 − x65
=0
Node 5
x23 + x25 x32 + x35 x46 x52 + x53 + x56 + x57
Node 6
x65 + x67
− x46 − x56 + x57 + x67
=0
Node 3 Node 4
Node 7
=1 =0 =0 =0 =1
xij > 0 for all i and j Optimal Solution: x12 = 1 , x25 = 1 , x56 = 1 , and x67 = 1 Shortest Route 1-2-5-6-7 Length = 17
24.
The linear program has 13 variables for the arcs and 6 constraints for the nodes. Use same six constraints for the Gorman shortest route problem as shown in the text. The objective function changes to travel time as follows. Min 40 x12 + 36 x13 + 6 x23 + 6 x32 + 12 x24 + 12 x42 + 25 x26 + 15 x35 + 15 x53 + 8 x45 + 8 x54 + 11 x46 + 23 x56 Optimal Solution: x12 = 1 , x24 = 1 , and x46 = 1 Shortest Route 1-2-4-6 Total Time = 63 minutes
50
Quantitative Analysis BA 452 Supplemental Questions 6 25. a.
Origin – Node 1 Transshipment Nodes 2 to 5 Destination – Node 6 The linear program will have 13 variables for the arcs and 6 constraints for the nodes.
1 if the arc from node i to node j is on the shortest route Let xij = 0 otherwise Min 35 x12 + 30 x13 + 12 x23 + 18 x24 + 39 x26 + 12 x32 + 15 x35 + 18 x42 + 12 x45
+16x46 +15x53 +12x54 +30x56 s.t. Flow Out Node 1
x12 + x13
Node 2
x23 + x24 + x26 x32 + x35 x42 + x45 + x46 + x53 + x54 + x56
Node 3 Node 4 Node 5
Flow In =1
− x12 − x32 − x42 − x13 − x23 − x53 − x24 − x54 − x35 − x45 + x26 + x46 + x56
Node 6
=0 =0 =0 =0 =1
xij > 0 for all I and j b.
Optimal Solution: x12 = 1 , x24 = 1 , and x46 = 1 Shortest Route 1-2-4-6 Total time = 69 minutes
c.
Allowing 8 minutes to get to node 1 and 69 minutes to go from node 1 to node 6, we expect to make the delivery in 77 minutes. With a 20% safety margin, we can guarantee a delivery in 1.2(77) = 92 minutes. It is 1:00 p.m. now. Guarantee delivery by 2:32 p.m.
51
Quantitative Analysis BA 452 Supplemental Questions 6 26.
Origin – Node 1 Transshipment Nodes 2 to 5 and node 7 Destination – Node 6 The linear program will have 18 variables for the arcs and 7 constraints for the nodes.
1 if the arc from node i to node j is on the shortest route Let xij = 0 otherwise Min
35 x12 + 30 x13 + 20 x14 + 8 x23 + 12 x25 + 8 x32 + 9 x34 + 10 x35 + 20 x36 +9 x43 + 15 x47 + 12 x52 + 10 x53 + 5 x56 + 20 x57 + 15 x74 + 20 x75 + 5 x76
s.t. Flow Out Node 2
x12 + x13 + x14 x23 + x25
Node 3
x32 + x34 + x35 + x36
Node 4
x43 + x47 x52 + x53 + x56 + x57
Node 1
Node 5 Node 6 Node 7
x74 + x75 + x76
Flow In =1
− x12 − x32 − x52 =0 − x13 − x23 − x43 − x53 = 0 − x14 − x34 − x74 =0 − x25 − x35 − x75 =0 + x36 + x56 + x76 =1 − x47 − x57
xij > 0 for all i and j Optimal Solution: x14 = 1 , x47 = 1 , and x76 = 1 Shortest Route 1-4-7-6 Total Distance = 40 miles
52
=0
Quantitative Analysis BA 452 Supplemental Questions 6 27.
Origin – Node 1 Transshipment Nodes 2 to 9 Destination – Node 10 (Identified by the subscript 0) The linear program will have 29 variables for the arcs and 10 constraints for the nodes.
1 if the arc from node i to node j is on the shortest route Let xij = 0 otherwise
Min
8 x12 + 13 x13 + 15 x14 + 10 x15 + 5 x23 + 15 x27 + 5 x32 + 5 x36 + 2 x43 + 4 x45 +3 x46 + 4 x54 + 12 x59 + 5 x63 + 3 x64 + 4 x67 + 2 x68 + 5 x69 + 15 x72 + 4 x76 +2 x78 + 4 x70 + 2 x86 + 5 x89 + 7 x80 + 12 x95 + 5 x96 + 5 x98 + 5 x90
s.t. Flow Out
Flow In
Node 1
x12 + x13 + x14 + x15
Node 2
x23 + x27 x32 + x36
− x12 − x32 − x72
=0
− x13 − x23 − x43 − x63
=0
Node 4
x43 + x45 + x46 x54 + x59 x63 + x64 + x67 + x68 + x69 x72 + x76 + x78 + x70
− x14 − x54 − x64 − x15 − x45 − x95
=0
Node 5
Node 3
Node 6 Node 7 Node 8 Node 9 Node 10
=1
=0
− x36 − x46 − x76 − x86 − x96 = 0 − x27 − x67 =0 x86 + x89 + x80 − x68 − x78 − x98 =0 x95 + x96 + x98 + x90 − x59 − x69 − x89 =0 + x70 + x80 + x90 =1 xij > 0 for all i and j
Optimal Solution: x15 = 1 , x54 = 1 , x46 = 1 , x67 = 1 , and x70 = 1 Shortest Route 1-5-4-6-7-10 Total Time = 25 minutes
53
Quantitative Analysis BA 452 Supplemental Questions 6 28.
Origin – Node 0 Transshipment Nodes 1 to 3 Destination – Node 4 The linear program will have 10 variables for the arcs and 5 constraints for the nodes.
1 if the arc from node i to node j is on the minimum cost route Let xij = 0 otherwise Min
600 x01 + 1000 x02 + 2000 x03 + 2800 x04 + 500 x12 + 1400 x13 + 2100 x14 +800 x23 + 1600 x24 + 700 x34
s.t. Flow Out Node 0 Node 1 Node 2 Node 3
x01 + x02 + x03 + x04 x12 + x13 + x14 x23 + x24 x34
Node 4
Flow In =1
− x01
=0
− x02 − x12
=0
− x03 − x13 − x23
=0
− x04 − x14 − x24 − x34 xij > 0 for all i and j
Optimal Solution: x02 = 1 , x23 = 1 , and x34 = 1 Shortest Route 0-2-3-4 Total Cost = $2500
54
=1
Quantitative Analysis BA 452 Supplemental Questions 6 29.
The capacitated transshipment problem to solve is given: Max x61 s.t. x12 + x24 + x34 + x42 + x54 + x61 -
x13 + x25 x36 x43 + x56 x36 +
x12 ≤ 2 x24 ≤ 1 x34 ≤ 3 x42 ≤ 1 x54 ≤ 1
x14 x12 x13 x45 + x25 x46 -
x61 = 0 x42 = 0 x43 = 0 x46 - x14 - x24 - x34 - x54 = 0 x45 =0 x56 =0
x13 ≤ 6 x25 ≤ 4 x36 ≤ 2 x43 ≤ 3 x56 ≤ 6
x14 ≤ 3 x45 ≤ 1
x46 ≤ 3
xij ≥ 0 for all i, j 3 2
5
2
1
3
3
1
4
1
4
6
2
4
2
3
The system cannot accommodate a flow of 10,000 vehicles per hour.
55
Maximum Flow 9,000 Vehicles Per Hour
Quantitative Analysis BA 452 Supplemental Questions 6 30. 4 2
5
3
1
3
3
1
6
2
4
6
3
5
11,000
2
3
31.
The maximum number of messages that may be sent is 10,000.
32. a.
10,000 gallons per hour or 10 hours
b. 33.
Flow reduced to 9,000 gallons per hour; 11.1 hours. Current Max Flow = 6,000 vehicles/hour. With arc 3-4 at a 3,000 unit/hour flow capacity, total system flow is increased to 8,000 vehicles/hour. Increasing arc 3-4 to 2,000 units/hour will also increase system to 8,000 vehicles/hour. Thus a 2,000 unit/hour capacity is recommended for this arc.
34.
Maximal Flow = 23 gallons / minute. Five gallons will flow from node 3 to node 5.
56
Quantitative Analysis BA 452 Supplemental Questions 6 35. a.
Modify the problem by adding two nodes and two arcs. Let node 0 be a beginning inventory node with a supply of 50 and an arc connecting it to node 5 (period 1 demand). Let node 9 be an ending inventory node with a demand of 100 and an arc connecting node 8 (period 4 demand to it).
b. + 2x15
Min s.t.
+ 5x26
+ 3x37
+ 3x48
+ 0.25x56
+ 0.25x67
+ 0.25x78
+ 0.25x89
x05 x15 x26 x37 x48 x05
+ x15
+
x26 x37
x56 x56
+
x48 xij ≥ 0 for all i and j
Optimal Solution: x05 = 50 x15 = 600 x26 = 250 x37 = 500 x48 = 400
x56 = 250 x67 = 0 x78 = 100 x89 = 100
Total Cost = $5262.50
57
x67 x67
+
x78 x78
-
x89 x89
= ≤ ≤ ≤ ≤ = = = = =
50 600 300 500 400 400 500 400 400 100
Quantitative Analysis BA 452 Supplemental Questions 6 36. a.
Let R1, R2, R3 O1, O2, O3 D1, D2, D3
represent regular time production in months 1, 2, 3 represent overtime production in months 1, 2, 3 represent demand in months 1, 2, 3
Using these 9 nodes, a network model is shown.
b.
Use the following notation to define the variables: first two letters designates the "from node" and the second two letters designates the "to node" of the arc. For instance, R1D1 is amount of regular time production available to satisfy demand in month 1, O1D1 is amount of overtime production in month 1 available to satisfy demand in month 1, D1D2 is the amount of inventory carried over from month 1 to month 2, and so on.
MIN 50R1D1 + 80O1D1 + 20D1D2 + 50R2D2 + 80O2D2 + 20D2D3 + 60R3D3 + 100O3D3 S.T.
58
Quantitative Analysis BA 452 Supplemental Questions 6 1) 2) 3) 4) 5) 6) 7) 8) 9) c.
R1D1 O1D1 R2D2 O2D2 R3D3 O3D3 R1D1 R2D2 R3D3
≤ ≤ ≤ ≤ ≤ ≤ + + +
275 100 200 50 100 50 O1D1 - D1D2 = 150 O2D2 + D1D2 - D2D3 = 250 O3D3 + D2D3 = 300
Optimal Solution:
Variable -------------R1D1 O1D1 D1D2 R2D2 O2D2 D2D3 R3D3 O3D3
Value --------------275.000 25.000 150.000 200.000 50.000 150.000 100.000 50.000
Value = $46,750 Note: Slack variable for constraint 2 = 75. d.
The values of the slack variables for constraints 1 through 6 represent unused capacity. The only nonzero slack variable is for constraint 2; its value is 75. Thus, there are 75 units of unused overtime capacity in month 1.
59