1. Find solution using integer simplex method (Gomory's cutting plane method)
MAX Z = x1 + x2
subject to
3x1 + 2x2 <= 5
x2 <= 2
and x1,x2 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,x_2` 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.67``->`
`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.67` 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.