3
$\begingroup$

I want to solve the following linear programming problem:

$$\min (5y_1-10y_2+7y_3-3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ -2y_1-y_2+3y_3+3y_4=2 \\ 2y_1+2y_2+8y_3+y_4=4 \\ y_i \geq 0, i \in \{ 1, \dots, 4 \}$$

$\begin{bmatrix} 1 & 1 & 7 & 2 & | & 3\\ -2 & -1 & 3 & 3 & | & 2\\ 2 & 2 & 8 & 1 & | & 4 \end{bmatrix} \to \begin{bmatrix} 1 & 1 & 7 & 2 & | & 3\\ 0 & 1 & 17 & 7 & | & 8\\ 0 & 0 & 6 & 3 & | & 2 \end{bmatrix}$

So the problem is written equivalently as follows:

$$-\max (-5y_1+10y_2-7y_3+3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ y_2+17y_3+7y_4=8 \\ 6y_3+3y_4=2 \\ y_i \geq 0, i \in \{ 1, \dots, 4 \}$$

But we want the $3 \times 3$ identity matrix to appear at the matrix that represents the linear programming problem, right?

So we solve the following problem, right?

$$-\max (-5y_1+10y_2-7y_3+3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ y_2+17y_3+7y_4+y_5=8 \\ 6y_3+3y_4+y_6=2 \\ y_i \geq 0, i \in \{ 1, \dots,6 \}$$

Then:

$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_5 & \theta & \\ P_1 & -5 & 3 & 1 & 1 & 7 & 2 & 0 & 0 & \frac{3}{7} &L_1 \\ P_5 & 0 & 8 & 0 & 1 & 17 & 7 & 1 & 0 & \frac{8}{17} & L_2\\ P_6 & 0 & 2 & 0 & 0 & 6 & 3 & 0 &1 & \frac{1}{3} &L_3 \\ & z & 0 & -5 & 10 & -7 & 3 & 0 & 0 & & L_4 \end{matrix}$

$|-7|> |-5|$ so $P_3$ gets in the basis and $P_6$ gets out of the basis.

Then we get the following tableau:

$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_5 & \theta & \\ P_1 & -5 & \frac{2}{3} & 1 & 1 & 0 & -\frac{3}{2} & 0 & -\frac{7}{6} & &L_1'=L_1-7L_3' \\ P_5 & 0 & \frac{7}{3} & 0 & 1 & 0 & -\frac{3}{2} & 1 & -\frac{17}{6} & & L_2'=L_2-17L_3'\\ P_3 & -7 & \frac{1}{3} & 0 & 0 & 1 & \frac{1}{2} & 0 &\frac{1}{6} & &L_3'=\frac{L_3}{6} \\ & z & \frac{7}{3} & -5 & 10 & 0 & \frac{13}{2} & 0 & \frac76 & & L_4'=L_4+7L_3' \end{matrix}$

Have I maybe done something wrong? Because from the last tableau we get that $P_1$ gets out of the basis and $P_1$ gets in the basis...

EDIT: We could introduce the artificial variables as follows:

$$- \max (-5x_1+10x_2-7x_3+3x_4) \\ x_1+x_2+7x_3+2x_4+x_5=3 \\ -2x_1-x_2+3x_3+3x_4+x_6=2 \\ 2x_1+2x_2+8x_3+x_4+x_7=4 \\ x_i \geq 0, i=1,2, \dots, 7$$

At the first phase, we solve the linear programming problem $\min (x_5+x_6+x_7)$ under the new restrictions and at the second phase the initial problem, for which we will have found from the first phase a basic feasible solution.

The problem of the first phase can be written as follows:

$$ -\max (-x_5-x_6-x_7) \\ x_1+x_2+7x_3+2x_4+x_5=3 \\ -2x_1-x_2+3x_3+3x_4+x_6=2 \\ 2x_1+2x_2+8x_3+x_4+x_7=4 \\ x_i \geq 0, i=1,2, \dots, 7$$

Then I thought the simplex tableau would be the following:

$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\ P_5 & -1 & 3 & 1 & 1 & 7 & 2 & 1 & 0 & 0 & & L_1\\ P_6 & -1 & 2 & -2 & -1 & 3 & 3 & 0 & 1 & 0 & & L_2\\ P_7 & -1 & 4 & 2 & 2 & 8 & 1 & 0 & 0 & 1 & & L_3\\ & z & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & & L_4 \end{matrix}$

But I found that it is this one:

enter image description here

How do we find the $z_k-c_k$- values?

EDIT 2: I get the following tableaus:

$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\ P_1 & -1 & 3 & 1& 1&7 & 2 & 1 & 0 & 0 & \frac{3}{7} & L_1 \\ P_5 & -1 & 2 & -2 & -1 & 3 & 3 & 0& 1 & 0 &\frac{2}{3} &L_2\\ P_6 & -1 & 4 & 2 & 2 & 8 & 1 & 0 & 0 & 1 &\frac12 &L_3\\ & z & -9& -1 & -2 & -18 & -6& 0& 0 & 0 & & \end{matrix}$

$$$$

$ \begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\ P_3 & 0 & \frac{3}{7} & \frac{1}{7}& \frac{1}{7}&1 & \frac{2}{7}& \frac{1}{7} & 0 & 0 & \frac{3}{2} & L_1'=\frac{L_1}{7} \\ P_6 & -1 & \frac{11}{7} & \frac{-17}{7} & -\frac{10}{7} & 0 & \frac{15}{7} & -\frac{3}{7}& 1 & 0 &\frac{11}{15} &L_2'=L_2-3L_1'\\ P_7 & -1 & \frac{4}{7} & \frac{6}{7} & \frac{6}{7} & 0 & -\frac{9}{7} & -\frac{8}{7} & 0 & 1 &- &L_3'=L_3-8L_1'\\ & z & \frac{-9}{7}& \frac{11}{7} & \frac{4}{7} & 0 & \frac{-6}{7}& \frac{18}{17}& 0 & 0 & & L_4'=L_4+18 L_1' \end{matrix}$

$ \begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\ P_3 & 0 & \frac{23}{105} & \frac{7}{15}& \frac{1}{3}&1 & 0& \frac{1}{5} & -\frac{2}{15} & 0 & & L_1''=L_1'-\frac{2}{7}L_2'' \\ P_4 & 0 & \frac{11}{15} & \frac{-17}{15} & -\frac{2}{3} & 0 & 1 & -\frac{1}{5}& \frac{7}{15} & 0 & &L_2''=\frac{7}{15} L_2'\\ P_7 & -1 & \frac{17}{5} & -\frac{123}{35} & 0 & 0 & 0 & -\frac{7}{15} & \frac{9}{15} & 1 & &L_3''=L_3'+\frac{9}{7}L_2''\\ & z & \frac{3}{5}& \frac{3}{5} & 0 & 0 & 0& \frac{12}{5}& \frac{6}{15} & 0 & & L_4''=L_4'+\frac{6}{7} L_2'' \end{matrix}$

$$$$

But according to my textbook it should be as follows:

enter image description here

Have I done something wrong at the calculations?

$\endgroup$
  • $\begingroup$ I think you can simplify matter by eliminating $y_1$ and $y_2$ first. (i.e. re-write the objective function in terms of $y_3$ and $y_4$). Then the optimal solution can be found easily. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 5 '16 at 13:47
  • $\begingroup$ @GNUSupporter So is the new form in which I have written the linear programming problem right, we just have to change the objective function? If so, how can we write it in therms of $y_3$ and $y_4$ ? $\endgroup$ – Evinda Jan 5 '16 at 14:03
  • 1
    $\begingroup$ Change $y_1+y_2+7y_3+2y_4=3$ to $y_1=3-(y_2+7y_3+2y_4)$, and substitute it to the objective function and the other constraints, and repeat this for $y_2$ and $y_3$, then only $y_4$ will be left. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 5 '16 at 14:26
  • $\begingroup$ @GNUSupporter A ok... You mean after having introduced the artificial variables? Or don't we have to introduce them? $\endgroup$ – Evinda Jan 5 '16 at 14:33
  • $\begingroup$ I guess you don't have to do so. Maybe I present you a quicker way to get the solution. Btw, in response to your question, the first tableau is not yet a simplex tableau because you have not yet make $z_1 - c_1$ zero. You need to replace $L_4$ by $5L_1 + L_4$ first. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 5 '16 at 14:38
4
$\begingroup$

The original minimization problem

\begin{align} \min z = 5y_1-10y_2+7y_3-3y_4 & \\ y_1+y_2+7y_3+2y_4 &= 3 \\ y_2+17y_3+7y_4 &= 8 \\ 6y_3+3y_4 &= 2 \\ y_i &\geq 0, i \in \{ 1, \dots, 4 \} \end{align}

We try to find a basic feasible solution to the original LPP by the two-phase method. Add the artificial variables $y_5,y_6 \ge 0$ into the LPP.

\begin{align} \min z = y_5+y_6 & \\ y_1+y_2+7y_3+2y_4 &= 3 \\ y_2+17y_3+7y_4+y_5 &= 8 \\ 6y_3+3y_4+y_6 &= 2 \\ y_i &\geq 0, i \in \{ 1, \dots, 6 \} \end{align}

We write the objective function as $z-y_5-y_6=0$. Since the coefficient of $z$ is always one, we omit it in the simplex tableaux to save ink.

\begin{equation*} \begin{array}{rrrrrrr|r} & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 & \\ \hline y_1 & 1 & 1 & 7 & 2 & 0 & 0 & 3 \\ y_5 & 0 & 1 & 17 & 7 & 1 & 0 & 8 \\ y_6 & 0 & 0 & 6 & 3 & 0 & 1 & 2 \\ \hline z & 0 & 0 & 0 & 0 & -1 & -1 & 0 \end{array} \end{equation*}

Make it a simplex tableau.

\begin{equation*} \begin{array}{rrrrrrr|r} & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 & \\ \hline y_1 & 1 & 1 & 7 & 2 & 0 & 0 & 3 \\ y_5 & 0 & 1 & 17 & 7 & 1 & 0 & 8 \\ y_6 & 0 & 0 & 6 & 3 & 0 & 1 & 2 \\ \hline z & 0 & 1 & 23 & 10 & 0 & 0 & 10 \end{array} \end{equation*}

Since it's minimization, we choose $y_j$ with the biggest $z_j - c_j$ as the entering variable.

\begin{equation*} \begin{array}{rrrrrrr|rr} & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 & & \theta \\ \hline y_1 & 1 & 1 & 7 & 2 & 0 & 0 & 3 & \frac{3}{7} \\ y_5 & 0 & 1 & 17 & 7 & 1 & 0 & 8 & \frac{8}{17} \\ y_6 & 0 & 0 & 6^* & 3 & 0 & 1 & 2 & \frac{1}{3} \\ \hline z & 0 & 1 & 23 & 10 & 0 & 0 & 10 & \end{array} \tag{*} \label{min} \end{equation*}

\begin{equation*} \begin{array}{rrrrrrr|rr} & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 & & \theta \\ \hline y_1 & 1 & 1^* & 0 & -\frac{3}{2} & 0 & -\frac{7}{6} & \frac{2}{3} & \frac{2}{3} \\ y_5 & 0 & 1 & 0 & -\frac{3}{2} & 1 & -\frac{17}{6} & \frac{7}{3} & \frac{7}{3} \\ y_3 & 0 & 0 & 1 & \frac{1}{2} & 0 & \frac{1}{6} & \frac{1}{3} & \\ \hline z & 0 & 1 & 0 & -\frac{3}{2} & 0 & -\frac{23}{6} & \frac{7}{3} & \end{array} \end{equation*}

Choose $y_2$ as the entering variable, $y_1$ as the leaving variable.

\begin{equation*} \begin{array}{rrrrrrr|r} & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 & \\ \hline y_2 & 1 & 1 & 0 & -\frac{3}{2} & 0 & -\frac{7}{6} & \frac{2}{3} \\ y_5 & -1 & 0 & 0 & 0 & 1 & -\frac{5}{3} & \frac{5}{3} \\ y_3 & 0 & 0 & 1 & \frac{1}{2} & 0 & \frac{1}{6} & \frac{1}{3} \\ \hline z & -1 & 0 & 0 & 0 & 0 & -\frac{8}{3} & \frac{5}{3} \end{array} \end{equation*}

Since we still have the artificial variable $y_5$ in the basis in the optimal tableau, we conclude that this problem is not feasible.

I tried phase one in GNU Octave. You may run the following code online.

A=[1 1 7 2 0 0; 0 1 17 7 1 0; 0 0 6 3 0 1];
b = [3 8 2]'; c=[0 0 0 0 1 1]';
[x_min z_min] = glpk(c,A,b,zeros(6,1),[],"SSS","CCCCCC")

Results

x_min =

   0.00000
   1.66667
   0.00000
   0.66667
   1.66667
   0.00000

z_min =  1.6667

I also tried directly solving the original LPP, and the program returned NA.

A = [1 1 7 2; -2 -1 3 3; 2 2 8 1]; b = [3 2 4]'; c = [5 -10 7 -3]';
[x_min,z_min] = glpk(c,A,b,zeros(4,1),[],"SSS","CCCC")

Result

glp_simplex: unable to recover undefined or non-optimal solution
x_min =

    NA
    NA
    NA
    NA

z_min = NA

To get $z_j - c_j$, you may simply calculate $c_B^T B^{-1} a_j$. For the derivation, you may see my answer for another question about the regeneration of optimal simplex tableau from the optimal BFS. To actually calculate this number, compute $c_B^T y_j$, where $y_j$ is the column for $P_j$ in the current simplex tableau. For example, in the given tableau, $c_B = (-1,-1,-1)^T$.

\begin{align} z_1 - c_1 &= (-1,-1,-1)(1,-2,2)^T = -1 \\ z_2 - c_2 &= (-1,-1,-1)(1,-1,2)^T = -2 \\ z_3 - c_3 &= (-1,-1,-1)(7,3,8)^T = -18 \text{, etc} \end{align}

We want the artificial variables $x_5,x_6,x_7 = 0$, so we $\min x_5 + x_6 + x_7$, which is equivalent to $\mathbf{\max -x_5 - x_6 - x_7}$ (what you see in your book). That's why you see $-9$ in the $z$-row, $b$-column in the given simplex tableau.

Question: In simplex tableau $\eqref{min}$, the entering variable has $z_j - c_j > 0$. This seems contradictory to what you've learnt.
Answer: See my answer another question for detailed explanation.

  • In a maximisation problem, the entering variable has $z_j - c_j \le 0$.
  • In a minimisation problem, the entering variable has $z_j - c_j \ge 0$.

\begin{array}{r|r|r|rrrrrrr|r|l} & & & 0 & 0 & 0 & 0 & -1 & -1 & -1 & & \\ \hline B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\ \hline \hline P_5 & -1 & 3 & 1 & 1 & 7 & 2 & 1 & 0 & 0 & & L_1 \\ P_6 & -1 & 2 & -2 & -1 & 3 & 3 & 0 & 1 & 0 & & L_2 \\ P_7 & -1 & 4 & 2 & 2 & 8 & 1 & 0 & 0 & 1 & & L_3 \\ \hline & z & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & & L_4 \\ \hline \hline P_5 & -1 & 3 & 1 & 1 & 7^* & 2 & 1 & 0 & 0 & 3/7^* & L_1' = L_1 \\ P_6 & -1 & 2 & -2 & -1 & 3 & 3 & 0 & 1 & 0 & 2/3 & L_2' = L_2 \\ P_7 & -1 & 4 & 2 & 2 & 8 & 1 & 0 & 0 & 1 & 4/8 & L_3' = L_3 \\ \hline & z & -9 & -1 & -2 & -18^* & -6 & 0 & 0 & 0 & & L_4' = -L_1 - L_2 - L_3 + L_4 \\ \hline \hline P_3 & 0 & 3/7 & 1/7 & 1/7 & 1 & 2/7 & 1/7 & 0 & 0 & 3/2 & L_1'' = \frac17 L_1' \\ P_6 & -1 & 5/7 & -17/7 & -10/7 & 0 & 15/7^* & -3/7 & 1 & 0 & 5/15^* & L_2'' = L_2' - \frac37 L_1' \\ P_7 & -1 & 4/7 & 6/7 & 6/7 & 0 & -9/7 & -8/7 & 0 & 1 & - & L_3'' = L_3' - \frac87 L_1' \\ \hline & z & -9/7 & 11/7 & 4/7 & 0 & -6/7^* & 18/7 & 0 & 0 & & L_4'' = L_4' + \frac{18}{7} L_1' \\ \hline \hline P_3 & 0 & 1/3 & 7/15 & 1/3 & 1 & 0 & 1/5 & -2/15 & 0 & & L_1''' = L_1'' - \frac{2}{15} L_2'' \\ P_4 & 0 & 1/3 & -17/15 & -2/3 & 0 & 1 & -1/5 & 7/15 & 0 & & L_2''' = \frac{7}{15} L_2'' \\ P_7 & -1 & 1 & -3/5 & 0 & 0 & 0 & -7/5 & 3/5 & 1 & & L_3''' = L_3'' + \frac{3}{5} L_2'' \\ \hline & z & -1 & 3/5 & 0 & 0 & 0 & 12/5 & 2/5 & 0 & & L_4''' = L_4'' + \frac{2}{5} L_2'' \end{array}

Since artificial variable $P_7$ is still in the basis, this LPP has no feasible solution.

$\endgroup$
  • $\begingroup$ To use the simplex method we firstly write the linear programming problem in its canonical form , so $\min z=y_5+y_6$ becommes $- \max (-z=-y_5-y_6)$. $$$$ $-1$ is the smallest value at the last row, so do deduce that $P_5$ gets in the basis and $P_6$ gets out of the basis. This can't be true. $$$$ Or am I wrong? $\endgroup$ – Evinda Jan 5 '16 at 23:48
  • $\begingroup$ @Evinda You may see the following table [my answer for another question][1] for a detailed description. \begin{array}{rr|l} & \text{a non-basic variable} & \text{RHS} \\ \hline \text{a basic variable} & \heartsuit > 0 & \spadesuit \ge 0 \\ \hline z & \clubsuit & \text{obj. fct. val.} \end{array} After each pivot operation, you have \begin{equation*} \text{new obj. fct. val.} = \text{obj. fct. val.} - \frac{\spadesuit\clubsuit}{\heartsuit} \end{equation*} [1]: math.stackexchange.com/a/1594962/290189 $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 6 '16 at 6:11
  • $\begingroup$ @Evinda "$-1$ is smallest, so $P_5$ gets out of the basis" is true when (1) we are doing a max-type LPP, and (2) it is a simplex tableau The problem is, in the first tableau of my answer, it is not a simplex tableau. The two $-1$ in the last row is in the column $P_5$ and $P_6$, which is in the basis. Therefore, to make it a simplex tableau, we do some row operations. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 6 '16 at 6:16
  • $\begingroup$ Directly using $\min z = y_5+y_6$ and remembering to choose the largest $z_j - c_j$ instead of converting it to a max-type and choosing the smallest $z_j - c_j$ LPP saves you one step. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 6 '16 at 6:44
  • $\begingroup$ I edited my post. Could you take a look at it? $\endgroup$ – Evinda Jan 7 '16 at 22:15

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.