2. The Simplex Method

Constructing Simplex Problem

To begin using the Simplex method, we must first introduce some slack variables for each constant, turning each inequality into an equation called the slack form:

$$\boxed{\begin{array}{rl}3x+2y& \le 15\\ 2y-x& \le 5\\ x+2y& \le 7\end{array}}\to \boxed{\begin{array}{rl}3x+2y+s_1& =15\\ 2y-x+s_2& =5\\ x+2y+s_3& =7\end{array}}$$

We can now rewrite this to find each variable:

$$\begin{array}{rl}{s}_1& =3x+2y-15\\ s_2& =2y-x-5\\ s_3& =x+2y-7\end{array}$$

Greater than inequality.

If we have an inequality such as $8x+2y\ge 24$, we must either re-arrange it to be $\le$ or we use a negative slack variable $-s_x$.

We can also turn our objective function into a variable by treating it as an equation for some new dependent variable $C$:

$$\text{Maximise }2x+3y\to C=2x+3y$$

Or otherwise, $-2x-3y+C=0$.

Simplex Method

1. Construct the initial tableau from the slack form of the linear program, along with the equation for the cost $C$. A Tableau is a matrix representation of a system of linear equations:
2. Identify the column with the most negative coefficient in the final row, corresponding to the objective function (bottom row).
3. Calculate row quotients by dividing each of the entries in final column by the entries in the pivot column.
4. Identify the row with the smallest row quotient where both numerator and denominator are positive.
5. The ‘pivot’ value is picked from the overlap of the column and row we just found.
6. Apply the following row transformation: $$\text{Pivot row: }{R}_{\text{pivot}}\leftarrow \left(\begin{array}{c}\frac{1}{\text{current pivot value}}\end{array}\right)\times R_{\text{pivot}}$$ $$\text{All non-pivot rows: }{R}_{\text{i}}\leftarrow R_i-\left(\begin{array}{c}\frac{\text{current }{R}_i\text{ value}}{\text{current pivot value}}\end{array}\right)\times R_{\text{pivot}}$$

• Where $R_i$ are the elements in the row $i$.
• Where $R_{\text{pivot}}$ are the corresponding elements in the pivot row.
• Where $\text{current }{R}_i\text{ value}$ is the value of the element in the current row in the pivot column.
• Where $\text{current pivot value}$ is the current pivot value.

Start with pivot row

If we start with the pivot row, we can use it in our calculations for all the non-pivot rows. After using the pivot transformation above, use the following non-pivot transformation: $R_i\leftarrow R_i-\text{current }{R}_i\text{ value}\times R_{\text{new pivot}}$

7. Repeat steps 2-6 until you run out of valid pivot columns.
8. Read off the optimal solution by copying out each formula from the matrix.

Example

Theorems (not sure if need to expand on this)

There are two Theorems here:

• Worst-case termination time for Simplex Method is exponential.
• Linear Programming is solvable in Polynomial Time.