Phase I finds a basic feasible solution to Ax = b (a corner). After changing signs to

Chapter 8, Problem 8.2.6

(choose chapter or problem)

Phase I finds a basic feasible solution to Ax = b (a corner). After changing signs to make b 0, consider the auxiliary problem of minimizing w1 + w2 + + wm, subject to x 0, w 0, Ax +w = b. Whenever Ax = b has a nonnegative solution, the minimum cost in this problem will be zerowith w = 0. (a) Show that, for this new problem, the corner x = 0, w = b is both basic and feasible. Therefore its Phase I is already set, and the simplex method can proceed to find the optimal pair x , w . If w = 0, then x is the required corner in the original problem. (b) With A = [1 1] and b = [3], write out the auxiliary problem, its Phase I vector x = 0, w = b, and its optimal vector. Find the corner of the feasible set x1x2 = 3, x1 x2 0, and draw a picture of this set.