2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.