MHB The column gets out of the basis

[evinda]

Hello! (Wave)

Find the basic feasible solutions of the system of restrictions:

$$2x_1+x_2+x_3=10 \\ 3x_1+8x_2+x_4=24 \\ x_2+x_5=2 \\ x_i \geq 0, i=1,2,3,4,5$$

We notice that the rank of the matrix $A=\begin{pmatrix}
2 & 1 & 1 & 0 & 0\\
3 & 8 & 0 & 1 & 0\\
0 & 1 & 0 & 0 & 1
\end{pmatrix}$ is $3$ and obviously for $x_1=x_2=0$ we have the solution $\overline{x_0}=(0,0,10,24,2)$ which is basic feasible non degenerate.
Thus the first tableaux of the algorithm of the searching of the vertices is the following:

$$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta \\ \\
P_3 & 10 & 2 & 1 & 1 & 0 & 0 & 10/2\\
P_4 & 24 & 3 & 8 & 0 & 1 & 0 & 24/3\\
P_5 & 2 & 0 & 1 & 0 & 0 & 5 & -
\end{matrix}$$We pick $P_1$ to get in the basis.

$$\theta_0= \min \{ \frac{10}{2}, \frac{24}{3}\}=5$$

The pivot is the element $2$ so the column $P_3$ gets out of the basis.How do we deduce that $P_3$ gets out of the basis? Since its the only column from $P_3, P_4, P_5$ that contains at the row where the pivot is a positive number? (Thinking)

 

[evinda]

Ok, I understood why $P_3$ gets out of the basis.Then we get this matrix:$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ \\
P_1 & 5 & 1 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & & \Gamma_1'=\frac{1}{2} \Gamma_1\\ \\
P_4 & 9 & 0 & \frac{13}{2} & -\frac{3}{2} & 1 & 0 & & \Gamma_2'=\Gamma_2-3\Gamma_1'\\ \\
P_5 & 2 & 0 & 1 & 0 &0 & 1 & & \Gamma_3'=\Gamma_3-0 \Gamma_1'
\end{matrix}$So the new solution that we found is $(5,0,0,9,2)$ which is basis feasible non degenerate.Then we choose to get in the basis whether the column $P_2$ or $P_3$.
We choose $P_2$.

$$\theta_0= \min \{ \frac{5}{\frac{1}{2}}, \frac{9}{\frac{13}{2}}, \frac{2}{1}\}=\frac{18}{3}$$

The pivot is the element $\frac{13}{2}$, so $P_4$ gets out of the basis.

Then we have this matrix:

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ \\
P_1 & \frac{56}{13} & 1 & 0 & \frac{8}{13} & -\frac{1}{13} & 0 & & \Gamma_1'= \Gamma_1-\frac{1}{2} \Gamma_2'\\ \\
P_2 & \frac{18}{13} & 0 & 1 & -\frac{3}{13} & \frac{2}{13} & 0 & & \Gamma_2'=\frac{2}{13} \Gamma_2\\ \\
P_5 & \frac{8}{13} & 0 & 0 & \frac{3}{13} &-\frac{2}{13} & 1 & & \Gamma_3'=\Gamma_3-\Gamma_2'
\end{matrix}$So the new solution that we found is $\left( \frac{56}{13}, \frac{18}{13}, 0,0, \frac{8}{13}\right)$ which is basic feasible non degenerate.Then we choose $P_3$ to get in the basis.

$\theta_0=\min \{ \frac{56}{8}, \frac{8}{3}\}=\frac{8}{3}$The pivot is the element $\frac{3}{13}$ and so the column $P_5$ gets out.
$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ \\
P_1 & \frac{664}{169} & 1 & 0 & 0 & \frac{1}{3} & -\frac{8}{3} & & \Gamma_1'= \Gamma_1-\frac{8}{13} \Gamma_3'\\ \\
P_2 & 2 & 0 & 1 & 0 & 0 & 1 & & \Gamma_2'= \Gamma_2+\frac{3}{13} \Gamma_3'\\ \\
P_3 & 0 & 0 & 0 & 1 &-\frac{2}{3} & \frac{13}{3} & & \Gamma_3'=\frac{13}{3}\Gamma_3
\end{matrix}$

Thus the new solution is $\left( \frac{664}{169}, 2 , \frac{8}{3}, 0, 0\right)$ which is basic feasible non degenerate.

If we choose $P_5$ we don't get a basic feasible solution, so we have to pick $P_1$.Is it right so far? (Thinking)