Example of Simplex Method

Taken from example 13.1 in the book Nocedal-Wright2006_Book_NumericalOptimization.pdf

---

Given the following optimization problem

$$\underset{x\in {\mathbb{R}}^2}{\min }-4x_1-2x_{2}s.t.\{\begin{array}{l}{x}_1+x_2\le 5\\ 2x_1+\frac{1}{2}{x}_2\le 8\\ x_1,x_2\ge 0\end{array}$$

We add a slack variable to rewrite this into

$$\underset{x\in {\mathbb{R}}^2}{\min }-4x_1-2x_{2}s.t.\{\begin{array}{l}{x}_1+x_2+x_3=5\\ 2x_1+\frac{1}{2}{x}_2+x_4=8\\ x_1,x_2,x_3,x_4\ge 0\end{array}$$

Which is the standard form for a LP problem

Link to original

Where

$$\begin{array}{rl}c& =\left[\begin{array}{c}-4\\ -2\\ 0\\ 0\end{array}\right]\\ A& =\left[\begin{array}{cccc}1& 1& 1& 0\\ 2& \frac{1}{2}& 0& 1\end{array}\right]\\ b& =\left[\begin{array}{c}5\\ 8\end{array}\right]\end{array}$$

Iteration 1

We then define the book-keeping needed for the Simplex Method

$$\begin{array}{rl}x& =(0,0,5,8{)}^T\\ \mathcal{B}& =\{3,4\}\\ \mathcal{N}& =\{1,2\}\end{array}$$

Where

$$B=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right],\text{and}N=\left[\begin{array}{cc}1& 1\\ 2& \frac{1}{2}\end{array}\right]$$

This gives

$$\begin{array}{rl}{x}_B& =B^{-1}b=\left[\begin{array}{c}5\\ 8\end{array}\right]\\ \lambda & =(B^T{)}^{-1}{c}_B=\left[\begin{array}{c}0\\ 0\end{array}\right]\\ s_N& =c_N-N^T\lambda =\left[\begin{array}{c}-4\\ -2\end{array}\right]\ngeqq 0\end{array}$$

We then have to change basis

• Pick the smallest element of $s_N$ : $s_1=-4$ → $q=1$
• Let $q=1$ enter $\mathcal{B}$ (leaving $\mathcal{N}$)
• Increase $x_1$ while $Ax=b$. $x_4$ becomes 0 first
• Let $p=4$ leave $\mathcal{B}$ and enter $\mathcal{N}$

Iteration 2

Now we get

$$\mathcal{B}=\{1,3\},\mathcal{N}=\{2,4\}$$

Giving us

$$B=\left[\begin{array}{cc}1& 1\\ 2& 0\end{array}\right],N=\left[\begin{array}{cc}1& 0\\ \frac{1}{2}& 1\end{array}\right]$$

and

$$\begin{array}{rl}{x}_N& =\left[\begin{array}{c}0\\ 0\end{array}\right],x_B=B^{-1}b=\left[\begin{array}{c}4\\ 1\end{array}\right]\\ \lambda & =(B^T{)}^{-1}{c}_B=\left[\begin{array}{c}0\\ -2\end{array}\right]\\ s_N& =c_N-N^T\lambda =\left[\begin{array}{c}-1\text{ <- q=2}\\ 2\end{array}\right]\end{array}$$

Where $q=2$ is the entering index and $p=3$ is the leaving index.

Iteration 3

Now we get

$$\mathcal{B}=\{1,2\},\mathcal{N}=\{3,4\}$$

Giving us

$$B=\left[\begin{array}{cc}1& 1\\ 2& \frac{1}{2}\end{array}\right],N=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$

and

$$\begin{array}{rl}{x}_N& =\left[\begin{array}{c}0\\ 0\end{array}\right],x_B=B^{-1}b=\left[\begin{array}{c}\frac{11}{3}\\ \frac{1}{3}\end{array}\right]\\ \lambda & =(B^T{)}^{-1}{c}_B=\left[\begin{array}{c}-\frac{4}{3}\\ -\frac{4}{3}\end{array}\right]\\ s_N& =c_N-N^T\lambda =\left[\begin{array}{c}\frac{4}{3}\\ \frac{4}{3}\end{array}\right]\ge 0\end{array}$$

Since $s_N\ge 0$ we get the Basic Optimal Point (BOP) (Aka the solution)

$$x^{\ast }=\left[\begin{array}{c}{x}_B\\ x_N\end{array}\right]=\left[\begin{array}{c}\frac{11}{3}\\ \frac{4}{3}\\ 0\\ 0\end{array}\right]$$