Solving System of Restrictions with Simplex Algorithm

[evinda]

Hello! (Wave)

I want to apply the simplex algorithm that finds the vertices of the following system of restrictions:

$$2x_1+3x_2-x_3+4x_4=8 \\ -x_1+2x_2-6x_3+7x_4=3 \\ x_i \geq 0, i=1,2,3,4$$

I took at the beginning the basic feasible solution non degenerate solution $(1,2,0,0)$ and I wrote the following tableaux:

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & \theta & \\
P_1 & 1 & 2 & 3 & -1 & 4 & \frac{1}{4} & L_1\\ \\
P_2 & 2 & -1 & 2 & -6 & 7 & \frac{2}{7} & L_2
\end{matrix}$

We choose $P_4$ to get in the basis. The pivot is the number $4$ and so $P_1$ gets out of the basis.

Then I get the following tableaux:

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & \theta & \\
P_4 & \frac{1}{4} & \frac{1}{2} & \frac{3}{4} & -\frac{1}{4} & 1 & & L_1'=\frac{L_1}{4}\\ \\
P_2 & \frac{1}{4} & -\frac{9}{2} & -\frac{13}{4} & -\frac{17}{4} & 0 & & L_2'=L_2-7L_1'
\end{matrix}$So we get that $\left( 0, \frac{1}{4}, 0, \frac{1}{4}\right)$ is a basic feasible solution.

But using an other method, I found these vertices: $(1,2,0,0), \left( \frac{22}{9}, 0,0, \frac{7}{9}\right), \left(0, \frac{45}{16}, \frac{7}{16}, 0 \right), \left( 0,0, \frac{44}{17}, \frac{45}{17} \right)$.

So is one of the first or second tableaux wrong?

 

[I like Serena]

Hello! (Wave)

I want to apply the simplex algorithm that finds the vertices of the following system of restrictions:

$$2x_1+3x_2-x_3+4x_4=8 \\ -x_1+2x_2-6x_3+7x_4=3 \\ x_i \geq 0, i=1,2,3,4$$

I took at the beginning the basic feasible solution non degenerate solution $(1,2,0,0)$ and I wrote the following tableaux:

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & \theta & \\
P_1 & 1 & 2 & 3 & -1 & 4 & \frac{1}{4} & L_1\\ \\
P_2 & 2 & -1 & 2 & -6 & 7 & \frac{2}{7} & L_2
\end{matrix}$

Hey evinda! (Smile)

The system of restrictions doesn't seem to match the tableau. (Worried)

 

[evinda]

Hey evinda! (Smile)

The system of restrictions doesn't seem to match the tableau. (Worried)

At the columns of $P_1$ and $P_2$ do we put the coefficients of the variables and at the other columns everywhere zero? (Thinking)

 

[I like Serena]

At the columns of $P_1$ and $P_2$ do we put the coefficients of the variables and at the other columns everywhere zero? (Thinking)

The $8$ and $3$ on the right hand side have to go somewhere... (Thinking)

 

[evinda]

The $8$ and $3$ on the right hand side have to go somewhere... (Thinking)

Ah, I see... So should it be as follows? (Thinking)

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & \theta & \\
P_1 & 8 & 2 & 3 & 0 & 0 & & L_1\\ \\
P_2 & 3 & -1 & 2 & 0 & 0 & & L_2
\end{matrix}$

 

[I like Serena]

Ah, I see... So should it be as follows? (Thinking)

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & \theta & \\
P_1 & 8 & 2 & 3 & 0 & 0 & & L_1\\ \\
P_2 & 3 & -1 & 2 & 0 & 0 & & L_2
\end{matrix}$

The coefficients of $x_3$ and $x_4$ should also be in there.
The tableau is just a different way to write the set of equations. (Nerd)

 

[evinda]

The coefficients of $x_3$ and $x_4$ should also be in there.
The tableau is just a different way to write the set of equations. (Nerd)

You mean that it should be like that?

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & \theta & \\
P_1 & 8 & 2 & 3 & -1 & 4 & & L_1\\ \\
P_2 & 3 & -1 & 2 & -6 & 7 & & L_2
\end{matrix}$

If so, then how does this represent the initial basic feasible non-degenerate solution? (Thinking)

 

[I like Serena]

You mean that it should be like that?

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & \theta & \\
P_1 & 8 & 2 & 3 & -1 & 4 & & L_1\\ \\
P_2 & 3 & -1 & 2 & -6 & 7 & & L_2
\end{matrix}$

Yes.
This is the initial tableau that corresponds one-to-one with the set of equations. (Nerd)
(Actually, the column $B$ should be empty at this point.)

If so, then how does this represent the initial basic feasible non-degenerate solution? (Thinking)

It doesn't - yet.
We need to pivot and sweep it in such a way that the columns $P_1$ and $P_2$ get to contain the identity matrix. (Thinking)

 

[evinda]

It doesn't - yet.
We need to pivot and sweep it in such a way that the columns $P_1$ and $P_2$ get to contain the identity matrix. (Thinking)

So do we have to multiply the first row by 7 and the second by 4 and then subtract them? (Thinking)

 

[evinda]

I tried it and I got the following:$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & \theta \\
P_1 & & 14 & 21 & -7 & 28 & \\
P_2 & & 18 & 13 & 17 & 0 &
\end{matrix}$

 

[I like Serena]

So do we have to multiply the first row by 7 and the second by 4 and then subtract them? (Thinking)

I guess you're looking at column $P_4$.
No, that's not the column we should pivot. (Shake)

Instead we should pivot column $P_1$.
That is:
1. divide the first row by $2$.
2. add the resulting row to the second row.

That way we get $\begin{pmatrix}1\\0\end{pmatrix}$ in column $P_1$. (Thinking)Basic variables are the variables that belong to the columns that can be rearranged in an identity matrix.
That is, the columns that contain only zeroes except for a non-zero entry. (Nerd)

 

[evinda]

Could you explain further to me why we have to pivot the column $P_1$ ? I am confused right now... (Thinking)

 

[I like Serena]

Could you explain further to me why we have to pivot the column $P_1$ ? I am confused right now... (Thinking)

So that we get $\begin{pmatrix}1\\0\end{pmatrix}$ in column $P_1$.

Do you perchance have an example of a tableau where it is given what the basic variables are?
Can you give the definition of a basic variable? (Wondering)

 

[evinda]

So that we get $\begin{pmatrix}1\\0\end{pmatrix}$ in column $P_1$.

Oh yes, right... But how can we have simultanesouly $\begin{pmatrix}0\\1\end{pmatrix}$ in column $P_2$ ?

Do you perchance have an example of a tableau where it is given what the basic variables are?
Can you give the definition of a basic variable? (Wondering)

I think that there is no definition given... But we have to write all the columns in respect to the basic variables, right? (Thinking)

 

[I like Serena]

Oh yes, right... But how can we have simultanesouly $\begin{pmatrix}0\\1\end{pmatrix}$ in column $P_2$ ?

That's the next step.
It works the same way as when we want to solve a regular set of equations, when we bring the matrix to row echelon form. (Sweating)

I think that there is no definition given... But we have to write all the columns in respect to the basic variables, right? (Thinking)

The columns with only zeroes and a single non-zero value correspond to the basic variables.
The other columns correspond to non-basic or free variables.
In the initial tableau all variables are non-basic.
See wiki. (Nerd)
To signify the basic variables, we can write them in the $B$ column where they correspond to the variable with the non-zero entry in its column of zeroes.

 

[evinda]

For example if I multiply the first row by $\frac{7}{3}$ and then subtract it from the second row, the latter becomes $$\frac{7}{3} \ \ \ \ \ 0 \ \ \ \ \ \frac{32}{6} \ \ \ \ \ \ -\frac{13}{3}$$But we want the first number to be equal to zero. What else could we do? (Sweating)

 

[I like Serena]

For example if I multiply the first row by $\frac{7}{3}$ and then subtract it from the second row, the latter becomes $$\frac{7}{3} \ \ \ \ \ 0 \ \ \ \ \ \frac{32}{6} \ \ \ \ \ \ -\frac{13}{3}$$But we want the first number to be equal to zero. What else could we do? (Sweating)

Multiply the first row with $\frac 12$ and add it to the second row? (Thinking)

 

[evinda]

Multiply the first row with $\frac 12$ and add it to the second row? (Thinking)

Don't we get then this matrix? (Thinking)

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & \theta\\
P_1 & & \frac{1}{2} & \frac{3}{4} & -\frac{1}{4} & 1 & \\
P_2 & & \frac{1}{2} & \frac{17}{4} & -\frac{27}{4} & 10 &
\end{matrix}$

 

[I like Serena]

Don't we get then this matrix? (Thinking)

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & \theta\\
P_1 & & \frac{1}{2} & \frac{3}{4} & -\frac{1}{4} & 1 & \\
P_2 & & \frac{1}{2} & \frac{17}{4} & -\frac{27}{4} & 10 &
\end{matrix}$

I don't understand how you got that.

Starting from the initial tableau it should be:
\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 \\
& 8 & 2 & 3 & -1 & 4 \\
& 3 & -1 & 2 & -6 & 7
\end{matrix}

Divide first row by 2:
\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 \\
& 4 & 1 & \frac 32 & -\frac 12 & 2 \\
& 3 & -1 & 2 & -6 & 7
\end{matrix}

Add first row to second row:
\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 \\
P_1 & 4 & 1 & \frac 32 & -\frac 12 & 2 \\
& 7 & 0 & \frac 72 & -\frac {13}2 & 9
\end{matrix}
(Sweating)

 

[evinda]

I don't understand how you got that.

Starting from the initial tableau it should be:
\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 \\
& 8 & 2 & 3 & -1 & 4 \\
& 3 & -1 & 2 & -6 & 7
\end{matrix}

Divide first row by 2:
\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 \\
& 4 & 1 & \frac 32 & -\frac 12 & 2 \\
& 3 & -1 & 2 & -6 & 7
\end{matrix}

Add first row to second row:
\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 \\
P_1 & 4 & 1 & \frac 32 & -\frac 12 & 2 \\
& 7 & 0 & \frac 72 & -\frac {13}2 & 9
\end{matrix}
(Sweating)

Yes, I got the same so far... I was trying to get $\begin{matrix} 0 \\ 1 \end{matrix}$ at the column of $P_2$ , but I don't know how... (Sweating)

 

[I like Serena]

Yes, I got the same so far... I was trying to get $\begin{matrix} 0 \\ 1 \end{matrix}$ at the column of $P_2$ , but I don't know how... (Sweating)

\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 \\
P_1 & 4 & 1 & \frac 32 & -\frac 12 & 2 \\
& 7 & 0 & \frac 72 & -\frac {13}2 & 9
\end{matrix}

Err... multiply the second row by $\frac 27$ and make a new tableau.
Then subtract the second row times $\frac 32$ from the first row. (Thinking)

 

[evinda]

Err... multiply the second row by $\frac 27$ and make a new tableau.
Then subtract the second row times $\frac 32$ from the first row. (Thinking)

Then we get the following tableau, right? (Thinking)$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 \\
P_1 & 1 & 1 &0 & \frac{16}{7} & -\frac{13}{7} \\
P_2 & 2 & 0 & 1 & -\frac {13}7 & \frac{18}{7}
\end{matrix}$

 

[I like Serena]

Then we get the following tableau, right? (Thinking)$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 \\
P_1 & 1 & 1 &0 & \frac{16}{7} & -\frac{13}{7} \\
P_2 & 2 & 0 & 1 & -\frac {13}7 & \frac{18}{7}
\end{matrix}$

Yep. There we go. (Nod)
Now we have a tableau that shows that $x_1$ and $x_2$ are the basic variables, and they have values of $1$ respectively $2$.
The other non-basic variables are $x_3$ and $x_4$ and they are taken to be $0$. (Nerd)

 

[evinda]

Yep. There we go. (Nod)
Now we have a tableau that shows that $x_1$ and $x_2$ are the basic variables, and they have values of $1$ respectively $2$.

I see... (Nod)

The other non-basic variables are $x_3$ and $x_4$ and they are taken to be $0$. (Nerd)

Do we set $x_3=x_4=0$ or do we get it from the tableau? (Thinking)

 

[I like Serena]

Do we set $x_3=x_4=0$ or do we get it from the tableau? (Thinking)

All slots for the basic variables have already been filled up.
That's why we set them to $0$, regardless of what is in the corresponding columns.

More specifically, we set them to $0$ because otherwise it's not a basic feasible solution (a vertex in the corresponding graph), but would at best be just a regular feasible solution. (Nerd)

 

[evinda]

All slots for the basic variables have already been filled up.
That's why we set them to $0$, regardless of what is in the corresponding columns.

More specifically, we set them to $0$ because otherwise it's not a basic feasible solution (a vertex in the corresponding graph), but would at best be just a regular feasible solution. (Nerd)

I see... Thanks a lot! (Party)