Home > Operation Research calculators > Two-Phase method example

2. Two-Phase method example ( Enter your problem )
 Algorithm & Example-1Example-2Infeasible solution example Other related methods

1. Algorithm & Example-1

Algorithm
 Two-Phase Method Steps (Rule) Step-1: Phase-1 a. Form a new objective function by assigning zero to every original variable (including slack and surplus variables) and -1 to each of the artificial variables. eg. Max Z = - A1 - A2 b. Using simplex method, try to eliminate the artificial varibles from the basis. c. The solution at the end of Phase-1 is the initial basic feasible solution for Phase-2. Step-2: Phase-2 a. The original objective function is used and coefficient of artificial variable is 0 (so artificial variable is removed from the calculation process). b. Then simplex algorithm is used to find optimal solution.

Example
Find solution using Two-Phase method
MIN Z = x1 + x2
subject to
2x1 + x2 >= 4
x1 + 7x2 >= 7
and x1,x2 >= 0

Solution:
Problem is
 Min Z =   x_1  +   x_2
subject to
  2 x_1  +   x_2 ≥ 4   x_1  +  7 x_2 ≥ 7
and x_1,x_2 >= 0;

-->Phase-1<--

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

1. As the constraint-1 is of type '>=' we should subtract surplus variable S_1 and add artificial variable A_1

2. As the constraint-2 is of type '>=' we should subtract surplus variable S_2 and add artificial variable A_2

After introducing surplus,artificial variables
 Min Z =   A_1  +   A_2
subject to
  2 x_1  +   x_2  -   S_1  +   A_1 = 4   x_1  +  7 x_2  -   S_2  +   A_2 = 7
and x_1,x_2,S_1,S_2,A_1,A_2 >= 0

 Iteration-1 C_j 0 0 0 0 1 1 B C_B X_B x_1 x_2 Entering variable S_1 S_2 A_1 A_2 MinRatio (X_B)/(x_2) A_1 1 4 2 1 -1 0 1 0 (4)/(1)=4 A_2 Leaving variable 1 7 1 (7)  (pivot element) 0 -1 0 1 (7)/(7)=1-> Z=0 0=Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 3 3=1xx2+1xx1Z_j=sum C_B x_1 8 8=1xx1+1xx7Z_j=sum C_B x_2 -1 -1=1xx(-1)+1xx0Z_j=sum C_B S_1 -1 -1=1xx0+1xx(-1)Z_j=sum C_B S_2 1 1=1xx1+1xx0Z_j=sum C_B A_1 1 1=1xx0+1xx1Z_j=sum C_B A_2 C_j-Z_j -3 -3=0-3 -8 -8=0-8   uarr 1 1=0-(-1) 1 1=0-(-1) 0 0=1-1 0 0=1-1

Negative minimum C_j-Z_j is -8 and its column index is 2. So, the entering variable is x_2.

Minimum ratio is 1 and its row index is 2. So, the leaving basis variable is A_2.

:. The pivot element is 7.

Entering =x_2, Departing =A_2, Key Element =7

R_2(new)= R_2(old)-: 7

R_1(new)= R_1(old)- R_2(new)

 Iteration-2 C_j 0 0 0 0 1 B C_B X_B x_1 Entering variable x_2 S_1 S_2 A_1 MinRatio (X_B)/(x_1) A_1 Leaving variable 1 3 3=4-1R_1(new)= R_1(old)- R_2(new) (13/7) 13/7=2-1/7 (pivot element)R_1(new)= R_1(old)- R_2(new) 0 0=1-1R_1(new)= R_1(old)- R_2(new) -1 -1=(-1)-0R_1(new)= R_1(old)- R_2(new) 1/7 1/7=0-(-1/7)R_1(new)= R_1(old)- R_2(new) 1 1=1-0R_1(new)= R_1(old)- R_2(new) (3)/(13/7)=1.62-> x_2 0 1 1=7-:7R_2(new)= R_2(old)-: 7 1/7 1/7=1-:7R_2(new)= R_2(old)-: 7 1 1=7-:7R_2(new)= R_2(old)-: 7 0 0=0-:7R_2(new)= R_2(old)-: 7 -1/7 -1/7=(-1)-:7R_2(new)= R_2(old)-: 7 0 0=0-:7R_2(new)= R_2(old)-: 7 (1)/(1/7)=7 Z=0 0=0xx1Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 13/7 13/7=1xx13/7+0xx1/7Z_j=sum C_B x_1 0 0=1xx0+0xx1Z_j=sum C_B x_2 -1 -1=1xx(-1)+0xx0Z_j=sum C_B S_1 1/7 1/7=1xx1/7+0xx(-1/7)Z_j=sum C_B S_2 1 1=1xx1+0xx0Z_j=sum C_B A_1 C_j-Z_j -13/7 -13/7=0-13/7   uarr 0 0=0-0 1 1=0-(-1) -1/7 -1/7=0-1/7 0 0=1-1

Negative minimum C_j-Z_j is -13/7 and its column index is 1. So, the entering variable is x_1.

Minimum ratio is 1.62 and its row index is 1. So, the leaving basis variable is A_1.

:. The pivot element is 13/7.

Entering =x_1, Departing =A_1, Key Element =13/7

R_1(new)= R_1(old)xx7/13

R_2(new)= R_2(old)- 1/7 R_1(new)

 Iteration-3 C_j 0 0 0 0 B C_B X_B x_1 x_2 S_1 S_2 MinRatio x_1 0 21/13 21/13=3xx7/13R_1(new)= R_1(old)xx7/13 1 1=13/7xx7/13R_1(new)= R_1(old)xx7/13 0 0=0xx7/13R_1(new)= R_1(old)xx7/13 -7/13 -7/13=(-1)xx7/13R_1(new)= R_1(old)xx7/13 1/13 1/13=1/7xx7/13R_1(new)= R_1(old)xx7/13 x_2 0 10/13 10/13=1-1/7xx21/13R_2(new)= R_2(old)- 1/7 R_1(new) 0 0=1/7-1/7xx1R_2(new)= R_2(old)- 1/7 R_1(new) 1 1=1-1/7xx0R_2(new)= R_2(old)- 1/7 R_1(new) 1/13 1/13=0-1/7xx(-7/13)R_2(new)= R_2(old)- 1/7 R_1(new) -2/13 -2/13=(-1/7)-1/7xx1/13R_2(new)= R_2(old)- 1/7 R_1(new) Z=0 0=0xx21/13+0xx10/13Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 0 0=0xx1+0xx0Z_j=sum C_B x_1 0 0=0xx0+0xx1Z_j=sum C_B x_2 0 0=0xx(-7/13)+0xx1/13Z_j=sum C_B S_1 0 0=0xx1/13+0xx(-2/13)Z_j=sum C_B S_2 C_j-Z_j 0 0=0-0 0 0=0-0 0 0=0-0 0 0=0-0

Since all C_j-Z_j >= 0

Hence, optimal solution is arrived with value of variables as :
x_1=21/13,x_2=10/13

Min Z = 0

-->Phase-2<--

we eliminate the artificial variables and change the objective function for the original,
 Iteration-1 C_j 1 1 0 0 B C_B X_B x_1 x_2 S_1 S_2 MinRatio x_1 1 21/13 1 0 -7/13 1/13 x_2 1 10/13 0 1 1/13 -2/13 Z=31/13 31/13=1xx21/13+1xx10/13Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 1 1=1xx1+1xx0Z_j=sum C_B x_1 1 1=1xx0+1xx1Z_j=sum C_B x_2 -6/13 -6/13=1xx(-7/13)+1xx1/13Z_j=sum C_B S_1 -1/13 -1/13=1xx1/13+1xx(-2/13)Z_j=sum C_B S_2 C_j-Z_j 0 0=1-1 0 0=1-1 6/13 6/13=0-(-6/13) 1/13 1/13=0-(-1/13)

Since all C_j-Z_j >= 0

Hence, optimal solution is arrived with value of variables as :
x_1=21/13,x_2=10/13

Min Z = 31/13

This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here

Dear user,