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

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)xx1`
`Z_j=sum C_B x_1`
 `-M` `-M=0xx3+0xx2+(-M)xx1`
`Z_j=sum C_B x_2`
 `0` `0=0xx1+0xx0+(-M)xx0`
`Z_j=sum C_B S_1`
 `0` `0=0xx0+0xx1+(-M)xx0`
`Z_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)xx1`
`Z_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 variableMinRatio
`(X_B)/(S_3)`
`S_1``0` `24` `24=30-2xx3`
`R_1`(new)`= R_1`(old)`- 2 R_3`(new)
 `0` `0=2-2xx1`
`R_1`(new)`= R_1`(old)`- 2 R_3`(new)
 `1` `1=3-2xx1`
`R_1`(new)`= R_1`(old)`- 2 R_3`(new)
 `1` `1=1-2xx0`
`R_1`(new)`= R_1`(old)`- 2 R_3`(new)
 `0` `0=0-2xx0`
`R_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-3xx3`
`R_2`(new)`= R_2`(old)`- 3 R_3`(new)
 `0` `0=3-3xx1`
`R_2`(new)`= R_2`(old)`- 3 R_3`(new)
 `-1` `-1=2-3xx1`
`R_2`(new)`= R_2`(old)`- 3 R_3`(new)
 `0` `0=0-3xx0`
`R_2`(new)`= R_2`(old)`- 3 R_3`(new)
 `1` `1=1-3xx0`
`R_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=3`
`R_3`(new)`= R_3`(old)
 `1` `1=1`
`R_3`(new)`= R_3`(old)
 `1` `1=1`
`R_3`(new)`= R_3`(old)
 `0` `0=0`
`R_3`(new)`= R_3`(old)
 `0` `0=0`
`R_3`(new)`= R_3`(old)
 `-1` `-1=-1`
`R_3`(new)`= R_3`(old)
---
 `Z=18` `18=6xx3`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `6` `6=0xx0+0xx0+6xx1`
`Z_j=sum C_B x_1`
 `6` `6=0xx1+0xx(-1)+6xx1`
`Z_j=sum C_B x_2`
 `0` `0=0xx1+0xx0+6xx0`
`Z_j=sum C_B S_1`
 `0` `0=0xx0+0xx1+6xx0`
`Z_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-2xx5`
`R_1`(new)`= R_1`(old)`- 2 R_2`(new)
 `0` `0=0-2xx0`
`R_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-2xx0`
`R_1`(new)`= R_1`(old)`- 2 R_2`(new)
 `-2/3` `-2/3=0-2xx1/3`
`R_1`(new)`= R_1`(old)`- 2 R_2`(new)
 `0` `0=2-2xx1`
`R_1`(new)`= R_1`(old)`- 2 R_2`(new)
`S_3``0` `5` `5=15-:3`
`R_2`(new)`= R_2`(old)`-: 3`
 `0` `0=0-:3`
`R_2`(new)`= R_2`(old)`-: 3`
 `-1/3` `-1/3=(-1)-:3`
`R_2`(new)`= R_2`(old)`-: 3`
 `0` `0=0-:3`
`R_2`(new)`= R_2`(old)`-: 3`
 `1/3` `1/3=1-:3`
`R_2`(new)`= R_2`(old)`-: 3`
 `1` `1=3-:3`
`R_2`(new)`= R_2`(old)`-: 3`
`x_1``6` `8` `8=3+5`
`R_3`(new)`= R_3`(old)`+ R_2`(new)
 `1` `1=1+0`
`R_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+0`
`R_3`(new)`= R_3`(old)`+ R_2`(new)
 `1/3` `1/3=0+1/3`
`R_3`(new)`= R_3`(old)`+ R_2`(new)
 `0` `0=(-1)+1`
`R_3`(new)`= R_3`(old)`+ R_2`(new)
 `Z=48` `48=6xx8`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `6` `6=0xx0+0xx0+6xx1`
`Z_j=sum C_B x_1`
 `4` `4=0xx5/3+0xx(-1/3)+6xx2/3`
`Z_j=sum C_B x_2`
 `0` `0=0xx1+0xx0+6xx0`
`Z_j=sum C_B S_1`
 `2` `2=0xx(-2/3)+0xx1/3+6xx1/3`
`Z_j=sum C_B S_2`
 `0` `0=0xx0+0xx1+6xx0`
`Z_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-2xx5`
`R_1`(new)`= R_1`(old)`- 2 R_2`(new)
 `0` `0=0-2xx0`
`R_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-2xx0`
`R_1`(new)`= R_1`(old)`- 2 R_2`(new)
 `-2/3` `-2/3=0-2xx1/3`
`R_1`(new)`= R_1`(old)`- 2 R_2`(new)
 `0` `0=2-2xx1`
`R_1`(new)`= R_1`(old)`- 2 R_2`(new)
`(14)/(5/3)=8.4``->`
`S_3``0` `5` `5=15-:3`
`R_2`(new)`= R_2`(old)`-: 3`
 `0` `0=0-:3`
`R_2`(new)`= R_2`(old)`-: 3`
 `-1/3` `-1/3=(-1)-:3`
`R_2`(new)`= R_2`(old)`-: 3`
 `0` `0=0-:3`
`R_2`(new)`= R_2`(old)`-: 3`
 `1/3` `1/3=1-:3`
`R_2`(new)`= R_2`(old)`-: 3`
 `1` `1=3-:3`
`R_2`(new)`= R_2`(old)`-: 3`
---
`x_1``6` `8` `8=3+5`
`R_3`(new)`= R_3`(old)`+ R_2`(new)
 `1` `1=1+0`
`R_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+0`
`R_3`(new)`= R_3`(old)`+ R_2`(new)
 `1/3` `1/3=0+1/3`
`R_3`(new)`= R_3`(old)`+ R_2`(new)
 `0` `0=(-1)+1`
`R_3`(new)`= R_3`(old)`+ R_2`(new)
`(8)/(2/3)=12`
 `Z=48` `48=6xx8`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `6` `6=0xx0+0xx0+6xx1`
`Z_j=sum C_B x_1`
 `4` `4=0xx5/3+0xx(-1/3)+6xx2/3`
`Z_j=sum C_B x_2`
 `0` `0=0xx1+0xx0+6xx0`
`Z_j=sum C_B S_1`
 `2` `2=0xx(-2/3)+0xx1/3+6xx1/3`
`Z_j=sum C_B S_2`
 `0` `0=0xx0+0xx1+6xx0`
`Z_j=sum C_B S_3`
`C_j-Z_j` `0` `0=6-6` `0` `0=4-4``uarr` `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/5`
`R_1`(new)`= R_1`(old)`xx3/5`
 `0` `0=0xx3/5`
`R_1`(new)`= R_1`(old)`xx3/5`
 `1` `1=5/3xx3/5`
`R_1`(new)`= R_1`(old)`xx3/5`
 `3/5` `3/5=1xx3/5`
`R_1`(new)`= R_1`(old)`xx3/5`
 `-2/5` `-2/5=(-2/3)xx3/5`
`R_1`(new)`= R_1`(old)`xx3/5`
 `0` `0=0xx3/5`
`R_1`(new)`= R_1`(old)`xx3/5`
`S_3``0` `39/5` `39/5=5+1/3xx42/5`
`R_2`(new)`= R_2`(old)`+ 1/3 R_1`(new)
 `0` `0=0+1/3xx0`
`R_2`(new)`= R_2`(old)`+ 1/3 R_1`(new)
 `0` `0=(-1/3)+1/3xx1`
`R_2`(new)`= R_2`(old)`+ 1/3 R_1`(new)
 `1/5` `1/5=0+1/3xx3/5`
`R_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/3xx0`
`R_2`(new)`= R_2`(old)`+ 1/3 R_1`(new)
`x_1``6` `12/5` `12/5=8-2/3xx42/5`
`R_3`(new)`= R_3`(old)`- 2/3 R_1`(new)
 `1` `1=1-2/3xx0`
`R_3`(new)`= R_3`(old)`- 2/3 R_1`(new)
 `0` `0=2/3-2/3xx1`
`R_3`(new)`= R_3`(old)`- 2/3 R_1`(new)
 `-2/5` `-2/5=0-2/3xx3/5`
`R_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/3xx0`
`R_3`(new)`= R_3`(old)`- 2/3 R_1`(new)
 `Z=48` `48=4xx42/5+6xx12/5`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `6` `6=4xx0+0xx0+6xx1`
`Z_j=sum C_B x_1`
 `4` `4=4xx1+0xx0+6xx0`
`Z_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/5`
`Z_j=sum C_B S_2`
 `0` `0=4xx0+0xx1+6xx0`
`Z_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
 
Copyright © 2018. All rights reserved. Terms, Privacy