1
$\begingroup$

Let be the following linear program.

\begin{cases} \max & 3x_1& +x_2\\ &x_1&-x_2 &\le -1\\ &-x_1 &-x_2&\le -3\\ &2x_1 &+x_2 &\le4\\ x_1,x_2\ge 0 \end{cases}

In the normal form it is:

\begin{cases} \max & 3x_1& +x_2\\ &x_1&-x_2 &+ x_3 &&&= -1\\ &-x_1 &-x_2&&+x_4&&= -3\\ &2x_1 &+x_2 &&&+x_5&=4\\ x_1,x_2\ge 0 \end{cases}

Which can be written as a dictionary:

\begin{cases} x_B&=\tilde b&+&\tilde Ax_\bar B\\ c^Tx&=\psi&+&\tilde c ^T_\bar Bx_\bar B \end{cases}

That is to say:

\begin{cases} x_B&=A_B^{-1}b&-&A_B^{-1}A_\bar Bx_{\bar B}\\ c^Tx&=c^T_BA_B^{-1}b&+&c^T_BA_B^{-1}A_{\bar B} \end{cases}

With:

\begin{equation} A= \begin{bmatrix} 1 & -1 & 1 &0 &0\\ -1 & -1 & 0 &1&0\\ 2 & 1 & 0 & 0 &1 \end{bmatrix}\\ \mbox{if B=1,2,5, } A_ B= \begin{bmatrix} 1 & -1 & 0\\ -1 & -1 & 0\\ 2 & 1 & 1 \end{bmatrix}\\ \end{equation}

We also need its invert, is there any other way than doing the heavy Gaussian elimination?

$$A_B^{-1}=\begin{bmatrix} 1/2 & -1/2 & 0\\ -1/2 & -1/2 & 0\\ -1/2 & 3/2 & 1 \end{bmatrix}$$

Now let's begin to do the dictionary:

\begin{equation} x_B=\begin{bmatrix} 1\\2\\0 \end{bmatrix}- \begin{bmatrix} 1/2 & -1/2 & 0\\ -1/2 & -1/2 & 0\\ -1/2 & 3/2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0\\ 0 & 1\\ 0 & 0 \end{bmatrix} \begin{bmatrix} x_3\\x_4 \end{bmatrix} \end{equation}

\begin{equation} x_B= \begin{cases} 1 -1/2(x_3+x_4)\\ 2+1/2(x_3+x_4)\\ 0-1/2(x_3-x_4) \end{cases} \end{equation}

Here is my main question which is revealed to be very important in order to follow and solve this problem: how to know which variable is assigned to each line?

It should be:

\begin{cases} (x_1):1 -1/2(x_3+x_4)\\ (x_2):2+1/2(x_3+x_4)\\ (x_5):0-1/2(x_3-x_4) \end{cases}

but why?

Knowing that it is $x_4$, that enter the basis (because it has an associated reduce cost positive with the basis $B=\{1,2,5\}$ let's solve this program using the revised simplex method:

In order to know which variable goes out of the basis,

$$A_Bd=A_p$$

find the greatest $t$ such that $x_B-td\ge 0$ (the pivot line p). The value of the incoming variable is $t$. The other variables value is $x_B-td$.

Only studying the effect of $x_4$, $A=\begin{bmatrix}0\\1\\0\end{bmatrix}$

$$\begin{cases} &d_1&-d_2&&=0\\ &-d_1&-d_2&&=1\\ &2d_1 &+d_2 &+ d_3&=0 \end{cases}\Leftrightarrow \begin{cases} d_1&=-1/2\\ d_2&=-1/2\\ d_3&=3/2 \end{cases}$$

We are going to find the greatest $t$ such that $x_B-td\ge 0$

\begin{cases} 1-t(-1/2)&\ge 0\\ 2-t(-1/2)&\ge 0\\ 0-t(3/2)&\ge 0 \end{cases}

It seems that, according to the marking, it is the last line, related to $x_5$, why is it related to such a variable?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.