4
$\begingroup$

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.

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?

$\endgroup$
  • $\begingroup$ A typo in the first tableaux, last row 5->1 that was fixed later. It should be \begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta \\ P_5 & 2 & 0 & 1 & 0 & 0 & 1 & - \end{matrix} $\endgroup$ – arthur Nov 2 '15 at 3:29
1
+100
$\begingroup$

The last tableaux should be:

\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ \\ P_1 & \color{red}{\frac{8}{3}} & 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 & \color{red}{\frac{8}{3}} & 0 & 0 & 1 &-\frac{2}{3} & \frac{13}{3} & & \Gamma_3'=\frac{13}{3}\Gamma_3 \end{matrix}

$\frac{56}{13} - \frac{8}{3}.\frac{8}{13} = \frac{8}{3}$

Which gives $(\frac{8}{3},2,\frac{8}{3},0,0)$.


feasible region (x_1,x_2)

The inner polygon $ABCDE$ is the feasible region.

$A(0,0,10,24,2)$

$B(0,2,8,8,0)$

$C(\frac{8}{3},2,\frac{8}{3},0,0)$

$D(\frac{56}{13},\frac{18}{13},0,0,\frac{8}{13})$

$E(5,0,0,9,2)$

Something went wrong with the $\left( \frac{664}{169}, 2 , \frac{8}{3}, 0, 0\right)$ calculation?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I retried the calculations and found the same result as you...Thanks for your answer!!! Could you maybe also take a look at my other question about Simplex math.stackexchange.com/questions/1517592/… ? $\endgroup$ – evinda Nov 7 '15 at 17:16
  • 1
    $\begingroup$ You're welcome. I'll take a look at the other problem. $\endgroup$ – arthur Nov 7 '15 at 17:54
  • $\begingroup$ Nice... I edited it now and added also a specific example... $\endgroup$ – evinda Nov 7 '15 at 18:04

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.