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?