Economics 172A: Introduction to Operations Research Winter 2008 Problem set 1 Answers Due Thursday, January 31 at start of class (no late papers) Instructions Unless otherwise noted on homework assignments and on examinations, you are required to supply complete answers and explain how you got them. Simply stating a numerical answer is insufficient. For this assignment, attach printouts of Excel spreadsheets when requested and indicate where to find the answers for each question the spreadsheet covers. This assignment asks you to solve many linear programming problems, but most are variations on the same basic problem. Set up one template for the Excel computations and then make changes to get the answers for variations of the problem. You need not include a separate printout for every simplex computation as long as you provide a clear description of how you got the answers. You are responsible for using the notes on Excel on the website to figure out how to get Excel answers yourself (I won’t lecture on it). For this assignment there is no need to provide answer reports and sensitivity reports, but please do indicate which cells on your spreadsheet have the solution. For graphs, clearly label the graph and show where the objective function is and how you identified a solution. If I ask you to solve a problem, please give both the solution (the optimal x) and the value (the objective function value for the optimal x). 1. Consider the linear programming problem: Choose x1,x2 ≥ 0 to solve max y subject to -x1 + 2x2 ≤ 5 3x1 + x2 ≤ 3, where the objective function y is a function of x1 and x2 to be specified. (a) Graph the feasible region. Put x1 on the vertical axis and x2 on the horizontal axis. [When x1 is on the vertical axis and x2 is on the horizontal axis, the feasible region is a quadrilateral with the west and south edges going along the x1 and x2 axes, and with a point sticking out to the east at (x1,x2 ) = (1/7, 18/7). It’s the intersection of the nonnegative quadrant (x1,x2 ≥ 0), the area northwest of the line from (x1,x2) = (-5,0) to (0,5/2), and the area southwest of the line from (x1,x2) = (1,0) to (0,3). The corners, starting from the southwest and going clockwise, are (0,0), (1,0), (1/7,18/7), (0,5/2).] (not drawn to scale)(b) Solve the problem graphically when: (i) y = x2. [The solution when y = x2 is at the point in the feasible region farthest to the east: the intersection of the two lines -x1 + 2x2 = 5 and 3x1 + x2 = 3, easily found by algebra to be (x1,x2 ) = (1/7, 18/7).] (ii) y = x1 + x2. [The solution when y = x1 + x2 is at the point in the feasible region farthest to the northeast (because the slope of the objective function contour, -1, is between the slopes of the constraints at this corner): again the intersection of the two lines at (x1,x2) = (1/7, 18/7).] (iii) y = x1 - x2. [The solution when y = x1 - x2 is at the point in the feasible region farthest to the northwest (because the slope of the objective function contour, 1, is between the slopes of the constraints at this corner): (x1,x2) = (1,0).] (c) Identify the corners of the feasible region. For each corner, give an example of a linear objective function y (a linear function of x1 and x2) such that the solution of the problem occurs at (and only at) that corner. [(x1,x2) = (0, 0), for which the objective function y = -x1 - x2 will work. (x1,x2) = (0, 5/2), for which the objective function y = -x1 + x2 will work. (x1,x2) = (1/7, 18/7), for which the objective function y = x1 + x2 will work. (x1,x2) = (1, 0), for which the objective function y = x1 will work.] (d) Now solve each of the problems in part (b) using Excel. Compare your answers to the graphical solutions. Are there any differences? Explain. [The answers are the same, except that if there were multiple solutions (which there aren’t here) Excel would not give you all of them: the particular solution the Excel finds will depend on how you entered the data.] (e) Now multiply each of the objective functions in part (b) by 3. Solve the new problem (graphically or using Excel, whichever you prefer). How do the optimal x’s and values change? [The optimal x’s don’t change because the only way to max 3f(x) subject to x in S is to max f(x) subject to x in S. The optimal values are multiplied by 3.] (Note that parts (e), (f), and (g) are independent. For example, when you do part (f) do not multiply the objective functions by 3: leave them as they were originally. Thinking should allow you to do (e)-(h) with little computation. But even if you don’t see why, you should be able to do these parts and use them to understand the ideas they get at. Please be sure to compare the answers and comment on the changes as requested.)(f) Now multiply the second constraint of the problem by 12 (so that it becomes 36x1 + 12x2 ≤ 36). With the new constraint, solve each of the problems in part (b) again (graphically or using Excel). How do the optimal x’s and values change? [The constraint hasn’t really changed, so the optimal x’s and values don’t change.] (g) Now multiply the coefficient of x1 in each constraint of the problem (except the nonnegativity constraints) and in each of the objective functions in part (b) by 12. With these changes, solve each of the problems in part (b) again (graphically or using Excel). How do the optimal x’s and values change? [The “real” optimal x1 won’t change, but the “nominal” solution for x1 will be multiplied by 1/12. The real and nominal solutions for x2 and the value don’t change. Multiplying the coefficient of x1 by 12 in each constraint and in the objective function—everywhere in the problem—is just like measuring x1 in feet rather than inches. (Not inches rather than feet! Make sure you understand why: because “12 inches” turns into “1 foot”.) Because x1 is now expressed in feet rather than inches, the constraints and the objective function trade-off between x1 and x2 haven’t really changed, but the nominal solution for x1 must be translated into the new language. Given the translation, the value doesn’t change.] (h) Now repeat part (f), except this time multiply as in (f) but by -12 instead of 12. [This doesn’t change the location of the second constraint’s boundary line, but it flips which side of it you are allowed to be on. The new feasible region is the intersection of the nonnegative