Solution:

Linear Programming Problem (LPP)

Converting into equalities according to the rules which are as:

By Two-Phase Method Subject to:

x1  4 x 2  3 x3  s1  A1  50
Two types of problems: 2 x1  x 2  x3  s2  A2  30
 Objective Function can maximise and can minimise
-3 x1  2 x 2  x3  s3  -40
Only minimise type of objective function can be solved with the help of Two-phase
method.

If there is maximise problem case, then first we convert into minimise case then apply x1 , x 2 , x3  0
two phase method.

Objective Function:
Rules for constraints:
 For ≥ type constraint
 Subtract slack variable and add artificial variable [-s, +A] Min z  3 x1  2 x 2  x3  0 s1  0 s 2  0 s 3  1 A1  1 A2
 For ≤ type constraint
 Add only slack variable [+s]
 For = type constraint
 Add only artificial variable [+A]

Procedure for method for Phase I and Phase II

Question # 8:
For Phase I

Objective Function: 1. Follow the previous simplex method with revised objective function
2. Follow that till we obtained the feasible solution and searched the optimality
Min z  3 x1  2 x 2  x 3 condition
3. revised objective function means taken only Artificial variable constant and take Zero
Subject to: all others
4. Priority given to A1 over s1
x1  4 x 2  3 x3  50 5. At the end of Phase I, check weather the objective function values are zero or not in
the optimal table.
2 x1  x 2  x3  30 6. If YES, then move to phase II.
7. If No, then that will be the Answer and Infeasible Solution as well.
-3 x1  2 x 2  x3  -40

x1 , x 2 , x3  0
1 2
 Simplex Table 1 Simplex Table 1

CBi Cj 0 0 0 0 0 0 1 1 CBi Cj 0 0 0 0 0 0 1 1
BV x1 x2 x3 s1 s2 s3 A1 A2 Solution BV x1 x2 x3 s1 s2 s3 A1 A2 Solution

1 A1 1 4 3 -1 0 0 1 0 50 1 A1 1 4 3 -1 0 0 1 0 50
1 A2 2 1 1 0 -1 0 0 1 30 1 A2 2 1 1 0 -1 0 0 1 30
0 s3 -3 -2 -1 0 0 1 0 0 -40 0 s3 -3 -2 -1 0 0 1 0 0 -40

Zj 3 5 4 -1 -1 0 1 1 80 Zj 3 5 4 -1 -1 0 1 1 80
Cj -Zj -3 -5 -4 1 1 0 0 0 Cj -Zj -3 -5 -4 1 1 0 0 0

x2 is entering variable and A1 is the leaving variable

CBi = coefficient (value) of slack variable
Cj = coefficient of objective faction
BV = Basic Variable
Simplex Table 2
Solution = Inequality converted as Equality
Ratio = Solution / Key Column values
CBi Cj 0 0 0 0 0 0 1

Zj = (obtained by multiplying and adding all the CBi) BV x1 x2 x3 s1 s2 s3 A2 Solution

0 x2 1/4 1 3/4 -1/4 0 0 0 25/2

After computing the Cj – Zj values, check the optimality condition. For Minimisation 1 A2 7/4 0 ¼ 1/4 -1 0 0 35/2
cases, 0 s3 -10/4 0 1/2 -1/2 0 0 0 -15

Cj – Zj ≥ 0
Zj 7/4 0 1/4 1/4 -1 0 0
We will select the highest negative value (-5) Cj -Zj -7/4 0 -1/4 -1/4 1 0 1

Selecting the maximum positive vale for row (50)

For Minimisation cases Cj – Zj ≥ 0

3 4
 Simplex Table 2
For Phase II:
We will use the previous table as it as. However, objective function actual/original values
will be using.
CBi Cj 0 0 0 0 0 0 1
BV x1 x2 x3 s1 s2 s3 A2 Solution
Simplex Table 4
0 x2 1/4 1 3/4 -1/4 0 0 0 25/2
1 A2 7/4 0 ¼ 1/4 -1 0 0 35/2 CBi Cj 3 2 1 0 0 0
0 s3 -10/4 0 1/2 -1/2 0 0 0 -15 BV x1 x2 x3 s1 s2 s3 Solution

Zj 7/4 0 1/4 1/4 -1 0 0 2 x2 0 1 5/7 -2/7 -1/7 0 10

Cj -Zj -7/4 0 -1/4 -1/4 1 0 1 3 x1 1 0 1/7 1/7 -4/7 0 10
0 s3 0 0 6/7 -1/7 10/7 0 10

x1 is entering variable and A2 is the leaving variable

Zj 3 2 13/7 -1/7 -14/7 0 50
Cj -Zj 00 00 -6/7 1/7 14/7 0
Simplex Table 3
For Minimisation cases Cj – Zj ≥ 0
CBi Cj 0 0 0 0 0 0
BV x1 x2 x3 s1 s2 s3 Solution
Simplex Table 4

0 x2 0 1 5/7 -2/7 -1/7 0 10

CBi Cj 3 2 1 0 0 0
0 x1 1 0 1/7 1/7 -4/7 0 10
BV x1 x2 x3 s1 s2 s3 Solution
0 s3 0 0 6/7 -1/7 10/7 0 10

2 x2 0 1 5/7 -2/7 -1/7 0 10

Zj 0 0 0 0 0 0 0
3 x1 1 0 1/7 1/7 -4/7 0 10
Cj -Zj 0 0 0 0 0 0
0 s3 0 0 6/7 -1/7 10/7 0 10

Optimality condition fulfil here

Zj 3 2 13/7 -1/7 -14/7 0 50
Cj -Zj 00 00 -6/7 1/7 14/7 0

5 6
x3 is entering variable and s3 is leaving variable
Practice Problem:
Simplex Table 5
Consider the following LPP and solve by Two-Phase method.

CBi Cj 3 2 1 0 0
Objective Function:
BV x1 x2 x3 s1 s2 Solution
M in z  4 x1  x 2
2 x2 0 1 0 -1/6 -4/3 5/3 Subject to:

3 x1 1 0 0 1/6 1/3 25/3

3 x1  x 2  3
1 x3 0 0 1 -1/6 5/3 35/3
4 x1  3 x 2  6
Zj 3 2 1 0 0 40 x1  2 x 2  4
Cj -Zj 0 0 0 0 0

x1 , x 2  0
Condition satisfied

Z j  40, when
x1  25 / 3
Answer:
x2  5 / 3
x3  35 / 3
optimum Z j  17 / 5, when
Substitute x1 to x3 in question then (O.F.), then Zj is coming out to be 40. x1  9 / 5
x2  5 / 3

7 8
 Linear Programming Problem (LPP) using x1  x 2  50
x1  20
Dual Simplex Method or Duality Problem x 2  40

Basic Concept: x1 , x 2  0
Every liner programming problems always have another problem which is called Duality
of a Primal Problem.
Solution:
For example: Maximize the profit means the same problem exist for minimization
MIN case will be converted to MAX case.
problem
Check the standard format of LP, here MIN case so all the constraint must be ≥ type.
Maximization of profit problem here is primal problem
Minimization of cost here is Dual problem
This is in the standard format now forming case.
Objective Function:

Primal means original Problem

Dual Means Derived problem M in z  25 x1  10 x 2
Subject to:

x1  x 2  50
Duality simplex method is method to solve LPP to obtained optimal solution.
x1  0 x 2  20
0 x1  x 2   40
Question # 9:
x1 , x 2  0
Solve the following dual problem by using Simplex method.

Objective Function: Convert into DUAL problem as

Min z  25 x1  10 x 2 Objective Function

Subject to:
MAX z  50 x1  20 x 2  40 x 3

9 10
****Subject to (Covert All Columns’ coefficients into Rows) Solution = Inequality converted as Equality
Ratio = Solution / Key Column values
x1  x 2  0 x3  25
x1  0 x 2  x3  10 Zj = (obtained by multiplying and adding all the CBi)

Before simplex table, we need to convert Non-equalities into Equalities by using slack
variable
Simplex Table 1

Subject to:
CBi Cj 50 20 -40 0 0
x1  x 2  0 x3  s1  25 BV x1 x2 x3 s1 s2 Solution Ratio
0 1 1 0 1 0 25 25/1 = 25
x1  0 x 2  x3  s 2  10 s1
0 S2 1 0 -1 0 1 10 10/1 = 10
Objective Function:
MAX z  50 x1  20 x 2  40 x3  0 s1  0 s 2 Zj 0 0 0 0 0
Cj -Zj 50 20 -40 0 0

Simplex Table 1 x1 is entering and s2 is leaving. 2nd row obtained as divined Key Element (1) to all the row
coefficients.

CBi Cj 50 20 -40 0 0
BV x1 x2 x3 s1 s2 Solution Ratio
0 s1 1 1 0 1 0 25
0 S2 1 0 -1 0 1 10 Simplex Table 2

Zj 0 0 0 0 0 CBi Cj 50 20 -40 0 0
Cj -Zj 50 20 -40 0 0
BV x1 x2 x3 s1 s2 Solution Ratio
0 s1 0 1 1 1 -1 15
All Cj – Zj ≤ 0 50 x1 1 0 -1 0 1 10

CBi = coefficient (value) of slack variable Zj 50 0 -50 0 50

Cj = coefficient of objective faction Cj -Zj 0 20 10 0 -50
BV = Basic Variable

11 12
 Check the duality condition from the above equation as

Simplex Table 2 MAX z  50 x1  20 x 2  40 x3  0 s1  0 s 2

CBi Cj 50 20 -40 0 0 Substitute all the values in the above equation to verify the result.
BV x1 x2 x3 s1 s2 Solution Ratio
Practice Question:
0 s1 0 1 1 1 -1 15 15/1 = 15
50 x1 1 0 -1 0 1 10 10/0 = ∞
Question # 9:
Zj 50 0 -50 0 50
Solve the following dual problem by using Simplex method.
Cj -Zj 0 20 10 0 -50

Objective Function:
x2 is entering variable and s1 is leaving variable.
Max z  12 x1  3 x 2  x3
Simplex Table 3 Subject to:

CBi Cj 50 20 -40 0 0 10 x1  2 x 2  x 3  100

BV x1 x2 x3 s1 s2 Solution Ratio
7 x1  3 x 2  2 x3  77
20 x2 0 1 1 1 -1 15
50 x1 1 0 -1 0 1 10
2 x1  4 x 2  x3  80

Zj 50 20 -30 20 30 800 x1 , x 2 , x 3  0
Cj -Zj 0 0 -10 -20 30

Condition Satisfied as all are –ve or less than zero.

Z j  800, when
x1  10
x 2  15
13 14
Question # 10: 2) Solution with Duality method
Solve the following dual problem by using Simplex method? Compare results from those
565
obtained without Duality methods? Zj  , when
23
Objective Function: x1  51 / 23
M ax z  3 x1  2 x 2  5 x3 x 2   58 / 23
Subject to: x3  9 / 23
x1  3 x 2  2 x3  15
2 x 2  x3  5
2 x1  x 2  5 x3  10

x1 , x 2 , x3  0

Solution:

1) With-out Duality method

565
Zj  , when
23
x1  120 / 23
x 2  65 / 23
x3  15 / 23

15 16