Home > Operation Research calculators > Simplex method example


1. Simplex (BigM) method example ( Enter your problem )
  1. Simplex method Algorithm
  2. BigM method Algorithm
  3. Maximization example
  4. Minimization example
  5. Degeneracy example-1 (Tie for leaving basic variable)
  6. Degeneracy example-2 (Tie - first Artificial variable removed)
  7. Unrestricted variable example
  8. Multiple optimal solution example
  9. Unbounded solution example
  10. Infeasible solution example
Other related methods
  1. Simplex (BigM) method
  2. Two-Phase method
  3. Graphical method
  4. Primal to dual conversion
  5. Dual simplex method
  6. Integer simplex method
  7. Branch and Bound method
  8. 0-1 Integer programming 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+0xx3`
`Z_j=sum C_B x_1`
 `0` `0=0xx3+0xx2+0xx2`
`Z_j=sum C_B x_2`
 `0` `0=0xx0+0xx5+0xx4`
`Z_j=sum C_B x_3`
 `0` `0=0xx1+0xx0+0xx0`
`Z_j=sum C_B S_1`
 `0` `0=0xx0+0xx1+0xx0`
`Z_j=sum C_B S_2`
 `0` `0=0xx0+0xx0+0xx1`
`Z_j=sum C_B S_3`
`C_j-Z_j` `3` `3=3-0` `5` `5=5-0``uarr` `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-:3`
`R_1`(new)`= R_1`(old)`-: 3`
 `2/3` `2/3=2-:3`
`R_1`(new)`= R_1`(old)`-: 3`
 `1` `1=3-:3`
`R_1`(new)`= R_1`(old)`-: 3`
 `0` `0=0-:3`
`R_1`(new)`= R_1`(old)`-: 3`
 `1/3` `1/3=1-:3`
`R_1`(new)`= R_1`(old)`-: 3`
 `0` `0=0-:3`
`R_1`(new)`= R_1`(old)`-: 3`
 `0` `0=0-:3`
`R_1`(new)`= R_1`(old)`-: 3`
---
 `S_2` Leaving variable`0` `14/3` `14/3=10-2xx8/3`
`R_2`(new)`= R_2`(old)`- 2 R_1`(new)
 `-4/3` `-4/3=0-2xx2/3`
`R_2`(new)`= R_2`(old)`- 2 R_1`(new)
 `0` `0=2-2xx1`
`R_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/3`
`R_2`(new)`= R_2`(old)`- 2 R_1`(new)
 `1` `1=1-2xx0`
`R_2`(new)`= R_2`(old)`- 2 R_1`(new)
 `0` `0=0-2xx0`
`R_2`(new)`= R_2`(old)`- 2 R_1`(new)
`(14/3)/(5)=0.93``->`
`S_3``0` `29/3` `29/3=15-2xx8/3`
`R_3`(new)`= R_3`(old)`- 2 R_1`(new)
 `5/3` `5/3=3-2xx2/3`
`R_3`(new)`= R_3`(old)`- 2 R_1`(new)
 `0` `0=2-2xx1`
`R_3`(new)`= R_3`(old)`- 2 R_1`(new)
 `4` `4=4-2xx0`
`R_3`(new)`= R_3`(old)`- 2 R_1`(new)
 `-2/3` `-2/3=0-2xx1/3`
`R_3`(new)`= R_3`(old)`- 2 R_1`(new)
 `0` `0=0-2xx0`
`R_3`(new)`= R_3`(old)`- 2 R_1`(new)
 `1` `1=1-2xx0`
`R_3`(new)`= R_3`(old)`- 2 R_1`(new)
`(29/3)/(4)=2.42`
 `Z=40/3` `40/3=5xx8/3`
`Z_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/3`
`Z_j=sum C_B x_1`
 `5` `5=5xx1+0xx0+0xx0`
`Z_j=sum C_B x_2`
 `0` `0=5xx0+0xx5+0xx4`
`Z_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+0xx0`
`Z_j=sum C_B S_2`
 `0` `0=5xx0+0xx0+0xx1`
`Z_j=sum C_B S_3`
`C_j-Z_j` `-1/3` `-1/3=3-10/3` `0` `0=5-5` `4` `4=4-0``uarr` `-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/3`
`R_1`(new)`= R_1`(old)
 `2/3` `2/3=2/3`
`R_1`(new)`= R_1`(old)
 `1` `1=1`
`R_1`(new)`= R_1`(old)
 `0` `0=0`
`R_1`(new)`= R_1`(old)
 `1/3` `1/3=1/3`
`R_1`(new)`= R_1`(old)
 `0` `0=0`
`R_1`(new)`= R_1`(old)
 `0` `0=0`
`R_1`(new)`= R_1`(old)
`(8/3)/(2/3)=4`
`x_3``4` `14/15` `14/15=14/3-:5`
`R_2`(new)`= R_2`(old)`-: 5`
 `-4/15` `-4/15=(-4/3)-:5`
`R_2`(new)`= R_2`(old)`-: 5`
 `0` `0=0-:5`
`R_2`(new)`= R_2`(old)`-: 5`
 `1` `1=5-:5`
`R_2`(new)`= R_2`(old)`-: 5`
 `-2/15` `-2/15=(-2/3)-:5`
`R_2`(new)`= R_2`(old)`-: 5`
 `1/5` `1/5=1-:5`
`R_2`(new)`= R_2`(old)`-: 5`
 `0` `0=0-:5`
`R_2`(new)`= R_2`(old)`-: 5`
---
 `S_3` Leaving variable`0` `89/15` `89/15=29/3-4xx14/15`
`R_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-4xx0`
`R_3`(new)`= R_3`(old)`- 4 R_2`(new)
 `0` `0=4-4xx1`
`R_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/5`
`R_3`(new)`= R_3`(old)`- 4 R_2`(new)
 `1` `1=1-4xx0`
`R_3`(new)`= R_3`(old)`- 4 R_2`(new)
`(89/15)/(41/15)=2.17``->`
 `Z=256/15` `256/15=5xx8/3+4xx14/15`
`Z_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/15`
`Z_j=sum C_B x_1`
 `5` `5=5xx1+4xx0+0xx0`
`Z_j=sum C_B x_2`
 `4` `4=5xx0+4xx1+0xx0`
`Z_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+0xx1`
`Z_j=sum C_B S_3`
`C_j-Z_j` `11/15` `11/15=3-34/15``uarr` `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/41`
`R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)
 `0` `0=2/3-2/3xx1`
`R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)
 `1` `1=1-2/3xx0`
`R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)
 `0` `0=0-2/3xx0`
`R_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/41`
`R_1`(new)`= R_1`(old)`- 2/3 R_3`(new)
`x_3``4` `62/41` `62/41=14/15+4/15xx89/41`
`R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)
 `0` `0=(-4/15)+4/15xx1`
`R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)
 `0` `0=0+4/15xx0`
`R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)
 `1` `1=1+4/15xx0`
`R_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/41`
`R_2`(new)`= R_2`(old)`+ 4/15 R_3`(new)
`x_1``3` `89/41` `89/41=89/15xx15/41`
`R_3`(new)`= R_3`(old)`xx15/41`
 `1` `1=41/15xx15/41`
`R_3`(new)`= R_3`(old)`xx15/41`
 `0` `0=0xx15/41`
`R_3`(new)`= R_3`(old)`xx15/41`
 `0` `0=0xx15/41`
`R_3`(new)`= R_3`(old)`xx15/41`
 `-2/41` `-2/41=(-2/15)xx15/41`
`R_3`(new)`= R_3`(old)`xx15/41`
 `-12/41` `-12/41=(-4/5)xx15/41`
`R_3`(new)`= R_3`(old)`xx15/41`
 `15/41` `15/41=1xx15/41`
`R_3`(new)`= R_3`(old)`xx15/41`
 `Z=765/41` `765/41=5xx50/41+4xx62/41+3xx89/41`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `3` `3=5xx0+4xx0+3xx1`
`Z_j=sum C_B x_1`
 `5` `5=5xx1+4xx0+3xx0`
`Z_j=sum C_B x_2`
 `4` `4=5xx0+4xx1+3xx0`
`Z_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/41`
`Z_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


Share with your friends
 
Copyright © 2018. All rights reserved. Terms, Privacy