Di culties in Simplex Procedure
1. Tie in selecting key column/key row.
2. Inequality of greater than or equal to
kind.
3. Equality constraints.
4. Negative RHS.
5. Unrestricted variables.
6. Restricted variables.
7. Minimization Problem.
Flow chart of SIMPLEX Algorithm
Start Max Z Do positive value
Compute exists?
Cj-Ej
Mini Z N
N Optimu o Select with
Key column
Do Negative value o m largest +ve value
exists?
Select Key column Select key row with
with min ratio (b/aij), if all
Largest -ve value aij<=0, unbounded
solution, stop
Identify key element, and
Update entries in table by
elementary
Row operations
(1) Tie in selecting key column/Key
row(A) Tie in selecting key column
• Decision variable and slack or
surplus variable → Select Decision
variable column
• Decision variable and Decision
variable → Select any one column
• Slack/Surplus variable and Slack/
Surplus variable → Select any one
column
(B) Tie in selecting key row
• aik are elements in key column.
• Compare the ratio of aij to aik for tied
rows rst in identity from L to R and
then in body.
• Key row → Min. Positive ratio.
Simplex
Method -A
Case for
inkeyselectingTie
row
Standard Form:
Max Z = 2x1+1x2+0w1+0w2+0w3
4x1+3x2+w1= 12
4x1+x2+w2 = 8
4x1- x2 +w3 = 8
Tableau-I
cj 2 1 0 0 0
ci bxii x1 x2 w1 w2 w3 Ratio
0 w1 12 4 3 1 0 0 3
0 w2 8 4 1 0 1 0 2 Tie
0 w38 4 -1 0 0 1 2
Ej 00 0 0 0
Cj - Ej= 21 000
Tableau-I
cj 2 1 0 0 0
ci bxii x1 x2 w1 w2 w3 Ratio
0 w1 12 4 3 1 0 0 3
0 w2 8 4 1 0 1 0 2 Tie
0 w38 4 -1 0 0 1 2
I0j Z = 2 1 0 0 0
Tableau-I
form : Rewri en in required
cj 0 0 0 2 1
ci bxii w1 w2 w3 x1x2 Ratio
0 w1 12 1 0 0 4 3 3
0 w2 8 0 1 0 4 1 2 Tie
0 w38 0 0 14 -1 2
Ij Z = 0 0 0 0 2 1
Ratio : 0/4
0.251/4 = - R2
0/4 - R3 ← Key Row
(2) Constraints with inequality
“greater than or equal to” kind
(3) Equality Constraints.
OR
(4) Negative R.H.S.
(5) Unrestricted
Variables.
If x is unrestricted then x is
changed to
(x’ - x”), where x’ & x” are
positive.
(6) Restricted
Variables.
Some More Methods
Suitable for >=
A. (Big M) / Penalty constraints
B. Two Phase Method
C. Dual Simplex Method Suitable for initial
solutions having optimal,
but infeasible solutions i.e
RHS b’s are -ve
(A) Big M / Penalty / Arti cial
variable Method :
Maximization : (Pro t)
If Problem is Minimization , convert it to
Maximization Problem & solve
Key
Ej) column → Max. + ve Index Number.(Cj-
Co-e . of ‘A’ in Obj. eq. = -M (Heavy loss)
(A) Big M / Penalty / Arti cial
variable Method : Minimization
(Cost)
Same methodology as
Maximization
except
criterion of selecting ‘key column’
Key column → Max. - ve Index Number.
Co-e
Cost) . of ‘
A ’ in Obj. eq. = +M (Heavy
(B) Two Phase Method:
In Phase-
Problem I : For a Maximization
Consider Cj = -1 for only A, else Cj =
0 and Get Final Usual
Tableau
In Phase- II : Consider
All Cj = Original values in Final
Tableau of Phase I and Get
Optimal Solution
(C) Dual Simplex
Method
This method is applicable to any Standard
Maximizaion Problem with - Ve RHS
First “Key Row” is selected w.r.t. Max. – Ve
RHS
Key Column is selected w.r.t. Max. (I/ aij) for
-ve aij only
(A) Big M : Maximization
Convert this into maximization problem
Convert this into Standard form.
Standard Form :
Max (-Z) = -3x1-5x2+0s1+(- M)A1+0w1+0w
3x1+2x2-s1+A1= 18
1x1+1w1 = 4
1x2+1w2 = 6
Tableau c-j I-3 -5 0 -M 0 0
ci x i b i x1 x2 s1 A1 w1 w2
-M A1 18 3 2 -1 1 0 0
0w1 4 1 0 0 01 0
0w2 6 0 1 0 001
Ej -3M -2M M 0 0 0
Cj - Ej 3M-3 2M-5 M
Z= -18M
Tableau c-j II-3 -5 0 -M 0 0
ci xi bi x1 x2 s1 A1 w1 w2
-M A1 6 0 2 -1 1 -3 0
-3 x1 4 1 0 0 0 1 0
0w2 6 0 1 0 0 0 1
Ej -03 -2M M M 3M 0
Cj - Ej 2M-5 -M -2M -3M 0
Z=
-12 -6M
Tableau c-j III-3 -5 0 -M 0 0
ci xi bi x1 x2 s1 A1 w1 w2
-5 x2 3 0 1 -1/2 ½ -3/2
-3 x1 4 01 0 0 0 1
0w2 3 0 0 0 1 1 3
Ej 1 -3 -5 5/2 -5/2 9/2
Cj - Ej 00 0 -5/2 -M+5/2 -9/2
Z= -27 0
Hence, Optimal Solution is x1=4, x2=3 giving Zmax = -27 ,
(B) Big M : Minimization
Convert this into Standard form.
Standard Form:
Min Z = 3x1+5x2+0s1+MA1+0w1+0w2
3x1+2x2-s1+MA1 = 18
1x1+1w1 = 4
1x2+1w2 = 6
Tableau c-j I3 5 0 M0 0
ci xi bi x1 x2 s1A1 w1 w2 Ratio
M A1 18 3 2 -11 0 0 6
0 w1 4 1 0 00 1 0 4
0 w2 6 0 1 0 0 0 1 α
Ej 3M 2M -M M0 0
Cj - Ej 3-3M 5-2M M 0 0
0
• Key Column →Max -ve (Cj – Ej)j
Z= 18M
Tableau c-j II3 5 0 M 0 0
ci xi bi x1 x2 s1A1 w1 w2 Ratio
MA1 6 0 2 -11 0 0 3
3 x14 1 0 0 0 1 0 α
0 w2 6 0 1 0 0 0 1 6
Ej 3 2M -M M 3
Cj - Ej 00 -2M+5 M 0 -3
0
Tableau - III
cj 3 5 0 M 0 0
ci xi bi x1 x2 s1A1 w1 w2
5 x2 3 0 1 -1/2 ½ 0
3 x1 4 0 1 0 0 0 1 0
0 w2 3 0 0 ½ -1/2 0 1
Ej 3 5 -5/2 5/2 3
Cj - Ej 00 5/2 0 M-5/2 -3 0
Hence, Optimal Solution is x1=4, x2=3 giving Z = 27. Z = 27
(C) Two Phase Method
Convert this into maximization
Convert this into Standard form.
Standard
Form: cj = -1 for only A, else cj =
(Phase- I) 0
Max (-Z) =
0x1+0x2+0s1-1A1+0w1+0w2
3x1+2x2-s1+A1= 18
x1+w1 = 4
x2+w2 = 6
Phase IC: 0Tableau -
0 0 -10 0
I
j
ci xi bi x1 x2 s1A1 w1 w2 Rati
o
-1A1 18 3 2 -1 1 0 0 6
0w1 4 1 0 0 0 1 0 4
0w2 6 0 1 0 0 0 1 ~
Ej -3 -2 1 -1 0
Cj - Ej 0-13 2 000
Z= -18
Phase I :cTableau - II
0 00 -10 0
j
ci xi bi x1 x2 s1 A w1 w2
-1 A1 6 0 2 -1 1 -3 0
0x1 4 1 0 0 0 1 0
0w2 6 0 1 0 0 0 1
Ej 0 -2 1 -1 3
Cj - Ej 00 2 -1 0 -3 0
Z= -6
Phase I :cTableau - III
0 00 -10 0
j
ci xi bi x1 x2 s1 A1 w1 w2
0 x2 3 0 1 -1/ 1/2 -3/2 0
0x1 4 2
1 0 0 0 1 0
0w2 3 0 0 1/2 -1/ 3/2 1
2
Ej 0 0 0 0 0
Cj - Ej 0 0 0 0 -1 0
0
Z= 0
Phase II c: Tableau - I
j -3 -5 0 -M 0 0
ci xi bi x1 x2 s1 A1 w1 w2
-5 x2 3 0 1 -1/ 1/2 -3/2 0
-3 x1 4 2
1 0 0 0 1 0
w20 3 0 0 1/2 -1/ 3/2 1
Z= Ej -3 -5 5/2 2 -5/2 9/2 0
-27 Cj - Ej 0 0 -5/ 5/2-M -9/ 2 0
2
Hence, Optimal Solution is
x1=4,
Zmin=27 x2=3 giving Zmax = -27 ,
(D) Dual Simplex Method
Convert this into maximization
Convert this into Standard format.
Standard Form:
Max (-Z) = -3x1-5x2+0w1+0w2+0w3
-3x1-2x2+w1+0w2+0w3 = -18
x1+0x2+0w1+w2+0w3= 4
0x1+1x2+0w1+0w2+w3 = 6
Convert this into Standard form.
To prepare initial Tableau:
Tableau c-j I-3 -5 0 0 0
ci bxii x1 x2 w1 w2 w3
0 w1 -18 -3 -2 1 0 0
0 w2 4 1 0 0 1 0
0 w36 0 1 0 0 1
I0j Z = 35 000
Ratio: 3/-3 5/-2 • Key Column
=-1 =-2.5 →Max Ratio
Tableau c-j II-3 -5 0 0 0
ci xi bi x1 x2 w1 w2 w3
-3 x1 1 2/3 -1/3 0 0
0 w2 6- 0 -2/3 1/3 1 0
5 w3 2 0 1 0 1
I=-18 Z 6 3 1 0
0 0
j
0
Ratio: 3/(-2/3)
=-9/2
Tableau -c III-3 -5 0 0 0
j
ci xi bi x1 x2 w1 w2 w3
-3 x1 4
-5 x2 3
0 w3 3
I-27
j Z= 0 0 3/ 2 2 01/
Hence, Optimal Solution is
x1=4, x2=3
Zmin = 27. giving Zmax= -27 and
• Cases for
• ‘Alternative Optimal Solution’
• ‘Unbounded Solution’,
• ‘Infeasible Solution’ and
• ‘Unrestricted
Simplex. Variable’ through
Case for
Alternative
Optimal
Solution
Standard Form:
Max Z =
6x1+4x2+0w1+0w2+0s1+(M)A1
2x1+3x2+w1+0w2+0s1+0A1 = 30
3x1+2x2+0w1+w2+0s1+0A1 = 24
x1+x2+0w1+0w2- s1+A1 = 3
cj 6 4 0 0 0 -M
ci xi bi x1 x2 w1 w2 s1 A1 Ratio
0 w1 14 0 5/3 1-2/3 00 8.4
0 s15 0 -1/3 0 1/3 1 -1 -
6 x18 1 2/3 0 1/3 00 12
Ij Z= 48 0 0 0 -2 0-M
Optimal Solution is
Final Tableaux1=8, x2=0 giving Z =
cj 6 4 0 0 0 -M
ci xi bi x1 x2 w1 w2 s1 A1
4 x2 42/5
0 s1 39/5
6 x1 12/5
Ij Z= 48 0 0 0 2 0M
Alternative Optimal Solution
is
x1=12/5 , x2= 42/5 giving Z
Case for
Unbounded
Solution
Standard Form:
Max Z =
3x1+5x2+0w1+0w2+0s1+(M)A1
x1-2x2+w1+0w2+0s1+0A1 = 6
x1+0x2+0w1+w2+0s1+0A1 = 10
0x1+x2+0w1+0w2- s1+A1 = 1
cj 3 5 0 0 0 -M
ci xi bi x1 x2 w1 w2 s1 A1 Ratio
0 w1 6 1 -2 1 0 00 -
0 w2 10 1 0 0 1 00 α
-M A1 1 0 1 0 0 -1 1 1
Ij Z= -M 3M 0 0 M 0
+5
Tableau-I
cj 6 4 0 0 0 -M
ci xibi x1 x2 w1 w2 s1 A1
0 w1 8 1 0 1 0 -2 -2
0 w2 1 0 0 1 0 0
5 x2 10 0 1 0 0 -1 1
1
Ij Z= 5 3 0 0 0 5 2M
+5
All aij<= 0 w.r.t. key column. Hence,
Solution is unbounded.
Case for
Infeasibl
eSolution
Standard Form:
Max Z = 6x1+4x2+0w1+0s1+(-M)A1
x1+x2+w1+0s1+0A1 = 5
0x1+x2+0w1- s1+A1 = 8
cj 6 4 0 0 -M
ci xi bi x1 x2 w1 s1 A1
4 x2 5 1 1 1 0 0
-M A1 3 -10 -1-11
Ij Z= -3M 2-M 0 -M-4 -M0
+20
Final Tableau As A1 = 3 in nal
tableu, Solution is
infeasible.
Case for
Unrestrict
ed
Variable
As x2 is unrestricted
x2 = x2’ - x2”
Hence the problem is converted to
Case for
Unrestrict
ed
Variable
Convert Minimization Problem into
Maximization Problem
Case for
Unrestrict
ed
Variable
Standard Form:
Max(-Z)
M)A1+0w1= -x1-4x2’+4x2”+0s1+(-
x1+2x2’-2x2”-s1+A1+0w1 = 1
3x1-5x2’+5x2”+0s1+0A1+w1 = 8
Case for
Variable Unrestricted
Tableau c-j -1I - 4 4 0-M 0
ci bxii x1 x2’ x2” s1 A1 w1
-M A11 1 2 -2 -11 0
0 w1 143 -5 5 00 1
Ij Z = -M -M -2M 2M 0M0
+1 +4 -4
• Ij = (Zj-cj) = (Σaij.ci)-cj
Case for
Variable Unrestricted
Tableau c-j -1-4
II 4 0 -M 0
ci xbi i x1 x2’ x2” s1 A1 w1
-4 x2’
1/2 1/2 1 -1-1/2 1/2 0
0 w1 33/211/2 00 -5/2 5/2 1
I2j Z = -1 0 0 2 -2 0
+M
Case for
Variable Unrestricted
Tableau c-j -1-4
III 4 0 -M 0
ci xbi i x1 x2’ x2” s1 A1 w1
-1 x1 1 1 2 -2 -1 1 0
0 w1 11 0 -11 11 3 -3 1
Ij Z = -1 0 2 -2 1 -1 0
+M
Case for
Variable Unrestricted
Tableau c-j -1-4
IV 4 0 -M 0
ci xbii x1 x2’ x2” s1 A1 w1
-1 x1 3
4x2” 1
Ij Z = 1 0 0 0 +ve +ve
Hence Optimal Solution+ve
is
x1=3, x2”=1, x2’=0
∴ x1 = 3, x2 = x2’ - x2”= -1 giving Zmin
= -1
• Duality and
• Primal Dual Relationship
Duality:Data for LPP (Primal)
Formulation
Factory: Two. products P1 & P2
Pro t/piece of P1 = Rs.6/-
Pro t/piece of P2 = Rs.8/-.
Time Constraint:
Time required/piece of P1 on m/c A=
hrs.
Time required/piece of P1 on m/c B= 5 hr
Time required/piece of P2 on m/c A= 20
Time required/piece of P2 on m/c B= 10
Max. time available on m/c A = 300 hrs.
Primal Problem Formulation
X1=No. of units of P1
X2=No. of units of P2
Max.Zp = 6 X1 + 8 X2
s/t 30 X1 + 20 X2 ≤ 300
5 X1 + 10 X2 ≤ 110
X1 , X2 ≥ 0
Dual Problem Formulation
Y1=Cost of 1 hr of m/c A
Y2=Cost of 1 hr of m/c B
Min. Zd = 300 Y1 + 110 Y2
s/t 30 Y1 + 5 Y2 ≥ 6
20 Y1 + 10 Y2 ≥ 8
Y1 , Y2 ≥ 0
Final Tableau of Primal
cj 6 8 0 0
ci xi bi X1 X2w1 w2
6 x14 1 0 1/20 -1/10
8 x2 9 0 1 -1/40 3/20
Zp = 96 0 0 1/10 6/10
• The Optimal Solution of Primal is
X1 = 4, X2 = 9 giving Zp = 96
• The Optimal Solution
Primal solution is of Dual from
Y1 = 1/10, Y2 = 6/10 giving Zd = 96
Primal - Dual Relationship
Primal (Max.) ( ≤ ) Dual (Min.)
----------------------------------------------- ( ≥ )
No. of ------------
Variables No. of Constraints
No.
Obj. of
fn.Constraints
Coe . No.
R.H.S. of Variables
R.H.S.
jthithCol. Of Coe . Obj.
jth fn.
Row Coe
of .
Coe .
jth relation
Variable ≥( ≤
0 ) ith
jth Variable
relation ≥
(≥)0
ith relation = ith variable
jth variable unrestricted j th relation =unrestricted
Primal Problem
Max.Zp = X1+2X2 -3X3
s/t 2 X1 + X2 +X3 ≤ 10
3 X1 - X2 =2 X3 ≥ 110
X1 + 2X2 - X3 = 4
X1 , X3 ≥ 0 , X3 unrestricted
To convert into Dual write in standard
format
Primal Problem : Standard Format
Max.Zp = X1+2X2 -3X3
s/t 2 X1 + X2 +X3 ≤ 10
-3 X1 + X2 -2 X3 ≤ - 110
X1 + 2X2 - X3 = 4
X1 , X3 ≥ 0 , X2 unrestricted
Dual will be
Min. Zd = 10 Y1 -110 Y2 +4 Y3
s/t 2 Y1 - 3 Y2 + Y3 ≥ 1
Y1 + Y2 +2 Y3 = 2
Y1 - 2 Y2 - Y3 ≥ - 3
Y1 , Y2 ≥ 0 , Y3 unrestricted
