Chapter 9 606o72
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report 3i3n4
Overview 26281t
& View Chapter 9 as PDF for free.
More details 6y5l6z
- Words: 5,002
- Pages: 13
Instructor’s Manual
Chapter 9
102
Chapter 9 I
Chapter Outline
9.1
Formulating a Management Problem as a Discrete Optimization Model • Integer optimization models • Binary optimization models • Mixed-integer optimization models
9.2
Graphical Analysis of Discrete Optimization Models in Two variables
9.3
Computer Solution of Discrete Optimization Problems • General principles on the solvability of a discrete optimization model • Using spreadsheet software to solve a discrete optimization problem
9.4
The Branch-and-Bound Method for Solving a Discrete Optimization Model • Discussion on how this method is used by spreadsheet software to solve binary optimization models
II
Teaching Tips
1.
It is interesting to show in class how difficult a discrete model can be even for a small set of decision variables (and even for binary variables). You can show how the number of feasible solutions grows at an exponential rate according to the number of variables.
2.
Some of the problems and exercises in this chapter can be also modeled as network problems. To develop student intuition in this chapter, it helps to present the alternative formulation in of graphs or networks.
3.
The discussion on solving discrete optimization models can be enhanced by mentioning new optimization techniques such as genetic algorithms, neural networks, taboo search, etc. In particular, it is not difficult to adapt the capital budgeting problem (Example 9.2) to be solved by genetic algorithms. Keep in mind that the most recent versions of Solver include the evolutionary/genetic search optimization techniques.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual III
Chapter 9
103
Answers to Chapter Exercises
9.1 (a) Not shown. (b) The new optimal strategy is to relocate to London, Madrid, and Hamburg, for a total cost of $56 million. The optimal fractions of service requests are shown in the following table (results may differ depending on the tolerance level):
London Madrid Paris Hamburg Rome
London 1.00 0.00 0.00 0.25 0.00
Fraction of service requests Madrid Paris Hamburg 0.00 0.00 0.00 0.00 0.00 1.00 0.00 0.00 1.00 0.75 0.00 0.00 0.25 0.00 0.75
Rome 0.00 0.00 0.00 0.00 0.00
(c) The results are shown in the table below. Notice that for an average shipping time across countries of 0.6, the model is no longer feasible (results may differ depending on the tolerance level).
Average shipping time 0.8 0.7 0.6
London 1 1
Optimal relocation Madrid Paris Hamburg 1 0 1 0 0 1 Infeasible
Rome 0 1
Total cost $56 $57
(d) In addition to changing the 1.1 value by 1 in the constraint corresponding to total shipping time, we replace the objective function by this function: Max 10y1 + 15y2 + 22y3 + 21y4 + 16y5 + 2(1-y1) + 2(1-y2) + 2(1-y3) + 3y4 + 3y5. The optimal relocation strategy is to close the centers in London and Madrid, and open a new one in Rome. The total cost of this strategy is $45 millions (results may differ depending on the tolerance level). 9.2 (a) Consider the following binary optimization model: Max 25X1 + 40X2 + 125X3 + 100X4 + 60X5 + 15X6. Subject to: Average search time: 10X1 + 20X2 + 35X3 + 40X4 + 45X5 + 5X6, Binary values: X1, X2, X3, X4, X5, X6 = 0 or 1. In this model X1 = 1 means that company A is chosen, and X1 = 0 means that company A is not chosen. Similarly, X2, X3, X4, X5, and X6 indicate whether or not companies B, C, D, E, and F are to be chosen or not, respectively.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
104
(b) The results are shown in the table below. As expected, the more the time limit T increases, the more search engine companies are added to the solution. For T >= 155 seconds, all of the companies will be in the optimal solution. T 100 130 150
A 0 1 1
B 1 0 1
C 1 1 1
D 1 1 1
E 0 1 1
F 1 0 0
Hits 280 310 350
9.3 (a) Let Y1, Y2, Y3, Y4, Y5, and Y6 be binary variables each representing whether or not we place an ATM machine in Arlington, Belmont, Cambridge, Lexington, Concord, and Winchester, respectively. For instance, Y1 = 1 means that we will place an ATM machine in Arlington. Let Xij represent whether we establish a connection between cities i and j, for all of the cities. For instance, X12 = 1 means that a connection between Arlington and Belmont will be established. Using these variables, we formulate the following discrete optimization model. Min Y1 + Y2 + Y3 + Y4 + Y5 + Y6. Subject to: Arlington is connected: X11 + X12 + X13 + X14 + X15 + X16 >= 1 – Y1, Belmont is connected: X21 + X22 + X23 + X24 + X25 + X26 >= 1 – Y2, Cambridge is connected: X31 + X32 + X33 + X34 + X35 + X36 >= 1 – Y3, Lexington is connected: X41 + X42 + X43 + X44 + X45 + X46 >= 1 – Y4, Concord is connected: X51 + X52 + X53 + X54 + X55 + X56 >= 1 – Y5, Winchester is connected: X61 + X62 + X63 + X64 + X65 + X66 >= 1 – Y6, Arlington distance: 5X12 + 10X13 + 15X14 + 20X15 + 15X16 <= 10(1 – Y1), Belmont distance: 5X21 + 8X23 + 10X24 + 15X25 + 12X26 <= 10(1 – Y2), Cambridge distance: 10X31 + 8X32 + 15X34 + 20X35 + 10X36 <= 10(1 – Y3), Lexington distance: 15X41 + 10X42 + 15X43 + 10X45 + 12X46 <= 10(1 – Y4), Concord distance: 20X51 + 15X52 + 20X53 + 10X54 + 12X56 <= 10(1 – Y5), Winchester distance: 15X61 + 12X62 + 10X63 + 12X64 + 12X65 <= 10(1 – Y6), Logical constraints: Yj >= Xij, for all i, j = 1, …, 6, Binary variables Yi, Xj = 0 or 1, for all i, j = 1, …, 6. (b) An optimal solution is to place two ATM machines, one in Cambridge and the other in Concord. Another solution is to place the ATM machines in Cambridge and Lexington.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
105
9.4 (a) Let X1, …, X9 denote whether or not we choose each of the TV shows. For instance, X1 = 1 means that we choose Cheers. In addition, let T denote whether or not we schedule more than 3 violence shows. Using these variables, we obtain the following discrete optimization model. Max 6X1 + 10X2 + 9X3 + 4X4 + 5X5 + 2X6 + 6X7 + 7X8 + 8X9 – 4T. Subject to: Total shows: X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9 = 5, Public=violence: X3 + X6 + X7 + X9 = X2 + X3 + X4 + X6, Jake+LALaw: X3 + X4 >= X7, Dry shows: X7 + X9 <= 1, Comedy+drama: 2(X1 + X2 + X3 + X4 + X7) + 1 >= X1 + X5 + X6 + X8, Violence cost: T + 3 >= X2 + X3 + X4 + X6, Binary: X1, X2, X3, X4, X5, X6, X7, X8, X9, T = 0 or 1. (b) The optimal solution is to show Cheers, Dynasty, LA Law, Beaches, and Urban Action for Education, with total revenues of $40 millions. 9.5 (a) Let X1, X2, X3, and X4 represent the amount to be ordered from each of the four furniture companies, respectively. Let Y1, Y2, Y3, and Y4 be binary variables representing whether or not we place an order with each of the four furniture companies, respectively. For instance, Y1 = 1 means that we place an order with Carolina Woodworks. Using these variables, we obtain the following discrete optimization model. Min 2,500X1 + 2,450X2 + 2,510X3 + 2,470X4 + 10,000Y1 + 20,000Y2 + 13,000Y4. Subject to: Required sets: X1 + X2 + X3 + X4 = 2,000, CW bounds: Y1 <= X1 <= 1,000Y1, NM bounds: Y2 <= X2 <= 1,000Y2, AFD bounds: Y3 <= X3 <= 1,000Y3, LAC bounds: Y4 <= X4 <= 1,000Y4, Integer: X1, X2, X3, X4 >= 0 and integer, Binary: Y1, Y2, Y3, Y4 = 0 or 1. (b) The optimal solution is to order 1,200 furniture sets from Nashawtuc Millworks and 800 furniture sets from Lancaster Artisan Company. The cost of this solution is $4,949,000 (results may differ depending on the tolerance level). (c) We add four more variables: X5 and X6 to represent the furniture sets ordered from Delaware Mills and Y1 and Y2 representing whether or not we place an order with Delaware Mills. X5 represents an order between up to 1,000 sets and X6 represents an order between 1,000 and 1,500 sets. Using these variables, we obtain the following reviewed discrete optimization model. Min 2,500X1 + 2,450X2 + 2,510X3 + 2,470X4 + 2,530X5 + 2,430X6 + 10,000Y1 + 20,000Y2 + 13,000Y4 + 9,000Y5 + (7,000 + 100x1,000)Y6.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
106
Subject to: Required sets: X1 + X2 + X3 + X4 + X5 + X6= 2,000, CW bounds: Y1 <= X1 <= 1,000Y1, NM bounds: Y2 <= X2 <= 1,000Y2, AFD bounds: Y3 <= X3 <= 1,000Y3, LAC bounds: Y4 <= X4 <= 1,000Y4, DM1 bounds: Y5 <= X5 <= 1,000Y5, DM2 bounds: 1,000Y6 <= X6 <= 1,500Y6, Logical: Y5 + Y6 <= 1, Integer: X1, X2, X3, X4, X5, X6 >= 0 and integer, Binary: Y1, Y2, Y3, Y4, Y5, Y6 = 0 or 1. The optimal solution is the same as before. 9.6
Let A1, B1, C1, D1, E1, A2, B2, C2, D2, E2, A3, B3, C3, D3, and E3 represent the amounts to be ordered for each module and engine for each year, respectively. Using these variables, we obtain the following discrete optimization problem: Min 0.7A1 + 2.5B1 + 6.0C1 + 1.3D1 + 9.0E1 + 0.6A2 + 2.2B2 + 5.5C2 + 1.1D2 + 8.5E2 + 0.5A3 + 2.0B3 + 5.0C3 + 1.0D3 + 7.8E3 Subject to: Inventory A1: A1 + E1 >= 5, Inventory B1: B1 + E1 >= 4, Inventory C1: C1 + E1 >= 4, Inventory D1: D1 + E1 >= 2, Inventory E1: E1 >= 1, Inventory A2: A1 + A2 + E1 + E2 >= 8, Inventory B2: B1 + B2 + E1 + E2 >= 6, Inventory C2: C1 + C2 + E1 + E2 >= 6, Inventory D2: D1 + D2 + E1 + E2 >= 10, Inventory E2: E1 + E2 >= 1, Inventory A3: A1 + A2 + A3 + E1 + E2 + E3 >= 13, Inventory B3: B1 + B2 + B3 + E1 + E2 + E3 >= 12, Inventory C3: C1 + C2 + C3 + E1 + E2 + E3 >= 11, Inventory D3: D1 + D2 + D3 + E1 + E2 + E3 >= 12, Inventory E3: E1 + E2 + E3 >= 3, Integer: A1, B1, C1, D1, E1, A2, B2, C2, D2, E2, A3, B3, C3, D3, E3 >= 0 and integer. The optimal schedule is shown in the following table. The cost of this schedule is $98.9 millions.
Year 1 Year 2 Year 3
Engine modules and engines A B C 1 0 0 0 0 0 1 1 0
D 0 1 0
E 5 4 2
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
107
9.7 (a) Let W1, …, W12 be the amounts to be produced of the Warrior model for each month. Let C1, …, C12 be the amounts to be produced of the Chomper model for each month. To control the inventory levels of the Warrior and Chomper models, respectively, we use the variables IWi and ICi, for i =1, …, 12. To determine what to produce each month, we use the binary variables Xi and Yi, for i =1, …, 12. For instance Xi = 1 indicates that we will produce the Warrior model. Finally, we use the variables Si, for i =1, …, 12, to indicate whether or not we switch production in a given month. We put together all of these variables in the following discrete optimization model. Min 7000(W1 + … + W6) + 7700(W7 + … + W12) + 6000(C1 + … + C6) + 6600(C7 + … + C12) + 700(IW1 + … + IW12) + 600(IC1 + … + IC12) + 1500(S1 + … + S12). Subject to: Warrior inventory: Wi + IWi-1 – IWi = DWi, i = 1, …, 12, Chomper inventory: Ci + ICi-1 – ICi = DCi, i = 1, …, 12, Either model: Xi + Yi <= 1, i = 1, …, 12, Warrior capacity: Xi <= Wi <= 100Xi, i = 1, …, 12, Chomper capacity: Yi <= Ci <= 110Yi, i = 1, …, 12, Switching 1: Xi-1 + Yi – Si <= 1, i = 1, …, 12, Switching 2: Yi-1 + Xi – Si <= 1, i = 1, …, 12, Binary: Xi, Yi, Si = 0 or 1, i = 1, …, 12, Integer: Wi, Ci, IWi, ICi >= 0 and integer, i = 1, …, 12. In this model we have IW0 =IC0 = 50, X0 = 1, and Y0 = 0. The variables DWi and DCi represent the demand for the Warrior and Chomper models, respectively, for each month. (b) The optimal production schedule is shown in the table below. The total cost of this schedule is $6,283,800,000 (results may differ depending on the tolerance level).
Month January February March April May June July August September October November December
Production Schedule W C 23 0 0 83 71 0 0 74 63 0 0 85 73 0 0 85 78 0 0 95 81 0 0 46
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
108
9.8 (a) Let F1, …, F20 be binary variables indicating whether or not Linda takes any of the 20 courses during the fall term. For instance, F1 = 1 means that Linda takes course number 1 in the fall. Similarly, let S1, …, S20 be binary variables indicating whether or not Linda takes any of the 20 courses during the spring term. Let OF1, …, OF20 and OS1, .., OS20 be binary constants indicating whether each of the classes is offered in the fall and spring , respectively. Finally, let I1, .., I20 be the interest level assigned by Linda to each of the 20 courses. Consider the following discrete optimization model. Max I1(F1 + S1) + … + I20(F20 + S20). Subject to: Fall course offering: F1 <= OF1, …, F20 <= OF20, Spring course offering: S1 <= OS1, …, S20 <= OS20, Fall term maximum: F1 + … + F20 <= 5, Spring term maximum: S1 + … + S20 <= 5, Prerequisites course 5: S5 <= F4, Prerequisites course 7: S7 <= F2, S7 <= F6, Prerequisites course 8: S8 <= F1, S8 <= F3 + S3, Prerequisites course 9: S9 <= F1, Prerequisites course 11: S11 <= F1, S11 <= F10, Prerequisites course 13: S13 <= S9, S13 <= F12, Prerequisites course 14: S14 <= F3 + S3, Prerequisites course 16: S16 <= F15, Prerequisites course 17: S17 <= F4, Prerequisites course 18: S18 <= F10, S18 <= F12, S18 <= S17, Prerequisites course 19: F19 <= F4, Fall term requirement: F1 + F2 + F3 + F6 + F20 >= 1, Financial or options: S14 <= (1 – S8), Marketing: F12 + S13 >= 1, O.M.: F10 + S11 >= 1, Binary: F1, …, F20, S1, …, S20 = 0 or 1. The optimal course schedule is to take courses 1, 2, 10, 12, and 20 during the fall term and courses 3, 8 , 9, 11, and 13 during the spring term. Linda would get 42 points of interest level by taking these courses. (b) The other optimal schedule is to take courses 1, 2, 10, 12, and 20 during the fall term and courses 3, 9, 11, 13, and 14 during the spring term. Linda would also get 42 points of interest level by taking these courses. 9.9 (a) Let X1, …, X10 be as defined in this problem and let Y1, …, Y20 be binary variables indicating whether or not we include a company in the portfolio. For instance, Y1 = 1 indicates that we will use company 1 in the portfolio. Using these variables, we obtain the following nonlinear discrete optimization model.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual Min
Chapter 9
109
|X1 – 0.15| + | X2 – 0.05| + | X3 – 0.08| + | X4 – 0.11| + | X5 – 0.14| + | X6 – 0.09| + | X7 – 0.08| + | X8 – 0.08| + | X9 – 0.14| + |X10 – 0.08|.
Subject to: Number of companies: Fractions: Investment: Technology: Last month fractions:
Y1 + … + Y10 = 6, X1 + … + X10 = 1, X1 <= Y1, …, X10 <= Y10, 0.45 <= X1 + X2 + X5 + X7 + X10 <= 0.55, |X1 – 0.12| + | X2 – 0.08| + | X3 – 0.07| + | X4 – 0.14| + | X5 – 0.17| + | X6 – 0.06| + | X7 – 0.09| + | X8 – 0.04| + | X9 – 0.18| + |X10 – 0.05| <= 0.60, Binary: Y1, …, Y10 = 0 or 1, Non-negativity X1, …, X10 >= 0. (b) There might be more than one optimal portfolio. The following table shows two of them. For both portfolios the optimal difference is 0.58 (results may differ depending on the tolerance level).
Company Selected Fraction
Portfolio 1 1 2 1 0 0.28 0.00
3 0 0.00
4 1 0.13
5 1 0.17
6 1 0.11
7 0 0.00
8 1 0.10
9 1 0.20
10 0 0.00
Company Selected Fraction
Portfolio 2 1 2 1 0 0.38 0.00
3 1 0.08
4 1 0.11
5 1 0.17
6 1 0.09
7 0 0.00
8 0 0.00
9 1 0.17
10 0 0.00
IV
Answers to Chapter Cases
INTERNATIONAL INDUSTRIES, INC. (a) We use the binary variables Ii, Mi, and Si to indicate whether or not to invest, maintain, or sell division I, respectively, for i = 1, …, 50. We represent the net present values for each decision (invest, maintain, or sell) and for each division as NIi, NMi, and NSi, respectively, for i = 1, …, 50. Similarly, we represent the investments required for each decision (invest, maintain, or sell) and for each division as IIi, IMi, and ISi, respectively, for i = 1, …, 50. Finally, we represent the cash flow for next year for each decision (invest, maintain, or sell) and for each division as CIi, CMi, and CSi, respectively, for i = 1, …, 50. Using these variables, we obtain the following discrete optimization model.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
110
Max NI1I1 + NM1M1 + NS1S1 + … + NI50I50 + NM50M50 + NS50S50. Subject to: Cash-flow: II1I1 + IM1M1 + IS1S1 + … + II50I50 + IM50M50 + IS50S50 <= CI1I1 + CM1M1 + CS1S1 + … + CI50I50 + CM50M50 + CS50S50 Constraint (a): S1 = I2, S1 = S4, S1 = S3, Constraint (b): I6 = I7, Constraint (c): S3 + S4 + S5 + M6 + S7 + S9 <= 1, Constraint (d): S2 + I4 + M6 + S6 + S8 + S12 + I14 <= 1, Constraint (e): I24 <= I28, Constraint (f): M30 <= I32 + M32, Make a decision: Ii + Mi + Si = 1, i = 1, …, 50, Binary: I1, …, I50, M1, …, M50, S1, …, S50 = 0 or 1. The optimal set of choices for each division is shown in the table below. The net present value of optimal choices is $33,689 millions. Division Number Choice 1 Maintain 2 Sell 3 Invest 4 Maintain 5 Maintain 6 Invest 7 Invest 8 Maintain 9 Maintain 10 Sell 11 Sell 12 Maintain 13 Invest 14 Sell 15 Maintain 16 Maintain 17 Invest 18 Invest 19 Invest 20 Sell 21 Sell 22 Invest 23 Maintain 24 Sell 25 Sell 26 Invest 27 Invest 28 Sell 29 Invest 30 Invest 31 Sell 32 Sell 33 Sell
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
111
Sell Maintain Sell Invest Invest Maintain Invest Sell Invest Maintain Invest Invest Maintain Invest Sell Maintain Sell
(b) If constraints (a) to (f) are removed, then the optimal NPV will increase to $39,278 millions. This represents a penalty of $5,589 millions for imposing the restrictions. (c) To find the second best and the third best solutions you can impose an additional constraint on the total NPV. For instance, we know that the optimal NPV is $33,689 millions. If we impose the constraint NI1I1 + NM1M1 + NS1S1 + … + NI50I50 + NM50M50 + NS50S50 <= $32,000 (or any other bound close to the optimal objective value), we will force the computer to find a solution with an objective value close to the original optimal solution. By decreasing even more the right-hand side of this constraint and re-solving the model, we can find other good solutions.
SUPPLY CHAIN MANAGEMENT AT DELLMAR, INC. (a) To describe our model, we index the months as follows: 0 corresponds to March, 1 corresponds to April, and 2 corresponds to May. We also use the following variables and parameters: HOi: Amount produced at New Hampshire and shipped to Ohio, for months i = 1, 2. HJi: Amount produced at New Hampshire and shipped to New Jersey, for months i = 1, 2. OWi: Amount shipped from Ohio to West Coast, for months i = 1, 2. OMi: Amount shipped from Ohio to Midwest, for months i = 1, 2. JMi: Amount shipped from New Jersey to Midwest, for months i = 1, 2. JEi: Amount shipped from New Jersey to East Coast, for months i = 1, 2. IOi: Inventory at Ohio center, for months i = 0, 1, 2. IJi: Inventory at New Jersey center, for months i = 0, 1, 2. IWi: Inventory at West Coast center, for months i = 0, 1, 2. IMi: Inventory at Midwest center, for months i = 0, 1, 2. Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
112
IEi: Inventory at East Coast center, for months i = 0, 1, 2. THOi: Whether or not to ship from New Hampshire to Ohio, for months i = 1, 2. THJi: Whether or not to ship from New Hampshire to New Jersey, for months i = 1, 2. TOWi: Whether or not to ship from Ohio to West Coast, for months i = 1, 2. TOMi: Whether or not to ship from Ohio to Midwest, for months i = 1, 2. TJMi: Whether or not to ship from New Jersey to Midwest, for months i = 1, 2. TJEi: Whether or not to ship from New Jersey to East Coast, for months i = 1, 2. DWi: Demand at West Coast center, for months i = 1, 2. DMi: Demand at Midwest center, for months i = 1, 2. DEi: Demand at East Coast center, for months i = 1, 2. Using these variables, we have the following discrete optimization model. Min 10(OW1 + OW2 + OM1 + OM2 + JM1 + JM2 + JE1 + JE2 + HO1 + HO2 + HJ1 + HJ2) + 5000(THO1 + THO2) + 4000(THJ1 + THJ2) + 4000(TOW1 + TOW2) + 3000(TOM1 + TOM2) + 5000(TJM1 + TJM2) + 3000(TJE1 + TJE2) + 5(IO1 + IO2 + IJ1 + IJ2) + 10(IW1 + IW2 + IM1 + IM2 + IE1 + IE2). Subject to: Inventory Ohio: HOi + IOi-1 – IOi = OWi + OMi, i = 1,2, Inventory New Jersey: HJi + IJi-1 – IJi = JWi + JMi, i = 1,2, Inventory West Coast: OWi + IWi-1 – IWi = DWi, i = 1,2, Inventory Midwest: OMi + JMi + IMi-1 – IMi = DMi, i = 1,2, Inventory East Coast: JEi + IEi-1 – IEi = DEi, i = 1,2, Production capacity: HOi + HJi <= 50,000, i = 1,2, Shipping decision 1: THOi <= HOi <= 50,000 THOi, i = 1,2, Shipping decision 2: THJi <= HJi <= 50,000 THJi, i = 1,2, Shipping decision 3: TOWi <= OWi <= 50,000 TOWi, i = 1,2, Shipping decision 4: TOMi <= OMi <= 50,000 TOMi, i = 1,2, Shipping decision 5: TJMi <= JMi <= 50,000 TJMi, i = 1,2, Shipping decision 6: TJEi <= JEi <= 50,000 TJEi, i = 1,2, Binary: THOi,THJi,TOWi,TOMi,TJMi,TJEi = 0 or 1, i = 1,2, Integer: HOi,HJi,OWi,OMi,JMi,JEi,IOi,IJi,IWi,IMi,IEi >= 0 and integer, i = 1,2. (b) If optimized, the average monthly cost in April and May is $1,230,000. The optimal production and shipping schedule, as well as the optimal inventory levels are shown in the tables below.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
113
Month 1 2
Production and Shipping HO HJ 32000 18000 0 50000
OW 18000 20000
OM 14000 0
JM 0 25000
Month 0 1 2
Inventory IO 20000 20000 0
IW 2000 0 0
IM 1000 0 0
IE 2000 0 0
IJ 10000 5000 0
JE 23000 30000
(c) If production is increased by 10%, then the average monthly cost decreases to $1,217,500 per month by using the optimal solution of the revised model. This represents savings of $12,500 per month. (d) The average monthly costs for each scenario are shown in the table below. NF means nor feasible.
Current capacity 10% increase
Minimum Inventory Level 0 500 1000 $1,230,000 NF NF $1,217,500 $1,257,500 $1,297,500
(e) Based on the results from the previous items, it is not recommendable to increase capacity by 10% while keeping minimum inventory levels at zero. This is because the cost of such extra capacity exceeds the amount of savings obtained by the additional capacity ($55,000 > $12,500). If minimum inventory levels of 500 or 1000 units per distribution center are necessary, then production needs to increase by 10%, otherwise it will be impossible to satisfy the minimum level requirements.
THE NATIONAL BASKETBALL DREAM TEAM (a) Let X1, …, X20 represent whether or not we choose any of the players. For instance, X1 = 1 means that we choose player 1 to be part of the team. Similarly, we use the parameters Pi, Ri, Ai, Di, and Hi to denote the points, rebounds, assists, defensive ability, and height of the i-th player, for i = 1, …, 20. Using these variables and parameters, we obtain the following discrete optimization model.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual Max Subject to: Points: Rebounds: Assists: Defense: Height: Play makers: Shooting guards: Forwards: Centers: NCAA: Logical 5 & 9: Logical 2 and 19: Bulls: Binary:
Chapter 9
114
P1X1 + … + P20X20, P1X1 + … + P20X20 >= 216, R1X1 + … + R20X20 >= 84, A1X1 + … + A20X20 >= 72, D1X1 + … + D20X20 >= 102, H1X1 + … + H20X20 >= 948, X1 + … + X5 >= 3, X4 + … + X11 >= 4, X9 + … + X16 >= 4, X16 + … + X20 >= 3, X4 + X8 + X15 + X20 >= 2, X5 <= 1 – X9, X2 = X19, X1 + X7 + X12 + X16 <= 3, X1, … , X20 = 0 or 1.
The optimal solution is to choose players 2, 3, 4, 5, 7, 10, 12, 13, 15, 17, 18, and 19. The average points per game among the players of this team are 22. (b) There is no feasible solution under the new set of constraints. (c) By re-solving the model for 14 players instead of just 12, we obtain an optimal team with almost the same objective value as before. This team contains the players 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 15, 17, 18, and 19. Therefore, the alternate players might be 6 and 11.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Chapter 9
102
Chapter 9 I
Chapter Outline
9.1
Formulating a Management Problem as a Discrete Optimization Model • Integer optimization models • Binary optimization models • Mixed-integer optimization models
9.2
Graphical Analysis of Discrete Optimization Models in Two variables
9.3
Computer Solution of Discrete Optimization Problems • General principles on the solvability of a discrete optimization model • Using spreadsheet software to solve a discrete optimization problem
9.4
The Branch-and-Bound Method for Solving a Discrete Optimization Model • Discussion on how this method is used by spreadsheet software to solve binary optimization models
II
Teaching Tips
1.
It is interesting to show in class how difficult a discrete model can be even for a small set of decision variables (and even for binary variables). You can show how the number of feasible solutions grows at an exponential rate according to the number of variables.
2.
Some of the problems and exercises in this chapter can be also modeled as network problems. To develop student intuition in this chapter, it helps to present the alternative formulation in of graphs or networks.
3.
The discussion on solving discrete optimization models can be enhanced by mentioning new optimization techniques such as genetic algorithms, neural networks, taboo search, etc. In particular, it is not difficult to adapt the capital budgeting problem (Example 9.2) to be solved by genetic algorithms. Keep in mind that the most recent versions of Solver include the evolutionary/genetic search optimization techniques.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual III
Chapter 9
103
Answers to Chapter Exercises
9.1 (a) Not shown. (b) The new optimal strategy is to relocate to London, Madrid, and Hamburg, for a total cost of $56 million. The optimal fractions of service requests are shown in the following table (results may differ depending on the tolerance level):
London Madrid Paris Hamburg Rome
London 1.00 0.00 0.00 0.25 0.00
Fraction of service requests Madrid Paris Hamburg 0.00 0.00 0.00 0.00 0.00 1.00 0.00 0.00 1.00 0.75 0.00 0.00 0.25 0.00 0.75
Rome 0.00 0.00 0.00 0.00 0.00
(c) The results are shown in the table below. Notice that for an average shipping time across countries of 0.6, the model is no longer feasible (results may differ depending on the tolerance level).
Average shipping time 0.8 0.7 0.6
London 1 1
Optimal relocation Madrid Paris Hamburg 1 0 1 0 0 1 Infeasible
Rome 0 1
Total cost $56 $57
(d) In addition to changing the 1.1 value by 1 in the constraint corresponding to total shipping time, we replace the objective function by this function: Max 10y1 + 15y2 + 22y3 + 21y4 + 16y5 + 2(1-y1) + 2(1-y2) + 2(1-y3) + 3y4 + 3y5. The optimal relocation strategy is to close the centers in London and Madrid, and open a new one in Rome. The total cost of this strategy is $45 millions (results may differ depending on the tolerance level). 9.2 (a) Consider the following binary optimization model: Max 25X1 + 40X2 + 125X3 + 100X4 + 60X5 + 15X6. Subject to: Average search time: 10X1 + 20X2 + 35X3 + 40X4 + 45X5 + 5X6, Binary values: X1, X2, X3, X4, X5, X6 = 0 or 1. In this model X1 = 1 means that company A is chosen, and X1 = 0 means that company A is not chosen. Similarly, X2, X3, X4, X5, and X6 indicate whether or not companies B, C, D, E, and F are to be chosen or not, respectively.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
104
(b) The results are shown in the table below. As expected, the more the time limit T increases, the more search engine companies are added to the solution. For T >= 155 seconds, all of the companies will be in the optimal solution. T 100 130 150
A 0 1 1
B 1 0 1
C 1 1 1
D 1 1 1
E 0 1 1
F 1 0 0
Hits 280 310 350
9.3 (a) Let Y1, Y2, Y3, Y4, Y5, and Y6 be binary variables each representing whether or not we place an ATM machine in Arlington, Belmont, Cambridge, Lexington, Concord, and Winchester, respectively. For instance, Y1 = 1 means that we will place an ATM machine in Arlington. Let Xij represent whether we establish a connection between cities i and j, for all of the cities. For instance, X12 = 1 means that a connection between Arlington and Belmont will be established. Using these variables, we formulate the following discrete optimization model. Min Y1 + Y2 + Y3 + Y4 + Y5 + Y6. Subject to: Arlington is connected: X11 + X12 + X13 + X14 + X15 + X16 >= 1 – Y1, Belmont is connected: X21 + X22 + X23 + X24 + X25 + X26 >= 1 – Y2, Cambridge is connected: X31 + X32 + X33 + X34 + X35 + X36 >= 1 – Y3, Lexington is connected: X41 + X42 + X43 + X44 + X45 + X46 >= 1 – Y4, Concord is connected: X51 + X52 + X53 + X54 + X55 + X56 >= 1 – Y5, Winchester is connected: X61 + X62 + X63 + X64 + X65 + X66 >= 1 – Y6, Arlington distance: 5X12 + 10X13 + 15X14 + 20X15 + 15X16 <= 10(1 – Y1), Belmont distance: 5X21 + 8X23 + 10X24 + 15X25 + 12X26 <= 10(1 – Y2), Cambridge distance: 10X31 + 8X32 + 15X34 + 20X35 + 10X36 <= 10(1 – Y3), Lexington distance: 15X41 + 10X42 + 15X43 + 10X45 + 12X46 <= 10(1 – Y4), Concord distance: 20X51 + 15X52 + 20X53 + 10X54 + 12X56 <= 10(1 – Y5), Winchester distance: 15X61 + 12X62 + 10X63 + 12X64 + 12X65 <= 10(1 – Y6), Logical constraints: Yj >= Xij, for all i, j = 1, …, 6, Binary variables Yi, Xj = 0 or 1, for all i, j = 1, …, 6. (b) An optimal solution is to place two ATM machines, one in Cambridge and the other in Concord. Another solution is to place the ATM machines in Cambridge and Lexington.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
105
9.4 (a) Let X1, …, X9 denote whether or not we choose each of the TV shows. For instance, X1 = 1 means that we choose Cheers. In addition, let T denote whether or not we schedule more than 3 violence shows. Using these variables, we obtain the following discrete optimization model. Max 6X1 + 10X2 + 9X3 + 4X4 + 5X5 + 2X6 + 6X7 + 7X8 + 8X9 – 4T. Subject to: Total shows: X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9 = 5, Public=violence: X3 + X6 + X7 + X9 = X2 + X3 + X4 + X6, Jake+LALaw: X3 + X4 >= X7, Dry shows: X7 + X9 <= 1, Comedy+drama: 2(X1 + X2 + X3 + X4 + X7) + 1 >= X1 + X5 + X6 + X8, Violence cost: T + 3 >= X2 + X3 + X4 + X6, Binary: X1, X2, X3, X4, X5, X6, X7, X8, X9, T = 0 or 1. (b) The optimal solution is to show Cheers, Dynasty, LA Law, Beaches, and Urban Action for Education, with total revenues of $40 millions. 9.5 (a) Let X1, X2, X3, and X4 represent the amount to be ordered from each of the four furniture companies, respectively. Let Y1, Y2, Y3, and Y4 be binary variables representing whether or not we place an order with each of the four furniture companies, respectively. For instance, Y1 = 1 means that we place an order with Carolina Woodworks. Using these variables, we obtain the following discrete optimization model. Min 2,500X1 + 2,450X2 + 2,510X3 + 2,470X4 + 10,000Y1 + 20,000Y2 + 13,000Y4. Subject to: Required sets: X1 + X2 + X3 + X4 = 2,000, CW bounds: Y1 <= X1 <= 1,000Y1, NM bounds: Y2 <= X2 <= 1,000Y2, AFD bounds: Y3 <= X3 <= 1,000Y3, LAC bounds: Y4 <= X4 <= 1,000Y4, Integer: X1, X2, X3, X4 >= 0 and integer, Binary: Y1, Y2, Y3, Y4 = 0 or 1. (b) The optimal solution is to order 1,200 furniture sets from Nashawtuc Millworks and 800 furniture sets from Lancaster Artisan Company. The cost of this solution is $4,949,000 (results may differ depending on the tolerance level). (c) We add four more variables: X5 and X6 to represent the furniture sets ordered from Delaware Mills and Y1 and Y2 representing whether or not we place an order with Delaware Mills. X5 represents an order between up to 1,000 sets and X6 represents an order between 1,000 and 1,500 sets. Using these variables, we obtain the following reviewed discrete optimization model. Min 2,500X1 + 2,450X2 + 2,510X3 + 2,470X4 + 2,530X5 + 2,430X6 + 10,000Y1 + 20,000Y2 + 13,000Y4 + 9,000Y5 + (7,000 + 100x1,000)Y6.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
106
Subject to: Required sets: X1 + X2 + X3 + X4 + X5 + X6= 2,000, CW bounds: Y1 <= X1 <= 1,000Y1, NM bounds: Y2 <= X2 <= 1,000Y2, AFD bounds: Y3 <= X3 <= 1,000Y3, LAC bounds: Y4 <= X4 <= 1,000Y4, DM1 bounds: Y5 <= X5 <= 1,000Y5, DM2 bounds: 1,000Y6 <= X6 <= 1,500Y6, Logical: Y5 + Y6 <= 1, Integer: X1, X2, X3, X4, X5, X6 >= 0 and integer, Binary: Y1, Y2, Y3, Y4, Y5, Y6 = 0 or 1. The optimal solution is the same as before. 9.6
Let A1, B1, C1, D1, E1, A2, B2, C2, D2, E2, A3, B3, C3, D3, and E3 represent the amounts to be ordered for each module and engine for each year, respectively. Using these variables, we obtain the following discrete optimization problem: Min 0.7A1 + 2.5B1 + 6.0C1 + 1.3D1 + 9.0E1 + 0.6A2 + 2.2B2 + 5.5C2 + 1.1D2 + 8.5E2 + 0.5A3 + 2.0B3 + 5.0C3 + 1.0D3 + 7.8E3 Subject to: Inventory A1: A1 + E1 >= 5, Inventory B1: B1 + E1 >= 4, Inventory C1: C1 + E1 >= 4, Inventory D1: D1 + E1 >= 2, Inventory E1: E1 >= 1, Inventory A2: A1 + A2 + E1 + E2 >= 8, Inventory B2: B1 + B2 + E1 + E2 >= 6, Inventory C2: C1 + C2 + E1 + E2 >= 6, Inventory D2: D1 + D2 + E1 + E2 >= 10, Inventory E2: E1 + E2 >= 1, Inventory A3: A1 + A2 + A3 + E1 + E2 + E3 >= 13, Inventory B3: B1 + B2 + B3 + E1 + E2 + E3 >= 12, Inventory C3: C1 + C2 + C3 + E1 + E2 + E3 >= 11, Inventory D3: D1 + D2 + D3 + E1 + E2 + E3 >= 12, Inventory E3: E1 + E2 + E3 >= 3, Integer: A1, B1, C1, D1, E1, A2, B2, C2, D2, E2, A3, B3, C3, D3, E3 >= 0 and integer. The optimal schedule is shown in the following table. The cost of this schedule is $98.9 millions.
Year 1 Year 2 Year 3
Engine modules and engines A B C 1 0 0 0 0 0 1 1 0
D 0 1 0
E 5 4 2
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
107
9.7 (a) Let W1, …, W12 be the amounts to be produced of the Warrior model for each month. Let C1, …, C12 be the amounts to be produced of the Chomper model for each month. To control the inventory levels of the Warrior and Chomper models, respectively, we use the variables IWi and ICi, for i =1, …, 12. To determine what to produce each month, we use the binary variables Xi and Yi, for i =1, …, 12. For instance Xi = 1 indicates that we will produce the Warrior model. Finally, we use the variables Si, for i =1, …, 12, to indicate whether or not we switch production in a given month. We put together all of these variables in the following discrete optimization model. Min 7000(W1 + … + W6) + 7700(W7 + … + W12) + 6000(C1 + … + C6) + 6600(C7 + … + C12) + 700(IW1 + … + IW12) + 600(IC1 + … + IC12) + 1500(S1 + … + S12). Subject to: Warrior inventory: Wi + IWi-1 – IWi = DWi, i = 1, …, 12, Chomper inventory: Ci + ICi-1 – ICi = DCi, i = 1, …, 12, Either model: Xi + Yi <= 1, i = 1, …, 12, Warrior capacity: Xi <= Wi <= 100Xi, i = 1, …, 12, Chomper capacity: Yi <= Ci <= 110Yi, i = 1, …, 12, Switching 1: Xi-1 + Yi – Si <= 1, i = 1, …, 12, Switching 2: Yi-1 + Xi – Si <= 1, i = 1, …, 12, Binary: Xi, Yi, Si = 0 or 1, i = 1, …, 12, Integer: Wi, Ci, IWi, ICi >= 0 and integer, i = 1, …, 12. In this model we have IW0 =IC0 = 50, X0 = 1, and Y0 = 0. The variables DWi and DCi represent the demand for the Warrior and Chomper models, respectively, for each month. (b) The optimal production schedule is shown in the table below. The total cost of this schedule is $6,283,800,000 (results may differ depending on the tolerance level).
Month January February March April May June July August September October November December
Production Schedule W C 23 0 0 83 71 0 0 74 63 0 0 85 73 0 0 85 78 0 0 95 81 0 0 46
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
108
9.8 (a) Let F1, …, F20 be binary variables indicating whether or not Linda takes any of the 20 courses during the fall term. For instance, F1 = 1 means that Linda takes course number 1 in the fall. Similarly, let S1, …, S20 be binary variables indicating whether or not Linda takes any of the 20 courses during the spring term. Let OF1, …, OF20 and OS1, .., OS20 be binary constants indicating whether each of the classes is offered in the fall and spring , respectively. Finally, let I1, .., I20 be the interest level assigned by Linda to each of the 20 courses. Consider the following discrete optimization model. Max I1(F1 + S1) + … + I20(F20 + S20). Subject to: Fall course offering: F1 <= OF1, …, F20 <= OF20, Spring course offering: S1 <= OS1, …, S20 <= OS20, Fall term maximum: F1 + … + F20 <= 5, Spring term maximum: S1 + … + S20 <= 5, Prerequisites course 5: S5 <= F4, Prerequisites course 7: S7 <= F2, S7 <= F6, Prerequisites course 8: S8 <= F1, S8 <= F3 + S3, Prerequisites course 9: S9 <= F1, Prerequisites course 11: S11 <= F1, S11 <= F10, Prerequisites course 13: S13 <= S9, S13 <= F12, Prerequisites course 14: S14 <= F3 + S3, Prerequisites course 16: S16 <= F15, Prerequisites course 17: S17 <= F4, Prerequisites course 18: S18 <= F10, S18 <= F12, S18 <= S17, Prerequisites course 19: F19 <= F4, Fall term requirement: F1 + F2 + F3 + F6 + F20 >= 1, Financial or options: S14 <= (1 – S8), Marketing: F12 + S13 >= 1, O.M.: F10 + S11 >= 1, Binary: F1, …, F20, S1, …, S20 = 0 or 1. The optimal course schedule is to take courses 1, 2, 10, 12, and 20 during the fall term and courses 3, 8 , 9, 11, and 13 during the spring term. Linda would get 42 points of interest level by taking these courses. (b) The other optimal schedule is to take courses 1, 2, 10, 12, and 20 during the fall term and courses 3, 9, 11, 13, and 14 during the spring term. Linda would also get 42 points of interest level by taking these courses. 9.9 (a) Let X1, …, X10 be as defined in this problem and let Y1, …, Y20 be binary variables indicating whether or not we include a company in the portfolio. For instance, Y1 = 1 indicates that we will use company 1 in the portfolio. Using these variables, we obtain the following nonlinear discrete optimization model.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual Min
Chapter 9
109
|X1 – 0.15| + | X2 – 0.05| + | X3 – 0.08| + | X4 – 0.11| + | X5 – 0.14| + | X6 – 0.09| + | X7 – 0.08| + | X8 – 0.08| + | X9 – 0.14| + |X10 – 0.08|.
Subject to: Number of companies: Fractions: Investment: Technology: Last month fractions:
Y1 + … + Y10 = 6, X1 + … + X10 = 1, X1 <= Y1, …, X10 <= Y10, 0.45 <= X1 + X2 + X5 + X7 + X10 <= 0.55, |X1 – 0.12| + | X2 – 0.08| + | X3 – 0.07| + | X4 – 0.14| + | X5 – 0.17| + | X6 – 0.06| + | X7 – 0.09| + | X8 – 0.04| + | X9 – 0.18| + |X10 – 0.05| <= 0.60, Binary: Y1, …, Y10 = 0 or 1, Non-negativity X1, …, X10 >= 0. (b) There might be more than one optimal portfolio. The following table shows two of them. For both portfolios the optimal difference is 0.58 (results may differ depending on the tolerance level).
Company Selected Fraction
Portfolio 1 1 2 1 0 0.28 0.00
3 0 0.00
4 1 0.13
5 1 0.17
6 1 0.11
7 0 0.00
8 1 0.10
9 1 0.20
10 0 0.00
Company Selected Fraction
Portfolio 2 1 2 1 0 0.38 0.00
3 1 0.08
4 1 0.11
5 1 0.17
6 1 0.09
7 0 0.00
8 0 0.00
9 1 0.17
10 0 0.00
IV
Answers to Chapter Cases
INTERNATIONAL INDUSTRIES, INC. (a) We use the binary variables Ii, Mi, and Si to indicate whether or not to invest, maintain, or sell division I, respectively, for i = 1, …, 50. We represent the net present values for each decision (invest, maintain, or sell) and for each division as NIi, NMi, and NSi, respectively, for i = 1, …, 50. Similarly, we represent the investments required for each decision (invest, maintain, or sell) and for each division as IIi, IMi, and ISi, respectively, for i = 1, …, 50. Finally, we represent the cash flow for next year for each decision (invest, maintain, or sell) and for each division as CIi, CMi, and CSi, respectively, for i = 1, …, 50. Using these variables, we obtain the following discrete optimization model.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
110
Max NI1I1 + NM1M1 + NS1S1 + … + NI50I50 + NM50M50 + NS50S50. Subject to: Cash-flow: II1I1 + IM1M1 + IS1S1 + … + II50I50 + IM50M50 + IS50S50 <= CI1I1 + CM1M1 + CS1S1 + … + CI50I50 + CM50M50 + CS50S50 Constraint (a): S1 = I2, S1 = S4, S1 = S3, Constraint (b): I6 = I7, Constraint (c): S3 + S4 + S5 + M6 + S7 + S9 <= 1, Constraint (d): S2 + I4 + M6 + S6 + S8 + S12 + I14 <= 1, Constraint (e): I24 <= I28, Constraint (f): M30 <= I32 + M32, Make a decision: Ii + Mi + Si = 1, i = 1, …, 50, Binary: I1, …, I50, M1, …, M50, S1, …, S50 = 0 or 1. The optimal set of choices for each division is shown in the table below. The net present value of optimal choices is $33,689 millions. Division Number Choice 1 Maintain 2 Sell 3 Invest 4 Maintain 5 Maintain 6 Invest 7 Invest 8 Maintain 9 Maintain 10 Sell 11 Sell 12 Maintain 13 Invest 14 Sell 15 Maintain 16 Maintain 17 Invest 18 Invest 19 Invest 20 Sell 21 Sell 22 Invest 23 Maintain 24 Sell 25 Sell 26 Invest 27 Invest 28 Sell 29 Invest 30 Invest 31 Sell 32 Sell 33 Sell
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
111
Sell Maintain Sell Invest Invest Maintain Invest Sell Invest Maintain Invest Invest Maintain Invest Sell Maintain Sell
(b) If constraints (a) to (f) are removed, then the optimal NPV will increase to $39,278 millions. This represents a penalty of $5,589 millions for imposing the restrictions. (c) To find the second best and the third best solutions you can impose an additional constraint on the total NPV. For instance, we know that the optimal NPV is $33,689 millions. If we impose the constraint NI1I1 + NM1M1 + NS1S1 + … + NI50I50 + NM50M50 + NS50S50 <= $32,000 (or any other bound close to the optimal objective value), we will force the computer to find a solution with an objective value close to the original optimal solution. By decreasing even more the right-hand side of this constraint and re-solving the model, we can find other good solutions.
SUPPLY CHAIN MANAGEMENT AT DELLMAR, INC. (a) To describe our model, we index the months as follows: 0 corresponds to March, 1 corresponds to April, and 2 corresponds to May. We also use the following variables and parameters: HOi: Amount produced at New Hampshire and shipped to Ohio, for months i = 1, 2. HJi: Amount produced at New Hampshire and shipped to New Jersey, for months i = 1, 2. OWi: Amount shipped from Ohio to West Coast, for months i = 1, 2. OMi: Amount shipped from Ohio to Midwest, for months i = 1, 2. JMi: Amount shipped from New Jersey to Midwest, for months i = 1, 2. JEi: Amount shipped from New Jersey to East Coast, for months i = 1, 2. IOi: Inventory at Ohio center, for months i = 0, 1, 2. IJi: Inventory at New Jersey center, for months i = 0, 1, 2. IWi: Inventory at West Coast center, for months i = 0, 1, 2. IMi: Inventory at Midwest center, for months i = 0, 1, 2. Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
112
IEi: Inventory at East Coast center, for months i = 0, 1, 2. THOi: Whether or not to ship from New Hampshire to Ohio, for months i = 1, 2. THJi: Whether or not to ship from New Hampshire to New Jersey, for months i = 1, 2. TOWi: Whether or not to ship from Ohio to West Coast, for months i = 1, 2. TOMi: Whether or not to ship from Ohio to Midwest, for months i = 1, 2. TJMi: Whether or not to ship from New Jersey to Midwest, for months i = 1, 2. TJEi: Whether or not to ship from New Jersey to East Coast, for months i = 1, 2. DWi: Demand at West Coast center, for months i = 1, 2. DMi: Demand at Midwest center, for months i = 1, 2. DEi: Demand at East Coast center, for months i = 1, 2. Using these variables, we have the following discrete optimization model. Min 10(OW1 + OW2 + OM1 + OM2 + JM1 + JM2 + JE1 + JE2 + HO1 + HO2 + HJ1 + HJ2) + 5000(THO1 + THO2) + 4000(THJ1 + THJ2) + 4000(TOW1 + TOW2) + 3000(TOM1 + TOM2) + 5000(TJM1 + TJM2) + 3000(TJE1 + TJE2) + 5(IO1 + IO2 + IJ1 + IJ2) + 10(IW1 + IW2 + IM1 + IM2 + IE1 + IE2). Subject to: Inventory Ohio: HOi + IOi-1 – IOi = OWi + OMi, i = 1,2, Inventory New Jersey: HJi + IJi-1 – IJi = JWi + JMi, i = 1,2, Inventory West Coast: OWi + IWi-1 – IWi = DWi, i = 1,2, Inventory Midwest: OMi + JMi + IMi-1 – IMi = DMi, i = 1,2, Inventory East Coast: JEi + IEi-1 – IEi = DEi, i = 1,2, Production capacity: HOi + HJi <= 50,000, i = 1,2, Shipping decision 1: THOi <= HOi <= 50,000 THOi, i = 1,2, Shipping decision 2: THJi <= HJi <= 50,000 THJi, i = 1,2, Shipping decision 3: TOWi <= OWi <= 50,000 TOWi, i = 1,2, Shipping decision 4: TOMi <= OMi <= 50,000 TOMi, i = 1,2, Shipping decision 5: TJMi <= JMi <= 50,000 TJMi, i = 1,2, Shipping decision 6: TJEi <= JEi <= 50,000 TJEi, i = 1,2, Binary: THOi,THJi,TOWi,TOMi,TJMi,TJEi = 0 or 1, i = 1,2, Integer: HOi,HJi,OWi,OMi,JMi,JEi,IOi,IJi,IWi,IMi,IEi >= 0 and integer, i = 1,2. (b) If optimized, the average monthly cost in April and May is $1,230,000. The optimal production and shipping schedule, as well as the optimal inventory levels are shown in the tables below.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual
Chapter 9
113
Month 1 2
Production and Shipping HO HJ 32000 18000 0 50000
OW 18000 20000
OM 14000 0
JM 0 25000
Month 0 1 2
Inventory IO 20000 20000 0
IW 2000 0 0
IM 1000 0 0
IE 2000 0 0
IJ 10000 5000 0
JE 23000 30000
(c) If production is increased by 10%, then the average monthly cost decreases to $1,217,500 per month by using the optimal solution of the revised model. This represents savings of $12,500 per month. (d) The average monthly costs for each scenario are shown in the table below. NF means nor feasible.
Current capacity 10% increase
Minimum Inventory Level 0 500 1000 $1,230,000 NF NF $1,217,500 $1,257,500 $1,297,500
(e) Based on the results from the previous items, it is not recommendable to increase capacity by 10% while keeping minimum inventory levels at zero. This is because the cost of such extra capacity exceeds the amount of savings obtained by the additional capacity ($55,000 > $12,500). If minimum inventory levels of 500 or 1000 units per distribution center are necessary, then production needs to increase by 10%, otherwise it will be impossible to satisfy the minimum level requirements.
THE NATIONAL BASKETBALL DREAM TEAM (a) Let X1, …, X20 represent whether or not we choose any of the players. For instance, X1 = 1 means that we choose player 1 to be part of the team. Similarly, we use the parameters Pi, Ri, Ai, Di, and Hi to denote the points, rebounds, assists, defensive ability, and height of the i-th player, for i = 1, …, 20. Using these variables and parameters, we obtain the following discrete optimization model.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Instructor’s Manual Max Subject to: Points: Rebounds: Assists: Defense: Height: Play makers: Shooting guards: Forwards: Centers: NCAA: Logical 5 & 9: Logical 2 and 19: Bulls: Binary:
Chapter 9
114
P1X1 + … + P20X20, P1X1 + … + P20X20 >= 216, R1X1 + … + R20X20 >= 84, A1X1 + … + A20X20 >= 72, D1X1 + … + D20X20 >= 102, H1X1 + … + H20X20 >= 948, X1 + … + X5 >= 3, X4 + … + X11 >= 4, X9 + … + X16 >= 4, X16 + … + X20 >= 3, X4 + X8 + X15 + X20 >= 2, X5 <= 1 – X9, X2 = X19, X1 + X7 + X12 + X16 <= 3, X1, … , X20 = 0 or 1.
The optimal solution is to choose players 2, 3, 4, 5, 7, 10, 12, 13, 15, 17, 18, and 19. The average points per game among the players of this team are 22. (b) There is no feasible solution under the new set of constraints. (c) By re-solving the model for 14 players instead of just 12, we obtain an optimal team with almost the same objective value as before. This team contains the players 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 15, 17, 18, and 19. Therefore, the alternate players might be 6 and 11.
Manual to accompany Data, Models & Decisions: The Fundamentals of Management Science by Bertsimas and Freund. Copyright 2000, South-Western College Publishing. Prepared by Manuel Nunez, Chapman University.
Related Documents 3h463d
Chapter 9 606o72
August 2020 0
Chapter 9 606o72
December 2019 47
Chapter 9 606o72
November 2019 54
Chapter 9 606o72
December 2021 0
Chapter 9 606o72
November 2019 83
Chapter 9 606o72
November 2022 0More Documents from "Mao Han" 111j6r
Chapter 9 606o72
November 2022 0
N Risk For Infection t2e6g
October 2019 787
N For Pain Ob 262l1p
December 2019 353
4p345f
March 2021 0
N Social Phobia 5k6a2n
December 2021 0