Discrete Optimization
Page 1 of 6 Part I : (Problem #11, page 962 of text by Winston ) Suppose there are 50 matches on a table. I begin by picking up 1, 2, 3, 4 or 5 matches. Then my opponent must pick up 1, 2, 3, 4 or 5 matches. We continue until the last match is picked up. The player who picks up the last match is the loser. Can I be sure of victory? If so, how? Part II: (Problem #3, page 988 of text by Winston ) It costs $40 to buy a telephone from a department store. The estimated maintenance cost for each year of operation is shown in the following table. (I can keep a telephone for at most five years.) I have just purchased a new telephone, and my old telephone has no salvage value. Determine how to minimize the total cost of purchasing and operating a telephone for the next six years : Year Maintenance Cost ($) 1 30 2 35 3 45 4 65 5 90 Part III: Consider a production/inventory system with the following characteristics: • Maximum inventory level is 8 • Storage costs are $1/week per unit in inventory at the beginning of the week • Initially, the inventory contains 2 units. • Maximum production level is 6/week • Setup cost for production is $10 in each week in which production is scheduled • Marginal production costs (costs in excess of setup cost) are $2 per unit • Demand in each of the next 8 weeks is assumed to be known and must be satisfied They are (where t =stage="weeks remaining", i.e., D[8] = first week demand, ...
D[1] = 8th week demand): Demands t 8 7 6 5 4 3 2 1 D[t] 5 1 4 4 3 2 3 1 • Anything produced during a certain week (plus anything in inventory at the beginning of the week) may be used to satisfy demand during that week, while Page 2 of 6 anything in excess of the maximum inventory level (8) at the end of the week, after demand is satisfie d, is discarded) • At the end of the 8 weeks, a salvage value of $3 per unit remaining in inventory is recovered. a. Suppose that, upon recounting the initial inventory, you find that you had previously overlooked three units, so that you actually have 5 unit s in stock. What is now your optimal total cost for the 8 -week period? b. If you have 5 units in stock initially, what is now your optimal production schedule?
That is, in which weeks should you produce, and how much? c. Suppose that, in the third week (i. e. stage #6), you have an unexpected cancellation of an order for one unit. Does this change your production schedule for the remaining 6 weeks? If so, what is the new production schedule? Hint: To answer all of these questions, use the original tables below. (No re -computation of these tables is required.) Page 3 of 6 Part IV: A system consists of 4 devices, each subject to possible failure, such that the system fails if any one or more of the devices fail: Device Reliability Weight (kg) 1 75% 2 2 90% 3 Page 4 of 6 3 80% 1 4 85% 2 Suppose that redundant units of devices 1 and 3 are included as shown below. That is, system failure occurs if all 3 of device 1, or both of device 3, or device 2, or device 4 were to fail. (1) What is the reliability of device 3 in the system shown? (2) What is the reliability of this entire system? Suppose that we wish to find the system design having maximum reliability subject to a limit of 14 kg weight. We define a dynamic programming model with optimal value function fn(s), where fn(s) the maximum reliability of devices 1 through n, if S kg of weight is allocated to them. (3) The value of S4 is (choose one or more): a. the safety factor for device 4 b. 15% c. the state of the DE system at stage 4 d. 1 kg e. the reliability of d evice #4 f. 14 kg The following table shows the reliability of a device for various numbers of redundant units: Device # of units 1 2 3 Page 5 of 6 1 0.75 0.9375 0.984375 2 0.9 0.99 0.999 3 0.8 0.96 0.992 4 0.85 0.9775 0.996625 The following output is obtained during the solution of the DP model, where several values have been omitted. Note that the value -99.99999 is used to indicate - , i.e., an infeasible combination of s & x. (4) Enter the missing value for each of the entries in the tables (2 points) : α_______ , β_______ , γ_______ , δ_______ , ε_______ (5) The optimal design, weighing 14 kg., has reliability: ____________ (6) The optimal design has ___ units of #1, ___ unit of #2, ___ units of #3, and ___ units of #4. Stage 1 Stage 2 Page 6 of 6 Stage 3 Stage 4