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 method (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`

Tableau-1	`C_j`	`6`	`4`	`0`	`0`	`0`	`-M`
`C_B`	`"Basis"`	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`	`"Ratio"=(RHS)/(x_1)`
`R_1` `0`	`S_1`	`2`	`3`	`1`	`0`	`0`	`0`	`30`	`(30)/(2)=15`
`R_2` `0`	`S_2`	`3`	`2`	`0`	`1`	`0`	`0`	`24`	`(24)/(3)=8`
`R_3` `-M`	`A_1`	`(1)`	`1`	`0`	`0`	`-1`	`1`	`3`	`(3)/(1)=3``->`
	`Z_j`	`-M`	`-M`	`0`	`0`	`M`	`-M`	`Z=-3M`
	`C_j-Z_j`	`M+6``uarr`	`M+4`	`0`	`0`	`-M`	`0`

Most Positive `C_j-Z_j` is `M+6`. So, the entering variable is `x_1`.

Minimum ratio 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)

	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`
`R_3`(old) =	`1`	`1`	`0`	`0`	`-1`	`1`	`3`
`R_3`(new)`= R_3`(old)	`1`	`1`	`0`	`0`	`-1`	`1`	`3`

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

	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`
`R_1`(old) =	`2`	`3`	`1`	`0`	`0`	`0`	`30`
`R_3`(new) =	`1`	`1`	`0`	`0`	`-1`	`1`	`3`
`2 xx R_3`(new) =	`2`	`2`	`0`	`0`	`-2`	`2`	`6`
`R_1`(new)`= R_1`(old) - `2 R_3`(new)	`0`	`1`	`1`	`0`	`2`	`-2`	`24`

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

	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`
`R_2`(old) =	`3`	`2`	`0`	`1`	`0`	`0`	`24`
`R_3`(new) =	`1`	`1`	`0`	`0`	`-1`	`1`	`3`
`3 xx R_3`(new) =	`3`	`3`	`0`	`0`	`-3`	`3`	`9`
`R_2`(new)`= R_2`(old) - `3 R_3`(new)	`0`	`-1`	`0`	`1`	`3`	`-3`	`15`

Tableau-2	`C_j`	`6`	`4`	`0`	`0`	`0`	`-M`
`C_B`	`"Basis"`	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`	`"Ratio"=(RHS)/(S_3)`
`R_1` `0`	`S_1`	`0`	`1`	`1`	`0`	`2`	`-2`	`24`	`(24)/(2)=12`
`R_2` `0`	`S_2`	`0`	`-1`	`0`	`1`	`(3)`	`-3`	`15`	`(15)/(3)=5``->`
`R_3` `6`	`x_1`	`1`	`1`	`0`	`0`	`-1`	`1`	`3`	`(3)/(-1)` (ignore, denominator is -ve)
	`Z_j`	`6`	`6`	`0`	`0`	`-6`	`6`	`Z=18`
	`C_j-Z_j`	`0`	`-2`	`0`	`0`	`6``uarr`	`-M-6`

Most Positive `C_j-Z_j` is `6`. So, the entering variable is `S_3`.

Minimum ratio is `5`. 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`

	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`
`R_2`(old) =	`0`	`-1`	`0`	`1`	`3`	`-3`	`15`
`R_2`(new)`= R_2`(old) `-: 3`	`0`	`-0.3333`	`0`	`0.3333`	`1`	`-1`	`5`

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

	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`
`R_1`(old) =	`0`	`1`	`1`	`0`	`2`	`-2`	`24`
`R_2`(new) =	`0`	`-0.3333`	`0`	`0.3333`	`1`	`-1`	`5`
`2 xx R_2`(new) =	`0`	`-0.6667`	`0`	`0.6667`	`2`	`-2`	`10`
`R_1`(new)`= R_1`(old) - `2 R_2`(new)	`0`	`1.6667`	`1`	`-0.6667`	`0`	`0`	`14`

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

	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`
`R_3`(old) =	`1`	`1`	`0`	`0`	`-1`	`1`	`3`
`R_2`(new) =	`0`	`-0.3333`	`0`	`0.3333`	`1`	`-1`	`5`
`R_3`(new)`= R_3`(old) + `R_2`(new)	`1`	`0.6667`	`0`	`0.3333`	`0`	`0`	`8`

Tableau-3	`C_j`	`6`	`4`	`0`	`0`	`0`	`-M`
`C_B`	`"Basis"`	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`	`"Ratio"`
`R_1` `0`	`S_1`	`0`	`1.6667`	`1`	`-0.6667`	`0`	`0`	`14`
`R_2` `0`	`S_3`	`0`	`-0.3333`	`0`	`0.3333`	`1`	`-1`	`5`
`R_3` `6`	`x_1`	`1`	`0.6667`	`0`	`0.3333`	`0`	`0`	`8`
	`Z_j`	`6`	`4`	`0`	`2`	`0`	`0`	`Z=48`
	`C_j-Z_j`	`0`	`0`	`0`	`-2`	`0`	`-M`

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.

Tableau-3	`C_j`	`6`	`4`	`0`	`0`	`0`	`-M`
`C_B`	`"Basis"`	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`	`"Ratio"=(RHS)/(x_2)`
`R_1` `0`	`S_1`	`0`	`(1.6667)`	`1`	`-0.6667`	`0`	`0`	`14`	`(14)/(1.6667)=8.4``->`
`R_2` `0`	`S_3`	`0`	`-0.3333`	`0`	`0.3333`	`1`	`-1`	`5`	`(5)/(-0.3333)` (ignore, denominator is -ve)
`R_3` `6`	`x_1`	`1`	`0.6667`	`0`	`0.3333`	`0`	`0`	`8`	`(8)/(0.6667)=12`
	`Z_j`	`6`	`4`	`0`	`2`	`0`	`0`	`Z=48`
	`C_j-Z_j`	`0`	`0``uarr`	`0`	`-2`	`0`	`-M`

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 `1.6667`.

Entering `=x_2`, Departing `=S_1`, Key Element `=1.6667`

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

	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`
`R_1`(old) =	`0`	`1.6667`	`1`	`-0.6667`	`0`	`0`	`14`
`R_1`(new)`= R_1`(old) `-: 1.6667`	`0`	`1`	`0.6`	`-0.4`	`0`	`0`	`8.4`

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

	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`
`R_2`(old) =	`0`	`-0.3333`	`0`	`0.3333`	`1`	`-1`	`5`
`R_1`(new) =	`0`	`1`	`0.6`	`-0.4`	`0`	`0`	`8.4`
`0.3333 xx R_1`(new) =	`0`	`0.3333`	`0.2`	`-0.1333`	`0`	`0`	`2.8`
`R_2`(new)`= R_2`(old) + `0.3333 R_1`(new)	`0`	`0`	`0.2`	`0.2`	`1`	`-1`	`7.8`

`R_3`(new)`= R_3`(old) - `0.6667 R_1`(new)

	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`
`R_3`(old) =	`1`	`0.6667`	`0`	`0.3333`	`0`	`0`	`8`
`R_1`(new) =	`0`	`1`	`0.6`	`-0.4`	`0`	`0`	`8.4`
`0.6667 xx R_1`(new) =	`0`	`0.6667`	`0.4`	`-0.2667`	`0`	`0`	`5.6`
`R_3`(new)`= R_3`(old) - `0.6667 R_1`(new)	`1`	`0`	`-0.4`	`0.6`	`0`	`0`	`2.4`

Tableau-4	`C_j`	`6`	`4`	`0`	`0`	`0`	`-M`
`C_B`	`"Basis"`	`x_1`	`x_2`	`S_1`	`S_2`	`S_3`	`A_1`	`RHS`	`"Ratio"`
`R_1` `4`	`x_2`	`0`	`1`	`0.6`	`-0.4`	`0`	`0`	`8.4`
`R_2` `0`	`S_3`	`0`	`0`	`0.2`	`0.2`	`1`	`-1`	`7.8`
`R_3` `6`	`x_1`	`1`	`0`	`-0.4`	`0.6`	`0`	`0`	`2.4`
	`Z_j`	`6`	`4`	`0`	`2`	`0`	`0`	`Z=48`
	`C_j-Z_j`	`0`	`0`	`0`	`-2`	`0`	`-M`

Since all `C_j-Z_j <= 0`

Hence, optimal solution is arrived with value of variables as :
`x_1=2.4,x_2=8.4`

Max `Z=48`

---

---