Carry out the Simplex Algorithm
The Simplex Algorithm is a method of solving linear programming problems. In plain English, it's used to reach a goal while also having constraints. Since this is math, we're dealing with numbers and the formulas just use add, subtract and multiply (which is why it is called linear programming).
Typical uses of the simplex algorithm are to find the right mix of ingredients at the lowest cost (the goal). If the ingredients are food, the constraints would be having at least so many calories, so much protein, fats, carbohydrates, vitamins, minerals, etc. Of course the simplex algorithm is applicable to much more than food.
Steps
- First you need to look at what you're trying to work out. Do you already have the function you are maximising/minimising and the constraint inequalities?
- Once you have these you need to introduce slack variables into the inequalities. Slack variables turn inequalities into equations and usually use the letters s onwards (though you can use any letter you like), for example:
- 2y+4x<=8 becomes 2y+4x+s=8
- 6y+2x<=28 becomes 6y+2x+t=28
- The constraint should be in the form P=x+y(+z) which you need to rearrange to become 0=P-x-y(-z). for example:
- P=2x+2y becomes 0=P-2x-2y
- Once you have your data you need to construct the tableau. This is constructed as follows:
| P | x | y | (etc) | s | t | (etc) | l | equation |
|---|
- You then need to put your data into the tableau. Your first row will be what you are maximising, the rows below the constraints. If you have that letter in wat goes in that row the number goes into that column. If the letter is not there put a 0.
| P | x | y | s | t | l | equation |
|---|---|---|---|---|---|---|
| 1 | -2 | -2 | 0 | 0 | 0 | (1) |
| 0 | 4 | 2 | 1 | 0 | 8 | (2) |
| 0 | 2 | 6 | 0 | 1 | 28 | (3) |
- Now the fun bit. Pick a column, any column, so long as the top number is negative (please note that you can't use l) For the sake of the example I'm going to use x, but if you're bored you can use y just to be different (if you have a lot of columns to choose from I'd recommend starting at the left, makes life easier).
- For each row (for which the number in your chosen column is positive) divide the number in the l column by the number in your chosen column.
- For the row which gave the smallest value, ring the number in your chosen column. (In my example it would be 4) This number is called the pivot.
- At this point you need to draw a line in your tableau so you can write in the first iteration. Leave a line for equation 4 and divide (2) by the pivot (in this case 4) then write that into the space for (5)
- You now need to make all the values in the x column (apart from your pivot line) equal to 0. You do this by combining appropriate multiples of the pivot with the original equation for each line. For example (4)=(1)+0.5(2) Once you have done this your tableau should look like this:
| P | x | y | s | t | l | equation |
|---|---|---|---|---|---|---|
| 1 | -2 | -2 | 0 | 0 | 0 | (1) |
| 0 | 4 | 2 | 1 | 0 | 8 | (2) |
| 0 | 2 | 6 | 0 | 1 | 28 | (3) |
| 1 | 0 | -1 | 0.5 | 0 | 4 | (4)=(1)+0.5(2) |
| 0 | 1 | 0.5 | 0.25 | 0 | 2 | (5)=(2)/4 |
| 0 | 0 | 5 | -0.5 | 1 | 24 | (6)=(3)-0.5(2) |
- If you still have negative numbers on your top row (not including column l) repeat steps 6-8 until all your top row are positive. Once this is the case you have completed your simplex problem.
- You read the solution of your simplex problem very simply. Ignore the slack variables. The last (l) column (of the final iteration) contains the values for the function (P) and non-zero variables.
Tips
- Once you can use Simplex just be happy that you can use it and go boast to all your friends who can't. Never under any circumstances try to write a wikiHow about it.
Warnings
- The name is deceptive. Simplex is not simple. Normally, it is a graduate level subject in the field Operations Research, though some exam boards also include it in the A-level maths module D2.
- Real life uses of the simplex algorithm are very important to business (their answers can save millions) but they are also huge and are only done on computers.
- May result in large amounts of stress. In graduate school the simplex algorithm is done manually by students just once. From then on it's done on computers.
- It is very easy to make mistakes and very hard to find them. Don't rush Simplex!
- Only apply to situations where decimal quantities make sense. A third of a volleyball or half a horse doesn't make sense.
- The "answer" should sometimes be rejected on political, social or psychological grounds. Linear programming is applied to developing countries in designing the "mix" of industries in the economy. An "answer" of a single industry or agricultural crop for a country is deficient on stability grounds.
Things You'll Need
- A pen/pencil
- Paper
- Ruler
- Calculator (unless you're very good with numbers)
