Unit – IV

Lecture– III
Mr.R.R.Kshatriya
Assistant Professor,
Department of Civil Engineering,
Matoshri College of Engineering and Research Centre, Nashik.
Savitribai Phule Pune University, Pune.
Department of Civil Engineering

Linear Programming (B)

Simplex method

Two phase method

Big – M method

Duality

Operation Research 2
Department of Civil Engineering

Contents of Lecture
 Two phase method
 Maximization problems
 Minimization problem

Operation Research 3
Department of Civil Engineering

Two phase method

Operation Research 4
Department of Civil Engineering

Two phase method

Obj. function
 Phase–I:
 If the problem is of minimization, then convert it in
Max. -A to maximization.
 Put ‘0’ coefficient to all variable except ‘A’ in
objective function
Constraints  Find the optimal solution for Phase-I (free from ‘A’)
 Phase–II:
≤ +S
 Assign actual coefficient to all variables in objective
≥ -S+A function to the optimal solution of Phase-I
= +A  Find the optimal solution for Phase-II

Operation Research 5
Department of Civil Engineering
Maximization Problems
Example 1 Solution:
Max. Z = 4x1+5x2
Let’s introduce slack variables s1, s2 (with 0
Subject to: coefficient in objective function and 1 coefficient in
2x1 + 3x2 ≤ 6 constraints) and artificial variable A1 to convert
3x1 + x2 ≥ 3 inequality constraints into equality constraints
And x1, x2 ≥ 0 Max. Z = 4x1 + 5x2 + 0s1 + 0s2 – A1
Subject to:
Max. -A 2x1 + 3x2 + s1 = 6
3x1+ x2 - s2 + A1 = 3
≤ +S And x1, x2 ≥ 0
≥ -S+A
= +A Operation Research 6
Department of Civil Engineering

Phase-I Max. Z = 0x1 + 0x2 + 0s1 + 0s2 – A1

Subject to: 2x1 + 3x2 + s1 = 6
3x1+ x2 - s2 + A1 = 3
Iteration 1:
Cj 0 0 0 0 -1
Coeff. B θ
BV X1 X2 S1 S2 A1
0 S1 2 3 1 0 0 6 3
-1 A1 3 1 0 -1 1 3 1
Zj -3 -1 0 1 -1 -3
Zj – Cj -3 -1 0 1 0
R2 new = R2 old / 3
R1 new = R1 old – 2*R2 new
Operation Research 7
Department of Civil Engineering

Iteration 2: R2 new = R2 old / 3

R1 new = R1 old – 2*R2 new
Cj 0 0 0 0
Coeff. B
BV X1 X2 S1 S2
0 S1 0 2.33 1 -0.67 4
0 X1 1 0.33 0 0.33 1
Zj 0 0 0 0 0
Zj – Cj 0 0 0 0

This is an optimal solution for Phase-I

Operation Research 8
Department of Civil Engineering

Phase-II
Max. Z = 4x1 + 5x2 + 0s1 + 0s2
Iteration 3:
Cj 4 5 0 0
Coeff. B θ
BV X1 X2 S1 S2
0 S1 0 2.33 1 -0.67 4 1.72
4 X1 1 0.33 0 0.33 1 3
Zj 4 1.33 0 1.33 4
Zj – Cj 0 -3.67 0 1.33

R1 new = R1 old / 2.33

R2 new = R2 old – 0.33*R1 new

Operation Research 9
Department of Civil Engineering
Iteration 4:
R1 new = R1 old / 2.33
R2 new = R2 old – 0.33*R1 new

Cj 4 5 0
Coeff. B
BV X1 X2 S2
5 X2 0 1 -0.29 1.72
4 X1 1 0 0.43 0.43
From table,
Zj 4 5 0.27 10.32 X1 = 0.43, X2 = 1.72
Zj – Cj 0 0 0.27 And S1 = 0, S2 = 0, A1 = 0

This is an optimal solution for Phase-II Max. Z = 4x1+5x2

= 4(0.43) + 5(1.72)
= 10.32
Operation Research 10
Department of Civil Engineering

Example 2
Max. Z = x1+2x2+3x3 Solution:
Subject to: Let’s introduce slack variables s1, s2 (with 0
x1+x2+x3 = 2 coefficient in objective function and 1 coefficient in
3x1-2x2+2x3 ≤ 3 constraints) and artificial variable A1, A2 to convert
x1+2x3 ≥ 3 inequality constraints into equality constraints
And x1, x2, x3 ≥ 0 Max. Z = x1 + 2x2 + 3x3 + 0s1 + 0s2 – A1 – A2
Subject to:
Max. -A x1+x2+x3+A1 = 2
3x1-2x2+2x3+S1 = 3
x1+2x3-S2+A2 = 3
≤ +S And x1, x2, x3 ≥ 0
≥ -S+A
= +A Operation Research 11
Department of Civil Engineering
Max. Z = 0x1 + 0x2 + 0x3 + 0s1 + 0s2 – A1 – A2
Phase-I
Subject to: x1+x2+x3+A1 = 2
3x1-2x2+2x3+S1 = 3
Iteration 1: x1+2x3-S2+A2 = 3
Cj 0 0 0 0 0 -1 -1
Coeff. B θ
BV X1 X2 X3 S1 S2 A1 A2
-1 A1 1 1 1 0 0 1 0 2 2
0 S1 3 -2 2 1 0 0 0 3 1.5
-1 A2 1 0 2 0 -1 0 1 3 1.5
Zj -2 -1 -3 0 1 -1 -1 -5
Zj – Cj -2 -1 -3 0 1 0 0
R3 new = R3 old / 2
R1 new = R1 old – 1*R3 new
Operation Research R2 new = R2 old – 2*R3 new 12
Department of Civil Engineering
Iteration 2: R3 new = R3 old / 2
R1 new = R1 old – 1*R3 new
R2 new = R2 old – 2*R3 new
Cj 0 0 0 0 0 -1
Coeff. B θ
BV X1 X2 X3 S1 S2 A1
-1 A1 0.5 1 0 0 0.5 1 0.5 0.5
0 S1 2 -2 0 1 1 0 0 0
0 X3 0.5 0 1 0 -0.5 0 1.5 ∞
Zj -0.5 -1 0 0 -0.5 -1 -0.5
Zj – Cj -0.5 -1 0 0 -0.5 0
R1 new = R1 old
R2 new = R2 old + 2*R1 new
R3 new = R3 old
Operation Research 13
Department of Civil Engineering
Iteration 3: R1 new = R1 old
R2 new = R2 old + 2*R1 new
R3 new = R3 old
Cj 0 0 0 0 0
Coeff. B
BV X1 X2 X3 S1 S2
0 X2 0.5 1 0 0 0.5 0.5
0 S1 3 0 0 1 2 1
0 X3 0.5 0 1 0 -0.5 1.5
Zj 0 0 0 0 0 0
Zj – Cj 0 0 0 0 0
This is an optimal solution for Phase-I

Operation Research 14
Department of Civil Engineering

Phase-II
Max. Z = x1 + 2x2 + 3x3 + 0s1 + 0s2
Iteration 4:
Cj 1 2 3 0 0
Coeff. B θ
BV X1 X2 X3 S1 S2
2 X2 0.5 1 0 0 0.5 0.5 1
0 S1 3 0 0 1 2 1 0.5
3 X3 0.5 0 1 0 -0.5 1.5 -3
Zj 2.5 2 3 0 -0.5 5.5
Zj – Cj 1.5 0 0 0 -0.5
R2 new = R2 old / 2
R1 new = R1 old – 0.5*R2 new
R3 new = R3 old + 0.5*R2 new
Operation Research 15
Department of Civil Engineering
R2 new = R2 old / 2
R1 new = R1 old – 0.5*R2 new
Iteration 5: R3 new = R3 old + 0.5*R2 new

Cj 1 2 3 0
Coeff. B
BV X1 X2 X3 S2
2 X2 -0.25 1 0 0 0.25
0 S2 1.5 0 0 1 0.5
3 X3 1.25 0 1 0 1.75 From table,
X2 = 0.25, X3 = 1.75 , S2 = 0.5
Zj 3.25 2 3 0 5.75 And X1 = 0, S1 = 0, A1 = 0 , A2 = 0
Zj – Cj 2.25 0 0 0
Max. Z = x1+2x2+3x3
This is an optimal solution for Phase-II = 0 + 2(0.25) + 3(1.75)
= 5.75
Operation Research 16
Department of Civil Engineering
Minimization Problem
Example 3
Min. Z = x1+x2 Solution:
Subject to: Multiply by (-1) to objective function to convert
minimization problem into maximization problem.
2x1+x2 ≥ 4
Max.Z = -x1 - x2
x1+7x2 ≥ 7
Let’s introduce slack variables s1, s2 (with 0 coefficient in
And x1, x2, x3 ≥ 0 objective function and 1 coefficient in constraints) and artificial
variable A1, A2 to convert inequality constraints into equality
constraints
Max. -A Max. Z = -x1 - x2 + 0s1 + 0s2 – A1 – A2
Subject to:
≤ +S 2x1+ x2 – s1 + A1 = 4
≥ -S+A x1 + 7x2 – s2 + A2 = 7
And x1, x2, x3 ≥ 0
= +A Operation Research 17
Department of Civil Engineering
Phase-I Max. Z = -0x1 - 0x2 + 0s1 + 0s2 – A1 – A2
Subject to:
2x1+ x2 – s1 + A1 = 4
Iteration 1: x1 + 7x2 – s2 + A2 = 7
Cj 0 0 0 0 -1 -1
Coeff. B θ
BV X1 X2 S1 S2 A1 A2
-1 A1 2 1 -1 0 1 0 4 4
-1 A2 1 7 0 -1 0 1 7 1
Zj -3 -8 1 1 -1 -1 -11
Zj – Cj -3 -8 1 1 0 0
R2 new = R2 old / 7
R1 new = R1 old – 1*R2 new
Operation Research 18
Department of Civil Engineering
Iteration 2:
R2 new = R2 old / 7
R1 new = R1 old – 1*R2 new
Cj 0 0 0 0 -1
Coeff. B θ
BV X1 X2 S1 S2 A1
-1 A1 1.857 0 -1 0.143 1 3 1.615
0 X2 0.143 1 0 -0.143 0 1 7
Zj -1.857 0 1 -0.143 -1 -3
Zj – Cj -1.857 0 1 -0.143 0

R1 new = R1 old / 1.857

R2 new = R2 old – 0.143*R1 new

Operation Research 19
Department of Civil Engineering
Iteration 3:
R1 new = R1 old / 1.857
R2 new = R2 old – 0.143*R1 new
Cj 0 0 0 0
Coeff. B
BV X1 X2 S1 S2
0 X1 1 0 -0.538 0.077 1.615
0 X2 0 1 0.077 -0.154 0.77
Zj 0 0 0 0 0
Zj – Cj 0 0 0 0

This is an optimal solution for Phase-I

Operation Research 20
Department of Civil Engineering

Phase-II Max. Z = -x1 - x2 + 0s1 + 0s2

Iteration 4:
Cj -1 -1 0 0
Coeff. B
BV X1 X2 S1 S2
-1 X1 1 0 -0.538 0.077 1.615 From table,
X1 = 1.615, X2 = 0.77
-1 X2 0 1 0.077 -0.154 0.77 And S1 = 0, S2 = 0, A1 = 0, A2 = 0

Zj -1 -1 0.461 0.077 -2.385 Max. Z = -x1 - x2

Zj – Cj 0 0 0.461 0.077 = - 1.615 – 0.77
= - 2.385
This is an optimal solution for Phase-II
Min.Z = Max.Z * (-1)
= 2.385

Operation Research 21
Department of Civil Engineering

Summary

 Two phase method

 Maximization problems
 Minimization problem

Operation Research 22
Department of Civil Engineering

Assignment
Example 1 Example 2
Max. Z = 5x1+2x2-x3 Min. Z = 4x1+8x2+3x3
Subject to: Subject to:
2x1+2x2-x3 ≥ 2 x1+x2 ≥ 2
3x1-4x2 ≤ 3 2x1+x3 ≥ 5
x2+3x3 ≤ 5 And x1, x2, x3 ≥ 0
And x1, x2, x3 ≥ 0

Operation Research 23
Department of Civil Engineering

Thank you
Operation Research 24