Linear Algebra and Its Applications · Problem 8.2.6

Linear Programming and Game Theory — Gilbert Strang

Mathematics · simplex-method-phase-i

Problem

Phase I finds a basic feasible solution to Ax=bAx = b (a corner). After changing signs to make b≥0b \geq 0, consider the auxiliary problem of minimizing w1+w2+⋯+wmw_1 + w_2 + \cdots + w_m, subject to x≥0x \geq 0, w≥0w \geq 0, Ax+w=bAx + w = b. Whenever Ax=bAx = b has a nonnegative solution, the minimum cost in this problem will be zero---with w∗=0w^* = 0. (a) Show that, for this new problem, the corner x=0x = 0, w=bw = 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∗x^*, w∗w^*. If w∗=0w^* = 0, then x∗x^* is the required corner in the original problem. (b) With A=[1 1]A = [1\ 1] and b=[3]b = [3], write out the auxiliary problem, its Phase I vector x=0x = 0, w=bw = b, and its optimal vector. Find the corner of the feasible set x1−x2=3x_1 - x_2 = 3, x1≥x2≥0x_1 \geq x_2 \geq 0, and draw a picture of this set.

Related theory

Browse the problem library