A Simplex Iteration
John Mitchell

Consider the linear programming problem

$$\begin{array}{lrcrcrcrcl} \min & x_1 & + & x_2 & + & x_3 &... ... 3x_4 &=& 1 \\ &&&&& x_i &\geq & 0 \;\;\forall i \end{array}$$

We have

$$A = \left[\begin{array}{rrrr}1&2&-1&-1\\ -1&-5&2&3\end{array... ...nd } c^T = \left[\begin{array}{rrrr}1&1&1&1\end{array}\right].$$

Columns 1 and 3 of A are linearly independent, so we initialize with B equal to these two columns:

$$B = \left[\begin{array}{rr}1&-1\\ -1&2\end{array}\right],$$

and then

$$N = \left[\begin{array}{rr}2&-1\\ -5&3\end{array}\right], \... ...quad x_N = \left[\begin{array}{r}x_2\\ x_4\end{array}\right].$$

The corresponding basic solution is obtained by calculating B^-1b:

$$x_B = \left[\begin{array}{r}x_1\\ x_3\end{array}\right] = B^... ...array}\right] = \left[\begin{array}{r}3\\ 2\end{array}\right].$$

Thus, we have a basic feasible solution x¹=[3, 0, 2, 0]^T. The objective function value is

c^Tx¹=c_B^TB^-1b=5.

We next express the LP in the form

$$\begin{array}{lccrcl} \min & c_B^TB^{-1}b & + & (c_N^T-c_B... ...-1}Nx_N & = & B^{-1}b \\ &&& x_B, x_N & \geq & 0 \end{array}$$

This requires the following calculations:

$$B^{-1}N = \left[\begin{array}{rr}2&1\\ 1&1\end{array}\right]... ...right] = \left[\begin{array}{rr}-1&1\\ -3&2\end{array}\right].$$

and

$$c_N^T-c_B^TB^{-1}N = [1, \; 1] - [1, \; 1] \left[\begin{arra... ... -3&2\end{array}\right] = [1, \; 1] - [-4, \; 3] = [5, \; -2].$$

(This vector is the vector of reduced costs.) Thus we can express our original linear programming problem equivalently as

$$\begin{array}{llrcrcrcrcl} \min & 5 &&&&+& 5x_2 & - & 2x_4 \... ...4 & = & 2 \\ &&&&&& x_i & \geq & 0 \;\; \forall i. \end{array}$$

(Notice the order of the variables.) Since the cost of x₄ is negative in this formulation and x₄ is currently zero, we can try to improve the solution by increasing x₄. The first constraint tells us that we have (with x₂=0)

x₁ = 3-x₄,

so we can't make x₄ any bigger than 3 without violating the nonnegativity restriction on x₁. Similarly, the second constraint tells us that we have

x₃ = 2 - 2x₄,

so we can't make x₄ any bigger than 1 without violating the nonnegativity restriction on x₃. (This examination to find the largest possible increase in the variable entering the basis is known as the minimum ratio test.) Thus, we set x₄ to 1 and remove x₃ from the basis, giving a new basis of x₁ and x₄. (This is a pivot from one basic feasible solution to another.)

We can now repeat the whole process over again from the new basic feasible solution. The matrix B now consists of columns 1 and 4 of A:

$$B = \left[\begin{array}{rr}1&-1\\ -1&3\end{array}\right],$$

We have

$$N = \left[\begin{array}{rr}2&-1\\ -5&2\end{array}\right], \... ...quad x_N = \left[\begin{array}{r}x_2\\ x_3\end{array}\right].$$

The corresponding basic solution is obtained by calculating B^-1b:

$$x_B = \left[\begin{array}{r}x_1\\ x_4\end{array}\right] = B^... ...array}\right] = \left[\begin{array}{r}2\\ 1\end{array}\right].$$

Thus, we have the basic feasible solution x²=[2, 0, 0, 1]^T. The objective function value is

c^Tx²=c_B^TB^-1b=3,

which is indeed an improvement on the previous objective function value of 5. We next express the LP in the form

$$\begin{array}{lccrcl} \min & c_B^TB^{-1}b & + & (c_N^T-c_B... ...-1}Nx_N & = & B^{-1}b \\ &&& x_B, x_N & \geq & 0 \end{array}$$

This requires the following calculations:

$$B^{-1}N = \frac{1}{2}\left[\begin{array}{rr}3&1\\ 1&1\end{ar... ...frac{1}{2}\left[\begin{array}{rr}1&-1\\ -3&1\end{array}\right]$$

and

$$c_N^T-c_B^TB^{-1}N = [1, \; 1] - \frac{1}{2}[1, \; 1] \left[... ...\ -3&1\end{array}\right] = [1, \; 1] - [-1, \; 0] = [2, \; 1].$$

Thus, we have another equivalent formulation of our original linear programming problem:

$$\begin{array}{llrcrcrcrcl} \min & 3 &&&&+& 2x_2 & + & x_3 \\... ...3 & = & 1 \\ &&&&&& x_i & \geq & 0 \;\; \forall i. \end{array}$$

Since the reduced costs are all nonnegative, this solution is actually optimal.

Note: Let z be the objective function, so -z+x₁+x₂+x₃+x₄=0. Then the pivot we performed can be calculated exactly like a pivot in Gaussian elimination, by pivoting on x₄ in the second constraint of the formulation:

$$\begin{array}{llrcrcrcrcr} \min & -z &&&&+& 5x_2 & - & 2x_4 ... ...4 & = & 2 \\ &&&&&& x_i & \geq & 0 \;\; \forall i. \end{array}$$

becomes

$$\begin{array}{llrcrcrcrcr} \min & -z &&&&+& 2x_2 & + & x_3 &... ...3 & = & 1 \\ &&&&&& x_i & \geq & 0 \;\; \forall i, \end{array}$$

after reordering the columns.

Note: In a practical implementation, only quantities that are actually needed are calculated, and the quantities are calculated more efficiently. For example, the inverse matrix B^-1 is never calculated explicitly.