Home > Operation Research calculators > Simplex method example

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

3. Maximization example

1. Find solution using Simplex(BigM) method
MAX Z = 3x1 + 5x2 + 4x3
subject to
2x1 + 3x2 <= 8
2x2 + 5x3 <= 10
3x1 + 2x2 + 4x3 <= 15
and x1,x2,x3 >= 0

Solution:
Problem is
 Max Z =  3 x_1  +  5 x_2  +  4 x_3
subject to
  2 x_1  +  3 x_2 ≤ 8  2 x_2  +  5 x_3 ≤ 10  3 x_1  +  2 x_2  +  4 x_3 ≤ 15
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 add slack variable S_3

After introducing slack variables
 Max Z =  3 x_1  +  5 x_2  +  4 x_3  +  0 S_1  +  0 S_2  +  0 S_3
subject to
  2 x_1  +  3 x_2  +   S_1 = 8  2 x_2  +  5 x_3  +   S_2 = 10  3 x_1  +  2 x_2  +  4 x_3  +   S_3 = 15
and x_1,x_2,x_3,S_1,S_2,S_3 >= 0

 Iteration-1 C_j 3 5 4 0 0 0 B C_B X_B x_1 x_2 Entering variable x_3 S_1 S_2 S_3 MinRatio (X_B)/(x_2) S_1 Leaving variable 0 8 2 (3)  (pivot element) 0 1 0 0 (8)/(3)=2.67-> S_2 0 10 0 2 5 0 1 0 (10)/(2)=5 S_3 0 15 3 2 4 0 0 1 (15)/(2)=7.5 Z=0 0=Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 0 0=0xx2+0xx0+0xx3Z_j=sum C_B x_1 0 0=0xx3+0xx2+0xx2Z_j=sum C_B x_2 0 0=0xx0+0xx5+0xx4Z_j=sum C_B x_3 0 0=0xx1+0xx0+0xx0Z_j=sum C_B S_1 0 0=0xx0+0xx1+0xx0Z_j=sum C_B S_2 0 0=0xx0+0xx0+0xx1Z_j=sum C_B S_3 C_j-Z_j 3 3=3-0 5 5=5-0uarr 4 4=4-0 0 0=0-0 0 0=0-0 0 0=0-0

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

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

:. The pivot element is 3.

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

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

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

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

 Iteration-2 C_j 3 5 4 0 0 0 B C_B X_B x_1 x_2 x_3 Entering variable S_1 S_2 S_3 MinRatio (X_B)/(x_3) x_2 5 8/3 8/3=8-:3R_1(new)= R_1(old)-: 3 2/3 2/3=2-:3R_1(new)= R_1(old)-: 3 1 1=3-:3R_1(new)= R_1(old)-: 3 0 0=0-:3R_1(new)= R_1(old)-: 3 1/3 1/3=1-:3R_1(new)= R_1(old)-: 3 0 0=0-:3R_1(new)= R_1(old)-: 3 0 0=0-:3R_1(new)= R_1(old)-: 3 --- S_2 Leaving variable 0 14/3 14/3=10-2xx8/3R_2(new)= R_2(old)- 2 R_1(new) -4/3 -4/3=0-2xx2/3R_2(new)= R_2(old)- 2 R_1(new) 0 0=2-2xx1R_2(new)= R_2(old)- 2 R_1(new) (5) 5=5-2xx0 (pivot element)R_2(new)= R_2(old)- 2 R_1(new) -2/3 -2/3=0-2xx1/3R_2(new)= R_2(old)- 2 R_1(new) 1 1=1-2xx0R_2(new)= R_2(old)- 2 R_1(new) 0 0=0-2xx0R_2(new)= R_2(old)- 2 R_1(new) (14/3)/(5)=0.93-> S_3 0 29/3 29/3=15-2xx8/3R_3(new)= R_3(old)- 2 R_1(new) 5/3 5/3=3-2xx2/3R_3(new)= R_3(old)- 2 R_1(new) 0 0=2-2xx1R_3(new)= R_3(old)- 2 R_1(new) 4 4=4-2xx0R_3(new)= R_3(old)- 2 R_1(new) -2/3 -2/3=0-2xx1/3R_3(new)= R_3(old)- 2 R_1(new) 0 0=0-2xx0R_3(new)= R_3(old)- 2 R_1(new) 1 1=1-2xx0R_3(new)= R_3(old)- 2 R_1(new) (29/3)/(4)=2.42 Z=40/3 40/3=5xx8/3Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 10/3 10/3=5xx2/3+0xx(-4/3)+0xx5/3Z_j=sum C_B x_1 5 5=5xx1+0xx0+0xx0Z_j=sum C_B x_2 0 0=5xx0+0xx5+0xx4Z_j=sum C_B x_3 5/3 5/3=5xx1/3+0xx(-2/3)+0xx(-2/3)Z_j=sum C_B S_1 0 0=5xx0+0xx1+0xx0Z_j=sum C_B S_2 0 0=5xx0+0xx0+0xx1Z_j=sum C_B S_3 C_j-Z_j -1/3 -1/3=3-10/3 0 0=5-5 4 4=4-0uarr -5/3 -5/3=0-5/3 0 0=0-0 0 0=0-0

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

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

:. The pivot element is 5.

Entering =x_3, Departing =S_2, Key Element =5

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

R_1(new)= R_1(old)

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

 Iteration-3 C_j 3 5 4 0 0 0 B C_B X_B x_1 Entering variable x_2 x_3 S_1 S_2 S_3 MinRatio (X_B)/(x_1) x_2 5 8/3 8/3=8/3R_1(new)= R_1(old) 2/3 2/3=2/3R_1(new)= R_1(old) 1 1=1R_1(new)= R_1(old) 0 0=0R_1(new)= R_1(old) 1/3 1/3=1/3R_1(new)= R_1(old) 0 0=0R_1(new)= R_1(old) 0 0=0R_1(new)= R_1(old) (8/3)/(2/3)=4 x_3 4 14/15 14/15=14/3-:5R_2(new)= R_2(old)-: 5 -4/15 -4/15=(-4/3)-:5R_2(new)= R_2(old)-: 5 0 0=0-:5R_2(new)= R_2(old)-: 5 1 1=5-:5R_2(new)= R_2(old)-: 5 -2/15 -2/15=(-2/3)-:5R_2(new)= R_2(old)-: 5 1/5 1/5=1-:5R_2(new)= R_2(old)-: 5 0 0=0-:5R_2(new)= R_2(old)-: 5 --- S_3 Leaving variable 0 89/15 89/15=29/3-4xx14/15R_3(new)= R_3(old)- 4 R_2(new) (41/15) 41/15=5/3-4xx(-4/15) (pivot element)R_3(new)= R_3(old)- 4 R_2(new) 0 0=0-4xx0R_3(new)= R_3(old)- 4 R_2(new) 0 0=4-4xx1R_3(new)= R_3(old)- 4 R_2(new) -2/15 -2/15=(-2/3)-4xx(-2/15)R_3(new)= R_3(old)- 4 R_2(new) -4/5 -4/5=0-4xx1/5R_3(new)= R_3(old)- 4 R_2(new) 1 1=1-4xx0R_3(new)= R_3(old)- 4 R_2(new) (89/15)/(41/15)=2.17-> Z=256/15 256/15=5xx8/3+4xx14/15Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 34/15 34/15=5xx2/3+4xx(-4/15)+0xx41/15Z_j=sum C_B x_1 5 5=5xx1+4xx0+0xx0Z_j=sum C_B x_2 4 4=5xx0+4xx1+0xx0Z_j=sum C_B x_3 17/15 17/15=5xx1/3+4xx(-2/15)+0xx(-2/15)Z_j=sum C_B S_1 4/5 4/5=5xx0+4xx1/5+0xx(-4/5)Z_j=sum C_B S_2 0 0=5xx0+4xx0+0xx1Z_j=sum C_B S_3 C_j-Z_j 11/15 11/15=3-34/15uarr 0 0=5-5 0 0=4-4 -17/15 -17/15=0-17/15 -4/5 -4/5=0-4/5 0 0=0-0

Positive maximum C_j-Z_j is 11/15 and its column index is 1. So, the entering variable is x_1.

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

:. The pivot element is 41/15.

Entering =x_1, Departing =S_3, Key Element =41/15

R_3(new)= R_3(old)xx15/41

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

R_2(new)= R_2(old)+ 4/15 R_3(new)

 Iteration-4 C_j 3 5 4 0 0 0 B C_B X_B x_1 x_2 x_3 S_1 S_2 S_3 MinRatio x_2 5 50/41 50/41=8/3-2/3xx89/41R_1(new)= R_1(old)- 2/3 R_3(new) 0 0=2/3-2/3xx1R_1(new)= R_1(old)- 2/3 R_3(new) 1 1=1-2/3xx0R_1(new)= R_1(old)- 2/3 R_3(new) 0 0=0-2/3xx0R_1(new)= R_1(old)- 2/3 R_3(new) 15/41 15/41=1/3-2/3xx(-2/41)R_1(new)= R_1(old)- 2/3 R_3(new) 8/41 8/41=0-2/3xx(-12/41)R_1(new)= R_1(old)- 2/3 R_3(new) -10/41 -10/41=0-2/3xx15/41R_1(new)= R_1(old)- 2/3 R_3(new) x_3 4 62/41 62/41=14/15+4/15xx89/41R_2(new)= R_2(old)+ 4/15 R_3(new) 0 0=(-4/15)+4/15xx1R_2(new)= R_2(old)+ 4/15 R_3(new) 0 0=0+4/15xx0R_2(new)= R_2(old)+ 4/15 R_3(new) 1 1=1+4/15xx0R_2(new)= R_2(old)+ 4/15 R_3(new) -6/41 -6/41=(-2/15)+4/15xx(-2/41)R_2(new)= R_2(old)+ 4/15 R_3(new) 5/41 5/41=1/5+4/15xx(-12/41)R_2(new)= R_2(old)+ 4/15 R_3(new) 4/41 4/41=0+4/15xx15/41R_2(new)= R_2(old)+ 4/15 R_3(new) x_1 3 89/41 89/41=89/15xx15/41R_3(new)= R_3(old)xx15/41 1 1=41/15xx15/41R_3(new)= R_3(old)xx15/41 0 0=0xx15/41R_3(new)= R_3(old)xx15/41 0 0=0xx15/41R_3(new)= R_3(old)xx15/41 -2/41 -2/41=(-2/15)xx15/41R_3(new)= R_3(old)xx15/41 -12/41 -12/41=(-4/5)xx15/41R_3(new)= R_3(old)xx15/41 15/41 15/41=1xx15/41R_3(new)= R_3(old)xx15/41 Z=765/41 765/41=5xx50/41+4xx62/41+3xx89/41Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 3 3=5xx0+4xx0+3xx1Z_j=sum C_B x_1 5 5=5xx1+4xx0+3xx0Z_j=sum C_B x_2 4 4=5xx0+4xx1+3xx0Z_j=sum C_B x_3 45/41 45/41=5xx15/41+4xx(-6/41)+3xx(-2/41)Z_j=sum C_B S_1 24/41 24/41=5xx8/41+4xx5/41+3xx(-12/41)Z_j=sum C_B S_2 11/41 11/41=5xx(-10/41)+4xx4/41+3xx15/41Z_j=sum C_B S_3 C_j-Z_j 0 0=3-3 0 0=5-5 0 0=4-4 -45/41 -45/41=0-45/41 -24/41 -24/41=0-24/41 -11/41 -11/41=0-11/41

Since all C_j-Z_j <= 0

Hence, optimal solution is arrived with value of variables as :
x_1=89/41,x_2=50/41,x_3=62/41

Max Z = 765/41

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