2
$\begingroup$

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.

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

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.