Introduction to Optimization Problem Set 2

Introduction to Optimization Problem Set 2 1. LP Definitions (5 points). Consider the following linear program: min ax1 + bx 2 s.t. − 2 x1 + 3x 2 ≤ 4 2 x1 + x 2 ≤ 2 where a and b are some constants. a) Find an example of values for a and b so that the problem has a single optimal solution. b) Find an example of values for a and b so that the problem has multiple optimal solutions. c) Find an example of values for a and b so that the objective value is unbounded. d) Add a constraint to the problem so that the LP has no feasible solution. 2. Review of Linear Algebra (6 points). Suppose we would like to find a linear combination of the vectors ⎡ 2 ⎤ ⎡ 3⎤ ⎡1 ⎤ ⎢ 1 ⎥ , ⎢ 3⎥ , ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ and ⎢2⎥, so that the combination sums to ⎢⎣− 3⎥⎦ ⎢⎣6⎥⎦ ⎢⎣5⎥⎦ ⎡12⎤ ⎢18⎥. ⎢ ⎥ ⎢⎣10⎥⎦ a) Formulate this problem as a system of three linear equations. b) Solve this problem using the Pivot routine in CyTools. Hand in a printout of the matrix at each pivoting step. (Note: You will need to add CyTools as an Excel add-in. Instructions and the file itself [CyTools.xla] are located in the “Handouts” folder under “Documents” on server.) [Error Checking Hint: The sum o f the coefficients (x1 + x2 + x3) equals 16.] ⎡5⎤ c) Suppose a fourth column vector is added to the three original columns: ⎢ ⎥ ⎢6⎥. Thus we obtain the following matrix: ⎢⎣4⎥⎦ Page 1 of 4 ⎡ 2 3 1 5⎤ ⎢ 1 3 2 6⎥ . ⎥ ⎢ ⎢⎣− 3 6 5 4⎥⎦ Construct 4 different Jordan canonical forms of this matrix. Hand in a printout of the matrix at each pivoting step. (Note: once you find the first canonical form, you should be able to find the remaining three each via a single additional pivot. For simplicity, round answers to three decimal places.) 3. Varying Problem Data (6 points). As an aid to decision making, it is often useful to solve an LP over ranges of values for certain elements of the problem data. Here we consider the Glass Problem from AMP Section 1.4 (Chapter 1, page 12). In the original formulation, the storage capacity is 15,000 cubic feet. However, we would like to determine how the total contribution changes as storage capacity varies from 6,000 to 18,000 cubic feet (e.g., to see if it would be advantageous to rent some of the existing space to another company or perhaps to increase capacity). a) Use SolverTable to solve the LP (in the sheet labeled “Glass Problem” in Homework_02.xls), by letting the storage capacity range from 60 to 180 in increments of 5 (five). You only need to hand in the table generated by SolverTable, which should include columns for storage capacity and total contribution. (Note: You need to install SolverTable as an Excel add-in. A set-up file containing the add-in and instructions is found in the “Handouts” folder under “Documents” on server.) b) Plot total contribution versus capacity (using Excel’s scatter plot, with lines connected) and hand in a printout of the plot. [Error Checking Hint: The plot should look like a piecewise linear function.] c) Suppose the company is considering renting an extra 1,500 cubic feet of storage. Based on your answer from part (a), what is the maximum amount the company would be willing to spend per week for the extra storage? In your answer, provide the amount and a brief 1-sentence justification. 4. (Adapted from Wagner, Principles of Operations Research, 7 points.) Mr. Dustin (nicknamed Dusty) Jacquette, is production manager of the Eye-to-I Brand frozen food company, which processes potatoes into packages of French fries, hash browns, and flakes (for mashed potatoes). At the beginning of the manufacturing process, the raw potatoes are sorted by length and quality, and then allocated to the separate product lines. Dusty can purchase potatoes from two sources, which differ in their yields of various sizes and quality. These yield characteristics are displayed in the table below. Observe that from Source 1, there is a 10% yield of French fries, a 30% yield of hash browns, and a 30% yield of flakes; the remaining 30% is unrecoverable waste. The figures for flakes and waste are also 30% for potatoes from source 2, but the yield of French fries is higher. Assume that the manufacturing process does not allow processing potatoes from either source if any resulting product amounts will exceed the sales limitations. Page 2 of 4 Product in tons French Fries Hash Browns Flakes Waste Profit per ton Source 1 .1 .3 .3 .3 $50 Source 2 .3 .1 .3 .3 $60 Sales Limitations 2 1.5 2.5 a) Formulate a linear program that determines the number of tons of potatoes from Source 1 and Source 2 to use so total profit is maximized. b) Use the Excel solver spreadsheet provided to input the problem and find the optimal solution (the sheet labeled Eye-to-I in Homework_02.xls). You only need to write the optimal solution (the values of the decision variables) and the optimal value (the profit). [Error Checking Hint: the sum of the digits of the optimal total profit is 16.] c) Use SolverTable to observe the sensitivity of the optimal solution to changes in the profit per ton from Source 2 from $20 to $80 in increments of $5. Output the optimal values of the decision variables (tons from Source 1 and tons from Source 2) as well as the optimal revenue generated by your solution. Hand in the data table created by SolverTable. 5. (Adapted from Bradley, Hax, Magnanti, Applied Mathematical Programming, 5 points.) A corporation that produces gasoline must mix distillates of different octane ratings to produce different gasoline blends for sale. The company can purchase the following distillates. Distillate Octane Content A B C 96 88 80 Max. quantity avail. per day (gals) 4500 4000 3500 Cost $/gallon .6 .52 .47 The company sells three blends of gasoline as described in the following table. Blend Premium (P) High Grade (H) Regular (R) Minimum Octane Rating 93 89 87 Selling price $/gallon 1.53 1.29 1.15 In general, the octane rating for each blend is the weighted average of the distillates it is composed of. Formulate a linear program to determine the production policy that will maximize profits for the company. Make sure you represent the program in linear form. (This problem does not involve Excel.) Page 3 of 4 6. Non-linear constraints (5 points). In lecture, we have discussed cases when the objective is to minimize the sum of the absolute values of a number of variables (which can be interpreted as deviations from some goal, for example), and the case when the objective is to minimize the maximum of a number of variables (which can be interpreted as minimizing the largest deviation). Now consider the problem of minimizing the largest absolute value: min(max{x1 , x2 ,…, xn }), n s.t. ∑ aij x j ≤ bi , i = 1,..., n. j =1 a) Formulate the problem as a linear program by adding an additional variable sj for each absolute value x j , and an additional variable t for the maximum. b) Now modify your formulation from point a) so that it stays correct, but only includes the variables xj and t. (This problem does not involve Excel.) B. Challenging Problem (optional, 6 points) A company produces two kinds of products. A product of the first type requires 1/4 hours of assembly labor, 1/8 hours of testing, and $1.2 worth of raw materials. A product of the second type requires 1/3 hours of assembly, 1/3 hours of testing, and $0.9 worth of raw materials. Given the current personnel of the company, there can be at most 90 hours of assembly labor and 80 hours of testing each day. Products of the first and second type have a market value of $9 and $8, respectively. Formulate a linear program that can be used to maximize the daily profit of the company. Next, consider the following two modifications of the problem: i) Suppose that up to 50 hours of overtime assembly labor can be scheduled, at a cost of $7 per hour. ii) Suppose that the raw material supplier provides a 10% discount if the daily bill is above $300. Which of the two above elements can be easily incorporated into the linear programming formulation, and how? If one or both are not easy to incorporate, indicate how you might nevertheless solve the problem. Page 4 of 4