Simplex Method for Linear Programming Problems: Limitations and Exceptions

[evinda]

If we have a linear programming problem that is of the form as the following:

$$\max (- x_1+ 2 x_2-3x_3) \\ x_1- \frac{1}{2} x_2+x_3+x_{4}=11 \\ 2x_2-x_3+x_5=0 \\ 2x_4+x_6=8 \\ x_i \geq 0, i \in \{ 1, \dots, 6 \}$$

we cannot use the simplex method since we cannot find a basic feasible non-degenerate solution , right?

 

[I like Serena]

Re: Optimal solution

If we have a linear programming problem that is of the form as the following:

$$\max (- x_1+ 2 x_2-3x_3) \\ x_1- \frac{1}{2} x_2+x_3+x_{4}=11 \\ 2x_2-x_3+x_5=0 \\ 2x_4x_6=8 \\ x_i \geq 0, i \in \{ 1, \dots, 6 \}$$

we cannot use the simplex method since we cannot find a basic feasible non-degenerate solution , right?

Hey evinda! (Smile)

I think we can still use the simplex method.
A degenerate basic feasible solution does not prohibit that - it's just something to be careful with. (Nerd)

 

[evinda]

Re: Optimal solution

Hey evinda! (Smile)

I think we can still use the simplex method.
A degenerate basic feasible solution does not prohibit that - it's just something to be careful with. (Nerd)

So we pick $(11,0,0,0,0,8)$ as the initial solution? (Thinking)

- - - Updated - - -

But then don't we have just two basic variables? Or am I wrong? (Thinking)

 

[I like Serena]

Re: Optimal solution

So we pick $(11,0,0,0,0,8)$ as the initial solution? (Thinking)

But then don't we have just two basic variables? Or am I wrong? (Thinking)

I think that's not a solution. (Shake)

Can you make an initial tableau? (Wondering)

 

[evinda]

Re: Optimal solution

I think that's not a solution. (Shake)

Can you make an initial tableau? (Wondering)

$\begin{bmatrix}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & \theta\\
P_1 & 11 & 1 & -\frac{1}{2} & 1 & 1 & 0 & 0 & \\
P_5 & 0 & 0 & 2 & -1 & 0 & 1 & 0 & \\
P_6 & 8 & 0 & 0 & 0 & 2 & 0 & 1 & \\
& z & 1 & -2 & 3 & 0 & 0 &0 &
\end{bmatrix}$

Right?

 

[I like Serena]

Is there a typo in the 3rd equation? (Wondering)

 

[evinda]

Is there a typo in the 3rd equation? (Wondering)

Oh yes, I am sorry...
It should be $2x_4+x_6=8$... (Blush)

 

[I like Serena]

Re: Optimal solution

So we pick $(11,0,0,0,0,8)$ as the initial solution? (Thinking)

But then don't we have just two basic variables? Or am I wrong? (Thinking)

Then that initial solution is fine.
And we will still have 3 basic variables.
They correspond to the columns with a single non-zero entry. (Mmm)

 

[evinda]

Re: Optimal solution

Then that initial solution is fine.
And we will still have 3 basic variables.
They correspond to the columns with a single non-zero entry. (Mmm)

Then we get this:

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & \theta & \\
P_1 & 11 & 1 & 0 & \frac{3}{4} & 1 & \frac{1}{4} & 0 & &L_1'=L_1+ \frac{1}{2}L_2' \\
P_2 & 0 & 0 & 1 & -\frac{1}{2} & 0 & \frac{1}{2} & 0 & & L_2'=\frac{L_2}{2}\\
P_6 & 8 & 0 & 0 & 0 & 2 & 0 & 1 & &L_3'=L_3 \\
& z & 1 & 0 & 2 & 0 & 1 &0 & & L_4'=L_4+2L_2'
\end{matrix}$

Do we accept this tableau, although it gives again a degenerate basic feasible solution? (Thinking)

If so, then it gives the optimal solution, right?

 

[I like Serena]

Re: Optimal solution

Do we accept this tableau, although it gives again a degenerate basic feasible solution? (Thinking)

If so, then it gives the optimal solution, right?

That's the problem with a degenerate condition - we can't be sure yet.
So there may still be a better solution.
We have to keep trying. (Thinking)

 

[evinda]

Re: Optimal solution

That's the problem with a degenerate condition - we can't be sure yet.
So there may still be a better solution.
We have to keep trying. (Thinking)

So we apply the simplex method till what criterion is satisfied? (Thinking)

 

[I like Serena]

Re: Optimal solution

So we apply the simplex method till what criterion is satisfied? (Thinking)

Until it's not degenerate and it's optimal, or until we cannot find a more optimal solution. (Nerd)

 

[evinda]

Re: Optimal solution

Until it's not degenerate and it's optimal, or until we cannot find a more optimal solution. (Nerd)

A ok... In this case, do we choose any of $P_3, P_4,P_5$ to get in the basis or do we take into consideration an other criterion? (Thinking)

 

[I like Serena]

Re: Optimal solution

A ok... In this case, do we choose any of $P_3, P_4,P_5$ to get in the basis or do we take into consideration an other criterion? (Thinking)

Which one will get us out of the degenerate condition? (Wondering)

 

[evinda]

Re: Optimal solution

Which one will get us out of the degenerate condition? (Wondering)

Both $P_3$ and $P_5$, right? (Thinking)

I chose $P_3$ and I got the following tableau:$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & & \theta\\
P_3 & \frac{44}{3} & \frac{4}{3} & 0 & 1 & \frac{4}{3} & \frac{1}{3} & 0 & 11 &L_1''=\frac{L_1' 4}{3} \\
P_2 & \frac{22}{3} & \frac{2}{3} & 1 & 0 & \frac{2}{3} & \frac{2}{3} & 0 & 11 & L_2''=L_2'+\frac{1}{2}L_1''\\
P_6 & 8 & 0 & 0 & 0 & 2 & 0 & 1 & 4 &L_3''=L_3' \\
&z & -\frac{5}{3} & 0 & 0 & -\frac{8}{3} & \frac{1}{3} & 0 & & L_4''=L_4'-2L_1''
\end{matrix}$

$-\frac{5}{3}>-\frac{8}{3}$, thus $P_4$ gets in the basis and $P_6$ gets out of the basis.
Then I got the following tableau:

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & & \theta\\
P_3 & \frac{28}{3} & \frac{4}{3} & 0 & 1 & 0 & \frac{1}{3} & -\frac{2}{4} & \frac{28}{4} &L_1'''=L_1''-\frac{4}{3}L_3'' \\
P_2 & \frac{14}{3} & 0 & 1 & 0 & 0 & \frac{2}{3} & -\frac{1}{3} & - & L_2'''=L_2''-\frac{2}{3}L_3'''\\
P_4 & 4 & 0 & 0 & 0 & 1 & 0 & \frac{1}{2} & - &L_3'''=\frac{L_3''}{2} \\
&z & -\frac{5}{3} & 0 & 0 & 0 & \frac{1}{3} & \frac{4}{3} & & L_4'''=L_4''+\frac{8}{3}L_3'''
\end{matrix}$

Then $P_1$ gets in the basis and $P_3$ gets out of the basis:

$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & & \theta\\
P_1 & \frac{28}{4} & 1 & 0 & \frac{3}{4} & 0 & \frac{1}{4} & -\frac{1}{2} & &L_1''''=\frac{L_1''' 3}{4} \\
P_2 & \frac{14}{3} & 0 & 1 & 0 & 0 & \frac{2}{3} & -\frac{1}{3} & & L_2''''=L_2'''\\
P_4 & 4 & 0 & 0 & 0 & 1 & 0 & \frac{1}{2} & - &L_3''''=L_3''' \\
&z & 0 & 0 & \frac{5}{4} & 0 & \frac{3}{4} & \frac{3}{4} & & L_4''''=L_4'''+\frac{5}{3}L_1''''
\end{matrix}$

Is everything right? (Thinking)

If so, do we deduce now from the fact that $z_k''''-c_k \geq 0 \forall k$ and that we have a non-degenerate basic feasible solution, that it is the optimal one? (Thinking)

 

[I like Serena]

Re: Optimal solution

We had the initial tableau:

$\begin{bmatrix}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & \theta\\
P_1 & 11 & 1 & -\frac{1}{2} & 1 & 1 & 0 & 0 & \\
P_5 & 0 & 0 & 2 & -1 & 0 & 1 & 0 & \\
P_6 & 8 & 0 & 0 & 0 & 2 & 0 & 1 & \\
& z & 1 & -2 & 3 & 0 & 0 &0 &
\end{bmatrix}$

Then we picked the initial solution $(11,0,0,0,0,8)$ and got this:

Then we get this:
$\begin{matrix}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & \theta & \\
P_1 & 11 & 1 & 0 & \frac{3}{4} & 1 & \frac{1}{4} & 0 & &L_1'=L_1+ \frac{1}{2}L_2' \\
P_2 & 0 & 0 & 1 & -\frac{1}{2} & 0 & \frac{1}{2} & 0 & & L_2'=\frac{L_2}{2}\\
P_6 & 8 & 0 & 0 & 0 & 2 & 0 & 1 & &L_3'=L_3 \\
& z & 1 & 0 & 2 & 0 & 1 &0 & & L_4'=L_4+2L_2'
\end{matrix}$

Is everything right? (Thinking)

I think there is a mistake in that tableau. (Worried)

Shouldn't it be:
\begin{array}{cc|cccccc}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 \\
\hline
P_1 & 11 & 1 & & \frac{1}{2} & 1 & \frac{1}{2} & \\
P_2 & 0 & & 1 & -\frac{1}{2} & & \frac{1}{2} & \\
P_6 & 8 & & & & 2 & & 1 \\
\hline
& & 1 & & 2 & & 1 &
\end{array}
(Wondering)

 

[evinda]

Re: Optimal solution

We had the initial tableau:Then we picked the initial solution $(11,0,0,0,0,8)$ and got this:

I think there is a mistake in that tableau. (Worried)

Shouldn't it be:
\begin{array}{cc|cccccc}
B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 \\
\hline
P_1 & 11 & 1 & & \frac{1}{2} & 1 & \frac{1}{2} & \\
P_2 & 0 & & 1 & -\frac{1}{2} & & \frac{1}{2} & \\
P_6 & 8 & & & & 2 & & 1 \\
\hline
& & 1 & & 2 & & 1 &
\end{array}
(Wondering)

I retried it and I got again the same result... (Worried)

Isn't it $L_1'=L_1+ \frac{1}{2} L_2'$ ?

At the first row and third column we have the number $1$.
And then $1+ \frac{1}{2} \left( - \frac{1}{2} \right)=1- \frac{1}{4}=\frac{4-1}{4}=\frac{3}{4}$

Or am I wrong? (Thinking)

 

[evinda]

If so, then the optimal solution is $\frac{7}{3}$, right? (Thinking)

 

[I like Serena]

The optimal solution has an objective value of $-7$.
Currently you're at $-11$.
To get there, we need $P_4$ in the basis.

 

[evinda]

The optimal solution has an objective value of $-7$.
Currently you're at $-11$.
To get there, we need $P_4$ in the basis.

How did you find that the optimal solution has an objective value of $-7$? (Thinking)

There should be a mistake at one of my tableaus. But I always find the same ones... (Sweating)
Do you have an idea what might be wrong?

 

[I like Serena]

Let's start from the beginning. (Sweating)
We have the initial tableau:
\begin{array}{cc|ccccc}
B &b &P1 &P2 &P3 &P4 &P5 &P6 \\
\hline
P1 &11 &1 &-0.5 &1 &1 & & \\
P5 &0 & &\enclose{circle}{2} &-1 & &1 & \\
P6 &8 & & & &2 & &1 \\
\hline
& &1 &-2 &3 & & & \\
\end{array}
With corresponding solution $(11, 0, 0, 0, 0, 8)$ and objective value $z=-x_1+2x_2-3x_3=-11$.

After selecting the circled $\enclose{circle}2$ we get:
\begin{array}{cc|ccccc}
B &b &P1 &P2 &P3 &P4 &P5 &P6 \\
\hline
P1 &11 &1 &0 &0.75 &1 &0.25 &0 \\
P2 &0 &0 &1 &\enclose{circle}{-0.5} &0 &0.5 &0 \\
P6 &8 &0 &0 &0 &2 &0 &1 \\
\hline
&0 &1 &0 &2 &0 &1 &0 \\
\end{array}
With corresponding solution $(11, 0, 0, 0, 0, 8)$ and objective value $z=-11$.
I think you also had this. (Thinking)

I believe you then selected $P_3$, in which case I'm getting:
\begin{array}{cc|ccccc}
B &b &P1 &P2 &P3 &P4 &P5 &P6 \\
\hline
P1 &11 &1 &1.5 &0 &1 &1 &0 \\
P3 &0 &0 &-2 &1 &0 &-1 &0 \\
P6 &8 &0 &0 &0 &2 &0 &1 \\
\hline
&0 &1 &4 &0 &0 &3 &0 \\
\end{array}
But this looks different from what you have...

 

[evinda]

Let's start from the beginning. (Sweating)
We have the initial tableau:
\begin{array}{cc|ccccc}
B &b &P1 &P2 &P3 &P4 &P5 &P6 \\
\hline
P1 &11 &1 &-0.5 &1 &1 & & \\
P5 &0 & &\enclose{circle}{2} &-1 & &1 & \\
P6 &8 & & & &2 & &1 \\
\hline
& &1 &-2 &3 & & & \\
\end{array}
With corresponding solution $(11, 0, 0, 0, 0, 8)$ and objective value $z=-x_1+2x_2-3x_3=-11$.

After selecting the circled $\enclose{circle}2$ we get:
\begin{array}{cc|ccccc}
B &b &P1 &P2 &P3 &P4 &P5 &P6 \\
\hline
P1 &11 &1 &0 &0.75 &1 &0.25 &0 \\
P2 &0 &0 &1 &\enclose{circle}{-0.5} &0 &0.5 &0 \\
P6 &8 &0 &0 &0 &2 &0 &1 \\
\hline
&0 &1 &0 &2 &0 &1 &0 \\
\end{array}
With corresponding solution $(11, 0, 0, 0, 0, 8)$ and objective value $z=-11$.
I think you also had this. (Thinking)

I believe you then selected $P_3$, in which case I'm getting:
\begin{array}{cc|ccccc}
B &b &P1 &P2 &P3 &P4 &P5 &P6 \\
\hline
P1 &11 &1 &1.5 &0 &1 &1 &0 \\
P3 &0 &0 &-2 &1 &0 &-1 &0 \\
P6 &8 &0 &0 &0 &2 &0 &1 \\
\hline
&0 &1 &4 &0 &0 &3 &0 \\
\end{array}
But this looks different from what you have...

Before we put $P_3$ in the basis we see that the pivot is $\frac{3}{4}$, so we have to multiply the first line by $\frac{4}{3}$, don't we? (Thinking)

 

[I like Serena]

Before we put $P_3$ in the basis we see that the pivot is $\frac{3}{4}$, so we have to multiply the first line by $\frac{4}{3}$, don't we? (Thinking)

I picked the pivot $\enclose{circle}{-\frac 12}$. Doesn't that one have a lower $\theta$ value? (Wondering)

 

[evinda]

I picked the pivot $\enclose{circle}{-\frac 12}$. Doesn't that one have a lower $\theta$ value? (Wondering)

I didn't pick it since $\theta$ is defined as follows:

$$\theta= \min_i \left \{ \frac{x_{i0}}{x_{ij}}: x_{ij}>0\right \}>0$$

(Thinking)

 

[I like Serena]

I didn't pick it since $\theta$ is defined as follows:

$$\theta= \min_i \left \{ \frac{x_{i0}}{x_{ij}}: x_{ij}>0\right \}>0$$

(Thinking)

Simplex algorithms vary. What is your algorithm exactly?
Which column should we select?
And does it take degenerate tableaux into account? (Wondering)

 

[evinda]

$(\overline{x_0})$ is a basic non-degenerate feasible solution

Step 1: We create a $(m+1) \times (n+4)$ matrix as follows:

• At the first column we write the basic columns $P_1, \dots, P_m$
• At the second column we write the values of the corresponding cost factor.
• At the third column we write the initial basic non-degenerate feasible solution $\overline{x_0}$.
• At the next n columns we write the elements of the columns of the matrix $A$.
• The last column remains currently empty.
• At the last row we write the value $z_0$ of the objective function that corresponds to the solution $\overline{x_0}$, and also the values of the differences $z_k-c_k, k=1, \dots, n$.

Step 2: We check if $\overline{x_0}$ is optimal by checking the differences $z_k-c_k, k=m+1, \dots, n$.

• If $z_k-c_k \geq 0 \forall k=m+1, \dots, n$ then $\overline{x_0}$ is an optimal solution.
• If $z_j-c_j<0$ for some $j \in \{ m+1, \dots, n \}$ then $\overline{x_0}$ is not an optimal solution.

Step 3: How do I choose the new column $P_j$ that gets into the basis ( of $\mathbb{R}^m$)

The column that will get basic is given by the following relation:

$P_j$ such that $|z_j-c_j|= \max_k \{ |z_k-c_k|: z_k-c_k<0\}$

Step 4: How do I choose the column $P_i$ that gets out of the initial basis $B=P_1, \dots, P_m)$

$P_i$ such that $\frac{x_{i0}}{x_{ij}}= \min \{ \frac{x_{k0}}{x_{kj}}: x_{kj}>0\}$Step 5: We compute thecoefficients of the next tableau from the relations:

$$x_{ik}'=\frac{x_{ik}}{x_{ij}} , k=0,1, \dots, n \\ x_{sk}'=x_{sk}-\frac{x_{ik}}{x_{ij}} x_{sj}, s=1,2, \dots, m, m+1, s \neq i, k=0,1,2, \dots, n \\ x_{(m+1)k}=z_k-c_k, k=1, \dots, n \\ x_{(m+1)0}=z_0$$

$$\Gamma_i'=\frac{1}{x_{ij}} \Gamma_i \\ \Gamma_m'=\Gamma_m- x_{mj} \Gamma_i'$$

 

[I like Serena]

Indeed. It does not take a degenerate tableau into account.
It considers a situation where $z_k−c_k=0$ as an optimal solution.
But that is not necessarily the case when one of the $b$ values is $0$.
In such a case we need an extension to the algorithm to find the actual optimal solution.

Does your course material mention what to do when we have a degenerate basic feasible solution? (Wondering)

 

[evinda]

I found this now in my textbook:

Degenerate solutions:

• Obviously if $\theta_0=\min_i \left\{ \frac{x_{i0}}{x_{ij}}: x_{ij}>0\right\}$ is achieved in more than one rows ( for example $\theta_0=\frac{x_{10}}{x_{1j}}=\frac{x_{20}}{x_{2j}}$), then the corresponding solution $x_1$ is degenerate.
• If the initial solution is degenerate , then we might have had $x_{10}=0, x_{1j}>0$, thus $\theta_0=0$ and therefore $x_1=x_0$ and $z_1=z_0$, i.e. that the solution couldn't be improved.At both of the above cases, we turn the degenerate solution to non-degenerate, replacing $0$ of the basic variable by $\epsilon>0$, arbitrarily small and we continue normally till we find the optimal solution, and then we set again $\epsilon=0$.

If we do this, will we get a different tableau? (Thinking)

 

[evinda]

The last tableau that we get is the following, right?

$\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & \theta & \\
P_1 & -1& 7 & 1 & 0 & \frac{3}{4} & 0 & \frac{1}{4} & -\frac{1}{2} & & L_1''''=L_1''' \frac{3}{4}\\
P_2 & 2 & 0 & 0 & 1 & -\frac{1}{2} & 0 & \frac{1}{2} & 0 & & L_2''''=L_2'''-\frac{2}{3}L_1''''\\
P_4 & 0 & 4 & 0 & 0 & 0 &1 & 0 & \frac{1}{2} & & L_3''''=L_3'''\\
& z & -7 & 0 & 0 & \frac{5}{4} & 0 & \frac{3}{4} & \frac{1}{2} & & L_4''''=L_4'''+\frac{5}{3}L_1''''
\end{matrix}$If we replace $0$ of the basic variable by $\epsilon$ and then set $\epsilon=0$ at the last tableau to find the solution, don't we get the same tableau? (Thinking)