Lexicography Rule with a Tie - an example

Question

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?

Answer 1

You should clean up your question because you are messing up rows with collumns.

Okay, so I guess what you want to say is:

You chose $x_3$ as entering variable, because of greatest coefficient, ok.

Now you need to choose between row 1 and row 2 for leaving variable.

Lexicographic rule means, that you create set S of rows with equal ratio $p_i/q_{ij}$ here 8/2 and 12/3 so S={1,2}.

So you have vectors: $row_1 = (-2,1,-2)$ and $row2=(1,-3,-3)$, we label them $row_1=l$, $row2=m$

Now you choose smallest vector lexicographically, which here means you compare vectors elementwise: is $l_1<m_1$? if yes, you take row 1 and variable $u_1$ as leaving variable, if they are equal, you compare $l_2$ with $m_2$ and so on...

Here $-2<1$ so you take $u_1$ as leaving variable.

If set S of row indices is bigger than 2, you compare all vectors lexicographically and take the smallest.

Hope this helps.