EXAMPLE 7 Two-Phase Simplex: Case 3 Use the two-phase simplex method to solve the following LP: min z = 40x1 + 10x2 + 7x5 + 14x6 s.t. X1 - *2 + 2x5 =0 -2x1 + *2 - 2x5 =0 X1 + X'3 + x5 - X6 = 3 2x2 + X3 + X4 + 2x5 + 16 = 4 All x; 2 0 Solution We may use x4 as a basic variable for the fourth constraint and use artificial variables a1, a2, and a; as basic variables for the first three constraints. Our Phase I objective is to min- imize w = a1 + a2 + a3. After adding the first three constraints to w - dj - d2 - d; = 0, we obtain the initial Phase I tableau shown in Table 43. Even though x5 has the most positive coefficient in row 0, we choose to enter x; into the basis (as a basic variable in row 3). We see that this will immediately yield w = 0. Our final Phase I tableau is shown in Table 44. Because w = 0, we now have an optimal Phase I tableau. Two artificial variables re- main in the basis (a, and a2) at a zero level. We may now drop the artificial variable a; from our first Phase II tableau. The only original variable with a negative coefficient in the optimal Phase I tableau is x1, so we may drop x, from all future tableaus. This is be- cause from the optimal Phase I tableau we find w = x1. This implies that x, can never be- come positive during Phase II, so we may drop x, from all future tableaus. Because z - 40x1 - 10x2 - 7x5 - 14x6 = 0 contains no basic variables, our initial tableau for Phase II is as in Table 45. TABLE 43 Basic W rhs Variable - 3 01 = 0 N - N-NN - AWOOW :0 - CO 03 =