Home > Operation Research calculators > Simplex method example

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

7. Unrestricted variable example

Unrestricted variable
Sometimes decision variables are positive, negative or zero values, then they are called unrestricted variables.
In all such cases, the decision variables can be expressed as the difference between two non-negative variables.

For example, if x_r is unrestricted in sign, then
x_r = x_r' - x_r'' ; x_r' - x_r'' >= 0
Example
Find solution using Simplex(BigM) method
MAX Z = 3x1 + 2x2 + x3
subject to
2x1 + 5x2 + x3 = 12
3x1 + 4x2 = 11
and x2,x3 >= 0 and x1 unrestricted in sign

Solution:
Problem is
 Max Z =  3 x_1  +  2 x_2  +   x_3
subject to
  2 x_1  +  5 x_2  +   x_3 = 12  3 x_1  +  4 x_2 = 11
and x_2,x_3 >= 0; x_1 unrestricted in sign

Since x_1 is unrestricted in sign, introduce the non-negative variables x_1',x_1''

so that x_1=x_1'-x_1''; x_1',x_1''>=0.

The standard form of the LP problem becomes
Problem is
 Max Z =  3 x_1'  -  3 x_1''  +  2 x_2  +   x_3
subject to
  2 x_1'  -  2 x_1''  +  5 x_2  +   x_3 = 12  3 x_1'  -  3 x_1''  +  4 x_2 = 11
and x_1',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 artificial variable A_1

2. As the constraint-2 is of type '=' we should add artificial variable A_2

After introducing artificial variables
 Max Z =  3 x_1'  -  3 x_1''  +  2 x_2  +   x_3  -  M A_1  -  M A_2
subject to
  2 x_1'  -  2 x_1''  +  5 x_2  +   x_3  +   A_1 = 12  3 x_1'  -  3 x_1''  +  4 x_2  +   A_2 = 11
and x_1',x_1'',x_2,x_3,A_1,A_2 >= 0

 Iteration-1 C_j 3 -3 2 1 -M -M B C_B X_B x_1' x_1'' x_2 Entering variable x_3 A_1 A_2 MinRatio (X_B)/(x_2) A_1 Leaving variable -M 12 2 -2 (5)  (pivot element) 1 1 0 (12)/(5)=2.4-> A_2 -M 11 3 -3 4 0 0 1 (11)/(4)=2.75 Z=0 0=Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j -5M -5M=(-M)xx2+(-M)xx3Z_j=sum C_B x_1' 5M 5M=(-M)xx(-2)+(-M)xx(-3)Z_j=sum C_B x_1'' -9M -9M=(-M)xx5+(-M)xx4Z_j=sum C_B x_2 -M -M=(-M)xx1+(-M)xx0Z_j=sum C_B x_3 -M -M=(-M)xx1+(-M)xx0Z_j=sum C_B A_1 -M -M=(-M)xx0+(-M)xx1Z_j=sum C_B A_2 C_j-Z_j 5M+3 5M+3=3-(-5M) -5M-3 -5M-3=(-3)-5M 9M+2 9M+2=2-(-9M)uarr M+1 M+1=1-(-M) 0 0=(-M)-(-M) 0 0=(-M)-(-M)

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

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

:. The pivot element is 5.

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

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

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

 Iteration-2 C_j 3 -3 2 1 -M B C_B X_B x_1' Entering variable x_1'' x_2 x_3 A_2 MinRatio (X_B)/(x_1') x_2 2 12/5 12/5=12-:5R_1(new)= R_1(old)-: 5 2/5 2/5=2-:5R_1(new)= R_1(old)-: 5 -2/5 -2/5=(-2)-:5R_1(new)= R_1(old)-: 5 1 1=5-:5R_1(new)= R_1(old)-: 5 1/5 1/5=1-:5R_1(new)= R_1(old)-: 5 0 0=0-:5R_1(new)= R_1(old)-: 5 (12/5)/(2/5)=6 A_2 Leaving variable -M 7/5 7/5=11-4xx12/5R_2(new)= R_2(old)- 4 R_1(new) (7/5) 7/5=3-4xx2/5 (pivot element)R_2(new)= R_2(old)- 4 R_1(new) -7/5 -7/5=(-3)-4xx(-2/5)R_2(new)= R_2(old)- 4 R_1(new) 0 0=4-4xx1R_2(new)= R_2(old)- 4 R_1(new) -4/5 -4/5=0-4xx1/5R_2(new)= R_2(old)- 4 R_1(new) 1 1=1-4xx0R_2(new)= R_2(old)- 4 R_1(new) (7/5)/(7/5)=1-> Z=24/5 24/5=2xx12/5Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j -(7M)/(5)+4/5 -(7M)/(5)+4/5=2xx2/5+(-M)xx7/5Z_j=sum C_B x_1' (7M)/(5)-4/5 (7M)/(5)-4/5=2xx(-2/5)+(-M)xx(-7/5)Z_j=sum C_B x_1'' 2 2=2xx1+(-M)xx0Z_j=sum C_B x_2 (4M)/(5)+2/5 (4M)/(5)+2/5=2xx1/5+(-M)xx(-4/5)Z_j=sum C_B x_3 -M -M=2xx0+(-M)xx1Z_j=sum C_B A_2 C_j-Z_j (7M)/(5)+11/5 (7M)/(5)+11/5=3-(-(7M)/(5)+4/5)uarr -(7M)/(5)-11/5 -(7M)/(5)-11/5=(-3)-((7M)/(5)-4/5) 0 0=2-2 -(4M)/(5)+3/5 -(4M)/(5)+3/5=1-((4M)/(5)+2/5) 0 0=(-M)-(-M)

Positive maximum C_j-Z_j is (7M)/(5)+11/5 and its column index is 1. So, the entering variable is x_1'.

Minimum ratio is 1 and its row index is 2. So, the leaving basis variable is A_2.

:. The pivot element is 7/5.

Entering =x_1', Departing =A_2, Key Element =7/5

R_2(new)= R_2(old)xx5/7

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

 Iteration-3 C_j 3 -3 2 1 B C_B X_B x_1' x_1'' x_2 x_3 Entering variable MinRatio (X_B)/(x_3) x_2 Leaving variable 2 2 2=12/5-2/5xx1R_1(new)= R_1(old)- 2/5 R_2(new) 0 0=2/5-2/5xx1R_1(new)= R_1(old)- 2/5 R_2(new) 0 0=(-2/5)-2/5xx(-1)R_1(new)= R_1(old)- 2/5 R_2(new) 1 1=1-2/5xx0R_1(new)= R_1(old)- 2/5 R_2(new) (3/7) 3/7=1/5-2/5xx(-4/7) (pivot element)R_1(new)= R_1(old)- 2/5 R_2(new) (2)/(3/7)=4.6667-> x_1' 3 1 1=7/5xx5/7R_2(new)= R_2(old)xx5/7 1 1=7/5xx5/7R_2(new)= R_2(old)xx5/7 -1 -1=(-7/5)xx5/7R_2(new)= R_2(old)xx5/7 0 0=0xx5/7R_2(new)= R_2(old)xx5/7 -4/7 -4/7=(-4/5)xx5/7R_2(new)= R_2(old)xx5/7 --- Z=7 7=2xx2+3xx1Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 3 3=2xx0+3xx1Z_j=sum C_B x_1' -3 -3=2xx0+3xx(-1)Z_j=sum C_B x_1'' 2 2=2xx1+3xx0Z_j=sum C_B x_2 -6/7 -6/7=2xx3/7+3xx(-4/7)Z_j=sum C_B x_3 C_j-Z_j 0 0=3-3 0 0=(-3)-(-3) 0 0=2-2 13/7 13/7=1-(-6/7)uarr

Positive maximum C_j-Z_j is 13/7 and its column index is 4. So, the entering variable is x_3.

Minimum ratio is 4.6667 and its row index is 1. So, the leaving basis variable is x_2.

:. The pivot element is 3/7.

Entering =x_3, Departing =x_2, Key Element =3/7

R_1(new)= R_1(old)xx7/3

R_2(new)= R_2(old)+ 4/7 R_1(new)

 Iteration-4 C_j 3 -3 2 1 B C_B X_B x_1' x_1'' x_2 x_3 MinRatio x_3 1 14/3 14/3=2xx7/3R_1(new)= R_1(old)xx7/3 0 0=0xx7/3R_1(new)= R_1(old)xx7/3 0 0=0xx7/3R_1(new)= R_1(old)xx7/3 7/3 7/3=1xx7/3R_1(new)= R_1(old)xx7/3 1 1=3/7xx7/3R_1(new)= R_1(old)xx7/3 x_1' 3 11/3 11/3=1+4/7xx14/3R_2(new)= R_2(old)+ 4/7 R_1(new) 1 1=1+4/7xx0R_2(new)= R_2(old)+ 4/7 R_1(new) -1 -1=(-1)+4/7xx0R_2(new)= R_2(old)+ 4/7 R_1(new) 4/3 4/3=0+4/7xx7/3R_2(new)= R_2(old)+ 4/7 R_1(new) 0 0=(-4/7)+4/7xx1R_2(new)= R_2(old)+ 4/7 R_1(new) Z=47/3 47/3=1xx14/3+3xx11/3Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 3 3=1xx0+3xx1Z_j=sum C_B x_1' -3 -3=1xx0+3xx(-1)Z_j=sum C_B x_1'' 19/3 19/3=1xx7/3+3xx4/3Z_j=sum C_B x_2 1 1=1xx1+3xx0Z_j=sum C_B x_3 C_j-Z_j 0 0=3-3 0 0=(-3)-(-3) -13/3 -13/3=2-(19/3) 0 0=1-1

Since all C_j-Z_j <= 0

Hence, optimal solution is arrived with value of variables as :
x_1'=11/3,x_1''=0,x_2=0,x_3=14/3

Max Z = 47/3

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