The Revised Simplex Method in Matrix Form

Performs one iteration of the simplex method using matrix operations: identify the basic feasible solution via $x_B = B^{-1}b$ , compute reduced costs to select the entering variable, then apply the minimum ratio test to find the leaving variable.

Step 1 of 157%

Tutorial

Introduction

Consider a linear program in standard form:

\min\; c^T x \quad \text{subject to} \quad Ax = b,\; x \geq 0,

where $A$ is $m \times n$ with $m < n$ , $b \in \mathbb{R}^m$ , and $c \in \mathbb{R}^n$ .

The revised simplex method tracks the current vertex of the feasible region using matrix operations rather than a tableau. At each iteration, we maintain a basis -- a choice of $m$ linearly independent columns of $A$ forming an invertible $m \times m$ matrix $B$ . The remaining columns form $N$ , so

A = [\,B \mid N\,], \quad x = \begin{bmatrix} x_B \\ x_N \end{bmatrix}, \quad c = \begin{bmatrix} c_B \\ c_N \end{bmatrix}.

The constraint $Ax = b$ becomes $Bx_B + Nx_N = b$ . Setting the nonbasic variables $x_N = 0$ gives the basic solution

x_B = B^{-1}b, \qquad x_N = 0.

If $x_B \geq 0$ , this is a basic feasible solution (BFS) and corresponds to a vertex of the feasible polytope.

For example, with

A = \begin{bmatrix} 2 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix},\quad b = \begin{bmatrix} 5 \\ 3 \end{bmatrix},

and basis indices $\{3, 4\}$ , the basis matrix is $B = I$ , so $x_B = b = (5, 3)^T$ . The BFS is $x = (0, 0, 5, 3)^T$ .