# Solve this linear programming by using lexicographic simplex algorithm

I can actually solve tasks like that but this one seems special. I cannot decide which element is the best to be chosen as pivot element because they are all equal.

$(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 \}$

It's said that using lexicographic simplex algorithm is ideal. But how shall I use it if every element is equal when divided?

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


The third row is the row where we have possible pivot element, because 3 is greatest value of the last line. Now if we devide, we get that $\frac{8}{2}=4$ and $\frac{12}{3}=4$. You see the problem :(

I choose in third row 2 as pivot element or rather 3? How can I use lexicographic simplex algorithm if we have same elements? I think in lexicographic I need to choose the smallest but there is no other element left.

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.