From The Student Room

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > The Simplex Algorithm

---

The simplex algorithm is used to solve linear programming problems when the graphical method cannot be used - on computers or when there are more than 2 variables to plot.

Contents 1 How the simplex algorithm works 2 Slack variables 2.1 Example 3 Formulating the tableau 4 The Pivot 5 Solving the equations 6 Also See 7 Comments

How the simplex algorithm works

The simplex algorithm takes the equations of the constraints and solves them simultaneously to find the nodes. It then works out whether that node maximises the objective function.

Slack variables

In order to solve the simultaneous equations, the constraints must be in a format without inequalilities. Therefore slack variables are used, to stand for an arbitrary number to "make up the difference" between one side and the other. The letters s and t are used for these.

Example

• would become
• would become

Formulating the tableau

The equations are then put into a computer-readable form - a tableau. This is a table with one row for each equation and a column for each variable. The coefficients of all the variables are listed in the cells.

The top row is always the equation for the objective function. The next 2 rows are the equations of the constraints.

Rearrange the equations so that they all have the constants on the right hand side. Then enter the equations into the tableau.

The objective function is made to equal P if it is to be maximised, and -P it is to be minimised (e.g. maximise would become and would be entered on the tableau as ).

The Pivot

When you have formulated the tableau, choose any column which has a negative number in the top row. Our aim now is to manipulate the equations to eliminate this chosen variable from 2 of the equations. To do this, first choose a pivot - divide the k (constant) values for each equation by their respective values in the selected columns. The pivot is the value of the selected column of whichever equation gives the smallest answer to this calculation.

Solving the equations

Divide the pivot row by the pivot to get 1 in the selected column. Add a multiple of the pivot eqn to the other equations to get the pivot column to equal 0. If the top row has no negative elements, stop. If it still contains negative elements, find a new pivot from the newest 3 equations and repeat the procedure.

Find the maximum by interpreting the tableau as in the picture. P equals the k value in the top row; non-zero elements in the top row equal zero. Use the other two equations to find the remaining values.

Also See

See the other D1 notes:

1. Algorithms
2. Sorting algorithms
3. Packing algorithms
4. Graphs and networks
5. Minimum connector problems
6. The shortest path
7. Route inspection
8. The travelling salesman problem
9. Linear programming
10. The simplex algorithm

Comments