Introduction to Optimization Problem Set 5

Introduction to Optimization Problem 1 – Using tableaus to determine sensitivity information Consider the following problem Max z = 4x1 + x2 + 2x3 St 8x1 + 3x2 + x3 ≤ 2 6x1 + x2 + x3 ≤ 8 x1,x2,x3 ≥ 0 and the following final optimal tableau z 1 0 0 x1 8 2 6 x2 1 2 1 x3 0 0 1 s1 0 1 0 s2 2 -1 1 rhs 16 4 8 I. Changes in Cost Coefficients a) Basic Variables: find the range of values of the objective function coefficient of x3 for which the current basis remains optimal. b) Nonbasic Variables: find the range of values of the objective function coefficient for x1 for which the current basis remains optimal. II Changes in the RHS c) Find the range of values of the right-hand side of the first constraint for which the current basis remains optimal. d) Find the new optimal solution if the right-hand side of the first constraint were increased to 4. Problem 2 – Linear Programs, simplex and geometry (Partially adopted from last years midterm) Answer these true/false questions about the simplex method and Linear Programs: Page 1 of 3 a) It is possible for the simplex method to terminate with one or more slack variables still in the basis. b) If an LP has two or more optimal solutions then it has an infinite number of different optimal solutions. c) If an LP with non-negativity constraints has more than one optimal solution then there are at least two BFS that are optimal. d) Every LP has a corner point. e) When we do a (nondegenerate) simplex-pivot, then we move from one basic feasible solution to another. f) Basic Feasible Solution is another word for a Corner Point. For the rest of this problem consider the following tableau: z x1 x2 x3 x4 x5 x6 RHS 1 c d 0 0 0 0 10 0 4 a 1 0 b 0 e 0 -1 -5 0 1 -1 0 2 0 f -3 0 0 -4 1 3 g) If c=0 and d=2 then the current solution is optimal, but there are alternative optimal solutions. h) If this tableau was obtained during a run of the simplex algorithm, and if a and b are both greater than zero, then it is possible that the tableau represent an infeasible solution. i) If both d and a are less than zero then the optimal objective value is unbounded. j) If e>0, d<0 and a >0, then the objective value can be improved by pivoting and letting x2 enter the basis and x6 leave the basis. Problem 3 – Simplex and Sensitivity Suppose you are given the final tableau for a typical production-type problem, along with some sensitivity analysis: z 1 0 0 a) b) c) d) x1 3 2 -1 x2 0 1 0 x3 5 4 1 s1 2 1 -1 s2 0 0 1 RHS 20 10 2 Price Allow Inc Allow Dec 2 0 2 1E+30 10 2 What is the optimal solution? What is a reduced cost? Are there multiple optimal solutions? How much must the original profit of x1 change by in order for it to be produced in an optimal production schedule? Page 2 of 3 e) Now we are given the following sensitivity information on the cost coefficients: Cost Coefficient off: x1 x2 x3 i. ii. f) g) h) i) Original Value 3 2 6 Allow Inc Allow Dec 3 1E+30 5 1E+30 1.25 1E+30 How would the optimal solution change if the cost coefficient of x1 increases by 2? (Do you have any intuition why the allowable decrease is 1E+30?) How would the optimal solution change if the cost coefficient of x2 increases by 7? (Do you have any intuition why the allowable increase is 1E+30?) What is a shadow price? Why is the shadow price for one of the constraints zero? What is the new objective function value if the RHS of constraint 1 is increased by 2? Suppose a new product, x4, is under consideration. It requires 2 units of resource 1 and 3 units of resource 2. What must the earnings from selling one unit of x4 be in order for it to be profitable to produce x4? Problem 4 - Formulation Ann and Ben are getting divorced and want to determine how to divide their joint property: retirement account, home, summer cottage, investments, and miscellaneous assets. To begin, Ann and Ben are told to allocate 100 total points to the assets. Their allocation is as shown below. Item Retirement account Home Summer cottage Investments Miscellaneous Points Ann's Ben's 50 40 20 30 15 10 10 10 5 10 Assuming that all assets are divisible (that is, a fraction of each asset may be given to each person), how should the assets be allocated? Two criteria should govern the asset allocation: Criteria 1: Each person should end up with the same number of points. This prevents Ann from envying Ben and Ben from envying Ann. Criteria 2: The total number of points received by Ann and Ben should be maximized. Page 3 of 3