Systems Optimization Sample Midterm 4

Systems Optimization Practice Mid-Term Exam This Practice Exam consists of 3 questions from last year’s Mid-Term Exam 1 question (#3) based on Challenge #1 that illustrates the sort of question that may appear on the Mid-Term Instructions You have two hours to complete the exam from the time you first begin it. Watch your time. If you are having difficulty with a question, you might wish to pass over it and return to it later if you have enough time at the end of the exam. The exam is open book: you may use any notes or text material. You are encouraged to use Excel to build your models. The exam is to be done individually, without collaboration with anyone else. Problem 1 (20 points) Consider the case of Auto power Europe trying to determine which VP to send to each site. The VP's are negotiating over the assignments (as well you might imagine). Answer each of the following questions arising during the discussions (arguments) based on the information in the following Sensitivity Report (see the next page) a) What are the basic variables in this optimal solution? This is a balanced network flow problem with 8 constraints (4 VP constraints and 4 plant constraints), so there are 7 basic variables. They are highlighted in Yellow Cell $B$15 $C$15 $D$15 $E$15 $B$16 $C$16 $D$16 $E$16 $B$17 $C$17 $D$17 $E$17 $B$18 $C$18 $D$18 $E$18 Name Finance (F) Leipzig Finance (F) Nancy Finance (F) Liege Finance (F) Tilburg Marketing (M) Leipzig Marketing (M) Nancy Marketing (M) Liege Marketing (M) Tilburg Operations (O) Leipzig Operations (O) Nancy Operations (O) Liege Operations (O) Tilburg Personnel (P) Leipzig Personnel (P) Nancy Personnel (P) Liege Personnel (P) Tilburg Final Reduced Objective Allowable Allowable Value Cost Coefficient Increase Decrease 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 15 0 9 0 7 14 0 6 0 1 2 2 0 7 0 0 24 10 21 11 14 22 10 15 15 17 20 19 11 19 14 13 1E+30 1 1E+30 6 1E+30 1E+30 6 1E+30 1 1E+30 1E+30 1E+30 4 1E+30 2 1 15 16 9 1 7 14 1E+30 6 4 1 2 2 1 7 6 6 b) One VP has asked whether or not there is another optimal solution other than the one proposed. The President, having gotten his MS at MIT, is a clever fellow and realizes how he can quickly resolve the question. Is this the only optimal solution? Explain your answer. This is the unique optimal solution because no NON-BASIC variable has zero reduced cost. c) The VP of Operations attended Ecole des Mines de Nancy and would like to have a chance to return to the campus. He is trying to convince the President that the cost of his going to Nancy is less than the estimated cost of 17. He must convince the President to reduce his estimate of this cost by how much? If we send the VP of Operations to Nancy, the total cost of the solution rises by 1 (that's what the reduced cost says). So, to break even, he must convince the President to reduce the cost estimate by 1 to $16. d) Which VP's time is most valuable? We measure the value of a VP's time based on the reduction in the cost of the optimal assignments we would obtain if we convince a second VP to visit 2 sites so the VP in question does not need to visit any. The greater the reduction in cost, the more valuable the VP's time. By our definition the VP with the highest shadow price on the Plants Assigned constraint is the one whose time is most valuable. We would prefer he stays at home. That's the VP of Operations with shadow price 0. Microsoft Excel 8.0a Sensitivity Report Worksheet: [01AssignmentModel.xls]Sheet1 Report Created: 12/18/01 4:29:06 PM Adjustable Cells Cell $B$15 $C$15 $D$15 $E$15 $B$16 $C$16 $D$16 $E$16 $B$17 $C$17 $D$17 $E$17 $B$18 $C$18 $D$18 $E$18 Name Finance (F) Leipzig Finance (F) Nancy Finance (F) Liege Finance (F) Tilburg Marketing (M) Leipzig Marketing (M) Nancy Marketing (M) Liege Marketing (M) Tilburg Operations (O) Leipzig Operations (O) Nancy Operations (O) Liege Operations (O) Tilburg Personnel (P) Leipzig Personnel (P) Nancy Personnel (P) Liege Personnel (P) Tilburg Final Reduced Objective Allowable Allowable Value Cost Coefficient Increase Decrease 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 15 0 9 0 7 14 0 6 0 1 2 2 0 7 0 0 24 10 21 11 14 22 10 15 15 17 20 19 11 19 14 13 1E+30 1 1E+30 6 1E+30 1E+30 6 1E+30 1 1E+30 1E+30 1E+30 4 1E+30 2 1 15 16 9 1 7 14 1E+30 6 4 1 2 2 1 7 6 6 Constraints Cell $F$15 $F$16 $F$17 $F$18 $B$19 $C$19 $D$19 $E$19 Name Finance (F) Plants Assigned Marketing (M) Plants Assigned Operations (O) Plants Assigned Personnel (P) Plants Assigned VPs Assigned Leipzig VPs Assigned Nancy VPs Assigned Liege VPs Assigned Tilburg Final Shadow Value Price 1 1 1 1 1 1 1 1 -6 -8 0 -4 15 16 18 17 Constraint Allowable Allowable R.H. Side Increase Decrease 1 1 1 1 1 1 1 1 1 0 1E+30 1 0 0 0 0 0 0 0 0 1 1 0 1 Problem 2 (30 points) Extend the assignment model for Auto power to accommodate the following enhancements. In our new model each VP can visit up to three sites and to ensure an unbiased and thorough inspection, we want at least two different VP's to visit each site. We still want to minimize the estimated total cost of the assignments. Your model should be a Network Flow model. a) Using the spreadsheet ExtendAssignment.xls found in the Exams folder, build a Solver model for this problem. Be sure your model is a Network Flow model. Click on this image to view the model Autoppower Europe: Assignment Model Moore et al. pp224 Finance (F) Marketing (M) Operations (O) Personnel (P) Estimated Assignment Costs Leipzig Nancy Liege Tilburg 1 2 3 4 24 10 21 11 14 22 10 15 15 17 20 19 11 19 14 13 VP Leipzig 1 VP 0 1 0 1 2 Assignments Nancy Liege 2 3 1 0 1 0 2 0 14 0 11 25 Cost of Assignments Nancy Liege 2 3 10 0 0 10 17 0 0 14 27 24 Finance (F) Marketing (M) Operations (O) Personnel (P) VPs Assigned Leipzig 1 VP Finance (F) Marketing (M) Operations (O) Personnel (P) Total Cost b) Tilburg 4 0 1 0 1 2 1 0 0 1 2 Plants Assi 2 2 1 3 Tilburg Total Cost 4 11 21 0 24 0 17 13 38 24 100 Formulate a (pseudo) AMPL model of the problem (Do not worry about reading the data, just formulate the model by describing the sets, parameters, variables, objective and constraints) set VPS; set PLANTS; param Cost{VPS, PLANTS}; param Supply {VPS}; param Demand{PLANTS}; var Assign{VPS, PLANTS} >= 0, <= 1; minimize TotalCost: sum{vp in VPS, plant in PLANTS} Cost[vp, plant]*Assign[vp, plant]; s.t. ObserveSupply{vp in VPS}: sum{plant in PLANTS} Assign[vp, plant] <= Supply[vp]; s.t. Meet Demand{plant in PLANTS}: sum{vp in VPS} Assign[vp, plant] >= Demand[plant]; Problem 3 (30 points) Having struggled with Challenge #1 in great detail, let’s take a more tactical and strategic look at the problem. Briefly address the major issues associated with developing a practical decision support tool for NASA building on the basic problem we address in Challenge #1. In particular, answer the following three questions. Focus your answers on the issues that particularly relate to decision support systems based on optimization models like the one we propose. Eschew truisms, tautologies and other fluff. A. (10 points) Describe the data you will need from NASA in order to build your model. Be as specific as possible. Remember, Data costs money: to obtain; to organize; and to maintain its quality. We don’t want to ask for unnecessary data. B. (10 points) Briefly describe in prose objectives and constraints you feel NASA should consider for the model beyond the ones we built into our basic models of the problem. C. (10 points) Discuss implementation issues NASA will face in developing a decision support system built around a model like the one you proposed. These issues may range from availability and quality of data to time and memory for computation to challenges translating the model’s recommendations into action. Problem 4 (20 points) Provide brief answers to the following questions. (a) Solver only considers basic feasible (extreme) solutions in looking for an optimal solution to a network flow problem. Does this mean that all the optimal solutions to a given network flow problem must be a basic feasible solution? No. In the case of alternative optimum solutions, for example, the optimum solutions we obtain by increasing the value of a non-basic variable with zero reduced cost are not basic solutions. (b) What are the three possible conclusions Solver can reach regarding the solutions to a given network flow problem? 1. The problem has a finite optimum solution 2. The problem admits no feasible solutions 3. The problem admits feasible solutions, but none is optimal as the objective function value is unbounded. (c) How many basic variables will there be in a basic feasible solution to an Assignment Problem like Auto power's, but with 5 Vice Presidents and 5 plants to audit? This refers to the original assignment problem, which is balanced. Since there are 10 constraints, there will be 10 -1 or 9 basic variables. (d) Consider again an Assignment Problem like Auto power's, but with 5 Vice President's and 5 plants to audit. How many variables will be positive in a basic feasible solution to this problem? 5. One for each assignment in the solution.