The Simplex Method - Intuitively
A Random Walk with the Simplex Method
Let us try to form a geometric intuition for the Simplex method.
We will define an LP problem, and geometrically traverse the steps the Simplex method might take to solve for the optimum solution.
Let us define a problem:
The Objective function is:
The Constraints are defined by the three inequalities
The Feasibility region for this LP problem is plotted below:
The corner points of the Feasibility Region are:
# name x1 x2
# 1 A 0.000 0.0000
# 2 B 10.000 0.0000
# 3 C 5.625 3.9375
# 4 D 2.625 5.4375
# 5 E 0.000 1.5000
Recall that:
- The optimum in an LP problem is found on the boundary, at one of the vertices
- At each of these vertices one or more constraints (
) is tight, i.e. there is no slack.
Procedure
We start with an arbitrary point on the edge of the Feasibility Region.
is a common choice. At this point, since all variables are , the objective function is also .We (arbitrarily) decide to move along the boundary of the Feasibility Region, to another FSP. We arbitrarily chose the
axis, and set/keep . We now wish to find out the coordinate of the next FSP point. This would be at the intersection of the axis and one of the Constraint lines.
All the three Constraint Lines would possibly intersect the axis. We need to choose that intercept point that has the smallest, non-negative intercept value. (Why?)
So, which Constraint Line intersects the axis at the smallest value? Is it point B, or point F?
To find out, we substitute in each of the Constraint equations, and solve for the :
Negative values for any variable are not permitted. So the smallest value of intercept is for Constraint . We therefore move to point . At this point the objective function has improved to:
- We now start from Point B, and move to the next nearest point. In
identical fashion to Step2, we βimagineβ that we move along a new
axis defined by:
We express in terms of with : As in Step 2, we substitute this equation into the other two constraints, and : As before we choose the smaller of the two intercepts, so . Calculating for , we get point . At this point the objective function has improved to:
- We now proceed along the constraint line
towards the next point. In identical fashion to Step 2 and 3, we βimagineβ that we move along a new axis defined by: Again, We express in terms of with this time: As in Step 2 and, we substitute this equation into the other constraint, the only remaining : Calculating for , we get point . At this point the objective function hasimproveddecreased to: Since this value for the Objective function is smaller than that at the previous point, our search terminates and we decide that Point is the optimal point.
So the final result is: The final result is plotted below:
Summary
The essence of this βintuitive methodβ can be captured as follows:
- Start from a known simple point on the edge of Feasibility Region,
e.g. (0,0), since the two coordinate axes frequently form two edges
to the Feasibility Region.
- Move along one of the axis to find a first adjacent edge point. This
adjacent point corresponds to the βtighteningβ of one or other of
the Constraint equations(i.e. slack = 0 for that Constraint)
- Calculate the Objective function at that point.
- Use this new point as the next starting point and move along the
Constraint line from the previous step.
- Repeat step 2 and 3, calculating the Objective function each time.
- Keep the solution point where the objective function hits a maximum, i.e. when moving to the next point reduces the value of the Objective function.