3
$\begingroup$

The question is:

Maximize $x_1 − 2x_2 − 3x_3 − x_4$ subject to the constraints $x_j ≥ 0$ for all $j$ and

\begin{align} x_1 − x_2 − 2x_3 − x_4 \le& 4 \\ 2x_1 + x_3 − 4x_4 \le& 2 \\ −2x_1 + x_2 + x_4 \le& 1. \end{align}

Adding slack variables I get:

\begin{align} x_1 − x_2 − 2x_3 − x_4 + s_1 + 0s_2 + 0s_3 =& 4 \\ 2x_1 + 0x_2 + x_3 − 4x_4 + 0s_1 +s_2 + 0s_3 =& 2 \\ −2x_1 + x_2 + 0x_3 + x_4 + 0s_1 + 0s_2 + s_3 =& 1. \end{align}

Doing out my table I get:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline BASES&x_1&x_2&x_3&x_4&s_1&s_2&s_3&RHS \\ \hline &1&-2&-3&-1&0&0&0&0\\ \hline s_1&1&-1&-2&-1&1&0&0&4\\ \hline s_2&2&0&1&-4&0&1&0&2\\ \hline s_3&-2&1&0&1&0&0&1&1\\ \hline \end{array}

I choose to swap bases $x_1$ and $s_2$ since $x_1$ takes on the greatest coefficient in the objective function and $s_2$ basis row takes on the smallest non-negative ratio between RHS and and $x_1$. I get:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline BASES&x_1&x_2&x_3&x_4&s_1&s_2&s_3&RHS \\ \hline &0&2&\frac{7}{2}&-1&0&\frac{1}{2}&0&1\\ \hline s_1&0&1&\frac{5}{2}&-1&-1&\frac{1}{2}&0&-3\\ \hline x_1&1&0&\frac{1}{2}&-2&0&\frac{1}{2}&0&1\\ \hline s_3&0&1&1&-3&0&1&1&3\\ \hline \end{array}

Now $x_3$ holds the greatest coefficient and $x_1$ the smallest ratio since $1/\frac{1}{2} = 2 < 3$

Swapping those we get

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline BASES&x_1&x_2&x_3&x_4&s_1&s_2&s_3&RHS \\ \hline &7&-2&0&-13&0&3&0&6\\ \hline s_1&5&-1&0&-9&1&2&0&13\\ \hline x_3&2&0&1&-4&0&1&0&2\\ \hline s_3&-2&1&0&1&0&0&1&1\\ \hline \end{array}

Now we choose to swap $x_1$ in for the basis of $x_3$ since $x_1=7$ holds the largest value and $\frac{2}{2} = 1$ holds the smallest ratio.

From here we just keep swapping $x_1$ and $x_3$ indefinitely and the coefficients of the objective function never reach all-negative values.

Yet this seems to have a solution on linear programming calculators, so I must be doing something wrong. Does anyone know what?

$\endgroup$
1
$\begingroup$

Here's some errors in the OP's steps.

  1. In the initial tableau, at the row representing the objective function $z = x_1 − 2x_2 − 3x_3 − x_4$ (a.k.a. $z$-row), always change the sign of coefficients \begin{array}{|r|r|r|r|r|r|r|r|r|r|} \hline \text{bases} &x_1&x_2&x_3&x_4&s_1&s_2&s_3& \text{RHS} \\ \hline &\bf-1&\bf2&\bf3&\bf1&0&0&0&0\\ \hline s_1&1&-1&-2&-1&1&0&0&4\\ \hline s_2&2&0&1&-4&0&1&0&2\\ \hline s_3&-2&1&0&1&0&0&1&1\\ \hline \end{array} because
    • $z -(x_1 - 2x_2 - 3x_3 - x_4) = 0$ (To understand the row of the rightmost 0, you may think about $A {\bf x} + I_3 {\bf s} = {\bf b}$ on RHS.) \begin{array}{|r|r|r|r|r|r|r|r|r|r|r|} \hline \text{bases} &z&x_1&x_2&x_3&x_4&s_1&s_2&s_3& \text{RHS} \\ \hline &\bf1&\bf-1&\bf2&\bf3&\bf1&0&0&0&0\\ \hline s_1&\bf0&1&-1&-2&-1&1&0&0&4\\ \hline s_2&\bf0&2&0&1&-4&0&1&0&2\\ \hline s_3&\bf0&-2&1&0&1&0&0&1&1\\ \hline \end{array}
    • the coefficient of $z$ is always one, and it's never changed, so it's omitted (to save ink).
  2. Choose only negative elements in the $z$-row.
    • Think of $z$ as an affine function of $x_1,\dots,x_4$. In $z = x_1 − 2x_2 − 3x_3 − x_4$, it's natural to increase $x_1$ in order to maximize $z$.
    • This corresponds to choosing a negative entry at the $z$-row in the simplex tableau. (We often choose the most negative one.) \begin{array}{|r|r|r|r|r|r|r|r|r|r|} \hline \text{bases} &x_1&x_2&x_3&x_4&s_1&s_2&s_3& \text{RHS} \\ \hline &\bf-1&2&3&1&0&0&0&0\\ \hline s_1&1&-1&-2&-1&1&0&0&4\\ \hline s_2&\bf2^*&0&1&-4&0&1&0&\bf2\\ \hline s_3&-2&1&0&1&0&0&1&1\\ \hline \end{array}
    • In this case, we replace $s_2$ with $x_1$. (Denote this as $\{s_1,s_2,s_3\}\to\{s_1,x_1,s_3\}$ for short.)
  3. As the RHS of a simplex tableau represents the current basic feasible solution (BFS, denoted as $\bf x_B$), it can never take a negative value. (OP's second tableau row $s_1$ should be multiplied by -1.) \begin{array}{|r|r|r|r|r|r|r|r|r|r|} \hline \text{bases} &x_1&x_2&x_3&x_4&s_1&s_2&s_3& \text{RHS} \\ \hline &0&2&\frac{7}{2}&-1&0&\frac{1}{2}&0&1\\ \hline s_1&0&-1&-\frac{5}{2}&1^*&1&-\frac{1}{2}&0&\bf3\\ \hline x_1&1&0&\frac{1}{2}&-2&0&\frac{1}{2}&0&1\\ \hline s_3&0&1&1&-3&0&1&1&3\\ \hline \end{array}
  4. At the $z$-row in the above tableau, the only negative entry -1 under $x_4$ is chosen, as well as the only positive entry 1 in the $x_4$ column. Do a pivot operation at the entry marked with *. \begin{array}{|r|r|r|r|r|r|r|r|r|r|} \hline \text{bases} & x_1 & x_2 & x_3 & x_4 & s_1 & s_2 & s_3 & \text{RHS} \\ \hline & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 4 \\ \hline x_4 & 0 & -1 & -\frac52 & 1 & 1 & -\frac12 & 0 & 3 \\ \hline x_1 & 1 & -2 & -\frac92 & 0 & 2 & -\frac12 & 0 & 7 \\ \hline s_3 & 0 & -2 & -\frac{13}{2} & 0 & 3 & -\frac12 & 1 & 12 \\ \hline \end{array} Since every entry in the $z$-row is non-negative, we've done.

Hence, the optimal solution is $(x_1,x_2,x_3,x_4) = (7,0,0,3)$ with optimal value 4.

$\endgroup$
  • 1
    $\begingroup$ Very nice explanation, thanks! $\endgroup$ – Gregory Peck Feb 17 '17 at 21:32

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.