# Wrong optimal solution

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

The initial tableau is the following:

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}$

Any of $P_3, P_4, P_5$ we choose the solution that we will get will be non-degenerate, right?

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?

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?

But the optimal solution should be equal to $-7$. Are the values of one of the tableaus wrong?

EDIT: 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?

• The solution $x_1=7$ and $x_4=4$ looks right. Therefore $z^*=-7$. You are finish with the simplex algorithm if all $c_j\geq 0$. But at the simplex algorithm you usually introduce an artificial variable if you have an equality as a constraint. Thus $a_1,a_2$ and $a_3$ are missing. – callculus Jan 4 '16 at 15:32
• @callculus Could you explain it further to me? Why do we have to introduce an artificial variable in this case where we just have equalities? – Evinda Jan 4 '16 at 15:49
• If you apply the simplex algorithm you always introduce a artificial variable for every $=$- and $\geq$-constraint. This is the algorithm. In the case of a $\geq$-constraint you additional have a negative slack variable. – callculus Jan 4 '16 at 16:20
• If we have equalities we don't have to introduce artificial variables. So why do we have to indruce one in this case? @callculus – Evinda Jan 4 '16 at 16:56
• That is not true. See here: www3.nd.edu/~dgalvin1/30210/30210_F07/presentations/… – callculus Jan 4 '16 at 17:28

Staring form the tableau with basis $P_3,P_2,P_4$, some entries are incorrect. In the tableau with basis $P_3,P_2,P_4$, the entry at column $P_1$ row $P_2$ should be $\frac23$ instead of $0$.

You may verify the GNU Octave code online.

format rat;
c = [-1 2 -3 0 0 0]'; b = [11 0 8]';
A = [
1 -.5 1 1 0 0;
0 2 -1 0 1 0;
0 0 0 2 0 1];
basis = [3 2 6]; B = A(:,basis); cB = c(basis);
T = [B\b B\A; 0 cB'*(B\A)-c']
T =

44/3        4/3          0          1        4/3        1/3          0
22/3        2/3          1          0        2/3        2/3          0
8          0          0          0          2          0          1
0       -5/3          0          0       -8/3        1/3          0
basis = [3 2 4]; B = A(:,basis); cB = c(basis);
T = [B\b B\A; 0 cB'*(B\A)-c']
T =

28/3        4/3          0          1          0        1/3       -2/3
14/3        2/3          1          0          0        2/3       -1/3
4          0          0          0          1          0        1/2
0       -5/3          0          0          0        1/3        4/3
basis = [1 2 4]; B = A(:,basis); cB = c(basis);
T = [B\b B\A; 0 cB'*(B\A)-c']
T =

7          1          0        3/4          0        1/4       -1/2
0          0          1       -1/2          0        1/2          0
4          0          0          0          1          0        1/2
0          0          0        5/4          0        3/4        1/2


Thererfore, the optimal solution is $(7,0,0,4,0,0)^T$, with an optimal value of $-7+2(0)-3(0) = -7$.

The degeneracy of the BFS and its optimality are two different things. Let me use an adapted example in another question to illustrate this.

$\max y$ subject to

\begin{align} \color{blue}{x+y}&\le\color{blue}{1}\\ \color{red}x\phantom{+y}&\le\color{red}1\\ x,y&\ge0 \end{align}

Obviously, exactly one of the blue and red constraints is redundant, so this LPP has degenerate solution.

We transform it to the standard form by adding slack variable $\color{blue}{s_1}, \color{red}{s_2}$.

$\max x$ subject to

\begin{align} \color{blue}{x+y+s_1\phantom{+s_2}}&=\color{blue}{1}\\ \color{red}{x\phantom{+y+s_1}+s_2}&=\color{red}1\\ x,y,\color{blue}{s_1},\color{red}{s_2}&\ge0 \end{align}

Thus, each of $x=0,y=0,\color{blue}{s_1=0},\color{red}{s_2=0}$ corresponds to a line which bounds the feasible region. If we choose $x,y$ as basic variables, then the basic solution is $x_B=(x,y)=(1,0)$, and we calculate the simplex tableau at this degenerate point.

format rat;
c = [0 1 0 0]'; b = [1 1]'; A = [1 1 1 0; 1 0 0 1];
basis = [1 2]; B = A(:,basis); cB = c(basis);
T = [B\b B\A; cB'*(B\b) cB'*(B\A) - c']
T =

1          1          0          0          1
-0         -0          1          1         -1
0          0          0          1         -1


Therefore, the simplex tableau is

\begin{array}{c|r|rrrr|r} B & b & x & y & s_1 & s_2 & \theta \\ \hline x & 1 & 1 & 0 & 0 & 1^* & 1 \\ y & 0 & 0 & 1 & 1 & -1 & - \\ \hline z & 0 & 0 & 0 & 1 & -1 & \end{array}

We are not trapped in the degenerate solution. Therefore, $x$ leaves the basis and $\color{red}{s_2}$ enters the basis.

basis = [4 2]; B = A(:,basis); cB = c(basis);
T = [B\b B\A; cB'*(B\b) cB'*(B\A) - c']
T =

1          1          0          0          1
1          1          1          1          0
1          1          0          1          0


Therefore, the simplex tableau is

\begin{array}{c|r|rrrr|r} B & b & x & y & s_1 & s_2 & \theta \\ \hline s_2 & 1 & 1 & 0 & 0 & 1 & - \\ y & 1 & 1 & 1 & 1 & 0 & - \\ \hline z & 1 & 1 & 0 & 1 & 0 & \end{array}

I don't think that "replacing $0$ of the basic variable by $\epsilon > 0$" is meaningful.

Suppose that "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 can't be improved". Then congratulations, you have found the optimal degenerate solution, if you aren't trapped in a cycle with negative entries on the last row.

I'll now demonstrate "turning the degenerate solution to non-degenerate, replacing $0$ of the basic variable by $\epsilon>0$".

We have this simplex tableau.

\begin{equation*} \begin{array}{c|r|r|rr|r} B & c_B & b & P_1 & P_j & \theta \\ \hline P_1 & * & 0 & \cdots & x_{1j} (> 0) & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \hline & z & \star & \cdots & z_j - c_j & \end{array} \end{equation*}

Replace $0$ by $\epsilon$.

\begin{equation*} \begin{array}{c|r|r|rr|r} B & c_B & b & P_1 & P_j & \theta \\ \hline P_1 & * & \epsilon & \cdots & x_{1j} (> 0) & \epsilon/x_{1j} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \hline & z & \star & \cdots & z_j - c_j & \end{array} \end{equation*}

Therefore, the new objective function value is

\begin{equation*} z' = \star - \frac{z_j - c_j}{x_{1j}} \epsilon. \end{equation*}

If $z_j - c_j < 0$, you've improved the objective function value by $\dfrac{c_j - z_j}{x_{1j}} \color{red}{\epsilon}$, and you still have an arbitrarily small number $\epsilon/x_{1j}$ in the first row. Therefore, I don't understand what's the point of replacing $0$ by $\epsilon$.

• Is it necessary to replace $0$ of the basic variable by $\epsilon>0$ ?  Also I get other values of $z_0-c_0$. At the last tableau, I get it equal to $-7$ and at the other previous one $-\frac{56}{3}$. Am I wrong? – Evinda Jan 9 '16 at 13:03
• @Evinda I'm editing my answer. <del>Which one are you referring to? Where you do get $-\frac{56}{3}$?</del> You're right for the values of $z_0 - c_0 = c_B x_B$, which can be calculated by cB'*(B\b). Btw, I don't understand the point of "replacing $0$ of the basic variable by $\epsilon > 0$. – GNUSupporter 8964民主女神 地下教會 Jan 9 '16 at 16:17
• The last tableau that I got is this one: $\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}$  and the previous tableau at the last row where -7 is, I had found $-\frac{56}{3}$. – Evinda Jan 9 '16 at 16:26
• According to the textbook, we can replace at the intitial solution $(11,0,0,0,0,8)$ , the $0$ that corresponds to $x_5$ by $\epsilon$ and then apply the simplex method. Then at the last tableau we replace $\epsilon$ by $0$ and get the solution. But this isn't necessary, isn't it? – Evinda Jan 9 '16 at 16:29
• @Evinda Yes, your tableau is correct. I'm going to edit my answer again and explain why "replacing $\epsilon$ by $0$" is pointless. – GNUSupporter 8964民主女神 地下教會 Jan 9 '16 at 16:33