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

Copyright © 2020. All rights reserved. Terms, Privacy

# Adblocker detected!

Dear user,

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

## We need money to operate the site, and almost all of it comes from our online advertising.

Please add atozmath.com to your ad blocking whitelist or disable your adblocking software.

Thanks for your support

×