Using the Lexicography rule makes sure that the algorithm terminates. This example below is a classical example where there is a tie in the leaving variables which I am uncertain which variable should leave the basis. $$(P_1) \text{ }\text{max}\left \{ 3+x_1+2x_2+3x_3 \mid \begin{matrix}2x_1-x_2+2x_3 \leq 8\\-x_1+3x_2+3x_3 \leq 12\\ -x_1-x_2+5x_3 \geq -4\\ x_1,x_2,x_3 \geq 0 \end{matrix} \right \}$$
I firstly formed these inequations to equations:
$2x_1-x_2+2x_3 +u_1 = 8$
$-x_1+3x_2+3x_3 +u_2 = 12$
$x_1+x_2-5x_3+u_3 = 4$
$x_1,x_2,x_3 \geq 0$
Now I started to make the simplex table:
x1 | x2 | x3 | u1 | u2 | u3 |
_____|_____|_____|______|_____|_____|___
2 | -1 | 2 | 1 | 0 | 0 | 8
-1 | 3 | 3 | 0 | 1 | 0 | 12
1 | 1 | -5 | 0 | 0 | 1 | 4
_____|_____|_____|______|_____|_____|___
1 | 2 | 3 | 0 | 0 | 0 | 0
We pick $x_3$ as the entering variable since it has the largest reduce cost. Now deciding which variable should leave the basis, we have row 1$ (u_1): \frac{8}{2}=4$ and row 2$ (u_2): \frac{12}{3}=4$. There's a tie.
What should I do?