Home > Operation Research calculators > Simplex method example

2. Two-Phase method example ( Enter your problem )

2. Example-2

Find solution using Two-Phase method
MIN Z = 5x1 + 2x2 + 10x3
subject to
x1 - x3 <= 10
x2 + x3 >= 10
and x1,x2,x3 >= 0

Solution:
Problem is
 Min Z =  5 x_1  +  2 x_2  +  10 x_3
subject to
   x_1  -   x_3 ≤ 10   x_2  +   x_3 ≥ 10
and x_1,x_2,x_3 >= 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 add slack variable S_1

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

After introducing slack,surplus,artificial variables
 Min Z =   A_1
subject to
   x_1  -   x_3  +   S_1 = 10   x_2  +   x_3  -   S_2  +   A_1 = 10
and x_1,x_2,x_3,S_1,S_2,A_1 >= 0

 Iteration-1 C_j 0 0 0 0 0 1 B C_B X_B x_1 x_2 Entering variable x_3 S_1 S_2 A_1 MinRatio (X_B)/(x_2) S_1 0 10 1 0 -1 1 0 0 --- A_1 Leaving variable 1 10 0 (1)  (pivot element) 1 0 -1 1 (10)/(1)=10-> Z=0 0=Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 0 0=0xx1+1xx0Z_j=sum C_B x_1 1 1=0xx0+1xx1Z_j=sum C_B x_2 1 1=0xx(-1)+1xx1Z_j=sum C_B x_3 0 0=0xx1+1xx0Z_j=sum C_B S_1 -1 -1=0xx0+1xx(-1)Z_j=sum C_B S_2 1 1=0xx0+1xx1Z_j=sum C_B A_1 C_j-Z_j 0 0=0-0 -1 -1=0-1uarr -1 -1=0-1 0 0=0-0 1 1=0-(-1) 0 0=1-1

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

Minimum ratio is 10 and its row index is 2. So, the leaving basis variable is A_1.

:. The pivot element is 1.

Entering =x_2, Departing =A_1, Key Element =1

R_2(new)= R_2(old)

R_1(new)= R_1(old)

 Iteration-2 C_j 0 0 0 0 0 B C_B X_B x_1 x_2 x_3 S_1 S_2 MinRatio S_1 0 10 10=10R_1(new)= R_1(old) 1 1=1R_1(new)= R_1(old) 0 0=0R_1(new)= R_1(old) -1 -1=-1R_1(new)= R_1(old) 1 1=1R_1(new)= R_1(old) 0 0=0R_1(new)= R_1(old) x_2 0 10 10=10R_2(new)= R_2(old) 0 0=0R_2(new)= R_2(old) 1 1=1R_2(new)= R_2(old) 1 1=1R_2(new)= R_2(old) 0 0=0R_2(new)= R_2(old) -1 -1=-1R_2(new)= R_2(old) Z=0 0=0xx10Z_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(-1)+0xx1Z_j=sum C_B x_3 0 0=0xx1+0xx0Z_j=sum C_B S_1 0 0=0xx0+0xx(-1)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 0 0=0-0

Since all C_j-Z_j >= 0

Hence, optimal solution is arrived with value of variables as :
x_1=0,x_2=10,x_3=0

Min Z = 0

-->Phase-2<--

we eliminate the artificial variables and change the objective function for the original,
 Iteration-1 C_j 5 2 10 0 0 B C_B X_B x_1 x_2 x_3 S_1 S_2 MinRatio S_1 0 10 1 0 -1 1 0 x_2 2 10 0 1 1 0 -1 Z=20 20=2xx10Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 0 0=0xx1+2xx0Z_j=sum C_B x_1 2 2=0xx0+2xx1Z_j=sum C_B x_2 2 2=0xx(-1)+2xx1Z_j=sum C_B x_3 0 0=0xx1+2xx0Z_j=sum C_B S_1 -2 -2=0xx0+2xx(-1)Z_j=sum C_B S_2 C_j-Z_j 5 5=5-0 0 0=2-2 8 8=10-2 0 0=0-0 2 2=0-(-2)

Since all C_j-Z_j >= 0

Hence, optimal solution is arrived with value of variables as :
x_1=0,x_2=10,x_3=0

Min Z = 20

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