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$
10
  • $\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 14:38

1 Answer 1

Reset to default
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$
25
  • $\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, 2016 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, 2016 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, 2016 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, 2016 at 6:44
  • $\begingroup$ I edited my post. Could you take a look at it? $\endgroup$
    – Evinda
    Jan 7, 2016 at 22:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .