Degeneracy example-1 (Tie for leaving basic variable)
During solving LP problem, a situation may arise in which there is a tie between, 2 or more basic variables for leaving the basis. (means minimum ratios are same).
It is called degeneracy and to resolve this we can select any of them arbitrarily.
But if artificial variable is present then it must be removed first.

---

Example
Find solution using Simplex method (BigM method)
MAX Z = 3x1 + 9x2
subject to
x1 + 4x2 <= 8
x1 + 2x2 <= 4
and x1,x2 >= 0;

Solution:
Problem is

Max `Z` `=` `` `3` `x_1` ` + ` `9` `x_2`

subject to

`` `` `x_1` ` + ` `4` `x_2` ≤ `8` `` `` `x_1` ` + ` `2` `x_2` ≤ `4`

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`

After introducing slack variables

Max `Z` `=` `` `3` `x_1` ` + ` `9` `x_2` ` + ` `0` `S_1` ` + ` `0` `S_2`

subject to

`` `` `x_1` ` + ` `4` `x_2` ` + ` `` `S_1` = `8` `` `` `x_1` ` + ` `2` `x_2` ` + ` `` `S_2` = `4`

and `x_1,x_2,S_1,S_2 >= 0`

Tableau-1	`C_j`	`3`	`9`	`0`	`0`
`C_B`	`"Basis"`	`x_1`	`x_2`	`S_1`	`S_2`	`RHS`	`"Ratio"=(RHS)/(x_2)`
`R_1` `0`	`S_1`	`1`	`4`	`1`	`0`	`8`	`(8)/(4)=2`
`R_2` `0`	`S_2`	`1`	`(2)`	`0`	`1`	`4`	`(4)/(2)=2``->`
	`Z_j`	`0`	`0`	`0`	`0`	`Z=0`
	`Z_j-C_j`	`-3`	`-9``uarr`	`0`	`0`

Most Negative `Z_j-C_j` is `-9`. So, the entering variable is `x_2`.

Minimum ratio is `2`. So, the leaving basis variable is `S_2`.

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

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

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

	`x_1`	`x_2`	`S_1`	`S_2`	`RHS`
`R_2`(old) =	`1`	`2`	`0`	`1`	`4`
`R_2`(new)`= R_2`(old) `-: 2`	`0.5`	`1`	`0`	`0.5`	`2`

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

	`x_1`	`x_2`	`S_1`	`S_2`	`RHS`
`R_1`(old) =	`1`	`4`	`1`	`0`	`8`
`R_2`(new) =	`0.5`	`1`	`0`	`0.5`	`2`
`4 xx R_2`(new) =	`2`	`4`	`0`	`2`	`8`
`R_1`(new)`= R_1`(old) - `4 R_2`(new)	`-1`	`0`	`1`	`-2`	`0`

Tableau-2	`C_j`	`3`	`9`	`0`	`0`
`C_B`	`"Basis"`	`x_1`	`x_2`	`S_1`	`S_2`	`RHS`	`"Ratio"`
`R_1` `0`	`S_1`	`-1`	`0`	`1`	`-2`	`0`
`R_2` `9`	`x_2`	`0.5`	`1`	`0`	`0.5`	`2`
	`Z_j`	`4.5`	`9`	`0`	`4.5`	`Z=18`
	`Z_j-C_j`	`1.5`	`0`	`0`	`4.5`

Since all `Z_j-C_j >= 0`

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

Max `Z=18`

---

---