**Unformatted text preview:**

90-722: Management Science I, Final Exam Solution, Spring 2013Question #1: (12 Points): In the first half of the course, we only had to press “Solve” once for any given optimization (apart from sensitivity analysis). By contrast, in all three chapters since the midterm there have been reasons to optimize multiple times for any given problem. In a few concise, complete, and legible sentences explainwhy that is so for:a) Integer programming and different levels of the “tolerance” parameter b) Goal programming and varying weights on deviational variablesc) Nonlinear programming with the GRG algorithm and various initial values for the decision variablesFor IP, the branch and bound algorithm runs slowly if we insist on obtaining an optimal solution, so we often start with the tolerance parameter set at some valuegreater than zero so Solver can prune more nodes in its search tree, and then once we have a feasible solution, and have fully debugged the model, we dial the tolerance down and solve again.With GP we are trying to generate a number of different feasible solutions that are efficient in terms of how they trade off various competing objectives, and the mechanism for doing this is repeatedly solving with different sets of penalty weights on the deviational variables.A danger with NLP is that Solver will stop at a local optimum that is no the global optimum. Repeatedly solving starting from different initial conditions increases the likelihood that at least one of those runs will find a global optimum. Question #2: (5 Points): Why does the GRG algorithm for NLPs dislike plateaus?GRG is near-sighted. On a plateau it can’t detect improvement in any direction, so it stalls and returns the current solution even if there are appealing heights to climb starting at the edge of the plateau.1Question #3: (15 Points): Below are snapshots of the node portion (i.e., right hand side) of a node-arc incidence approach to modeling network optimization problems in a spreadsheet. Identify as precisely as possible what type of problem is being solved in each case (where by type of problem I mean something like “product mix”, “make vs. buy”, “allocation”, etc.). 2Question #4: (12 Points): The SS solution to the MasterDebt Lockbox problem is pasted below. Recall that the challenge was to decide which of the six lockboxes to operate, and which regions to assign to each lockbox, in order to minimize the combined cost of (1) lockbox operation plus (2) “float”. a) Where (in what cities) are lockboxes being operated in this solution?b) What is the cost of float in this solution? (Give the answer in thousands of dollars.)c) Part of the logic of the model is “If any region is assigned to a given lockbox, then we must operate that lockbox and pay the associated price,” but that logic is implemented with linear equations rather than with an =IF() statement to make things easier on Solver. What constraint would you add to Solver to implement this logic? (Specify cell range on left and right hand side and whether the comparator is ≥ , ≤ or, =.)d) Write the algebraic expression(s) which correspond to the constraint described in part c.(I.e., parts c & d ask about the same constraint. Part c asks you to state it in “Solver speak”; d asks you toexpress it algebraically.) a) Dallas and New Yorkb) Key idea is that the overall problem seeks to minimize the sum of two costs: the cost of lockboxes and the cost of float. You know the total is $224 and can see that the cost of operating the two lockboxes mentioned in part a is $35 + $30 = $65. So cost of float is $224 - $65 = $159 thousand dollars.c) B26:G26 ≤ B28:G28d) For all j, ∑iXij≤ M Yj3Question #5: (12 Points): Suppose Branch & Bound were working on a minimization problem and its tree currently has eight activenodes whose LP relaxations yield the following results (a “?” for Z*IP indicates the solution to the LP relaxation was non-integer.)a) Which subproblems can be pruned without jeopardizing the ability to find an optimal solution?b) Which additional subproblems could be pruned if the tolerance parameter were set to 20%?c) What are the tightest bounds you can provide on the original problem’s optimal solution value? a) #5 and #6b) #3, #7, and #8c) 100 ≤ Z*IP ≤ 150.Question #6: (24 Points): This problem pertains to assigning students to systems project groups. Use the notation that Xij indicates whether student i ends up in group j. Assume the number of students and groups is fixed throughout this problem, and do not worry about specifying their values. a) If parameter lij denotes how much student i would like (letter “l” for like) being on project j (big numbers being good), formulate an LP that maximizes total student happiness subject to the constraint that every project has at least 7 and no more than 14 students.b) Suppose pij indicates how much the professor of course j would prefer (p for prefer) having student i in his or her project group. Suppose the Dean defines target levels for the happiness of students and professors as t1 and t2, respectively. Write soft (or goal) constraints for the twin goals of making students and professors as happy as possible.c) Suppose the Dean did not know how to pick target values. What would Ragsdale suggest based on the MOLP portions of Chapter 7?d) Write a GP objective function for the Dean that penalizes the relevant deviation from the student target three times as much as the corresponding deviation from the faculty target – in both cases thinking of deviations in percentage terms.e) Suppose the Dean did not want to specify the relative importance of the two goals, but instead wanted to see the full range of possibilities produced by varying the relative weight placed on them. Sketch the resulting figure you would produce for the Dean, paying attention to the slope 4of the efficient frontier. (Don’t sweat the curvature, meaning whether the frontier is convex or concave. I can tell you it’ll be concave.) f) The Dean has a third goal of holding down the maximum size of systems classes. So far in this problem that upper limit has been 14. So label the efficient frontier from part e with “max size = 14”. Now draw a dashed line on the same graph as in part e for the frontier with “max size = 12”,indicating which side of the original frontier it would be on. (Make the original frontier be a solidline so it is easy to

View Full Document