Home > Operation Research calculators > Simplex method example

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

4. Minimization example

Find solution using Simplex(BigM) method
MIN Z = x1 + x2
subject to
2x1 + 4x2 >= 4
x1 + 7x2 >= 7
and x1,x2 >= 0

Solution:
Problem is
 Min Z =   x_1  +   x_2
subject to
  2 x_1  +  4 x_2 ≥ 4   x_1  +  7 x_2 ≥ 7
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 subtract surplus variable S_1 and add artificial variable A_1

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

After introducing surplus,artificial variables
 Min Z =   x_1  +   x_2  +  0 S_1  +  0 S_2  +  M A_1  +  M A_2
subject to
  2 x_1  +  4 x_2  -   S_1  +   A_1 = 4   x_1  +  7 x_2  -   S_2  +   A_2 = 7
and x_1,x_2,S_1,S_2,A_1,A_2 >= 0

 Iteration-1 C_j 1 1 0 0 M M B C_B X_B x_1 x_2 Entering variable S_1 S_2 A_1 A_2 MinRatio (X_B)/(x_2) A_1 M 4 2 4 -1 0 1 0 (4)/(4)=1 A_2 Leaving variable M 7 1 (7)  (pivot element) 0 -1 0 1 (7)/(7)=1-> Z=0 0=Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 3M 3M=Mxx2+Mxx1Z_j=sum C_B x_1 11M 11M=Mxx4+Mxx7Z_j=sum C_B x_2 -M -M=Mxx(-1)+Mxx0Z_j=sum C_B S_1 -M -M=Mxx0+Mxx(-1)Z_j=sum C_B S_2 M M=Mxx1+Mxx0Z_j=sum C_B A_1 M M=Mxx0+Mxx1Z_j=sum C_B A_2 C_j-Z_j -3M+1 -3M+1=1-3M -11M+1 -11M+1=1-11Muarr M M=0-(-M) M M=0-(-M) 0 0=M-M 0 0=M-M

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

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

:. The pivot element is 7.

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

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

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

 Iteration-2 C_j 1 1 0 0 M B C_B X_B x_1 Entering variable x_2 S_1 S_2 A_1 MinRatio (X_B)/(x_1) A_1 Leaving variable M 0 0=4-4xx1R_1(new)= R_1(old)- 4 R_2(new) (10/7) 10/7=2-4xx1/7 (pivot element)R_1(new)= R_1(old)- 4 R_2(new) 0 0=4-4xx1R_1(new)= R_1(old)- 4 R_2(new) -1 -1=(-1)-4xx0R_1(new)= R_1(old)- 4 R_2(new) 4/7 4/7=0-4xx(-1/7)R_1(new)= R_1(old)- 4 R_2(new) 1 1=1-4xx0R_1(new)= R_1(old)- 4 R_2(new) (0)/(10/7)=0-> x_2 1 1 1=7-:7R_2(new)= R_2(old)-: 7 1/7 1/7=1-:7R_2(new)= R_2(old)-: 7 1 1=7-:7R_2(new)= R_2(old)-: 7 0 0=0-:7R_2(new)= R_2(old)-: 7 -1/7 -1/7=(-1)-:7R_2(new)= R_2(old)-: 7 0 0=0-:7R_2(new)= R_2(old)-: 7 (1)/(1/7)=7 Z=1 1=1xx1Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j (10M)/(7)+1/7 (10M)/(7)+1/7=Mxx10/7+1xx1/7Z_j=sum C_B x_1 1 1=Mxx0+1xx1Z_j=sum C_B x_2 -M -M=Mxx(-1)+1xx0Z_j=sum C_B S_1 (4M)/(7)-1/7 (4M)/(7)-1/7=Mxx4/7+1xx(-1/7)Z_j=sum C_B S_2 M M=Mxx1+1xx0Z_j=sum C_B A_1 C_j-Z_j -(10M)/(7)+6/7 -(10M)/(7)+6/7=1-((10M)/(7)+1/7)uarr 0 0=1-1 M M=0-(-M) -(4M)/(7)+1/7 -(4M)/(7)+1/7=0-((4M)/(7)-1/7) 0 0=M-M

Negative minimum C_j-Z_j is -(10M)/(7)+6/7 and its column index is 1. So, the entering variable is x_1.

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

:. The pivot element is 10/7.

Entering =x_1, Departing =A_1, Key Element =10/7

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

R_2(new)= R_2(old)- 1/7 R_1(new)

 Iteration-3 C_j 1 1 0 0 B C_B X_B x_1 x_2 S_1 S_2 Entering variable MinRatio (X_B)/(S_2) x_1 Leaving variable 1 0 0=0xx7/10R_1(new)= R_1(old)xx7/10 1 1=10/7xx7/10R_1(new)= R_1(old)xx7/10 0 0=0xx7/10R_1(new)= R_1(old)xx7/10 -7/10 -7/10=(-1)xx7/10R_1(new)= R_1(old)xx7/10 (2/5) 2/5=4/7xx7/10 (pivot element)R_1(new)= R_1(old)xx7/10 (0)/(2/5)=0-> x_2 1 1 1=1-1/7xx0R_2(new)= R_2(old)- 1/7 R_1(new) 0 0=1/7-1/7xx1R_2(new)= R_2(old)- 1/7 R_1(new) 1 1=1-1/7xx0R_2(new)= R_2(old)- 1/7 R_1(new) 1/10 1/10=0-1/7xx(-7/10)R_2(new)= R_2(old)- 1/7 R_1(new) -1/5 -1/5=(-1/7)-1/7xx2/5R_2(new)= R_2(old)- 1/7 R_1(new) --- Z=1 1=1xx0+1xx1Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 1 1=1xx1+1xx0Z_j=sum C_B x_1 1 1=1xx0+1xx1Z_j=sum C_B x_2 -3/5 -3/5=1xx(-7/10)+1xx1/10Z_j=sum C_B S_1 1/5 1/5=1xx2/5+1xx(-1/5)Z_j=sum C_B S_2 C_j-Z_j 0 0=1-1 0 0=1-1 3/5 3/5=0-(-3/5) -1/5 -1/5=0-(1/5)uarr

Negative minimum C_j-Z_j is -1/5 and its column index is 4. So, the entering variable is S_2.

Minimum ratio is 0 and its row index is 1. So, the leaving basis variable is x_1.

:. The pivot element is 2/5.

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

R_1(new)= R_1(old)xx5/2

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

 Iteration-4 C_j 1 1 0 0 B C_B X_B x_1 x_2 S_1 S_2 MinRatio S_2 0 0 0=0xx5/2R_1(new)= R_1(old)xx5/2 5/2 5/2=1xx5/2R_1(new)= R_1(old)xx5/2 0 0=0xx5/2R_1(new)= R_1(old)xx5/2 -7/4 -7/4=(-7/10)xx5/2R_1(new)= R_1(old)xx5/2 1 1=2/5xx5/2R_1(new)= R_1(old)xx5/2 x_2 1 1 1=1+1/5xx0R_2(new)= R_2(old)+ 1/5 R_1(new) 1/2 1/2=0+1/5xx5/2R_2(new)= R_2(old)+ 1/5 R_1(new) 1 1=1+1/5xx0R_2(new)= R_2(old)+ 1/5 R_1(new) -1/4 -1/4=1/10+1/5xx(-7/4)R_2(new)= R_2(old)+ 1/5 R_1(new) 0 0=(-1/5)+1/5xx1R_2(new)= R_2(old)+ 1/5 R_1(new) Z=1 1=1xx1Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 1/2 1/2=0xx5/2+1xx1/2Z_j=sum C_B x_1 1 1=0xx0+1xx1Z_j=sum C_B x_2 -1/4 -1/4=0xx(-7/4)+1xx(-1/4)Z_j=sum C_B S_1 0 0=0xx1+1xx0Z_j=sum C_B S_2 C_j-Z_j 1/2 1/2=1-(1/2) 0 0=1-1 1/4 1/4=0-(-1/4) 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=1

Min Z = 1

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