Simplex Algorithm
Simplex Algorithm is used to do linear programming and find the solution to a constrained optimization problem. Important concepts here: basic / non-basic variable, pivoting / entering variable and leaving variable.
For optimisation: you make use of a tableau, with all the constraint and the optimisation objective functions. Each time you pivot the variable with the most negative value coefficient in that objective function. Furthermore, to decide which row to set the entering variable to 1 choose the one with the smallest ratio of the constraint-value and the entering-variable coefficient. Then remove all the entering variable in other rows (just like Gaussian Elimination). Detailed process is in the following video of an inequality constraints linear optimisation task.
Inequality constraints optimisation example:
Part 1 of the video
Part 2 of the video
Equality constraints optimisation process:
To get an optimal solution, it is necessary to have a basic solution as a starting point. This means, that the number of constraint must be equal to the number of basic variables. Thus every constraint have to have a positive slack variable. We would add slack variable for each of the equality constraints and then add a pseudo-objective function with coefficient of the slack variable set to 1 all the basic variable or the actual variable’s coefficient to 0 and of-course the value to be zero initially.
For example:
\( x_1 + x_2 + x_3 = 20, \quad x_1 + 3x_2 + 5x_3 = 50 \)
we would add two slack variables for each of the constraint functions and first optimise with respect to this tableau:
\( \begin{bmatrix} 1 & 1 & 1 & 1 & 0 & 20 \newline 1 & 3 & 5 & 0 & 1 & 50 \newline 0 & 0 & 0 & 1 & 1 & 0 \newline \end{bmatrix} \)
First minus row 3 with row 2 and row 1 to let slack variable becomes zero and then we would like to pivot each basic variable until the last row’s coefficient becomes again 0 in basic variable, 1 in slack variable.
After that, we get rid of the last line and replace with our objective function, then we optimise normally just as what we did in inequality ones. Additionally, the slack variables can also be discarded. The optimisation ends when all the coefficient in the objective function becomes positive. The value of the objective function therefore becomes our maximum or minimum negative value. Furthermore, look at each column to find which variable is going to be zero, if more than one 1 or -1, then this variable would be zero. If not, then just read out the value to get the final optimum solution.
