Consider the problem: Minimize ex subject to Ax = b, x > 0. Let B be a basis. After adding the redundant constraints xN - = 0, the following equations represent all the variables in terms of the independent variables xN:

The simplex method proceeds by choosing the most positive zjcj, say, zkck Then xk enters the basis and the usual minimum ratio test indicates that xBr eaves the basis. The foregoing array can be updated by column pivoting at yrk as ollows: 1. Divide the k th column (pivot column) by yrk. 2. Multiply the k th column (pivot column) by yrj and add to the j th column. 3. Multiply the k th column by br and add to the right-hand-side. 4. Remove the variable xk from the list of nonbasic variables and add xBr instead in its place. Note that no row designations are changed. This method of displaying the tableau and updating it is usually called the column simplex method. Show that pivoting gives the representation of all the variables in terms of the new nonbasic variables. In particular, show that pivoting updates the tableau such that the new cBB1NcN,B1N, B1b, and cBB1b are immediately available