Home > Operation Research calculators > Simplex method example

1. Simplex (BigM) method example ( Enter your problem )
 Other related methods

6. Degeneracy example-2 (Tie - first Artificial variable removed)

Degeneracy example-2 (Tie - first Artificial variable removed)
During solving LP problem, a situation may arise in which there is a tie between, 2 or more basic variables for leaving the basis. (means minimum ratios are same).
It is called degeneracy and to resolve this we can select any of them arbitrarily.
But if artificial variable is present then it must be removed first.
Example
Find solution using Simplex(BigM) method
MAX z = 750x1 + 900x2 - 450x3
subject to
x1 + 2x2 <= 70
2x1 + 3x2 - x3 <= 100
x1 >= 20
x2 >= 25
and x1,x2,x3 >= 0

Solution:
Problem is
 Max z =  750 x_1  +  900 x_2  -  450 x_3
subject to
   x_1  +  2 x_2 ≤ 70  2 x_1  +  3 x_2  -   x_3 ≤ 100   x_1 ≥ 20   x_2 ≥ 25
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

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

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

After introducing slack,surplus,artificial variables
 Max z =  750 x_1  +  900 x_2  -  450 x_3  +  0 S_1  +  0 S_2  +  0 S_3  +  0 S_4  -  M A_1  -  M A_2
subject to
   x_1  +  2 x_2  +   S_1 = 70  2 x_1  +  3 x_2  -   x_3  +   S_2 = 100   x_1  -   S_3  +   A_1 = 20   x_2  -   S_4  +   A_2 = 25
and x_1,x_2,x_3,S_1,S_2,S_3,S_4,A_1,A_2 >= 0

 Iteration-1 C_j 750 900 -450 0 0 0 0 -M -M B C_B X_B x_1 x_2 Entering variable x_3 S_1 S_2 S_3 S_4 A_1 A_2 MinRatio (X_B)/(x_2) S_1 0 70 1 2 0 1 0 0 0 0 0 (70)/(2)=35 S_2 0 100 2 3 -1 0 1 0 0 0 0 (100)/(3)=33.3333 A_1 -M 20 1 0 0 0 0 -1 0 1 0 --- A_2 Leaving variable -M 25 0 (1)  (pivot element) 0 0 0 0 -1 0 1 (25)/(1)=25-> z=0 0=Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j -M -M=0xx1+0xx2+(-M)xx1+(-M)xx0Z_j=sum C_B x_1 -M -M=0xx2+0xx3+(-M)xx0+(-M)xx1Z_j=sum C_B x_2 0 0=0xx0+0xx(-1)+(-M)xx0+(-M)xx0Z_j=sum C_B x_3 0 0=0xx1+0xx0+(-M)xx0+(-M)xx0Z_j=sum C_B S_1 0 0=0xx0+0xx1+(-M)xx0+(-M)xx0Z_j=sum C_B S_2 M M=0xx0+0xx0+(-M)xx(-1)+(-M)xx0Z_j=sum C_B S_3 M M=0xx0+0xx0+(-M)xx0+(-M)xx(-1)Z_j=sum C_B S_4 -M -M=0xx0+0xx0+(-M)xx1+(-M)xx0Z_j=sum C_B A_1 -M -M=0xx0+0xx0+(-M)xx0+(-M)xx1Z_j=sum C_B A_2 C_j-Z_j M+750 M+750=750-(-M) M+900 M+900=900-(-M)uarr -450 -450=(-450)-0 0 0=0-0 0 0=0-0 -M -M=0-M -M -M=0-M 0 0=(-M)-(-M) 0 0=(-M)-(-M)

Positive maximum C_j-Z_j is M+900 and its column index is 2. So, the entering variable is x_2.

Minimum ratio is 25 and its row index is 4. So, the leaving basis variable is A_2.

:. The pivot element is 1.

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

R_4(new)= R_4(old)

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

R_2(new)= R_2(old)- 3 R_4(new)

R_3(new)= R_3(old)

 Iteration-2 C_j 750 900 -450 0 0 0 0 -M B C_B X_B x_1 Entering variable x_2 x_3 S_1 S_2 S_3 S_4 A_1 MinRatio (X_B)/(x_1) S_1 0 20 20=70-2xx25R_1(new)= R_1(old)- 2 R_4(new) 1 1=1-2xx0R_1(new)= R_1(old)- 2 R_4(new) 0 0=2-2xx1R_1(new)= R_1(old)- 2 R_4(new) 0 0=0-2xx0R_1(new)= R_1(old)- 2 R_4(new) 1 1=1-2xx0R_1(new)= R_1(old)- 2 R_4(new) 0 0=0-2xx0R_1(new)= R_1(old)- 2 R_4(new) 0 0=0-2xx0R_1(new)= R_1(old)- 2 R_4(new) 2 2=0-2xx(-1)R_1(new)= R_1(old)- 2 R_4(new) 0 0=0-2xx0R_1(new)= R_1(old)- 2 R_4(new) (20)/(1)=20 S_2 Leaving variable 0 25 25=100-3xx25R_2(new)= R_2(old)- 3 R_4(new) (2) 2=2-3xx0 (pivot element)R_2(new)= R_2(old)- 3 R_4(new) 0 0=3-3xx1R_2(new)= R_2(old)- 3 R_4(new) -1 -1=(-1)-3xx0R_2(new)= R_2(old)- 3 R_4(new) 0 0=0-3xx0R_2(new)= R_2(old)- 3 R_4(new) 1 1=1-3xx0R_2(new)= R_2(old)- 3 R_4(new) 0 0=0-3xx0R_2(new)= R_2(old)- 3 R_4(new) 3 3=0-3xx(-1)R_2(new)= R_2(old)- 3 R_4(new) 0 0=0-3xx0R_2(new)= R_2(old)- 3 R_4(new) (25)/(2)=12.5-> A_1 -M 20 20=20R_3(new)= R_3(old) 1 1=1R_3(new)= R_3(old) 0 0=0R_3(new)= R_3(old) 0 0=0R_3(new)= R_3(old) 0 0=0R_3(new)= R_3(old) 0 0=0R_3(new)= R_3(old) -1 -1=-1R_3(new)= R_3(old) 0 0=0R_3(new)= R_3(old) 1 1=1R_3(new)= R_3(old) (20)/(1)=20 x_2 900 25 25=25R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 1 1=1R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) -1 -1=-1R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) --- z=22500 22500=900xx25Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j -M -M=0xx1+0xx2+(-M)xx1+900xx0Z_j=sum C_B x_1 900 900=0xx0+0xx0+(-M)xx0+900xx1Z_j=sum C_B x_2 0 0=0xx0+0xx(-1)+(-M)xx0+900xx0Z_j=sum C_B x_3 0 0=0xx1+0xx0+(-M)xx0+900xx0Z_j=sum C_B S_1 0 0=0xx0+0xx1+(-M)xx0+900xx0Z_j=sum C_B S_2 M M=0xx0+0xx0+(-M)xx(-1)+900xx0Z_j=sum C_B S_3 -900 -900=0xx2+0xx3+(-M)xx0+900xx(-1)Z_j=sum C_B S_4 -M -M=0xx0+0xx0+(-M)xx1+900xx0Z_j=sum C_B A_1 C_j-Z_j M+750 M+750=750-(-M)uarr 0 0=900-900 -450 -450=(-450)-0 0 0=0-0 0 0=0-0 -M -M=0-M 900 900=0-(-900) 0 0=(-M)-(-M)

Positive maximum C_j-Z_j is M+750 and its column index is 1. So, the entering variable is x_1.

Minimum ratio is 12.5 and its row index is 2. So, the leaving basis variable is S_2.

:. The pivot element is 2.

Entering =x_1, Departing =S_2, Key Element =2

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

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

R_3(new)= R_3(old)- R_2(new)

R_4(new)= R_4(old)

 Iteration-3 C_j 750 900 -450 0 0 0 0 -M B C_B X_B x_1 x_2 x_3 Entering variable S_1 S_2 S_3 S_4 A_1 MinRatio (X_B)/(x_3) S_1 0 15/2 15/2=20-25/2R_1(new)= R_1(old)- R_2(new) 0 0=1-1R_1(new)= R_1(old)- R_2(new) 0 0=0-0R_1(new)= R_1(old)- R_2(new) 1/2 1/2=0-(-1/2)R_1(new)= R_1(old)- R_2(new) 1 1=1-0R_1(new)= R_1(old)- R_2(new) -1/2 -1/2=0-1/2R_1(new)= R_1(old)- R_2(new) 0 0=0-0R_1(new)= R_1(old)- R_2(new) 1/2 1/2=2-3/2R_1(new)= R_1(old)- R_2(new) 0 0=0-0R_1(new)= R_1(old)- R_2(new) (15/2)/(1/2)=15 x_1 750 25/2 25/2=25-:2R_2(new)= R_2(old)-: 2 1 1=2-:2R_2(new)= R_2(old)-: 2 0 0=0-:2R_2(new)= R_2(old)-: 2 -1/2 -1/2=(-1)-:2R_2(new)= R_2(old)-: 2 0 0=0-:2R_2(new)= R_2(old)-: 2 1/2 1/2=1-:2R_2(new)= R_2(old)-: 2 0 0=0-:2R_2(new)= R_2(old)-: 2 3/2 3/2=3-:2R_2(new)= R_2(old)-: 2 0 0=0-:2R_2(new)= R_2(old)-: 2 --- A_1 Leaving variable -M 15/2 15/2=20-25/2R_3(new)= R_3(old)- R_2(new) 0 0=1-1R_3(new)= R_3(old)- R_2(new) 0 0=0-0R_3(new)= R_3(old)- R_2(new) (1/2) 1/2=0-(-1/2) (pivot element)R_3(new)= R_3(old)- R_2(new) 0 0=0-0R_3(new)= R_3(old)- R_2(new) -1/2 -1/2=0-1/2R_3(new)= R_3(old)- R_2(new) -1 -1=(-1)-0R_3(new)= R_3(old)- R_2(new) -3/2 -3/2=0-3/2R_3(new)= R_3(old)- R_2(new) 1 1=1-0R_3(new)= R_3(old)- R_2(new) (15/2)/(1/2)=15-> x_2 900 25 25=25R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 1 1=1R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) -1 -1=-1R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) --- z=31875 31875=750xx25/2+900xx25Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 750 750=0xx0+750xx1+(-M)xx0+900xx0Z_j=sum C_B x_1 900 900=0xx0+750xx0+(-M)xx0+900xx1Z_j=sum C_B x_2 -(M)/(2)-375 -(M)/(2)-375=0xx1/2+750xx(-1/2)+(-M)xx1/2+900xx0Z_j=sum C_B x_3 0 0=0xx1+750xx0+(-M)xx0+900xx0Z_j=sum C_B S_1 (M)/(2)+375 (M)/(2)+375=0xx(-1/2)+750xx1/2+(-M)xx(-1/2)+900xx0Z_j=sum C_B S_2 M M=0xx0+750xx0+(-M)xx(-1)+900xx0Z_j=sum C_B S_3 (3M)/(2)+225 (3M)/(2)+225=0xx1/2+750xx3/2+(-M)xx(-3/2)+900xx(-1)Z_j=sum C_B S_4 -M -M=0xx0+750xx0+(-M)xx1+900xx0Z_j=sum C_B A_1 C_j-Z_j 0 0=750-750 0 0=900-900 (M)/(2)-75 (M)/(2)-75=(-450)-(-(M)/(2)-375)uarr 0 0=0-0 -(M)/(2)-375 -(M)/(2)-375=0-((M)/(2)+375) -M -M=0-M -(3M)/(2)-225 -(3M)/(2)-225=0-((3M)/(2)+225) 0 0=(-M)-(-M)

Positive maximum C_j-Z_j is (M)/(2)-75 and its column index is 3. So, the entering variable is x_3.

Minimum ratio is 15 and its row index is 3. So, the leaving basis variable is A_1.

:. The pivot element is 1/2.

Entering =x_3, Departing =A_1, Key Element =1/2

R_3(new)= R_3(old)xx2

R_1(new)= R_1(old)- 1/2 R_3(new)

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

R_4(new)= R_4(old)

 Iteration-4 C_j 750 900 -450 0 0 0 0 B C_B X_B x_1 x_2 x_3 S_1 S_2 S_3 S_4 MinRatio S_1 0 0 0=15/2-1/2xx15R_1(new)= R_1(old)- 1/2 R_3(new) 0 0=0-1/2xx0R_1(new)= R_1(old)- 1/2 R_3(new) 0 0=0-1/2xx0R_1(new)= R_1(old)- 1/2 R_3(new) 0 0=1/2-1/2xx1R_1(new)= R_1(old)- 1/2 R_3(new) 1 1=1-1/2xx0R_1(new)= R_1(old)- 1/2 R_3(new) 0 0=(-1/2)-1/2xx(-1)R_1(new)= R_1(old)- 1/2 R_3(new) 1 1=0-1/2xx(-2)R_1(new)= R_1(old)- 1/2 R_3(new) 2 2=1/2-1/2xx(-3)R_1(new)= R_1(old)- 1/2 R_3(new) x_1 750 20 20=25/2+1/2xx15R_2(new)= R_2(old)+ 1/2 R_3(new) 1 1=1+1/2xx0R_2(new)= R_2(old)+ 1/2 R_3(new) 0 0=0+1/2xx0R_2(new)= R_2(old)+ 1/2 R_3(new) 0 0=(-1/2)+1/2xx1R_2(new)= R_2(old)+ 1/2 R_3(new) 0 0=0+1/2xx0R_2(new)= R_2(old)+ 1/2 R_3(new) 0 0=1/2+1/2xx(-1)R_2(new)= R_2(old)+ 1/2 R_3(new) -1 -1=0+1/2xx(-2)R_2(new)= R_2(old)+ 1/2 R_3(new) 0 0=3/2+1/2xx(-3)R_2(new)= R_2(old)+ 1/2 R_3(new) x_3 -450 15 15=15/2xx2R_3(new)= R_3(old)xx2 0 0=0xx2R_3(new)= R_3(old)xx2 0 0=0xx2R_3(new)= R_3(old)xx2 1 1=1/2xx2R_3(new)= R_3(old)xx2 0 0=0xx2R_3(new)= R_3(old)xx2 -1 -1=(-1/2)xx2R_3(new)= R_3(old)xx2 -2 -2=(-1)xx2R_3(new)= R_3(old)xx2 -3 -3=(-3/2)xx2R_3(new)= R_3(old)xx2 x_2 900 25 25=25R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 1 1=1R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) 0 0=0R_4(new)= R_4(old) -1 -1=-1R_4(new)= R_4(old) z=30750 30750=750xx20+(-450)xx15+900xx25Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 750 750=0xx0+750xx1+(-450)xx0+900xx0Z_j=sum C_B x_1 900 900=0xx0+750xx0+(-450)xx0+900xx1Z_j=sum C_B x_2 -450 -450=0xx0+750xx0+(-450)xx1+900xx0Z_j=sum C_B x_3 0 0=0xx1+750xx0+(-450)xx0+900xx0Z_j=sum C_B S_1 450 450=0xx0+750xx0+(-450)xx(-1)+900xx0Z_j=sum C_B S_2 150 150=0xx1+750xx(-1)+(-450)xx(-2)+900xx0Z_j=sum C_B S_3 450 450=0xx2+750xx0+(-450)xx(-3)+900xx(-1)Z_j=sum C_B S_4 C_j-Z_j 0 0=750-750 0 0=900-900 0 0=(-450)-(-450) 0 0=0-0 -450 -450=0-450 -150 -150=0-150 -450 -450=0-450

Since all C_j-Z_j <= 0

Hence, optimal solution is arrived with value of variables as :
x_1=20,x_2=25,x_3=15

Max z = 30750

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