Wrong optimal solution

Question

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?

Answer 1

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