# Help please - Simplex algorithm

Discussion in 'Mathematics' started by Informant, Mar 3, 2011.

1. ### InformantNew commenter

When choosing a pivot, the AQA text book (Discrete Mathematics 2) says "Select any column (except the last one) whose top element is negative"......However a question which then follows only produces an optimal solution if a pivot is selected from the y column as shown below
P x y s t l
1 -1 -4 0 0 0
0 1 <u>3</u> 1 0 15
0 2 1 0 1 12
This correctly produces x=0 and y=5 gives P=20, but taking a pivot from the x column doesn't lead to this answer.
I have browsed the net and found that some sites suggest you must take a pivot from the column with the most negative value. However this is clearly not always necessary and even on-line simplex engines don't always do this.
Any suggestions on what I can say to my students who have stumbled into this problem?

2. ### InformantNew commenter

When choosing a pivot, the AQA text book (Discrete Mathematics 2) says "Select any column (except the last one) whose top element is negative"......However a question which then follows only produces an optimal solution if a pivot is selected from the y column as shown below
P x y s t l
1 -1 -4 0 0 0
0 1 <u>3</u> 1 0 15
0 2 1 0 1 12
This correctly produces x=0 and y=5 gives P=20, but taking a pivot from the x column doesn't lead to this answer.
I have browsed the net and found that some sites suggest you must take a pivot from the column with the most negative value. However this is clearly not always necessary and even on-line simplex engines don't always do this.
Any suggestions on what I can say to my students who have stumbled into this problem?

3. ### pwc9000New commenter

I am by no means an expert on this - but I recently taught this for the first time in Edexcel D1. My understanding is to choose the most negative value in the objective row to identify the pivot column - explaining the choice in the example you've given. I would imagine choosing the x column to pivot would require a further iteration to achieve an optimal solution.

4. ### fieldextensionNew commenter

Implementing the simplex alorithm for the 2D example you have provided corresponds to moving between the vertices of the following enclosed region at each iteration, always increasing P at each new iteration and stopping when the vertex which provides the maximum value of P has been located:
x>=0
y>=0
x+3y<=15 (i.e. s>=0)
2x+y<=12 (i.e. t>=0)

The initial tableau you are provided with gives you information about the value of P at the origin. We can see from your three equations that at the origin (x=0, y=0) P is zero and the slack variables s and t are 15 and 12 respectively. At each one of the 4 vertices in the region enclosed, two of the 4 (control and slack) variables will be zero.
From the equation P-x-4y=0 we can see that P can be increased from zero by increasing either x or y, which on the graph can be thought of as moving from the origin along an edge to a different vertex (where one of s or t will be zero) and examining the value of P at that vertex. Which vertex should we move to? It does not ultimately matter (you will get to the optimal vertex eventually so long as you pick a column with a negative entry at the top - i.e always move to a new vertex which involves an increase in P) but the "P gradient" in the y direction is bigger than in the x direction. That is, we can see from the objective row that if y is increased by 1 then P increases by 4, but if x is increased by 1 then P increases by only 1. So if we are guessing how to make P as large as possible it makes more sense to increase y and leave x as zero (i.e. move upwards on the graph).
So after 1 iteration you move up the y axis to the point (0,5) and it turns out that this vertex corresponds to an opimal (i.e. maximal) solution for P. By examining the objective row in the final tableau you can see that P cannot be increased by increasing the letters which appear in that row (the lack of negative signs ensures this).
I recommend that you teach the simplex algorithm by reference to graphs, certainly for 2D problems.

In 3D (i.e. with x, y and z) the constraints are planes and the feasible region is a polyhedron. The algorithm involves moving between vertices in a polyhedron to find the vertex which provides an optimal solution (where the objective function - which corresponds to a set of parallel planes - intersects the polyhedron and provides a maximum value of P). With more than 3 control variables the constraint "object" is an n-dimensional polytope and geometrical considerations are less helpful for understanding the implementation of the algorithm.
I hope that helps. You have my sympathy - I know firsthand that A-Level textbooks are usually terrible at providing any understanding of the Simplex algorithm, rather than merely a recipe for how to implement it.

5. ### KYPNew commenter

As you say, it is still not optimal, because you still have a negative value in the objective function row. You have to do another iteration! If you look at the graph, the values above are where the two constraint functions intersect. What this problem demonstrates is how you may well get to the optimal solution quicker by choosing the most negative value in the objective function row as your pivot column.(If the optimal solution in this case had been at the intersection of the two constraints, it would have taken two iterations whichever way round the vertices you went!)

6. ### fieldextensionNew commenter

As has been pointed out, you need a third iteration. Starting from the origin you have gone the "long way round" the four vertices of the feasible region (anticlockwise rather than clockwise in this case). The objective row after your second iteration is:
P+ 1.4s - 0.2t = 18.6
You can see that P can be increased further by increasing t. One more iteration will increase t and bring you to the vertex on the y-axis, which provides the optimal solution.
It doesn't matter whether you choose the most negative entry in the objective row or not, but you will find that choosing the most negative entry is quicker more often than not.
Think of it like this - you are trying to get to the top of the highest hill in your town and can go only either East or West. You are short sighted so cannot be sure which direction is the best to go. You see that East for the first few metres there is a steep upward climb and West for the first few metres there is a gentle upward climb. Based on this information alone, it makes more sense to guess that going East is best, even though going West could well be better and so long as you can change direction neither initial strategy precludes you from eventually finding the highest point.

7. ### InformantNew commenter

Great replies - Finally I am enlightened. Yes this all makes perfect sense and I look forward to sharing this with my students. I'd overlooked the third iteration as I was thinking about x and y, so I overlooked the negative slack variable. Thanks a lot.

8. ### Daisy74

When looking for the pivot - if you are not told which column to use.
Look for the most negative entry in the objective row - this identifies the pivotal column.
Calculate the value of
"the figure in the value column" divided by "the entry in the pivotal column" for each row.
Known as theta value in Edexcel version of simplex. ( I always have an extra column at the right of the tableau for this entry)
Chose the row that gives the smallest answer to identify the pivotal row.
The pivot is now the entry at the intersection of the pivotal column and the pivotal row.
Hope this helps