Additional Simplex Algorithms

Dual Simplex Method

and
Generalized Simplex method
Dual Simplex Method

In the simplex algorithm

The problem starts at a (basic) feasible solution.
Successive iterations continue to be feasible until the optimal is
reached at the last iteration.
The algorithm is sometimes referred to as the primal simplex
method.
Dual Simplex Method

In the dual simplex

The LP starts at a better than optimal infeasible (basic) solution.
Successive iterations remain infeasible and (better than) optimal
until feasibility is restored at the last iteration.
The generalized simplex combines both the primal and
dual simplex methods in one algorithm.
It deals with the problems that start both non-optimal and
infeasible (basic) solutions.
At the final iteration, the solution becomes optimal and feasible.
 Dual Simplex Method

To start the dual Simplex method, the following three

conditions are to be met:
The objective function must satisfy the optimality conditions
of the regular Simplex method.
All the constraints must be of the type ().
(This requires converting any () to () simply by
multiplying both sides of the inequality () by -1 and
if the LP includes (=) constraints, the equation can be
replaced by two inequalities.)
All variables should be 0.
 Remark
As in the simplex method, we must have an identity
matrix in the constraint matrix; however, the RHS
constants bi need NOT be 0.
After converting all the constraints to (), the LP will
have an infeasible starting solution if and only if at least
one of the right-hand sides of the inequalities is strictly
negative
else if z is optimal and none of the right hand sides are
negative, there will be no need to apply the dual simplex
method as the starting solution is already optimal and
feasible.
Dual Simplex Algorithm
In the dual simplex method
Each iteration is always associated with a basic
solution.
The optimality and feasibility conditions are
designed to preserve the optimality of the basic
solutions and
Simultaneously, moving the solution iterations
toward feasibility.
 Dual Simplex Algorithm
In any iteration, we first decide the leaving variable and
then decide which variable should enter (the basis).

Dual Feasibility Condition: Condition for a variable to leave

the basis
The leaving variable xi, is the basic variable having
the most negative value (i.e. in the Simplex tableau,
the corresponding constraint row has the most
negative RHS).
Ties are broken arbitrarily.
If all the basic variables are 0, the algorithm ends
and we have obtained the optimal solution.
 Dual Simplex Algorithm
Dual Optimality Condition: Condition for a non-basic variable
xj to enter the basis
The entering variable xj, is determined from among the
non-basic variables as the one for which the ratio
z j c j
: aij 0
aij
is least, where zj - cj is the coefficient of xj in the z-
row, aij is the coefficient of xj in the leaving variable
row.
Ties are broken arbitrarily.
If no variable can enter the basis, the problem has no
feasible solution.
Example 1:

Solve by Dual Simplex method

Minimize z 2 x1 3x2

subject to 2 x1 2 x2 30
x1 2 x2 10
x1 , x2 0
 Example 1: solution
Putting it in the form all constraints of the type and
adding slack variables, the problem becomes
Minimize z 2 x1 3x2
subject to
2 x1 2 x2 s1 30
x1 2 x2 s2 10
x1 , x2 , s1 , s2 0

Since all the objective coefficients are 0 and the

problem is minimization, optimality is met. We start the
solution by writing the Simplex tableau.
 (0,15)

2x1+2x2=30 2x1+3x2=45

2x1+3x2=30
(0,5)
2x1+3x2=20

(0,0) (10,0) (15,0)

2x1+3x2=15
x1+2x2=10
Example 2:
Solve by Dual Simplex method

Minimize z 2 x1 3x2

subject to 2 x1 2 x2 30
x1 2 x2 10
x1 , x2 0
Example 3:
Solve by Dual Simplex method

Maximize z 2 x1 3x2

subject to
2 x1 x2 x3 3
x1 x2 x3 2
x1 , x2 , x3 0
Remark:

If LPP of maximization type with positive objective

function coefficient, then the LPP can not be solved
by Dual Simplex Method.
Example 4:

Solve by Dual Simplex method

Minimize z 4 x1 2 x2

subject to x1 x2 1
3x1 x2 2
x1 , x2 0
Example 5:
Solve by Dual Simplex method

Maximize z x1 x2

subject to x1 x2 8
x2 3
x1 x2 2
x1 , x2 0
Dual Simplex with Artificial Constraints
Example 1: Consider the following LPP
Maximize z 2 x1 x2 x3
subject to
2 x1 3 x2 5 x3 4
x1 6 x2 x3 3
4 x1 6 x2 3 x3 8
x1 , x2 , x3 0
 Dual Simplex with Artificial Constraints
Adding the surplus variables s1 and s2 to the first and second
constraints and the slack variable s3 to the third constraint,
the LPP becomes:
Maximize z 2 x1 x2 x3
subject to
2 x1 3x2 5 x3 s1 4
x1 6 x2 x3 s2 3
4 x1 6 x2 3 x3 s3 8
x1 , x2 , x3 , s1 , s2 , s3 0
 Note that:

The starting Basic Solution consisting of surplus s1 and s2

and slack s3 is infeasible as s1 = -4 and s2 = -3.
However the dual Simplex method is NOT applicable as
the optimality condition is not met.
We will solve the problem by augmenting the artificial
constraint
x1 x3 M
where M is large enough NOT to eliminate any feasible
points of the original solution space.
Dual Simplex with Artificial Constraints

Using the new constraint row as the pivot row.

Taking x1 as the entering variable as it has the most

negative coefficient in the z-row
will give an all-optimal objective function row.

Next, we carry out the dual simplex method. The

working follows.
Basic z x1 x2 x3 s1 s2 s3 s4 Sol
z 1 -2 1 -1 0 0 0 0 0
s1 0 -2 -3 5 1 0 0 0 -4
s2 0 1 -9 1 0 1 0 0 -3
s3 0 4 6 3 0 0 1 0 8
s4 0 1 0 1 0 0 0 1 M
We now allow s4 to leave and x1 to enter the basis
z 1 0 1 1 0 0 0 2 2M
s1 0 0 -3 7 1 0 0 2 -4+2M
s2 0 0 -9 0 0 1 0 -1 -3- M
s3 0 0 6 -1 0 0 1 -4 8-4M
x1 0 1 0 1 0 0 0 1 M
Now dual simplex method starts: s3 leaves; s4 enters the basis
Basic z x1 x2 x3 s1 s2 s3 s4 Sol
z 1 0 4 1/2 0 0 1/2 0 4
s1 0 0 0 13/2 1 0 1/2 0 0
s2 0 0 -21/2 1/4 0 1 -1/4 0 -5
s4 0 0 -3/2 1/4 0 0 -1/4 1 -2+M
x1 0 1 3/2 3/4 0 0 1/4 0 2
z 1 0 0 25/42 0 8/21 17/42 0 44/21
s1 0 0 0 13/2 1 0 1/2 0 0
x2 0 0 1 -1/42 0 -2/21 1/42 0 10/21
s4 0 0 0 3/14 0 -1/7 -3/14 1 -9/7+M
x1 0 1 0 11/14 0 1/7 3/14 0 9/7

This is the optimal tableau.

 Dual Simplex with Artificial Constraints
Example 2: Consider the following LPP
Maximize z x1 3x2
subject to
x1 x2 2
x1 x2 4
2 x1 2 x2 3
x1 , x2 0
 Example 2
Adding the slack variable s1 to the first constraint and
the surplus variables s2 and s3 to the second and third
constraints, the LPP becomes

Maximize z x1 3x2
subject to x1 x2 s1 2
x1 x2 s2 4
2 x1 2 x2 s3 3
x1 , x2 , s1 , s2 , s3 0
 Example 2 Note that
The starting Basic Solution consisting of slack s1 and
surplus s2 and s3 is infeasible as s2 = - 4 and s3 = - 3.

However the dual Simplex method is NOT applicable as

the optimality condition is not met.

We will solve this by augmenting the artificial

constraint
x1 M
where M is large enough NOT to eliminate any
feasible points of the original solution space.
 Example 2 Note that

Use the new constraint row as the pivot row.

Taking x1 as the entering variable as it has the negative
coefficient in the z-row will give an all-optimal objective
function row.
Next we carry out the dual simplex method. The working
follows.
Basic z x1 x2 s1 s2 s3 s4 Sol
z 1 -1 3 0 0 0 0 0
s1 0 1 -1 1 0 0 0 2
s2 0 -1 -1 0 1 0 0 -4
S3 0 -2 2 0 0 1 0 -3
s4 0 1 0 0 0 0 1 M
We now allow x1 to enter and s4 to leave the basis
z 1 0 3 0 0 0 1 M
s1 0 0 -1 1 0 0 -1 2-M
s2 0 0 -1 0 1 0 1 -4+ M
s3 0 0 2 0 0 1 2 -3+2M
x1 0 1 0 0 0 0 1 M
Now dual simplex method starts: s1 leaves; s4 enters the basis
Basic z x1 x2 s1 s2 s3 s4 Sol
z 1 0 3 0 0 0 1 M
s1 0 0 -1 1 0 0 -1 2-M
s2 0 0 -1 0 1 0 1 -4+ M
s3 0 0 2 0 0 1 2 -3+2M
x1 0 1 0 0 0 0 1 M
z 1 0 2 1 0 0 0 2
s4 0 0 1 -1 0 0 1 M-2
s2 0 0 -2 1 1 0 0 -2
s3 0 0 0 2 0 1 0 1
x1 0 1 -1 1 0 0 0 2
Basic z x1 x2 s1 s2 s3 s4 Sol
z 1 0 2 1 0 0 0 2
s4 0 0 1 -1 0 0 1 M-2
s2 0 0 -2 1 1 0 0 -2
s3 0 0 0 2 0 1 0 1
x1 0 1 -1 1 0 0 0 2
z 1 0 0 2 1 0 0 0
s4 0 0 0 -1/2 1/2 0 1 M-3
x2 0 0 1 -1/2 -1/2 0 0 1
s3 0 0 0 2 0 1 0 1
x1 0 1 0 1/2 -1/2 0 0 3

This is the optimal tableau.

 Generalized Simplex Algorithm
The (primal) Simplex algorithm starts with a feasible
solution which is not optimal and then moves towards
optimality always retaining the feasibility.
The dual Simplex algorithm starts with (better than)
optimal solution which is not feasible and moves towards
feasibility always retaining the optimality.
What if the starting solution is neither feasible nor
optimal?
We have to use either (primal) Simplex Algorithm with
Artificial variables or Dual Simplex Algorithm with
Artificial constraints.
 Generalized Simplex Algorithm

In the both algorithms, we look for corner point solutions

(feasible or not).
The generalized Simplex algorithm exploits this fact and
without using artificial variables or constraints moves
from one corner point solution to another till optimality is
obtained (or the criterion that the problem is unbounded
or infeasible is detected).
Examples
 Generalized Simplex Algorithm
Example 1: Consider the following LPP
Maximize z x1 3x2
subject to x1 x2 2
x1 x2 4
2 x1 2 x2 3, x1 , x2 0

Solve with generalized simplex method (without adding

an artificial constraint). The starting Simplex tableau is
neither feasible nor optimal.
Basic z x1 x2 s1 s2 s3 Sol
z 1 -1 3 0 0 0 0
s1 0 1 -1 1 0 0 2
s2 0 -1 -1 0 1 0 -4
s3 0 -2 2 0 0 1 -3
We now allow s2 to leave the basis as it has the most ve
value and x1 to enter as it satisfies the minimum ratio test.
z 1 0 4 0 -1 0 4
s1 0 0 -2 1 1 0 -2
x1 0 1 1 0 -1 0 4
s3 0 0 4 0 -2 1 5
We now allow s1 to leave the basis as it has the ve value and
x2 to enter as it has the only ve coefficient in the leaving row.
Basic z x1 x2 s1 s2 s3 Sol
z 1 0 0 2 1 0 0
x2 0 0 1 -1/2 -1/2 0 1
x1 0 1 0 1/2 -1/2 0 3
s3 0 0 0 2 0 1 1

This is the optimal tableau

Generalized Simplex Method

Example 2: Consider the following LPP

Maximize z x1 x2
subject to x 4 x 5
1 2

x1 3x2 1
2 x1 5 x2 1, x1 , x2 0

Solve with generalized simplex method.

Example 2
Adding the slack variable s2 to the second constraint
and the surplus variables s1 and s3 to the first and third
constraints, the LPP becomes
Minimize z x1 x2
subject to x 4 x s 5
1 2 1

x1 3 x2 s2 1
2 x1 5 x2 s3 1
x1 , x2 , s1 , s2 , s3 0
Basic z x1 x2 x2 s1 s2 s3 Sol
z 1 -1 -2 2 0 0 0 0
s1 0 1 1 1 1 0 0 3
s2 0 -1 1 0 0 1 0 -1
s3 0 0 1 1 0 0 1 4
We now allow s1 to leave the basis as it has the most ve value
and x1 to enter as it has the only ve coefft in the leaving row.
z 1 0 3 1 0 0 5
x1 0 1 -4 -1 0 0 5
s2 0 0 1 1 1 0 -4
s3 0 0 -3 -2 0 1 9
The new s2 row shows that the problem has no feasible
solution.
Example 2: Consider the following LPP
Maximize z 2 x1 3x2
subject to 2 x1 x2 x3 5
x1 x2 x3 2
x1 , x2 0
Use dual simplex method after adding artificial
constraint.
Example:
Consider the LPP
Maximize z 5x1 2 x2 3x3

subject to x1 5 x2 3 x3 b1
x1 5 x2 6 x3 b2
x1 , x2 , x3 0
The following optimal tableau corresponds to specific
values of b1 and b2:
Basic z x1 x2 x3 x4 x5 Sol
z 1 0 a 7 d e 150
x1 0 1 b 2 1 0 30
x5 0 0 c -8 -1 1 10

Determine the following:

(a) The RHS values b1, b2
(b) The entries a, b, c, d, e
(c) The optimal solution of the dual.
(a) The optimal solution of the primal is B-1b, where
1 1 0 b1
B b
1 1 b2
Thus
b1 30
B-1b = b b Hence b1 = 30, b2 = 40
1 2 10
(b) b B 1 A 1 0 5 5
c 2 1 1 5 10

Hence b = 5, c = -10
 5
a = z2 c2 CB B A2 c2 5 0 10 2 23
1

1
d = z4 c4 CB B A4 c4 5 0 0
1
5
1
e = 0 as x5 is a basic variable.

(c) The optimal solution of the dual is

1 0
y1 y2 CB B
1
5 0 1 1 5 0