Linear Programming Problems (LPP):
General LPP to Standard LPP for Simplex Method Condition:
➢ Write the objective function in the maximization form.
➢ Convert all inequalities into to equation.
➢ The right-side elements of each constraint should be made non-
negative
➢ All variables must have non-negative values.
Linear Programming Problems (LPP):
General LPP to Standard LPP for Simplex Method Condition:
➢ Write the objective function in the maximization form.
Max Z or Min Z
If Max Z function No need of conversion
If Min W Function Need convert into Max Z function
Min (-Z)= Max Z\
For Example:
Min Z= -3x1+X2
After multiply with (-)
Max Z\ = 3x1-X2
Linear Programming Problems (LPP):
General LPP to Standard LPP for Simplex Method Condition:
➢ Convert all inequalities into to equation.
< + Slack
> - Surplus
For example,
x1+2x2 < 12
x1+2x2+s1= 12
And
2x1+x2 > 15
x1+2x2-s2=15
Linear Programming Problems (LPP):
General LPP to Standard LPP for Simplex Method Condition:
➢ The right-side elements of each constraint should be made non-
negative
For example,
x1+2x2-s2= -15 (Multiplying by -1)
x1-2x2+s2= 15
➢ All variables must have non-negative values.
For example,
x1+x2 < 3, x1> 0, x2 is unrestricted (-, + or 0) in sign
x1+(x\2-x\\2) < 3 x1, x\2, x\\ > 0
x1+x\2-x\\2+s1 = 3
Linear Programming Problems (LPP):
Example General LPP to Standard LPP :
1). Max Z= 3x1+x2
Subject to constraint
2x1+x2 < 2
3x1+4x2 > 12
and x1, x2> 0
SLPP:
Max Z= 3x1+x2
s.t. 2x1+x2+s1 = 2
3x1+4x2–s2 =12
and x1, x2, s1,s2> 0
Linear Programming Problems (LPP):
Example General LPP to Standard LPP :
2). Min Z= 4x1+2x2
Subject to constraint
3x1+x2 > 2
x1+x2 > 21
x1+2x2 > 30
and x1, x2> 0
SLPP: Max Z\= -4x1-2x2
s.t. 3x1+x2-s1 = 2
x1+x2-s2 = 21
x1+2x2-s3 = 30
and x1, x2, s1,s2, s3> 0
Linear Programming Problems (LPP):
Example General LPP to Standard LPP :
3). Min Z= x1+2x2+3x3
Subject to constraint
2x1+3x2+3x3 > -4
3x1+5x2+2x3 < 7
and x1, x2> 0, x3 is unrestricted in sign
SLPP: Max Z\= -x1-2x2-3x3
Subject to
-2x1-3x2-3(x\3-x\\3)+s1=4
3x1+5x2+2(x\3-x\\3)+s2 =7
and x1, x2, x\3, x\\,s1,s2> 0
Linear Programming Problems (LPP):
Step to solve linear programming problem using Simplex Method:
Step1: Convert the problem (Mathematical model) into standard form.
Step 2: Set up the initial simplex tableau
Step 3: Identify the entering and leaving variables
Step 4: Pivot to update tableau
Step 5: Identify the entering and leaving variables
Step 6: Pivot to update tableau
Step 7: Optimal solution
Linear Programming Problems (LPP):
Simplex Method, Maximization problem:
Q. Solve the following LPP Step 2: Represent in Matrix form [Ax=B]
Max Z= 80x1 +55x2
Subject to, x1
x1 x2 s1 s2
4x1+2x2 < 40 x2
2x1+4x2 < 32 4 2 1 0 = 40
s1 32
and x1, x2 > 0 2 4 0 1
Solution: s2
Step 1: Standard LPP
Max Z= 80x1 +55x2 +0s1 +0s2
4x1+2x2 +s1= 40
2x1+4x2 +s2= 32
and x1, x2 , s1, s2 > 0
Linear Programming Problems (LPP):
Simplex Method, Maximization problem:
Step:3 Construct starting simplex table
Cj 80 55 0 0
Basic Variable CB xB x1 x2 s1 s2
s1 0 40 4 2 1 0
s2 0 32 2 4 0 1
Z= ▲J
Linear Programming Problems (LPP):
Simplex Method, Maximization problem:
Step:4 Calculation of: Z and ▲J
Cj 80 55 0 0 Z=0x40+0x32=0
▲J=CBX1- C1=(0,0)(4,2) - 80
Basic Variable CB xB x1 x2 s1 s2 =(0x4+0x2)-80
=0+0-80=-80
s1 0 40 4 2 1 0 ▲J=CBX2- C2 =(0,0)(4,2) - 55
=(0x4+0x2) -55= -55
s2 0 32 2 4 0 1 ▲J=CBX3- C3 =(0,0)(1,0) - 0
=(0x1+0x0) - 0= 0
Z=0 ▲J -80 -55 0 0 ▲J=CBX4- C4 =(0,0)(1,0) - 0
=(0x1+0x0) - 0= 0
Z=CBXB CB=Coefficient of Basic variable (introduce new variables)
▲J=CBXj-CJ ▲J= net evaluation
Linear Programming Problems (LPP):
Simplex Method, Maximization problem:
Step 4:
➢ If all (Zj) or ▲J> 0, the solution under the test will be optimal
➢ If corresponding to any negative ▲J, all elements of the column xj are negative or
zero , then the solution under test will be unbounded.
➢ if at least one ▲J is negative, the solution is not optimal and then proceeds to
improve the solution in the next step.
Step 5:
➢ To improve the basic feasible solution, the incoming and outgoing vectors are need to
determined.
i) Incoming (entering) vector (xk) = Most negative value of ▲J
ii) Outgoing (leaving) vector= min (value) [xB/xk, xk>0]
Linear Programming Problems (LPP):
Simplex
Step 5: Method, Maximization problem:
Key Elements or Pivot element
Cj 80 55 0 0 Min Ratio
Basic Variable CB XB x1 x2 s1 s2 xB/xk
s1 0 40 4 2 1 0 40/4=10 Minimum value
Outgoing vector
s2 0 32 2 4 0 1 32/2=16
Z=0 ▲J -80 -55 0 0
Incoming vector
(xk)
Linear Programming Problems (LPP):
Simplex Method, Maximization problem:
Step 6: Mark the key elements (pivot elements) at the intersection of incoming and
outgoing.
i). Key elements should be one.
Solve for key elements= 1
ii). Remaining value of Xk (Column) should be zero. So
xB=40/4= 10
Min Ratio x1=4/4=1
Cj 80 55 0 0 x2=2/4=1/2
s1=1/4= ¼
Basic Variable CB xB x1 x2 s1 s2 xB/xk s2=0/4=0
ii)
x1 80 10 1 1/2 1/4 0 R2=R2 -2R1
32 2 4 0 1
s2 0 12 0 3 -1/2 1 20 2 1 1/2 0
- - - - -
Z= ▲J 12 0 3 -1/2 1
Step 7: Now repeat step 4 to step 6 until an optimal solution is obtained.
Linear Programming Problems (LPP):
Simplex Method, Maximization problem:
Step 6: Make the key elements (pivot elements) at the intersection of incoming and
outgoing.
i). Key elements should be one. Z=CB x XB = (80, 0) (10,12)
ii). Remaining value of Xk (Column) should be zero. Z=80x10 + 0x12=800
▲J=CBx1 - C1
=(80,0) (1,0) - 80
Cj 80 55 0 0 Min Ratio =80 + 0 – 80=0
▲J=CBx2 - C2
Basic Variable CB xB x1 x2 s1 s2 xB/xk =(80,0) (1/2,3) – 55
=40 +0 – 55=-15
x1 80 10 1 1/2 1/4 0 10 ÷1/2=20 ▲J=CBx3 - C3
Outgoing vector =(80,0) (1/4, -1/2) – 0
s2 0 12 0 3 -1/2 1 12÷3=4 =20-0-0=20
▲J=CBx4 - C4
Z=800 ▲J 0 -15 20 0 =(80,0) (0, 1) – 0=0
Incoming vector
Step 7: Now repeat step 4 to step 6 until an optimal solution is obtained.
Linear Programming Problems (LPP):
Simplex Method, Maximization problem:
Step 6: Make the key elements (pivot elements) at the intersection of incoming and
outgoing. Solve for key elements= 1
i). Key elements should be one. So
xB=12/3=4
ii). Remaining value of Xk (Column) should be zero. x =0/3=01
Min Ratio x2=3/3=1
Cj 80 55 0 0 s1=-1/2÷3= -1/6
s2=1÷3=1/3
Basic Variable CB xB x1 x2 s1 s2 xB/xk ii)
R1=R1 -1/2R2
x1 80 8 1 0 1/3 -1/6 10 1 1/2 1/4 0
2 0 1/2 -1/12 1/6
x2 55 4 0 1 -1/6 1/3 - - - - -
8 1 0 1/3 -1/6
Z= ▲J
Since all ▲J>0, optimal solution
Linear Programming Problems (LPP):
Simplex Method, Maximization problem:
Step 6: Make the key elements (pivot elements) at the intersection of incoming and
outgoing.
i). Key elements should be one. Z=CB x XB = (80, 55) (8,4)
Z=80x8 + 55x4=860
ii). Remaining value of Xk (Column) should be zero.
Min Ratio ▲J=CBx1 - C1
Cj 80 55 0 0 = (80,55) (1,0) - 80
=80 + 0 – 80=0
Basic Variable CB xB x1 x2 s1 s2 xB/xk ▲J=CBx2 - C2
=(80,55)(0,1)-55
x1 80 8 1 0 1/3 -1/6 =0+55-55=0
▲J=CBx3 - C3
x2 55 4 0 1 -1/6 1/3 = (80,55) (1/3,-1/6) - 0
=(80x1/3) + (55x-1/6) – 0
Z=860 ▲J 0 0 35/2 5 = 80/3 -55/6= 35/2
▲J=CBx4 - C4
Since all ▲J>0, optimal solution = (80,55) (-1/6,1/3)
=5
obtain Max z= 860, x1=8, x2=4
Linear Programming Problems (LPP):
Simplex Method, Unbounded problem:
Example of unbounded solution in simplex method
Max Z=3x1+4x2
Cj 3 4 0 0 Min Ratio
x1-x2< 1
x1-x2 < 2 Basic Variable CB xB x1 x2 s1 s2 xB/xk
and s1 0 3 0 0 1 1
x1, x2>0
x2 4 2 -1 1 0 1
Z=8 ▲J -7 0 0 4
Since all elements of the column x1 are negative or zero therefore the solution is
unbounded.
Linear Programming Problems (LPP):
Q2. Solve the following problem through simplex method
Max Z= 3x1+5x2
Subject to,
2x1+3x2 < 8
x1+2x2 < 5
and x1, x2 > 0
Q3. Solve the following problem through simplex method
Z= 6x1+ 2x2+12x3
Subject to,
4x1+x2+3x3<24
2x1+6x2+3x3<30
Standard form:
Z= 6x1+ 2x2+12x3+0s1+0s2
4x1+x2+3x3+s1+0s2=24
2x1+6x2+3x3+0s1+s2=30