Linear Programming Problems (LPP):

Simplex Method, Minimization problem:

Q. Solve the following LPP
Step 2: Represent in Matrix form [Ax=B]
Min Z= x1- 3x2+2x3
Subject to, x1 x2 x3 s1 s2 s3 x1
3x1-x2 +3x3< 7 x2
3 -1 3 1 0 0 = 7
-2x1+4x2 < 12 x3
12
-4x1+3x2 +8x3< 10 -2 4 0 0 1 0 s1
10
and x1, x2,x3 > 0 -4 3 8 0 0 1 s2
Solution: s3
Step 1: Standard LPP
Max Z|= -x1+3x2-2x3+0s1+0s2+0S3
Subject to:
3x1-x2 +3x3 +s1= 7
-2x1+4x2 +s2= 12
-4x1+3x2 +8x3+s3=10
and x1, x2 , s1, s2 ,s3> 0
 Linear Programming Problems (LPP):
Simplex Method, Maximization problem:
Step:3 Construct starting simplex table
Cj -1 3 -2 0 0 0

BasicVariable CB xB x1 x2 x3 s1 s2 s3

s1 0 7 3 -1 3 1 0 0

s2 0 12 -2 4 0 0 1 0
s3 0 10 -4 3 8 0 0 1
 Linear Programming Problems (LPP):
Simplex Method, Maximization problem:
Step:3 Construct starting simplex table Key Elements Z|=CBxXB
Z|=(0,0,0)(7,12,10)=0
Cj -1 3 -2 0 0 0 Min Ratio =(0,7)+(0,12)+(0,10)=0

▲J=CBXj-Cj
BasicVariable CB xB x1 x2 x3 s1 s2 s3 xB/xk, xk>0 ▲J=CBX1- C1=(0,0,0)(3,-2,-4) – (-1)
=0 – 0 - 0 + 1=1
▲J=CBX2- C2=(0,0,0)(-1,4,3) – 3
s1 0 7 3 -1 3 1 0 0 - =0 + 0 + 0 - 3= -3
Outgoing vector ▲J=CBX3- C3 =(0,0,0)(3,0,8) – (-2)
s2 0 12 -2 4 0 0 1 0 12/4=3 ==0 + 0 + 0 + 2= 2
▲J=CBS1- C3 =(0,0,0)(1,0,0) – 0
s3 0 10 -4 3 8 0 0 1 10/3=3.3 ==0 + 0 + 0 - 0= 0
▲J=CBS2- C3 =(0,0,0)(0,1,0) – 0
Z|=0 ▲J 1 -3 2 0 0 0 ==0 + 0 + 0 - 0= 0
▲J=CBS3- C3 =(0,0,0)(0,0,1) – 0
==0 + 0 + 0 - 0 = 0
Incoming vector
(xk)
 Linear Programming Problems (LPP): Solution for Key element= 1
XB=12/4=3, X1=-2/4=-1/2
Simplex Method, Maximization problem: Key Elements
X2=4/4=4, X3=0/4=0
Step:4 Updating table: S1=0/4=0 S2=1/4=1/4
S3=0/4=0
Cj -1 3 -2 0 0 0 Min Ratio Updating R1 So
R1=R1+R2
BasicVariable xB/xk 7 3 -1 3 1 0 0
CB xB x1 x2 x3 s1 s2 s3 3 -1/2 1 0 0 1/4 0
10 5/2 0 3 1 1/4 0
𝟓
s1 0 10 5/2 0 3 1 1/4 0 10÷ = 4
𝟐 R3=R3-3R2
x2 3 3 -1/2 1 0 0 1/4 0 10 -4 3 8 0 0 1
- 9 3/2 3 0 0 3/4 0
s3 0 1 -5/2 0 8 0 -3/4 1 - - + - - - - -
1 - 5/2 0 8 0 - 3/4 1
Z|= 9 ▲J -1/2 0 2 0 3/4 0

Z|=CBxXB
Z|=(0,3,0)(10,3,1)=(0,10)+(3,3)+(0,1)=9
▲J=CBXj-Cj
▲J=CBX1- C1=(0,3,0)(5/2,-1/2,-5/2) – (-1) =0–3/2-0+1=-1/2 ▲J=CBX2- C2=(0,3,0)(0,1,0) –3=0 + 3 + 0 - 3= 0
▲J=CBX3- C3 =(0,3,0)(3,0,8) – (-2)=0 + 0 + 0 + 2=2 ▲J=CBS1- S1 =(0,3,0)(1,0,0) – 0 =0 + 0 + 0 - 0= 0
▲J=CBS2- S2 =(0,3,0)(1/4,1/4,-3/4) –0=0+3/4+ 0-0=3/4 ▲J=CBS3- S3 =(0,3,0)(0,0,1) – 0=0 + 0 + 0 - 0 = 0
 Linear Programming Problems (LPP): Solution for Key element= 1
XB=10÷5/2=4, X1=5/2÷5/2=1
Simplex Method, Maximization problem: X2=0÷5/2=0, X3=3÷5/2=6/5
Step:4 Updating table: S1=1÷5/2=2/5 S2=1/4÷5/2=1/10
S3=0÷5/2=0
Cj -1 3 -2 0 0 0 Min Ratio
Updating R1 So
BasicVariable R2=R2+1/2R1
CB xB x1 x2 x3 s1 s2 s3 xB/xk 3 -1/2 1 0 0 1/4 0
2 1/2 0 3/5 1/5 1/20 0
x1 -1 4 1 0 6/5 2/5 1/10 0 5 0 1 3/5 1/5 3/10 0

x2 3 5 0 1 3/5 1/5 3/10 0 R3=R3+5/2R1

1 -5/2 0 8 0 -3/4 1
s3 0 11 0 0 11 1 -1/2 1 10 5/2 0 3 1 1/4 0
11 0 0 11 1 -1/2 1
Z|= 11 ▲J 0 0 13/5 1/5 4/5 0

Z|=CBxXB Since, all ▲J>optimal solution is obtained,

Z|=(-1,3,0)(4,5,11)=(-1,4)+(3,5)+(0,11)=-4+15+0=11 optimal solution is Z|=11, X1=4 and x2=5
▲J=CBXj-Cj
▲J=CBX1- C1= -1+0+0=-1+1=0 ▲J=CBX2- C2=0+ 3 + 0 - 3= 0
▲J=CBX3- C3 =(-1,3,0)(6/5,3/5,11)-(-2)=-6/5+9/5+0+2=13/5 ▲J=CBS1- S1 =(-1,3,0)(2/5,1/5,-1/2)–0 =-2/5+3/5+0-0=1/5
▲J=CBS2- S2 =(-1,3,0)(1/10,3/10,1)–0=-1/10+9/10+0-0=8/10=4/5 ▲J=CBS3- S3 =(-1,3,0)(0,0,1) – 0=0 + 0 + 0 - 0 = 0
 Linear Programming Problems (LPP):
Degeneracy Problem in Simplex Method |Tie for Minimum Ratio:
Cj -1 3 -2 0 0 0 Min Ratio

BasicVariable CB xB x1 x2 x3 s1 s2 s3 xB/xk xB/xk xB/xk

x2 2 2 2 1 -1 1 0 0 -
s2 0 8 4 0 4 1 1 0 8/4=2 0/4=0 1/4

s3 0 4 2 0 2 -1 0 1 4/2=2 0/2=0 0/2=0

Z=6 ▲J 3 0 -3 2 0 0

x2 s2 s3
➢ For finding minimum ratio: only for tied rows 1 0 0
Elements of the first column of unit matrix 0 1 0
Corresponding elements of key column
0 0 1
Linear Programming Problems (LPP):

Min Z=3x1+x2
Subject to
x1+x2> 1
2x1+3x > 2
And x1, x2> 0
Solve through simplex method