Home > Operation Research calculators > Simplex method example


6. Integer simplex method (gomory's cutting plane method) example ( Enter your problem )
  1. Algorithm & Example-1 (Pure integer)
  2. Example-2 (Mixed integer)
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 (Mixed integer)


Find solution using integer simplex method (Gomory's cutting plane method)
MAX Z = x1 + x2
subject to
3x1 + 2x2 <= 5
x2 <= 2
and x2 >= 0 and x1 non-negative integers


Solution:
Problem is
Max `Z``=``````x_1`` + ````x_2`
subject to
```3``x_1`` + ``2``x_2``5`
`````x_2``2`
and `x_1,x_2 >= 0; ``x_1` non-negative integers


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``=``````x_1`` + ````x_2`` + ``0``S_1`` + ``0``S_2`
subject to
```3``x_1`` + ``2``x_2`` + ````S_1`=`5`
`````x_2`` + ````S_2`=`2`
and `x_1,x_2,S_1,S_2 >= 0`


Iteration-1 `C_j``1``1``0``0`
`B``C_B``X_B` `x_1` Entering variable`x_2``S_1``S_2`MinRatio
`(X_B)/(x_1)`
 `S_1` Leaving variable`0``5` `(3)`  (pivot element)`2``1``0``(5)/(3)=1.6667``->`
`S_2``0``2``0``1``0``1`---
 `Z=0` `0=`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `0` `0=0xx3+0xx0`
`Z_j=sum C_B x_1`
 `0` `0=0xx2+0xx1`
`Z_j=sum C_B x_2`
 `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` `1` `1=1-0``uarr` `1` `1=1-0` `0` `0=0-0` `0` `0=0-0`


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

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

`:.` The pivot element is `3`.

Entering `=x_1`, Departing `=S_1`, Key Element `=3`

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

`R_2`(new)`= R_2`(old)

Iteration-2 `C_j``1``1``0``0`
`B``C_B``X_B``x_1` `x_2` Entering variable`S_1``S_2`MinRatio
`(X_B)/(x_2)`
`x_1``1` `5/3` `5/3=5-:3`
`R_1`(new)`= R_1`(old)`-: 3`
 `1` `1=3-:3`
`R_1`(new)`= R_1`(old)`-: 3`
 `2/3` `2/3=2-: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`
`(5/3)/(2/3)=2.5`
 `S_2` Leaving variable`0` `2` `2=2`
`R_2`(new)`= R_2`(old)
 `0` `0=0`
`R_2`(new)`= R_2`(old)
 `(1)` `1=1` (pivot element)
`R_2`(new)`= R_2`(old)
 `0` `0=0`
`R_2`(new)`= R_2`(old)
 `1` `1=1`
`R_2`(new)`= R_2`(old)
`(2)/(1)=2``->`
 `Z=5/3` `5/3=1xx5/3`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `1` `1=1xx1+0xx0`
`Z_j=sum C_B x_1`
 `2/3` `2/3=1xx2/3+0xx1`
`Z_j=sum C_B x_2`
 `1/3` `1/3=1xx1/3+0xx0`
`Z_j=sum C_B S_1`
 `0` `0=1xx0+0xx1`
`Z_j=sum C_B S_2`
`C_j-Z_j` `0` `0=1-1` `1/3` `1/3=1-(2/3)``uarr` `-1/3` `-1/3=0-(1/3)` `0` `0=0-0`


Positive maximum `C_j-Z_j` is `1/3` and its column index is `2`. So, the entering variable is `x_2`.

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

`:.` The pivot element is `1`.

Entering `=x_2`, Departing `=S_2`, Key Element `=1`

`R_2`(new)`= R_2`(old)

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

Iteration-3 `C_j``1``1``0``0`
`B``C_B``X_B``x_1``x_2``S_1``S_2`MinRatio
`x_1``1` `1/3` `1/3=5/3-2/3xx2`
`R_1`(new)`= R_1`(old)`- 2/3 R_2`(new)
 `1` `1=1-2/3xx0`
`R_1`(new)`= R_1`(old)`- 2/3 R_2`(new)
 `0` `0=2/3-2/3xx1`
`R_1`(new)`= R_1`(old)`- 2/3 R_2`(new)
 `1/3` `1/3=1/3-2/3xx0`
`R_1`(new)`= R_1`(old)`- 2/3 R_2`(new)
 `-2/3` `-2/3=0-2/3xx1`
`R_1`(new)`= R_1`(old)`- 2/3 R_2`(new)
`x_2``1` `2` `2=2`
`R_2`(new)`= R_2`(old)
 `0` `0=0`
`R_2`(new)`= R_2`(old)
 `1` `1=1`
`R_2`(new)`= R_2`(old)
 `0` `0=0`
`R_2`(new)`= R_2`(old)
 `1` `1=1`
`R_2`(new)`= R_2`(old)
 `Z=7/3` `7/3=1xx1/3+1xx2`
`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`
 `1/3` `1/3=1xx1/3+1xx0`
`Z_j=sum C_B S_1`
 `1/3` `1/3=1xx(-2/3)+1xx1`
`Z_j=sum C_B S_2`
`C_j-Z_j` `0` `0=1-1` `0` `0=1-1` `-1/3` `-1/3=0-(1/3)` `-1/3` `-1/3=0-(1/3)`


Since all `C_j-Z_j <= 0`

Hence, non-integer optimal solution is arrived with value of variables as :
`x_1=1/3,x_2=2`

Max `Z = 7/3`

To obtain the integer valued solution, we proceed to construct Gomory's fractional cut, with the help of `x_1`-row as follows:

`1/3= 1 x_1+1/3 S_1 -2/3 S_2`

`(0+1/3)=(1+0) x_1+(0+1/3) S_1+(-1+1/3) S_2`

The fractional cut will become
`-1/3 = Sg1 -1/3 S_1 -1/3 S_2 ->` (Cut-1)

Adding this additional constraint at the bottom of optimal simplex table. The new table so obtained is

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


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

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

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

Entering `=S_1`, Departing `=Sg1`, Key Element `=-1/3`

`R_3`(new)`= R_3`(old)`xx-3`

`R_1`(new)`= R_1`(old)`- 1/3 R_3`(new)

`R_2`(new)`= R_2`(old)

Iteration-2 `C_j``1``1``0``0``0`
`B``C_B``X_B``x_1``x_2``S_1``S_2``Sg1`
`x_1``1` `0` `0=1/3-1/3xx1`
`R_1`(new)`= R_1`(old)`- 1/3 R_3`(new)
 `1` `1=1-1/3xx0`
`R_1`(new)`= R_1`(old)`- 1/3 R_3`(new)
 `0` `0=0-1/3xx0`
`R_1`(new)`= R_1`(old)`- 1/3 R_3`(new)
 `0` `0=1/3-1/3xx1`
`R_1`(new)`= R_1`(old)`- 1/3 R_3`(new)
 `-1` `-1=(-2/3)-1/3xx1`
`R_1`(new)`= R_1`(old)`- 1/3 R_3`(new)
 `1` `1=0-1/3xx(-3)`
`R_1`(new)`= R_1`(old)`- 1/3 R_3`(new)
`x_2``1` `2` `2=2`
`R_2`(new)`= R_2`(old)
 `0` `0=0`
`R_2`(new)`= R_2`(old)
 `1` `1=1`
`R_2`(new)`= R_2`(old)
 `0` `0=0`
`R_2`(new)`= R_2`(old)
 `1` `1=1`
`R_2`(new)`= R_2`(old)
 `0` `0=0`
`R_2`(new)`= R_2`(old)
`S_1``0` `1` `1=(-1/3)xx(-3)`
`R_3`(new)`= R_3`(old)`xx-3`
 `0` `0=0xx(-3)`
`R_3`(new)`= R_3`(old)`xx-3`
 `0` `0=0xx(-3)`
`R_3`(new)`= R_3`(old)`xx-3`
 `1` `1=(-1/3)xx(-3)`
`R_3`(new)`= R_3`(old)`xx-3`
 `1` `1=(-1/3)xx(-3)`
`R_3`(new)`= R_3`(old)`xx-3`
 `-3` `-3=1xx(-3)`
`R_3`(new)`= R_3`(old)`xx-3`
 `Z=2` `2=1xx0+1xx2`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `1` `1=1xx1+1xx0+0xx0`
`Z_j=sum C_B x_1`
 `1` `1=1xx0+1xx1+0xx0`
`Z_j=sum C_B x_2`
 `0` `0=1xx0+1xx0+0xx1`
`Z_j=sum C_B S_1`
 `0` `0=1xx(-1)+1xx1+0xx1`
`Z_j=sum C_B S_2`
 `1` `1=1xx1+1xx0+0xx(-3)`
`Z_j=sum C_B Sg1`
`C_j-Z_j` `0` `0=1-1` `0` `0=1-1` `0` `0=0-0` `0` `0=0-0` `-1` `-1=0-1`
Ratio---------------


Since all `C_j-Z_j <= 0`

Hence, integer optimal solution is arrived with value of variables as :
`x_1=0,x_2=2`

Max `Z = 2`

The integer optimal solution found after 1-cuts.



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