ISyE323: Operations Research—Deterministic Models Problem Set #9 Due: May 4, 4:00PM

ISyE 323 Problem Set #9 Prof. Jim Luedtke ISyE323: Operations Research—Deterministic Models Problem Set #9 Due: May 4, 4:00PM The homework answers should be brought to class on 5/5. There will not be a quiz associated with this homework Deliverables: • Writeup (on paper) for each problem 1 Two-phase simplex We are using the two-phase simplex algorithm to solve the following linear proram: max z = x1− x2 s.t. 2x1+ x2 ≥ 6 3x1+2x2 = 4 x1 ≥ 0, x2 ≥ 0 Below is a tableau obtained when solving the Phase I problem in the two-phase simplex method. In this tableau, a1 and a2 are the artificial variables, and w 0 represents the Phase I objective. Row w 0 x1 x2 s1 a1 a2 RHS BV 0 1 0 −1/3 −1 0 −5/3 10/3 w 0 =? 1 0 0 −1/3 −1 1 −2/3 10/3 2 0 1 2/3 0 0 1/3 4/3 1.1 Problem Which variables are basic and which variables are nonbasic in this tableau? What basic variables are associated with row 1 and row 2 of this tableau, and what are the values of these variables? Answer: Row 1: a1 = 10/3 Riow 2: x1 = 4/3 1.2 Problem Identify which one of the following statements is correct, and answer the corresponding question. 1. The current basic feasible solution is optimal to the Phase I linear program, and can be used to define a feasible solution to the original linear program. If so, identify the feasible solution and the corresponding tableau to use in Phase II. 2. The original linear program is infeasible. If so, explain how you can be sure of this. 3. At least one more iteration of the simplex al