Home > Operation Research calculators > Simplex method example


5. Dual simplex method example ( Enter your problem )
  1. Algorithm & Example-1
  2. Example-2
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

2. Example-2


Find solution using dual-simplex method
MIN Z = 2x1 + 3x2 + 0x3
subject to
2x1 - x2 - x3 >= 3
x1 - x2 + x3 >= 2
and x1,x2,x3 >= 0


Solution:
Problem is
Min `Z``=````2``x_1`` + ``3``x_2`
subject to
```2``x_1`` - ````x_2`` - ````x_3``3`
`````x_1`` - ````x_2`` + ````x_3``2`
and `x_1,x_2,x_3 >= 0; `


In order to apply the dual simplex method, convert Min Z to Max Z and all `>=` constraint to `<=` constraint by multiply -1.

Problem is
Max `Z``=`` - ``2``x_1`` - ``3``x_2`
subject to
` - ``2``x_1`` + ````x_2`` + ````x_3``-3`
` - ````x_1`` + ````x_2`` - ````x_3``-2`
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`

After introducing slack variables
Max `Z``=`` - ``2``x_1`` - ``3``x_2`` + ``0``x_3`` + ``0``S_1`` + ``0``S_2`
subject to
` - ``2``x_1`` + ````x_2`` + ````x_3`` + ````S_1`=`-3`
` - ````x_1`` + ````x_2`` - ````x_3`` + ````S_2`=`-2`
and `x_1,x_2,x_3,S_1,S_2 >= 0`


Iteration-1 `C_j``-2``-3``0``0``0`
`B``C_B``X_B` `x_1` Entering variable`x_2``x_3``S_1``S_2`
 `S_1` Leaving variable`0``-3` `(-2)`  (pivot element)`1``1``1``0`
`S_2``0``-2``-1``1``-1``0``1`
 `Z=0` `0=`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `0` `0=0xx(-2)+0xx(-1)`
`Z_j=sum C_B x_1`
 `0` `0=0xx1+0xx1`
`Z_j=sum C_B x_2`
 `0` `0=0xx1+0xx(-1)`
`Z_j=sum C_B x_3`
 `0` `0=0xx1+0xx0`
`Z_j=sum C_B S_1`
 `0` `0=0xx0+0xx1`
`Z_j=sum C_B S_2`
`C_j-Z_j` `-2` `-2=(-2)-0` `-3` `-3=(-3)-0` `0` `0=0-0` `0` `0=0-0` `0` `0=0-0`
`"Ratio"=(C_j-Z_j)/(S_1,j)`
and `S_1,j<0`
 `1` `1=(-2)/(-2)`
`"Ratio"=(C_j-Z_j)/(S_1,j)`
`uarr`
 --- `S_1,j=1;` which is not `<0` --- `S_1,j=1;` which is not `<0` --- `S_1,j=1;` which is not `<0` --- `S_1,j=0;` which is not `<0`


Minimum negative `X_B` is `-3` and its row index is `1`. So, the leaving basis variable is `S_1`.

Minimum positive ratio is `1` and its column index is `1`. So, the entering variable is `x_1`.

`:.` The pivot element is `-2`.

Entering `=x_1`, Departing `=S_1`, Key Element `=-2`

`R_1`(new)`= R_1`(old)`-: -2`

`R_2`(new)`= R_2`(old)`+ R_1`(new)

Iteration-2 `C_j``-2``-3``0``0``0`
`B``C_B``X_B``x_1``x_2` `x_3` Entering variable`S_1``S_2`
`x_1``-2` `3/2` `3/2=(-3)-:(-2)`
`R_1`(new)`= R_1`(old)`-: -2`
 `1` `1=(-2)-:(-2)`
`R_1`(new)`= R_1`(old)`-: -2`
 `-1/2` `-1/2=1-:(-2)`
`R_1`(new)`= R_1`(old)`-: -2`
 `-1/2` `-1/2=1-:(-2)`
`R_1`(new)`= R_1`(old)`-: -2`
 `-1/2` `-1/2=1-:(-2)`
`R_1`(new)`= R_1`(old)`-: -2`
 `0` `0=0-:(-2)`
`R_1`(new)`= R_1`(old)`-: -2`
 `S_2` Leaving variable`0` `-1/2` `-1/2=(-2)+3/2`
`R_2`(new)`= R_2`(old)`+ R_1`(new)
 `0` `0=(-1)+1`
`R_2`(new)`= R_2`(old)`+ R_1`(new)
 `1/2` `1/2=1+(-1/2)`
`R_2`(new)`= R_2`(old)`+ R_1`(new)
 `(-3/2)` `-3/2=(-1)+(-1/2)` (pivot element)
`R_2`(new)`= R_2`(old)`+ R_1`(new)
 `-1/2` `-1/2=0+(-1/2)`
`R_2`(new)`= R_2`(old)`+ R_1`(new)
 `1` `1=1+0`
`R_2`(new)`= R_2`(old)`+ R_1`(new)
 `Z=-3` `-3=(-2)xx3/2`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `-2` `-2=(-2)xx1+0xx0`
`Z_j=sum C_B x_1`
 `1` `1=(-2)xx(-1/2)+0xx1/2`
`Z_j=sum C_B x_2`
 `1` `1=(-2)xx(-1/2)+0xx(-3/2)`
`Z_j=sum C_B x_3`
 `1` `1=(-2)xx(-1/2)+0xx(-1/2)`
`Z_j=sum C_B S_1`
 `0` `0=(-2)xx0+0xx1`
`Z_j=sum C_B S_2`
`C_j-Z_j` `0` `0=(-2)-(-2)` `-4` `-4=(-3)-1` `-1` `-1=0-1` `-1` `-1=0-1` `0` `0=0-0`
`"Ratio"=(C_j-Z_j)/(S_2,j)`
and `S_2,j<0`
 --- `S_2,j=0;` which is not `<0` --- `S_2,j=1/2;` which is not `<0` `0.6667` `0.6667=(-1)/(-3/2)`
`"Ratio"=(C_j-Z_j)/(S_2,j)`
`uarr`
 `2` `2=(-1)/(-1/2)`
`"Ratio"=(C_j-Z_j)/(S_2,j)`
 --- `S_2,j=1;` which is not `<0`


Minimum negative `X_B` is `-1/2` and its row index is `2`. So, the leaving basis variable is `S_2`.

Minimum positive ratio is `0.6667` and its column index is `3`. So, the entering variable is `x_3`.

`:.` The pivot element is `-3/2`.

Entering `=x_3`, Departing `=S_2`, Key Element `=-3/2`

`R_2`(new)`= R_2`(old)`xx-2/3`

`R_1`(new)`= R_1`(old)`+ 1/2 R_2`(new)

Iteration-3 `C_j``-2``-3``0``0``0`
`B``C_B``X_B``x_1``x_2``x_3``S_1``S_2`
`x_1``-2` `5/3` `5/3=3/2+1/2xx1/3`
`R_1`(new)`= R_1`(old)`+ 1/2 R_2`(new)
 `1` `1=1+1/2xx0`
`R_1`(new)`= R_1`(old)`+ 1/2 R_2`(new)
 `-2/3` `-2/3=(-1/2)+1/2xx(-1/3)`
`R_1`(new)`= R_1`(old)`+ 1/2 R_2`(new)
 `0` `0=(-1/2)+1/2xx1`
`R_1`(new)`= R_1`(old)`+ 1/2 R_2`(new)
 `-1/3` `-1/3=(-1/2)+1/2xx1/3`
`R_1`(new)`= R_1`(old)`+ 1/2 R_2`(new)
 `-1/3` `-1/3=0+1/2xx(-2/3)`
`R_1`(new)`= R_1`(old)`+ 1/2 R_2`(new)
`x_3``0` `1/3` `1/3=(-1/2)xx(-2/3)`
`R_2`(new)`= R_2`(old)`xx-2/3`
 `0` `0=0xx(-2/3)`
`R_2`(new)`= R_2`(old)`xx-2/3`
 `-1/3` `-1/3=1/2xx(-2/3)`
`R_2`(new)`= R_2`(old)`xx-2/3`
 `1` `1=(-3/2)xx(-2/3)`
`R_2`(new)`= R_2`(old)`xx-2/3`
 `1/3` `1/3=(-1/2)xx(-2/3)`
`R_2`(new)`= R_2`(old)`xx-2/3`
 `-2/3` `-2/3=1xx(-2/3)`
`R_2`(new)`= R_2`(old)`xx-2/3`
 `Z=-10/3` `-10/3=(-2)xx5/3+0xx1/3`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `-2` `-2=(-2)xx1+0xx0`
`Z_j=sum C_B x_1`
 `4/3` `4/3=(-2)xx(-2/3)+0xx(-1/3)`
`Z_j=sum C_B x_2`
 `0` `0=(-2)xx0+0xx1`
`Z_j=sum C_B x_3`
 `2/3` `2/3=(-2)xx(-1/3)+0xx1/3`
`Z_j=sum C_B S_1`
 `2/3` `2/3=(-2)xx(-1/3)+0xx(-2/3)`
`Z_j=sum C_B S_2`
`C_j-Z_j` `0` `0=(-2)-(-2)` `-13/3` `-13/3=(-3)-(4/3)` `0` `0=0-0` `-2/3` `-2/3=0-(2/3)` `-2/3` `-2/3=0-(2/3)`
Ratio---------------


Since all `C_j-Z_j <= 0` and all `X_(Bi) >= 0` thus the current solution is the optimal solution.

Hence, optimal solution is arrived with value of variables as :
`x_1=5/3,x_2=0,x_3=1/3`

Max `Z = -10/3`

`:.` Min `Z = 10/3`




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