Home > Operation Research calculators > Simplex method example

1. Simplex (BigM) method example ( Enter your problem )

8. Multiple optimal solution example

Multiple optimal solution
In the final simplex table when all c_j - z_j imply optimal solution (for maximization all c_j - z_j <= 0 and for minimization all c_j - z_j >= 0)
but if c_j - z_j = 0 for some non-basic variable column, then this indicates that there are more than 1 optimal solution of the problem. Thus by entering this variable into the basis, we may obtain another alternative optimal solution.
Example
Find solution using Simplex(BigM) method
MAX Z = 6x1 + 4x2
subject to
2x1 + 3x2 <= 30
3x1 + 2x2 <= 24
x1 + x2 >= 3
and x1,x2 >= 0

Solution:
Problem is
 Max Z =  6 x_1  +  4 x_2
subject to
  2 x_1  +  3 x_2 ≤ 30  3 x_1  +  2 x_2 ≤ 24   x_1  +   x_2 ≥ 3
and x_1,x_2 >= 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

After introducing slack,surplus,artificial variables
 Max Z =  6 x_1  +  4 x_2  +  0 S_1  +  0 S_2  +  0 S_3  -  M A_1
subject to
  2 x_1  +  3 x_2  +   S_1 = 30  3 x_1  +  2 x_2  +   S_2 = 24   x_1  +   x_2  -   S_3  +   A_1 = 3
and x_1,x_2,S_1,S_2,S_3,A_1 >= 0

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

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

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

:. The pivot element is 1.

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

R_3(new)= R_3(old)

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

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

 Iteration-2 C_j 6 4 0 0 0 B C_B X_B x_1 x_2 S_1 S_2 S_3 Entering variable MinRatio (X_B)/(S_3) S_1 0 24 24=30-2xx3R_1(new)= R_1(old)- 2 R_3(new) 0 0=2-2xx1R_1(new)= R_1(old)- 2 R_3(new) 1 1=3-2xx1R_1(new)= R_1(old)- 2 R_3(new) 1 1=1-2xx0R_1(new)= R_1(old)- 2 R_3(new) 0 0=0-2xx0R_1(new)= R_1(old)- 2 R_3(new) 2 2=0-2xx(-1)R_1(new)= R_1(old)- 2 R_3(new) (24)/(2)=12 S_2 Leaving variable 0 15 15=24-3xx3R_2(new)= R_2(old)- 3 R_3(new) 0 0=3-3xx1R_2(new)= R_2(old)- 3 R_3(new) -1 -1=2-3xx1R_2(new)= R_2(old)- 3 R_3(new) 0 0=0-3xx0R_2(new)= R_2(old)- 3 R_3(new) 1 1=1-3xx0R_2(new)= R_2(old)- 3 R_3(new) (3) 3=0-3xx(-1) (pivot element)R_2(new)= R_2(old)- 3 R_3(new) (15)/(3)=5-> x_1 6 3 3=3R_3(new)= R_3(old) 1 1=1R_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) -1 -1=-1R_3(new)= R_3(old) --- Z=18 18=6xx3Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 6 6=0xx0+0xx0+6xx1Z_j=sum C_B x_1 6 6=0xx1+0xx(-1)+6xx1Z_j=sum C_B x_2 0 0=0xx1+0xx0+6xx0Z_j=sum C_B S_1 0 0=0xx0+0xx1+6xx0Z_j=sum C_B S_2 -6 -6=0xx2+0xx3+6xx(-1)Z_j=sum C_B S_3 C_j-Z_j 0 0=6-6 -2 -2=4-6 0 0=0-0 0 0=0-0 6 6=0-(-6)uarr

Positive maximum C_j-Z_j is 6 and its column index is 5. So, the entering variable is S_3.

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

:. The pivot element is 3.

Entering =S_3, Departing =S_2, Key Element =3

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

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

R_3(new)= R_3(old)+ R_2(new)

 Iteration-3 C_j 6 4 0 0 0 B C_B X_B x_1 x_2 S_1 S_2 S_3 MinRatio S_1 0 14 14=24-2xx5R_1(new)= R_1(old)- 2 R_2(new) 0 0=0-2xx0R_1(new)= R_1(old)- 2 R_2(new) 5/3 5/3=1-2xx(-1/3)R_1(new)= R_1(old)- 2 R_2(new) 1 1=1-2xx0R_1(new)= R_1(old)- 2 R_2(new) -2/3 -2/3=0-2xx1/3R_1(new)= R_1(old)- 2 R_2(new) 0 0=2-2xx1R_1(new)= R_1(old)- 2 R_2(new) S_3 0 5 5=15-:3R_2(new)= R_2(old)-: 3 0 0=0-:3R_2(new)= R_2(old)-: 3 -1/3 -1/3=(-1)-:3R_2(new)= R_2(old)-: 3 0 0=0-:3R_2(new)= R_2(old)-: 3 1/3 1/3=1-:3R_2(new)= R_2(old)-: 3 1 1=3-:3R_2(new)= R_2(old)-: 3 x_1 6 8 8=3+5R_3(new)= R_3(old)+ R_2(new) 1 1=1+0R_3(new)= R_3(old)+ R_2(new) 2/3 2/3=1+(-1/3)R_3(new)= R_3(old)+ R_2(new) 0 0=0+0R_3(new)= R_3(old)+ R_2(new) 1/3 1/3=0+1/3R_3(new)= R_3(old)+ R_2(new) 0 0=(-1)+1R_3(new)= R_3(old)+ R_2(new) Z=48 48=6xx8Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 6 6=0xx0+0xx0+6xx1Z_j=sum C_B x_1 4 4=0xx5/3+0xx(-1/3)+6xx2/3Z_j=sum C_B x_2 0 0=0xx1+0xx0+6xx0Z_j=sum C_B S_1 2 2=0xx(-2/3)+0xx1/3+6xx1/3Z_j=sum C_B S_2 0 0=0xx0+0xx1+6xx0Z_j=sum C_B S_3 C_j-Z_j 0 0=6-6 0 0=4-4 0 0=0-0 -2 -2=0-2 0 0=0-0

Since all C_j-Z_j <= 0

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

Max Z = 48

Here C_2-Z_2=0 and x_2 is not in the basis (i.e. x_2=0).

This indicates that there are more than 1 optimal solution of the problem.
Thus by entering x_2 into the basis, we may obtain another alternative optimal solution.

 Iteration-3 C_j 6 4 0 0 0 B C_B X_B x_1 x_2 Entering variable S_1 S_2 S_3 MinRatio (X_B)/(x_2) S_1 Leaving variable 0 14 14=24-2xx5R_1(new)= R_1(old)- 2 R_2(new) 0 0=0-2xx0R_1(new)= R_1(old)- 2 R_2(new) (5/3) 5/3=1-2xx(-1/3) (pivot element)R_1(new)= R_1(old)- 2 R_2(new) 1 1=1-2xx0R_1(new)= R_1(old)- 2 R_2(new) -2/3 -2/3=0-2xx1/3R_1(new)= R_1(old)- 2 R_2(new) 0 0=2-2xx1R_1(new)= R_1(old)- 2 R_2(new) (14)/(5/3)=8.4-> S_3 0 5 5=15-:3R_2(new)= R_2(old)-: 3 0 0=0-:3R_2(new)= R_2(old)-: 3 -1/3 -1/3=(-1)-:3R_2(new)= R_2(old)-: 3 0 0=0-:3R_2(new)= R_2(old)-: 3 1/3 1/3=1-:3R_2(new)= R_2(old)-: 3 1 1=3-:3R_2(new)= R_2(old)-: 3 --- x_1 6 8 8=3+5R_3(new)= R_3(old)+ R_2(new) 1 1=1+0R_3(new)= R_3(old)+ R_2(new) 2/3 2/3=1+(-1/3)R_3(new)= R_3(old)+ R_2(new) 0 0=0+0R_3(new)= R_3(old)+ R_2(new) 1/3 1/3=0+1/3R_3(new)= R_3(old)+ R_2(new) 0 0=(-1)+1R_3(new)= R_3(old)+ R_2(new) (8)/(2/3)=12 Z=48 48=6xx8Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 6 6=0xx0+0xx0+6xx1Z_j=sum C_B x_1 4 4=0xx5/3+0xx(-1/3)+6xx2/3Z_j=sum C_B x_2 0 0=0xx1+0xx0+6xx0Z_j=sum C_B S_1 2 2=0xx(-2/3)+0xx1/3+6xx1/3Z_j=sum C_B S_2 0 0=0xx0+0xx1+6xx0Z_j=sum C_B S_3 C_j-Z_j 0 0=6-6 0 0=4-4uarr 0 0=0-0 -2 -2=0-2 0 0=0-0

So, the entering variable is x_2.

Minimum ratio is 8.4 and its row index is 1. So, the leaving basis variable is S_1.

:. The pivot element is 5/3.

Entering =x_2, Departing =S_1, Key Element =5/3

R_1(new)= R_1(old)xx3/5

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

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

 Iteration-4 C_j 6 4 0 0 0 B C_B X_B x_1 x_2 S_1 S_2 S_3 MinRatio x_2 4 42/5 42/5=14xx3/5R_1(new)= R_1(old)xx3/5 0 0=0xx3/5R_1(new)= R_1(old)xx3/5 1 1=5/3xx3/5R_1(new)= R_1(old)xx3/5 3/5 3/5=1xx3/5R_1(new)= R_1(old)xx3/5 -2/5 -2/5=(-2/3)xx3/5R_1(new)= R_1(old)xx3/5 0 0=0xx3/5R_1(new)= R_1(old)xx3/5 S_3 0 39/5 39/5=5+1/3xx42/5R_2(new)= R_2(old)+ 1/3 R_1(new) 0 0=0+1/3xx0R_2(new)= R_2(old)+ 1/3 R_1(new) 0 0=(-1/3)+1/3xx1R_2(new)= R_2(old)+ 1/3 R_1(new) 1/5 1/5=0+1/3xx3/5R_2(new)= R_2(old)+ 1/3 R_1(new) 1/5 1/5=1/3+1/3xx(-2/5)R_2(new)= R_2(old)+ 1/3 R_1(new) 1 1=1+1/3xx0R_2(new)= R_2(old)+ 1/3 R_1(new) x_1 6 12/5 12/5=8-2/3xx42/5R_3(new)= R_3(old)- 2/3 R_1(new) 1 1=1-2/3xx0R_3(new)= R_3(old)- 2/3 R_1(new) 0 0=2/3-2/3xx1R_3(new)= R_3(old)- 2/3 R_1(new) -2/5 -2/5=0-2/3xx3/5R_3(new)= R_3(old)- 2/3 R_1(new) 3/5 3/5=1/3-2/3xx(-2/5)R_3(new)= R_3(old)- 2/3 R_1(new) 0 0=0-2/3xx0R_3(new)= R_3(old)- 2/3 R_1(new) Z=48 48=4xx42/5+6xx12/5Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 6 6=4xx0+0xx0+6xx1Z_j=sum C_B x_1 4 4=4xx1+0xx0+6xx0Z_j=sum C_B x_2 0 0=4xx3/5+0xx1/5+6xx(-2/5)Z_j=sum C_B S_1 2 2=4xx(-2/5)+0xx1/5+6xx3/5Z_j=sum C_B S_2 0 0=4xx0+0xx1+6xx0Z_j=sum C_B S_3 C_j-Z_j 0 0=6-6 0 0=4-4 0 0=0-0 -2 -2=0-2 0 0=0-0

Since all C_j-Z_j <= 0

Hence, optimal solution is arrived with value of variables as :
x_1=12/5,x_2=42/5

Max Z = 48

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

Share with your friends