Optimization Methods in Management Science Recitation 5

Problem 1: Taking the Dual Let the following LP be the primal. Convert it into the dual (Use the SOB rule). Maximize 2 x1 + 3 x2 − 7 x4 s.t. 3 x1 − 2 x2 + x3 − 2 x4 ≤ 5 2x1 + x2 + 2 x3 − 4 x4 = 4 x1 + 2 x2 + 5 x3 − 3 x4 ≥ 3 x1 , x2 ≥ 0, x3 uris, x4 ≤ 0 Problem 2: Duality Facts: Short Answer &True/False Part A: If a constraint of the primal problem is NOT tight (binding) at the optimal solution, then the corresponding dual variable (shadow price) is zero. Part B: If a constraint in the dual variable is binding, then the corresponding primal variable is 0. Part C: If a primal variable is 0, what does it say about the dual problem? Part D: The dual of the dual always has an objective function that is greater than the dual. Part E: If a LP is feasible, then so is it dual and the optimal costs are equal. Part F: Given a maximization primal problem every dual simplex pivot increases the value of the dual problem’s objective function. Part G: If the dual is unique then the primal BFS is not degenerate. Part H: If the dual is degenerate than the primal has multiple optimal solutions. Part I: The dual simplex method is particularly useful given a dual feasible solution to the original problem and a new cost vector c. Part J: Solving the dual allows us to derive the upper bound on the primal LP. Problem 3 – Connecting Excel Output, Calculations and Graphical Analysis Gemstone Tool company produces wrenches and pliers. They are both made from steel, and the process involves molding on a molding machine, and assembling on an assembly machine. The amount of steel used and the daily availability of steel are shown in the following table. The next two lines contain the machine requirements for each product as well as the availability of machine time. The final two lines contain the daily demand and their per unit contribution to earnings. Steel (lbs.) Molding Machine (hrs) Assembly Machine (hrs) Demand Limit (tools/day) Contribution to earnings ($/1000 units) Wrenches 1.5 1.0 .3 15,000 $130 Pliers 1.0 1.0 0.5 16,000 $100 Availability 27,000 lbs./day 21,000 hours /day 9,000 hours / day The management has formulated a linear optimization problem to determine the optimal level of production for wrenches and pliers that maximizes the earnings: Let x1 = number of wrenches produced (in thousands) x2 = number of pliers produced (in thousands) Then the linear program is: Maximize s.t. z = 130 x1 + 100 x2 1.5 x1 + x2 ≤ 27 (Steel capacity) (1) x1 + x2 ≤ 21 (Molding capacity) (2) 0.3 x1 + 0.5 x2 ≤ 9 (Assembly capacity) (3) x1 ≤ 15 (Wrench demand limit) (4) x2 ≤ 16 (Plier demand limit) (5) x1, x2 ≥ 0 The company claims that the optimal solution to this problem is: (z,x1,x2)= (2460, 12, 9) Part A: Graph the feasible region – solve the problem graphically – does your answer agree with the companies claim? Part B: Using graphical analysis, what is the range of price of Wrenches? Does that agree with the following sensitivity report output? Adjustable Cells Cell $C$11 $D$11 Name Decision Variables Wrenches Decision Variables Pliers Final Value Reduced Cost Objective Coefficient Allowable Increase 0 0 130 100 20 30 12 9 Allowable Decrease 30 13.33333333 Constraints Cell $C$15 $C$16 $C$17 $C$18 $C$19 Name Steel capacity Molding capacity Assembly capacity Wrench demand limit Plier demand limit Final Valu e 27 21 8.1 12 9 Shado w Constrain t Allowabl e Allowable Price 60 40 0 0 0 R.H. Side 27 21 9 15 16 Increase 1.5 1 1E+30 1E+30 1E+30 Decrease 2.25 1.5 0.9 3 7 Part C: Using graphical analysis, what is the range of the steel availability for the current solution to be optimal (that is, for the optimal solution still be at the intersection of constraints (1) and (2))? Can you conclude anything about the shadow price from that analysis? Do you results agree with the sensitivity report above? Part D: If steel capacity increases to 28,000, how will the optimal objective value be affected? Part E: If molding capacity is increased to 23,000, how will the optimal objective value be affected? Part F: If Gemstone Tool company could produce screwdrivers using 0.5 lbs of steel, 0.8 hours of molding time and 0.3 hours of assembly time and sell it for $60, should it produce screwdrivers? If not, how high does the price have to be for screwdrivers to become profitable? If so, how much lower can the price before it is no longer profitable to produce them? Problem 4: March Madness The NCAA is making plans for distributing tickets to the upcoming regional basketball championships. Up to 10,000 available seats will be divided between the media, the competing universities, and the general public, subject to the following conditions: o Media people are admitted free, and at least 1000 tickets must be reserved for the media. o The NCAA receives $45 per ticket from competing universities and $100 per ticket from the general public. o At least half as many tickets should go to competing universities as the general public. Part A With these restrictions, formulate an LP so that the NCAA maximizes their profit: On solving this problem, the NCAA obtains the following sensitivity report: Name Media Tickets University Tickets Public Tickets Final Value 1 3 6 Reduced Cost 0 0 0 Objective Coefficient 0 45 100 Allowable Increase 81.667 55 1E+30 Allowable Decrease 1E+30 245 55 Name Capacity Constraint Final Value 10 Shadow Price 81.667 Constraint R.H. Side 10 Allowable Increase 1E+30 Allowable Decrease 9 Univ./Public Constraint Media Constraint 0 1 -36.667 -81.667 0 1 9 9 4.5 1 Part B: What is the optimal value of the decision variables, and what is the optimal profit? Part C: Suppose there is an alternate arrangement of the stadium that can provide 20,000 seats in total, and thus 20,000 tickets may be sold. How much additional revenue would be gained from the expanded seating? Part D: In order to make the games more affordable for fans, another proposal would reduce the price of public tickets to $50. (Ignore part b here.) Will the same solution be optimal if we implement this change? (By ‘solution’, we mean the values of the decision variables.) If the same solution is used, how much revenue would we lose? Part E: To accommodate high demand from student supporters of participating universities, the NCAA is considering marketing a new “scrunch seat” that costs $15 and consumes only 50% of a regular seat, but counts fully against the “university ≥ half public” rule. (So there can be two tickets sold for each available seat.) Let x4 indicate the number of seats of this type (in thousands). Formulate the revised LP. Part F: What is the reduced cost of x4, and would selling such seats be profitable? (Use the information in part d and the sensitivity report.) Part G: Suppose that the number of seats is changed to 13,000. What would be the optimal solution? (Hint: x1 will still be equal to 1.) What is the optimal profit? Verify that the change in the optimal solution value is what would have been predicted from the Excel Sensitivity Report. Problem 5 Turkey Tim was trying to find the optimal solution to a maximization problem in decision variables xj ≥ 0 (for j = 1, 2, …,6). After performing several pivots, he came up with a tableau similar to the one bellow. However, Turkey Tim was watching TV while working on the problem, so he could have mistakes while calculating the values of some of the elements in the simplex tableau. Ollie replaced these questionable elements in the tableau with variables hoping that you (the bright students taking 15.053) will be able to explain to Tim the importance of these variables’ values. z 1 0 0 0 x1 3 2 e 5 x2 a -1 0 f x3 0 0 0 1 x4 b 5 -1 2 x5 0 1 0 0 x6 0 0 1 0 RHS d c 2 4 For each statement below, give sufficient conditions on all six unknowns a, b, c, d, e, f such that the statement is true. If there is nothing that can be done to make the statement true please explain why. If there are several ways of accomplishing this, please state only one. Part A. 1) 2) 3) 4) 5) 6) The current solution is feasible but not optimal. The current solution is the unique optimal solution. The current solution is optimal and there are multiple optimal solutions. The optimal objective value is unbounded from above. The problem is infeasible. The current solution is degenerate. Part B. Turkey Tim verified some of his calculations and found out that c > 0 and that a < 0. What does this imply for optimality? From now on assume that c > 0 and a < 0. 1) Indicate the basic and non-basic variables corresponding to this tableau. Indicate the corresponding objective function value. 2) Perform one pivot using this simplex algorithm on the above tableau. In this part let f = 1. Indicate the variable that enters the basis, the variable that leaves the basis, and what the total change in profit would be for this one iteration of the simplex method (your answer may be in terms of a, b, c , d, and e)