MHB Solving System of Restrictions with Simplex Algorithm

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Algorithm System
AI Thread Summary
The discussion centers on applying the simplex algorithm to a system of linear restrictions. The initial tableau presented does not accurately represent the system, leading to confusion about the basic feasible solution. Participants clarify that the tableau must include the correct coefficients from the equations, and adjustments are needed to pivot correctly for basic variables. After several iterations, they arrive at a tableau that correctly identifies basic variables and their values, confirming the necessity of setting non-basic variables to zero for a valid basic feasible solution. The conversation emphasizes the importance of accurate tableau representation in the simplex method.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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?
 
Physics news on Phys.org
evinda said:
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)
 
I like Serena said:
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)
 
evinda said:
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)
 
I like Serena said:
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}$
 
evinda said:
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)
 
I like Serena said:
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)
 
evinda said:
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)
 
I like Serena said:
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)
 
  • #10
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}$
 
  • #11
evinda said:
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)
 
  • #12
Could you explain further to me why we have to pivot the column $P_1$ ? I am confused right now... (Thinking)
 
  • #13
evinda said:
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)
 
  • #14
I like Serena said:
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$ ?
I like Serena said:
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)
 
  • #15
evinda said:
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.
 
  • #16
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)
 
  • #17
evinda said:
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)
 
  • #18
I like Serena said:
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}$
 
  • #19
evinda said:
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. :confused:

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)
 
  • #20
I like Serena said:
I don't understand how you got that. :confused:

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)
 
  • #21
evinda said:
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 said:
\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)
 
  • #22
I like Serena said:
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}$
 
  • #23
evinda said:
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)
 
  • #24
I like Serena said:
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)

I like Serena said:
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)
 
  • #25
evinda said:
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)
 
  • #26
I like Serena said:
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)
 

Similar threads

Replies
32
Views
5K
Replies
4
Views
2K
Replies
1
Views
1K
Replies
4
Views
2K
Replies
6
Views
2K
Replies
3
Views
2K
Replies
11
Views
994
Replies
4
Views
1K
Back
Top