The Simplex Method - Intuitively

What is the Simplex Method?

To be written up.

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:

Maximise 7.75x1+10x2 Subject to{C1:βˆ’3x1+2x2<=3C2:2x1+4x2<=27C3:9x1+10x2<=90x1,x2>=0

The Objective function is: 7.75x1+10x2

The Constraints are defined by the three inequalities C1::C3. In order to plot these, we convert the inequalities to equalities and plot these as lines. Each line splits the x1:x2 plane into two half-planes. The inequality part is then taken into account by choosing the appropriate half-plane created by the equation. The intersection of all the half-planes defined by the constraints is the Feasibility Region.

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 (C1::Cn) is tight, i.e. there is no slack.

Procedure

  1. We start with an arbitrary point on the edge of the Feasibility Region. A=(0,0) is a common choice. At this point, since all variables are 0, the objective function is also 0.

  2. We (arbitrarily) decide to move along the boundary of the Feasibility Region, to another FSP. We arbitrarily chose the x1 axis, and set/keep x2=0. We now wish to find out the x1 coordinate of the next FSP point. This would be at the intersection of the x1 axis and one of the Constraint lines.
    All the three Constraint Lines would possibly intersect the x1 axis. We need to choose that intercept point that has the smallest, non-negative x1 intercept value. (Why?)
    So, which Constraint Line intersects the x1 axis at the smallest value? Is it point B, or point F?
    To find out, we substitute x2=0 in each of the Constraint equations, and solve for the x1:
    {C1:βˆ’3x1+2Γ—0=3 =>x1=βˆ’1C2:2x1+4Γ—0=27 =>x1=13.5 Point FC3:9x1+10Γ—0=90 =>x1=10 Point B
    Negative values for any variable are not permitted. So the smallest value of intercept is x1=10 for Constraint C3. We therefore move to point B(10,0). At this point the objective function has improved to:

Objective=7.75Γ—10+10Γ—0=77.5 at Point B

  1. 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:
    Intercept=Point B(10,0) Equation=Constraint C3:9x1+10x2=90 We express x1 in terms of x2 with C3: C^3:x1=90βˆ’10x29 As in Step 2, we substitute this equation C^3 into the other two constraints, C1 and C2: {C1:βˆ’3Γ—90βˆ’10x29+2x2=3 =>x2=6.18 Point KC2:2Γ—90βˆ’10x29+4x2=27=>x2=3.93 Point C As before we choose the smaller of the two intercepts, so x2=3.93. Calculating for x1, we get point C(5.63,3.93). At this point the objective function has improved to:

7.75Γ—5.63+10Γ—3.93=82.9 at Point C

  1. We now proceed along the constraint line C2 towards the next point. In identical fashion to Step 2 and 3, we β€œimagine” that we move along a new axis defined by: Intercept=Point C(5.63,3.93) Equation=Constraint C2:2x1+4x2=27 Again, We express x1 in terms of x2 with C2 this time: C^2:x1=27βˆ’4x22 As in Step 2 and, we substitute this equation C^2 into the other constraint, the only remaining C1: C1:βˆ’3Γ—27βˆ’4x22+2x2=3 =>x2=5.44 Point D Calculating for x1, we get point C(2.63,5.44). At this point the objective function has improved decreased to: 7.75Γ—2.63+10Γ—5.44=74.8 at Point D Since this value for the Objective function is smaller than that at the previous point, our search terminates and we decide that Point C(5.63,3.93) is the optimal point.
    So the final result is: x1(max)=5.63 x2(max)=3.93 Maximum Objective Function Value=82.9 The final result is plotted below:

Summary

The essence of this β€œintuitive method” can be captured as follows:

  1. 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.
  2. 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)
  3. Calculate the Objective function at that point.
  4. Use this new point as the next starting point and move along the Constraint line from the previous step.
  5. Repeat step 2 and 3, calculating the Objective function each time.
  6. 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.
Previous
Next