Problem 1: More Simplex Tableau Suppose while solving a maximization problem we obtain the following tableau, with the basic variables highlighted in blue: z 1 0 0 0 x1 a 0 1 0 x2 c d -5 e x3 0 0 0 1 x4 3 4 -1 2 x5 0 1 0 0 rhs 10 5 b 3 Give conditions on the missing values a, b, c, d, e and required to make the each of the following statements true: Part A: What is the current solution? Part B: The current tableau represents a basic feasible solution in canonical form. Part C: The current tableau is optimal and multiple optimal solutions exist. Part D: The current basic solution is a degenerate basic feasible solution. Part E: The current basic solution is feasible, but the objective function value can be improved by bringing x2 into the basis and pivoting x3 out. Part F: There exists an extreme ray of optimal solutions Part G: The current solution is both optimal and degenerate and there exists an extreme ray of optimal solutions Part H: Suppose a=0, d=e=2, and c=-2 perform a pivot in terms of the variables. Problem 2: 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 Univ./Public Constraint Media Constraint Final Value 10 0 1 Shadow Price 81.667 -36.667 -81.667 Constraint R.H. Side 10 0 1 Allowable Increase 1E+30 9 9 Allowable Decrease 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 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) Wrenches 1.5 1.0 .3 Pliers 1.0 1.0 0.5 Availability 27,000 lbs./day 21,000 hours /day 9,000 hours / day Demand Limit (tools/day) Contribution to earnings ($/1000 units) 15,000 $130 16,000 $100 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 12 9 Reduced Cost Objective Coefficient Allowable Increase 0 0 130 100 20 30 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?