Federico Mengozzi

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\]

Go to top