# Simplex method in matrix form

A linear programming problem in the standard-form as the following $\text{maximize } \zeta: \sum\limits_{j=1}^n c_jx_j, \text{subject to}\\ \sum\limits_{j=1}^n a_{ij}x_j \leq b_i, i = 0, \dots, m\\ x_j \geq 0, i = 0, \dots, m$

It’s possible to indicate slack variable with different symbols $w_i$ or just implicitly $x_{n+i} = b_i - \sum\limits_{j=1}^n a_{ij}x_j, i = 0, \dots, m$

The same problem in matrix form becomes $\text{maximize } c^Tx, \text{subject to}\\ Ax = b, x \geq 0$

where

$A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & 1\\ a_{21} & a_{22} & \cdots & a_{2n} & & 1\\ \vdots & \vdots & \ddots & \vdots & & & \ddots\\ a_{m1} & a_{m2} & \cdots & a_{mn} & & & & 1 \end{bmatrix}$ and $b = \begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_m \end{bmatrix}, c = \begin{bmatrix} c_1\\ c_2\\ \vdots\\ c_n\\ 0_{n+1}\\ \vdots\\ 0_{n+m} \end{bmatrix}, x = \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n\\ x_{n+1}\\ \vdots\\ x_{n+m} \end{bmatrix}$

If we consider the set of index for the basic variables as $\mathcal{B}$ and the set of index for non-basic variable $\mathcal{N}$ the following is equivalent to the previous notation $A = \sum\limits_{j=1}^{n+m} a_{ij}x_j = (B = \sum\limits_{j \in \mathcal{B}} a_{ij}x_j) + (N = \sum\limits_{j \in \mathcal{N}} a_{ij}x_j) = \begin{bmatrix} B & N \end{bmatrix}$

and similarly $c = \begin{bmatrix} c_{\mathcal{B}}\\ c_{\mathcal{N}} \end{bmatrix}, x = \begin{bmatrix} x_{\mathcal{B}}\\ x_{\mathcal{N}} \end{bmatrix}$

this implies

$Ax = \begin{bmatrix} B & N \end{bmatrix} \begin{bmatrix} x_{\mathcal{B}}\\ x_{\mathcal{N}} \end{bmatrix} = Bx_{\mathcal{B}} + Nx_{\mathcal{N}} = b$ and $c^Tx = \begin{bmatrix} c_{\mathcal{B}}\\ c_{\mathcal{N}} \end{bmatrix} \begin{bmatrix} x_{\mathcal{B}}\\ x_{\mathcal{N}} \end{bmatrix} = c^T_{\mathcal{B}}x_{\mathcal{B}} + c^T_{\mathcal{N}}x_{\mathcal{N}} = \zeta$

Since $B$ is invertible it’s possible to write

$Bx_{\mathcal{B}} + Nx_{\mathcal{N}} = b \implies x_{\mathcal{B}} = B^{-1}b - B^{-1}Nx_{\mathcal{N}}$ and $\zeta = c^T_{\mathcal{B}}x_{\mathcal{B}} + c^T_{\mathcal{N}}x_{\mathcal{N}} =\\ c^T_{\mathcal{B}}(B^{-1}b - B^{-1}Nx_{\mathcal{N}}) + c^T_{\mathcal{N}}x_{\mathcal{N}} =\\ c^T_{\mathcal{B}}B^{-1}b - ((B^{-1}N)^Tc_{\mathcal{B}} - c_{\mathcal{N}})^Tx_{\mathcal{N}}$

From this, the basic solution is obtained by setting the “slack variables” to zero leading to $x^*_{\mathcal{N}} = 0\\ x^*_{\mathcal{B}} = B^{-1}b$