9/24/2025
Dual
Linear Programming Problem
Dr. Anil Kumar
A-408
Generalized Simplex Algorithm
The (primal) Simplex algorithm starts with a feasible solution
that 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 must use either a (primal) Simplex Algorithm with
Artificial variables or a Dual Simplex Algorithm with
Artificial constraints.
Anil Kumar, Mathematics 89
Anil Kumar, Mathematics, BITS Goa 1
9/24/2025
Generalized Simplex Algorithm…
Since the key idea of both the primal and dual simplex methods
is that the optimum feasible solution, when finite, always
occurs at a corner point (or a basic solution).
This suggests that a new simplex algorithm can be developed
based on the tandem use of the dual simplex and the primal
simplex methods.
First, use the dual algorithm to get rid of infeasibility (without
worrying about optimality).
Once feasibility is restored, the primal simplex can be used to
find the optimum.
Anil Kumar, Mathematics 90
Generalized Simplex Algorithm…
In both algorithms, we look for corner point solutions (feasible or
not).
The generalized Simplex algorithm exploits this fact and moves
from one corner point solution to another without using artificial
variables or constraints until optimality is obtained (or the criterion
that the problem is unbounded or infeasible is detected).
This suggests that a new simplex algorithm can be developed based
on the dual and primal simplex methods.
First, use the dual algorithm to eliminate infeasibility (without
worrying about optimality).
Once feasibility is restored, the primal simplex can be used to find
the optimum.
Examples
Anil Kumar, Mathematics 91
Anil Kumar, Mathematics, BITS Goa 2
9/24/2025
Generalized Simplex Algorithm…
Example 1: Consider the following LPP
Maximize z x1 3x2
subject to
x1 x2 2
x1 x2 4
2x1 2x2 3, x1, x2 0
Solve with the generalized simplex method (without
adding an artificial constraint). The starting Simplex
tableau is neither feasible nor optimal.
Anil Kumar, Mathematics 92
Generalized Simplex Method…
Example 2: Consider the following LPP
Maximize z x1 x2
subject to
x1 4x2 5
x1 3x2 1
2x1 5x2 1, x1, x2 0
Solve with the generalized simplex method.
Anil Kumar, Mathematics 95
Anil Kumar, Mathematics, BITS Goa 3
9/24/2025
Example
Solve the following LPP by Generalized Simplex Method
(i) max z x1 2 x2 x3 (ii) max z 2 x3
s.t. 3 x1 x2 x3 10 s.t. x1 3x2 7 x3 5
x1 4 x2 x3 6 x1 x2 x3 1
x2 x3 4 3x1 x2 10 x3 8
x1 , x2 , x3 0 x1 , x2 , x3 0
Anil Kumar, Mathematics 98
Anil Kumar, Mathematics, BITS Goa 4