Home > Operation Research calculators > Simplex method example

5. Dual simplex method example ( Enter your problem )
 Algorithm & Example-1Example-2 Other related methods

2. Example-2

Find solution using dual-simplex method
MIN Z = 2x1 + 3x2 + 0x3
subject to
2x1 - x2 - x3 >= 3
x1 - x2 + x3 >= 2
and x1,x2,x3 >= 0

Solution:
Problem is
 Min Z =  2 x_1  +  3 x_2
subject to
  2 x_1  -   x_2  -   x_3 ≥ 3   x_1  -   x_2  +   x_3 ≥ 2
and x_1,x_2,x_3 >= 0;

In order to apply the dual simplex method, convert Min Z to Max Z and all >= constraint to <= constraint by multiply -1.

Problem is
 Max Z =  -  2 x_1  -  3 x_2
subject to
  -  2 x_1  +   x_2  +   x_3 ≤ -3  -   x_1  +   x_2  -   x_3 ≤ -2
and x_1,x_2,x_3 >= 0;

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 add slack variable S_2

After introducing slack variables
 Max Z =  -  2 x_1  -  3 x_2  +  0 x_3  +  0 S_1  +  0 S_2
subject to
  -  2 x_1  +   x_2  +   x_3  +   S_1 = -3  -   x_1  +   x_2  -   x_3  +   S_2 = -2
and x_1,x_2,x_3,S_1,S_2 >= 0

 Iteration-1 C_j -2 -3 0 0 0 B C_B X_B x_1 Entering variable x_2 x_3 S_1 S_2 S_1 Leaving variable 0 -3 (-2)  (pivot element) 1 1 1 0 S_2 0 -2 -1 1 -1 0 1 Z=0 0=Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 0 0=0xx(-2)+0xx(-1)Z_j=sum C_B x_1 0 0=0xx1+0xx1Z_j=sum C_B x_2 0 0=0xx1+0xx(-1)Z_j=sum C_B x_3 0 0=0xx1+0xx0Z_j=sum C_B S_1 0 0=0xx0+0xx1Z_j=sum C_B S_2 C_j-Z_j -2 -2=(-2)-0 -3 -3=(-3)-0 0 0=0-0 0 0=0-0 0 0=0-0 "Ratio"=(C_j-Z_j)/(S_1,j)and S_1,j<0 1 1=(-2)/(-2)"Ratio"=(C_j-Z_j)/(S_1,j)uarr --- S_1,j=1; which is not <0 --- S_1,j=1; which is not <0 --- S_1,j=1; which is not <0 --- S_1,j=0; which is not <0

Minimum negative X_B is -3 and its row index is 1. So, the leaving basis variable is S_1.

Minimum positive ratio is 1 and its column index is 1. So, the entering variable is x_1.

:. The pivot element is -2.

Entering =x_1, Departing =S_1, Key Element =-2

R_1(new)= R_1(old)-: -2

R_2(new)= R_2(old)+ R_1(new)

 Iteration-2 C_j -2 -3 0 0 0 B C_B X_B x_1 x_2 x_3 Entering variable S_1 S_2 x_1 -2 3/2 3/2=(-3)-:(-2)R_1(new)= R_1(old)-: -2 1 1=(-2)-:(-2)R_1(new)= R_1(old)-: -2 -1/2 -1/2=1-:(-2)R_1(new)= R_1(old)-: -2 -1/2 -1/2=1-:(-2)R_1(new)= R_1(old)-: -2 -1/2 -1/2=1-:(-2)R_1(new)= R_1(old)-: -2 0 0=0-:(-2)R_1(new)= R_1(old)-: -2 S_2 Leaving variable 0 -1/2 -1/2=(-2)+3/2R_2(new)= R_2(old)+ R_1(new) 0 0=(-1)+1R_2(new)= R_2(old)+ R_1(new) 1/2 1/2=1+(-1/2)R_2(new)= R_2(old)+ R_1(new) (-3/2) -3/2=(-1)+(-1/2) (pivot element)R_2(new)= R_2(old)+ R_1(new) -1/2 -1/2=0+(-1/2)R_2(new)= R_2(old)+ R_1(new) 1 1=1+0R_2(new)= R_2(old)+ R_1(new) Z=-3 -3=(-2)xx3/2Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j -2 -2=(-2)xx1+0xx0Z_j=sum C_B x_1 1 1=(-2)xx(-1/2)+0xx1/2Z_j=sum C_B x_2 1 1=(-2)xx(-1/2)+0xx(-3/2)Z_j=sum C_B x_3 1 1=(-2)xx(-1/2)+0xx(-1/2)Z_j=sum C_B S_1 0 0=(-2)xx0+0xx1Z_j=sum C_B S_2 C_j-Z_j 0 0=(-2)-(-2) -4 -4=(-3)-1 -1 -1=0-1 -1 -1=0-1 0 0=0-0 "Ratio"=(C_j-Z_j)/(S_2,j)and S_2,j<0 --- S_2,j=0; which is not <0 --- S_2,j=1/2; which is not <0 0.6667 0.6667=(-1)/(-3/2)"Ratio"=(C_j-Z_j)/(S_2,j)uarr 2 2=(-1)/(-1/2)"Ratio"=(C_j-Z_j)/(S_2,j) --- S_2,j=1; which is not <0

Minimum negative X_B is -1/2 and its row index is 2. So, the leaving basis variable is S_2.

Minimum positive ratio is 0.6667 and its column index is 3. So, the entering variable is x_3.

:. The pivot element is -3/2.

Entering =x_3, Departing =S_2, Key Element =-3/2

R_2(new)= R_2(old)xx-2/3

R_1(new)= R_1(old)+ 1/2 R_2(new)

 Iteration-3 C_j -2 -3 0 0 0 B C_B X_B x_1 x_2 x_3 S_1 S_2 x_1 -2 5/3 5/3=3/2+1/2xx1/3R_1(new)= R_1(old)+ 1/2 R_2(new) 1 1=1+1/2xx0R_1(new)= R_1(old)+ 1/2 R_2(new) -2/3 -2/3=(-1/2)+1/2xx(-1/3)R_1(new)= R_1(old)+ 1/2 R_2(new) 0 0=(-1/2)+1/2xx1R_1(new)= R_1(old)+ 1/2 R_2(new) -1/3 -1/3=(-1/2)+1/2xx1/3R_1(new)= R_1(old)+ 1/2 R_2(new) -1/3 -1/3=0+1/2xx(-2/3)R_1(new)= R_1(old)+ 1/2 R_2(new) x_3 0 1/3 1/3=(-1/2)xx(-2/3)R_2(new)= R_2(old)xx-2/3 0 0=0xx(-2/3)R_2(new)= R_2(old)xx-2/3 -1/3 -1/3=1/2xx(-2/3)R_2(new)= R_2(old)xx-2/3 1 1=(-3/2)xx(-2/3)R_2(new)= R_2(old)xx-2/3 1/3 1/3=(-1/2)xx(-2/3)R_2(new)= R_2(old)xx-2/3 -2/3 -2/3=1xx(-2/3)R_2(new)= R_2(old)xx-2/3 Z=-10/3 -10/3=(-2)xx5/3+0xx1/3Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j -2 -2=(-2)xx1+0xx0Z_j=sum C_B x_1 4/3 4/3=(-2)xx(-2/3)+0xx(-1/3)Z_j=sum C_B x_2 0 0=(-2)xx0+0xx1Z_j=sum C_B x_3 2/3 2/3=(-2)xx(-1/3)+0xx1/3Z_j=sum C_B S_1 2/3 2/3=(-2)xx(-1/3)+0xx(-2/3)Z_j=sum C_B S_2 C_j-Z_j 0 0=(-2)-(-2) -13/3 -13/3=(-3)-(4/3) 0 0=0-0 -2/3 -2/3=0-(2/3) -2/3 -2/3=0-(2/3) Ratio --- --- --- --- ---

Since all C_j-Z_j <= 0 and all X_(Bi) >= 0 thus the current solution is the optimal solution.

Hence, optimal solution is arrived with value of variables as :
x_1=5/3,x_2=0,x_3=1/3

Max Z = -10/3

:. Min Z = 10/3

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