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

4. Minimization example

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

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+Mxx1`
`Z_j=sum C_B x_1`
 `11M` `11M=Mxx4+Mxx7`
`Z_j=sum C_B x_2`
 `-M` `-M=Mxx(-1)+Mxx0`
`Z_j=sum C_B S_1`
 `-M` `-M=Mxx0+Mxx(-1)`
`Z_j=sum C_B S_2`
 `M` `M=Mxx1+Mxx0`
`Z_j=sum C_B A_1`
 `M` `M=Mxx0+Mxx1`
`Z_j=sum C_B A_2`
`C_j-Z_j` `-3M+1` `-3M+1=1-3M` `-11M+1` `-11M+1=1-11M``uarr` `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-4xx1`
`R_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-4xx1`
`R_1`(new)`= R_1`(old)`- 4 R_2`(new)
 `-1` `-1=(-1)-4xx0`
`R_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-4xx0`
`R_1`(new)`= R_1`(old)`- 4 R_2`(new)
`(0)/(10/7)=0``->`
`x_2``1` `1` `1=7-:7`
`R_2`(new)`= R_2`(old)`-: 7`
 `1/7` `1/7=1-:7`
`R_2`(new)`= R_2`(old)`-: 7`
 `1` `1=7-:7`
`R_2`(new)`= R_2`(old)`-: 7`
 `0` `0=0-:7`
`R_2`(new)`= R_2`(old)`-: 7`
 `-1/7` `-1/7=(-1)-:7`
`R_2`(new)`= R_2`(old)`-: 7`
 `0` `0=0-:7`
`R_2`(new)`= R_2`(old)`-: 7`
`(1)/(1/7)=7`
 `Z=1` `1=1xx1`
`Z_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/7`
`Z_j=sum C_B x_1`
 `1` `1=Mxx0+1xx1`
`Z_j=sum C_B x_2`
 `-M` `-M=Mxx(-1)+1xx0`
`Z_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+1xx0`
`Z_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 variableMinRatio
`(X_B)/(S_2)`
 `x_1` Leaving variable`1` `0` `0=0xx7/10`
`R_1`(new)`= R_1`(old)`xx7/10`
 `1` `1=10/7xx7/10`
`R_1`(new)`= R_1`(old)`xx7/10`
 `0` `0=0xx7/10`
`R_1`(new)`= R_1`(old)`xx7/10`
 `-7/10` `-7/10=(-1)xx7/10`
`R_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/7xx0`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
 `0` `0=1/7-1/7xx1`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
 `1` `1=1-1/7xx0`
`R_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/5`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
---
 `Z=1` `1=1xx0+1xx1`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `1` `1=1xx1+1xx0`
`Z_j=sum C_B x_1`
 `1` `1=1xx0+1xx1`
`Z_j=sum C_B x_2`
 `-3/5` `-3/5=1xx(-7/10)+1xx1/10`
`Z_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/2`
`R_1`(new)`= R_1`(old)`xx5/2`
 `5/2` `5/2=1xx5/2`
`R_1`(new)`= R_1`(old)`xx5/2`
 `0` `0=0xx5/2`
`R_1`(new)`= R_1`(old)`xx5/2`
 `-7/4` `-7/4=(-7/10)xx5/2`
`R_1`(new)`= R_1`(old)`xx5/2`
 `1` `1=2/5xx5/2`
`R_1`(new)`= R_1`(old)`xx5/2`
`x_2``1` `1` `1=1+1/5xx0`
`R_2`(new)`= R_2`(old)`+ 1/5 R_1`(new)
 `1/2` `1/2=0+1/5xx5/2`
`R_2`(new)`= R_2`(old)`+ 1/5 R_1`(new)
 `1` `1=1+1/5xx0`
`R_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/5xx1`
`R_2`(new)`= R_2`(old)`+ 1/5 R_1`(new)
 `Z=1` `1=1xx1`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `1/2` `1/2=0xx5/2+1xx1/2`
`Z_j=sum C_B x_1`
 `1` `1=0xx0+1xx1`
`Z_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+1xx0`
`Z_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`


 
Copyright © 2018. All rights reserved. Terms, Privacy