Introduction to Optimization Recitation 4

Problem 1 – Connecting Excel Output, Calculations and Graphical Analysis (Adapted from Bertsimas and Freund, Data, Models, and Decisions) 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) x2 ≤ 21 (Molding capacity) (2) x1 + 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) a) Graph the feasible region – solve the problem graphically – does your answer agree with the companies claim? Page 1 of 4 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$1 1 $D$1 1 Name Decision Variables Wrenches Decision Variables Pliers Final Valu e Reduce d Cost Objective Coefficie nt Allowabl e Allowable Increase Decrease 12 0 130 20 9 0 100 30 30 13.333333 33 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 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 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? d) If steel capacity increases to 28,000, how will the optimal objective value be affected? e) If molding capacity is increased to 23,000, how will the optimal objective value be affected? 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 2 – The Return of CCC Recall the Colorado Cattle Company problem: The Colorado Cattle Company (CCC) can purchase three types of raw feed ingredients from a wholesale distributor. The company's cattle have certain nutritional requirements with respect to fat, protein, calcium and iron. Each cow requires at least 10 units of Page 2 of 4 calcium, no more than 7.5 units of fat, at least 12 units of iron and at least 15 units of protein per day. The table below shows the amount of fat, protein, calcium and iron in each pound of the three feed ingredients. Grade 1 feed costs $.25, grade 2, $.10, and grade 3, $.08 per pound. The cattle can be fed a mixture of the three types of raw feed. CCC would like to feed its herd as cheaply as possible. Calcium Iron Protein Fat Grade 1 0.7 0.9 0.8 0.5 Grade 2 0.8 0.8 1.5 0.6 Grade 3 0 0.8 0.9 0.4 We have already solved this problem using Excel Solver, but today we want to take a look at what the sensitivity report can tell us. a) Resolve the problem using Excel Solver, asking for Sensitivity Report as part of the output. b) What is the shadow price of protein? Is the protein constraint tight (answer this only using the shadow price)? c) We are minimizing the cost of feeding a cow – does it make sense that the shadow price of the fat constraint is negative? Why? d) What is the range of iron requirement for the current solution to stay optimal? If you decrease the iron requirement by 1.5 what is the effect on the optimal solution (the objective vale and the decision variables)? e) Why are all the reduced costs zero? f) Now a new grade enters the market-place – Supergrade2000. It has 3 units of Calcium, 2.5 units of Iron, 2.7 units of Protein and only 0.3 units of fat and the costs $.69 per pound. Can Charlie the Cattle Coordinator feed his cows cheaper by including Supergrade2000 in his feed? Problem 3 – Taking a second look at Phase 1 (Adapted from AMP) Consider the following LP: Maximize Subject to z = 3 x1 + 2 x3 x1 + x2 + x3 + x4 = 4 -2 x1 + x2 – x3 =1 3 x2 + x3 + x4 = b x1, x2, x3, x4 ≥ 0 a) Assume b = 11. Find an initial basic feasible solution using Phase I of the simplex method. For parts b) through e), assume that b = 9. Page 3 of 4 b) Find an initial basic feasible solution using Phase I of the simplex method and an optimal solution to the original problem. c) Are there multiple optimal solutions? If so, find them by using extra pivots. d) Are any of the optimal solutions degenerate? Problem 4 – Thinking in 3D We have seen that in 2 dimensions, several properties of corner points hold we will now explore properties of corner points in 3 dimensions. a) In 2 dimensions constraints in the LP formulation translated to lines in the geometric plot, and we required all feasible points to be either on the line, on or above the line, on or under the line, depending on whether we had an equality, greater than or equal to, or less than or equal to constraint. What is the geometric equivalent of a linear constraint in 3 dimensions? b) In 2 dimensions, adjacent corner points share a constraint, which is an edge of the feasible set. What do corner points in 3 dimensions have in common? (Hint: how would you define a line in 3 dimensions?) c) In 2 dimensions each corner point is adjacent to at most 2 other corner points. Is there any bound on the number of corner points adjacent to a given corner point in 3 dimensions? d) In 2 dimensions if there was more than one optimal solution, and the objective was non-zero, it meant that the objective was parallel to a constraint. Is this the case in 3 dimensions? Page 4 of 4