1 Gauss-Jordan Elimination x1 x2 x3 x4 = c 1 1 1 2 3 1 6 1 -1 0 2 -2 -2 2 8 use the third equation to subsitute for x1 (x1 = x4) x1 x2 x3 x4 = c 1 1 1 2 3 1 6 1 -1 0 -2 -2 4 8 use the first equation to substitute for x2 (x2 = 2 - x3 - x4) x1 x2 x3 x4 = c 1 1 1 2 -2 -3 0 1 -1 0 6 12 use the fourth equation to substitute for x4 (x4 = 2) x1 x2 x3 x4 = c 1 1 0 -2 6 1 -2 1 2 use the second equation to substitute for x3 (x3 = -3 x1 x2 x3 x4 = c 1 3 1 -3 1 -2 1 2 There is one solution x1 = 2, x2 = 3, x3 = -3, x4 = 2 2 Standard Form x1 + x2 + x3 + s1 = 4 x1 + s2 = 2 x3 + s3 = 3 3x2 + x3 + s4 = 6 3 Pivoting z = -34 + x1 +14 x2 +6 x3 x4 = 4 - x1 - x2 - x3 x5 = 2 - x1 x6 = 3 - x3 x7 = 6 -3 x2 - x3 Entry variable x1, exit variable x5, substitute x1 = 2 - x5 z = -32 - x5 +14 x2 +6 x3 x4 = 2 + x5 - x2 - x3 x1 = 2 - x5 x6 = 3 - x3 x7 = 6 -3 x2 - x3 Entry variable x2 exit variable x4 (could also be x7 but fractions appear) x2 = 2 + x5 - x4 - x3 z = -4 +13 x5 -14 x4 -8 x3 x4 = 2 + x5 - x4 - x3 x1 = 2 - x5 x6 = 3 - x3 x7 = 0 -3 x5 +3 x4 +2 x3 entry variable x5 exit variable x7: x5 = 0 -1/3 x7 + x4 +2/3 x3 z = -4 -13/3x7 - x4 +2/3 x3 x4 = 2 -1/3 x7 -1/3 x3 x1 = 2 +1/3 x7 - x4 -2/3 x3 x6 = 3 - x3 x5 = 0 -1/3 x7 + x4 +2/3 x3 entry variable x3 exit variable x6 (could also be x1): x3 = 3 - x6 z = -2 -13/3x7 - x4 -2/3 x6 x2 = 1 -1/3 x7 +1/3 x6 x1 = 0 +1/3 x7 - x4 +2/3 x6 x6 = 3 - x6 x5 = 2 -1/3 x7 + x4 -2/3 x6 Optimal solution: x1 = 0, x2 = 1, x3 = 0, x4 = 0, x5 = 2, x6 = 3, x7 = 0 with optimal value z = -2. 4. Two Phase Simplex maximize -3x1 -2x2 + x3 subject to x1 + x2 = 3 -x1 -3x2 + 2x3 + x4 = 1 Artificial problem maximize -a1 -a2 subject to a1 = 3 - x1 - x2 a2 = 1 + x1 +3 x2 -2 x3 - x4 Equivalently z = -4 -2 x2 + 2 x3 + x4 a1 = 3 - x1 - x2 a2 = 1 + x1 +3 x2 - 2 x3 - x4 entry variable x4 exit variable a2: x4 = 1 + x1 + 3x2 - 2x3 - a2 z = -3 + x1 + x2 - a2 a1 = 3 - x1 - x2 x4 = 1 + x1 +3 x2 - 2 x3 - a2 entry variable x1 exit variable a1: x1 = 3 - a1 - x2 z = 0 - a1 - a2 x1 = 3 - a1 - x2 x4 = 4 - a1 +2 x2 - 2 x3 - a2 Basic feasible solution: x1 = 3, x2 = 0, x3 = 0, x4 = 4. maximize -3x1 -2x2 + x3 subject to x1 = 3 - x2 x4 = 4 + 2x2 - 2x3 Equivalently z = -9 + x2 + x3 x1 = 3 - x2 x4 = 4 +2 x2 -2 x3 entry variable x2 exit variable x1: x2 = 3 - x1 z = -6 - x1 + x3 x2 = 3 - x1 x4 = 10 -2 x1 -2 x3 entry variable x3 exit variable x4: x3 = 5 -x1 -1/2 x4 z = -1 -2 x1 -1/2 x3 x2 = 3 - x1 x3 = 5 - x1 -1/2 x4 Optimal solution: x1 = 0, x2 = 3, x3 = 5, x4 = 0. with optimal value z = -1 5. Corner Cases The result is unbounded: Entry variable x1 has no exit row. We can increase x1 without limit and hence also increase the objective function without limit 6. Standard Form Again x1 and x3 are nonnegative, but x2 we replace with x2 = x2p - x2m maximize - 2x1 + 2 x2p - 2 x2m subject to x1 + x2p - x2m = 3 x1 - s1 = 3 - x2p + x2m + s2 = 1 x1 -2 x2p +2 x2m + x3 + s3 = 6 x1, x2p, x2m, x3 >= 0