1
$\begingroup$

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

enter image description here

The initial tableau is the following:

enter image description here

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – callculus Jan 4 '16 at 15:32
  • $\begingroup$ @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? $\endgroup$ – Evinda Jan 4 '16 at 15:49
  • $\begingroup$ 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. $\endgroup$ – callculus Jan 4 '16 at 16:20
  • $\begingroup$ If we have equalities we don't have to introduce artificial variables. So why do we have to indruce one in this case? @callculus $\endgroup$ – Evinda Jan 4 '16 at 16:56
  • $\begingroup$ That is not true. See here: www3.nd.edu/~dgalvin1/30210/30210_F07/presentations/… $\endgroup$ – callculus Jan 4 '16 at 17:28
1
$\begingroup$

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}

a degenerate LPP

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Evinda Jan 9 '16 at 13:03
  • $\begingroup$ @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$. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 9 '16 at 16:17
  • $\begingroup$ 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}$. $\endgroup$ – Evinda Jan 9 '16 at 16:26
  • $\begingroup$ 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? $\endgroup$ – Evinda Jan 9 '16 at 16:29
  • $\begingroup$ @Evinda Yes, your tableau is correct. I'm going to edit my answer again and explain why "replacing $\epsilon$ by $0$" is pointless. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 9 '16 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.