Simplex Method
Dr. Edgar Reséndiz
Instituto Tecnológico de Saltillo
Dr. Edgar Reséndiz Simplex Method
Basic Solution
Dr. Edgar Reséndiz Simplex Method
Basic Solution
The solution x = (xB , xN )t to the system Ax = b where
xB = B −1 b and xN = 0 is called basic solution.
The components of xB are called basic variables and those of
xN nonbasic variables.
When xB ≥ 0, x is called a basic feasible solution of the
system
If xB > 0, x is called a nondegenerate basic feasible solution
If at least one component of xB is zero, then x is called a
degenarate basic feasible solution of the system
Dr. Edgar Reséndiz Simplex Method
Basic Feasible Solution
Dr. Edgar Reséndiz Simplex Method
Basic Feasible Solution
Constraint matrix
Possible ways of extracting B:
Points 1,2,3 and 5 are feasible solutions.
Dr. Edgar Reséndiz Simplex Method
Basic Feasible Solution
Constraint matrix
Possible ways of extracting B: The four basic feasible solutions:
Projected in R2 :
Number of basic feasible solutions:
Points 1,2,3 and 5 are feasible solutions.
Dr. Edgar Reséndiz Simplex Method
Degenerate Basic Feasible Solution
Dr. Edgar Reséndiz Simplex Method
Degenerate Basic Feasible Solution
Constraint matrix
If B = [a1 , a2 , a3 ]:
Degenerate solution since x3 = 0.
Now if B = [a1 , a2 , a4 ]:
we obtain the same result!.
Dr. Edgar Reséndiz Simplex Method
Degenerate Basic Feasible Solution
Constraint matrix
If B = [a1 , a2 , a3 ]:
Furthermore the basic feasible
solution with basis B = [a1 , a2 , a5 ]
is:
Degenerate solution since x3 = 0.
Now if B = [a1 , a2 , a4 ]: These three bases correspond to a
degenerate basic feasible solution.
we obtain the same result!.
Dr. Edgar Reséndiz Simplex Method
What we know about LP.
The collection of extreme points of an LP corresponds to the
collection of basic feasible solutions and both are nonempty,
provided that the feasible region is not empty
Let F S be nonempty. A finite optimal solution exists in a
maximization LP if and only if cdj ≤ 0 for j = 1, 2, ..., l
where d1 , d2 , ..., dl are the extreme directions of the feasible
region. Otherwise, the optimal solution value is unbounded.
In a minimization of a LP, cdj ≥ 0 is the necessary and
sufficient condition for a finite optimal solution to exist.
Dr. Edgar Reséndiz Simplex Method
What we know about LP.
Dr. Edgar Reséndiz Simplex Method
What we know about LP.
If an optimal solution exists, then an optimal extreme point
exists
For every extreme point there correspond a basis (not
necessarily unique), and, conversely, for every basis there
corresponds a (unique) extreme point
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Developed by Dantzig in 1947
First used by J. Lademan to solve a diet-planning LP program
with 9 equality constraints in 27 nonnegative variables (120
man-days using desk calculators)
Software today can solve for tens of thousands of variables
with thousands of constraints
After more than 50 years, and competition by other
algorithms, the Simplex Method is still a viable and very
popular LP solution algorithm
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Simplex Method recognizes the optimality of a given extreme
point solution based on local considerations without having to
(globaly) enumerate all extreme points or basic feasible
solutions.
It moves from an extreme point to another extreme point with
a better (at least no worse) objective
Is this good?
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Imagine using a method that analyses all possible points of a F S
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Additionally, the Simplex Method detects if a problem has an
unbounded solution
This is where to go after 2D.
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
The Algorithm
1 Formulate the problem in standard form
2 Find an initial basic feasible solution
3 Check for optimality
If optimal, then stop. The current extreme point is optimal.
Otherwise, find a non-basic variable that will improve the
solution if increased
4 Move to adjacent extreme point
Increase the non-basic variables as much as possible
Adjust the set of a basic and non-basic variables
Go to step 3.
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
The Key to the Simplex Method
Consider the following linear programming problem
suppose we have a feasible solution (B −1 b, 0)t whose objective
value is
If x = (xB , xN )t is an arbitrary feasible solution, xB , xN ≥ 0 and
b = Ax = BxB + N xN . From here we can obtain
where R is the set of indices for nonbasic variables.
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Furthermore
where zj = c−1
B aj for each nonbasic variable.
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Thus, our problem can be rewritten as
If no row has all zeros in the columns of the nonbasic variables
xj , j ∈ J. We can write the LP problem in the nonbasic variable
space as follows:
The number of nonbasic variables is p = n − m.
(cj − zj ) are the reduced cost coefficients.
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
If (zj − cj ) ≤ 0 for all j ∈ J, then the current basic feasible
solution is optimal.
Since zj − cj ≤ 0 for all j ∈ J, we have z ≥ z0 for any feasible
solution; but for the current basic feasible solution, we now that
z = z0 , since xj = 0 for all j ∈ J.
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Algebra of the Simplex Method:
Consider
Assume
(zk − ck ) > 0 there will be an impovement with increasing xk
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
So, we can increase xk until the first variable drops to zero, that is,
In the abscence of degeneracy, the objective function strictly
decreases since
As xk is increased, a new basic feasible solution is obtained:
All other x0j s are zero.
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Summarizing the operation:
We moved from one basis to an adjacent basis
This was achieved by increasing the value of a nonbasic
variable xk with positive zk − ck , and adjusting the current
basic variables
xBr drops to 0 in the process
xk inters the basis and xBr leaves the basis
In the abscence of degeneracy, the objective function strictly
decreases, hence the basic feasible generated solutions are
distinct.
The procedure will end in a finite number of steps since these
are at most
n n!
=
m m!(n − m)!
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Interpretation of zk − ck
On the other hand, the cost of increasing one unit of xk is ck
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
zk − ck > 0: an increase in xk will result in less cost
zk − ck < 0: an increase in xk will result in more cost (Don’t
do it!)
zk − ck = 0: an increase in xk will result in different solution
with the same cost
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Termination of the Simplex Method
The simplex will finish in a finite number of steps with the
following conclusions:
Optimal solution (unique or alternative)
Unbounded solution
Entering: xk may enter if zk − ck > 0
Leaving: xBr may leave if
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Termination of the Simplex Method
Optimal solution
zj − cj ≤ 0, for all nonbasic variables
Unique optimal solution
zj − cj < 0, for all nonbasic variables
Alternative optimal solution
zk − ck = 0, for at least one nonbasic variable xk
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Termination of the Simplex Method
Unbounded optimal solution
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Unbounded optimal solution
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Unbounded optimal solution
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
The Simplex Algorithm
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
The Simplex Algorithm
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
The Simplex Algorithm
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Example
Consider the problem:
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Iteration 1:
By solving BxB = b we obtain x2 is increased. Solve for y2
xB1 = x3 = 6, xB2 = x4 = 1 and
nonbasic variables x1 and x2 .
that is
Furthermore
Now compute
The leaving variable xBr is
determined by
Thus we find w by solving
that is r = 2 therefore XB2 = x4 leaves the
basis, since
Hence, and x4 → 0 when x2 = 1.
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Iteration 2:
Hence
x2 enters and x4 leaves the basis:
x4 cannot enter the basis since
z4 − c4 < 0. Therefore x1 is
xB is obtained by solving BxB = b: increased. Now solve By1 = a1 :
z = −3. Calculate w by solving Since y21 < 0, then xB1 = x3 leaves
wB = cB : the basis as x1 is increased. Observe
that
and x3 → 0 when x1 = 3/5.
Dr. Edgar Reséndiz Simplex Method
The Simplex Method
Iteration 3:
x1 enters and x3 leaves the basis:
Since z3 − c3 < 0, x3 cannot enter
the basis. Hence
Finally the current point is an
The objective is z = −27/5. Now optimal solution since zj − cj < 0
calculate w by solving wB = cB , for all nonbasic variables. This is
given by
Dr. Edgar Reséndiz Simplex Method
