Systems Optimization Sample Midterm 1 and Solutions

Systems Optimization Mid Term Exam Key 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) a) Using the spreadsheet ExtendShortPath.xls found in the Exams folder on Sloan Space, extend the Shortest Path Model into a network flow model that can simultaneously find the shortest path from Home to every other site. To find these paths you should only need to solve a single network flow model. The credit you receive on this model will depend in part on the size of the problem you formulate. For example, simply combining several separate shortest path models into one objective will not receive full credit. Determining the shortest paths from the solution to your model may take some interpretation, but should be unambiguous. To view the model, click on this image Shortest Path Model Connectivity From\To Home Site 1 Site 2 Site 3 Site 4 Site 5 Site 6 Site 7 Home 0 7 0 0 7 0 0 7 Site 1 7 0 7 7 0 0 0 0 Site 2 0 7 0 7 0 7 0 0 Site 3 0 7 7 0 7 0 0 0 0 Site 4 7 0 0 7 0 7 7 Site 5 0 0 7 0 7 0 7 0 7 Site 6 0 0 0 0 7 0 7 Site 7 7 0 0 0 7 0 7 0 Route From\To Home Site 1 Site 2 Site 3 Site 4 Site 5 Site 6 Site 7 Home 0 5 0 0 0 0 0 2 Site 1 0 0 0 4 0 0 0 0 Site 2 0 0 0 0 0 1 0 0 Site 3 0 0 2 0 1 0 0 0 0 Site 4 0 0 0 0 0 0 0 Site 5 0 0 0 0 0 0 0 0 0 Site 6 0 0 0 0 0 0 0 Site 7 0 0 0 0 0 0 1 0 Total To 0 5 2 4 1 1 1 2 Total From Total To 7 -1 -1 -1 -1 -1 -1 -1 Net Required 7 -1 -1 -1 -1 -1 -1 -1 Distance From\To Home Site 1 Site 2 Site 3 Sit Home 4 Site 1 4 6 1 Site 2 6 1 Site 3 1 1 Site 4 7 1 Site 5 2 Site 6 Site 7 8 Total From 7 4 1 3 0 0 0 1 Total Distance Home Site 1 Site 2 Site 3 Sit Home 0 20 0 0 Site 1 0 0 0 4 Site 2 0 0 0 0 Site 3 0 0 2 0 Site 4 0 0 0 0 Site 5 0 0 0 0 Site 6 0 0 0 0 Site 7 0 0 0 0 Total To 0 20 2 4 b) Describe briefly but clearly how to find the shortest path from Home to a given site from an answer to your model. This is a transshipment model with 7 units of supply at Home and one unit of demand at each other site. The solution gives the number of shortest paths that use each edge. Starting from Home and following positive flows, each time we reach a node we do so on a shortest path. 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.