ISyE323: Operations Research—Deterministic Models Problem Set #9 Due: December 5 with complete answers

ISyE323: Operations Research—Deterministic Models Problem Set #9 Due: December 5 The homework answers should be brought to class on 12/5. There will not be a quiz associated with this homework Deliverables: • Writeup (on paper) for each problem 1 Unbounded LP 1-1 Problem Using the simplex method show that the following linear program is unbounded. max 2x1 − 3x2 − x3 s.t.x2 − x3 ≤ 6 −x1 − x3 ≤ 10 x1, x2 ≥ 0 x3 free Answer: Since x3 is free, we need to do the substitution x3 = p3 − n3 in the problem, and then adding slack variables, gives us the equation system, with all variables non-negative, in which we wish to maximize the value of z: z − 2x1 + 3x2 − p3 + n3 = 0 x2 − p3 + n3 + s1 = 6 −x1 − p3 + n3 + s2 = 10 From this, if we let s1 and s2 be the baic variables, we see righ away that we can get a feasible solution of arbitraily large value, since increasing the value of x1, while leaving x2, p3, n3 all non-basic at value 0 gives the system: z = 0 + 2x1 s1 = 6 s2 = 10 + x1 1-2 Problem Find a solution those value is exactly 424, 242. Answer: The solution (in the original space of variables where x3 = p3 − n3) where(x1, x2, x3) = (, 0, 0)