Graphical motivation for the

simplex method
Recap from last lecture
• max 𝑧𝑧 = 5𝑥𝑥1 + 4𝑥𝑥2
Subject to:
6𝑥𝑥1 + 4𝑥𝑥2 ≤ 24
𝑥𝑥1 + 2𝑥𝑥2 ≤ 6
−𝑥𝑥1 + 𝑥𝑥2 ≤ 1
𝑥𝑥2 ≤ 2
𝑥𝑥1 , 𝑥𝑥2 ≥ 0
• Step 1. Draw the constraints and
define the feasible region.
• Step 2a. Draw the gradient
• Step 2b. Move the isoprofit line
parallel to itself in the direction
indicated by the gradient.
• Step 3c. Stop when the isoprofit line
crosses the feasible region at
boundary points only.
• Step 3d. Find the optimal solution.
Remarks
• A feasible region is :
• Unbounded if the feasible region is infinite
• Bounded if the feasible region is finite
• Infeasible if the feasible region is empty

• A solution to the LP can be:

• Finite
• Infinite (this can only happen when the feasible region is unbounded)
• Doesn’t exist in case the feasible region was empty
Writing LP in standard form
• In this form all constraints are transformed into equalities.
• All decision variables have to be positive
• This is achieved by adding slack variables for “≤” constraints and
surplus variables for “≥” constraints.
• For example, the LP
max =
Z 3 x1 + 4 x2
subject to 3 x1 + 2 x2 ≤ 6
x1 + 4 x2 ≤ 4
x1 ≥ 0, x2 ≥ 0

is written in standard form as

max =
Z 3 x1 + 4 x2
subject to 3 x1 + 2 x2 + S1 =
6
x1 + 4 x2 + S2 =
4
S1 ≥ 0, S 2 ≥ 0, x1 ≥ 0, x2 ≥ 0
Example 1
• The LP
min Z= x1 + x2
subject to x1 + 2 x2 ≥ 6
2x1 + x2 ≥ 4
x1 ≤3
x1 ≥ 0, x2 ≥ 0

• is written in standard form as

min Z= x1 + x2
subject to x1 + 2 x2 − S1 =
6
2x1 + x2 − S2 =
4
x1 + S3 =
3
Si ≥ 0, xi ≥ 0
Example 2
• Write the following LP into standard form:
• max 𝑍𝑍 = 3𝑥𝑥1 + 2𝑥𝑥2
𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑡𝑡𝑡𝑡
𝑥𝑥1 + 𝑥𝑥2 ≤ 2
𝑥𝑥1 𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢
−2 ≤ 𝑥𝑥2 ≤ 1
Definitions

• A constraint is binding at a given point if

this point is on the constraint (i.e., the
point’s coordinates satisfy the constraint
as an equality).
• In a LP with n decision variables, a
corner point is a point where n or more
constraints are binding.
• Points A,B,C,D,E,F are corner points
• At point F constraint 3 and 5 are
binding
Graphical Motivation for the simplex method
• Consider the following LP written in standard form
• Choose an initial corner point feasible solution (i.e.,
basic feasible solution). In the current example,
O(0, 0) can serve as such solution.
• Choose an initial corner point feasible solution (i.e.,
basic feasible solution). In the current example,
O(0, 0) can serve as such solution.
• At O define the “zero-variables” x1 and x2 as the
nonbasic variables. Define the remaining nonzero
variables S1 and S2 as the basic variables
• The problem is of the “max” type. To increase the
value of Z, one may increase x1 or x2 from their
current zero levels at O.
Graphical Motivation for the simplex method
• The problem is of the “max” type. To increase the
value of Z, one may increase x1 or x2 from their
current zero levels at O.
• We select to increase x2 since it has a better per unit
contribution to the objective function. We call x2
the entering variable since it will be > 0 and
therefore become basic (x2 enters the basis).
• Keeping x1 fixed at 0, increase x2 (i.e. move along the
direction of x2) while remaining feasible.
• We see that the maximum we can increase x2 is
when A is reached (i.e., x2 is increased from 0 to 4).
Increasing x2 further would make S2 < 0. We call S2
the “blocking variable.”
Graphical Motivation for the simplex method
• The simplex method requires that the blocking
variable leaves the basis and be replaced by the
entering variable.
• The simplex method then restarts at A with
nonbasic variables x1 and S2 and basic variables S1
and x2.
• The simplex method then moves to other extreme
points in a similar fashion until the optimal solution
is reached.
• In the current example, it can be verified that the
simplex algorithm will move from A to B and stop
with B being the optimal solution. This last move
involves x1 entering the basis and S1 (the blocking
variable) leaving the basis.
• The simplex “path” is plotted.
Analytical verification of blocking
• One can verify which basic variable is blocking
analytically without looking at the graph.
• For example, consider the first simplex move (iteration)
from O to A. To verify whether S1 or S2 is the blocking
variable note that when moving along the x2 direction
(and x1 = 0) the LP constraints give

• Setting the basic variables, S1 and S2, equal to zero

gives

• Therefore, as x2 increases from zero (at O) S2 hits zero

first. That is, S2 is the blocking variable.
Introduction to the simplex method in tabular
form
• Rewrite the LP in standard form as

• This gives the simplex tableau at O

Introduction to the simplex method in tabular
form

• We then determine the leaving or the blocking variable. This is based on a “minimum ration test.” The
blocking variable is the basic variable having the minimum ratio between the right hand side (RHS) and the
corresponding cell in the entering variable column. See the Ratio column in the above tableau. This implies
that S2 leaves the basis.
• With the new basic and nonbasic variables we need to develop a new simplex tableau (which corresponds to
the new corner point the simplex moved to; in our case the new corner point is A).
• The new tableau is filled by utilizing the element at the intersection of the entering variable column and the
leaving variable row as pivot element in Gauss-Jordan raw operations
• If ark is the pivot element (in our example, ark = a33 = 4), then rows ai, are rewritten in the new tableau as
′ ar / ark ⇒ a=
a=
r
′ arj / ark , ∀ j
rj

ai′ = ai − aik ar′ ⇒ aij′ = aij − aik arj′ , ∀i ≠ r , j

Introduction to the simplex method in tabular
form
• Applying this procedure to the above tableau give the following
simplex tableau (at A)
Introduction to the simplex method in tabular
form
• Optimality criteria: The optimal solution is reached when all the
values in the Z-row are nonnegative.
• This is not the case in the above tableau.
• Therefore, we perform another “simplex iteration.” (This iteration
corresponds to moving from A to B in the graphical method.)
• Applying similar steps as with the first table we see that x1 enters the
basis and S1 leaves the basis yielding the following simplex tableau (at
B)
• In this tableau, all the values in the Z-row are ≥ 0. This indicates that
the simplex method has “converged” to the optimal solution. The
optimal solution is

• The corresponding Z* is 36/5

• Note that this indeed corresponds to corner point B.
Basic, feasible, basic feasible, and basic infeasible
solutions
• A basic solution corresponds to a corner point.
For example, in the above (refer to the figure on
page 2), O, A, B, C, D, and E all correspond to
basic solutions.
• A feasible solution is a solution that satisfies all
constraints.
• A basic solution can either be feasible (hence
called basic feasible solution) or infeasible (called
basic infeasible solution).
• In the above, O, A, B, C are basic feasible
solutions, while E and D are basic infeasible
solutions.
• The simplex method starts at a basic feasible
solution and iterates through a sequence of basic
feasible solutions until it reaches optimality.