Skip to main content
$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.4: Pablo Meets Dantzig

[ "article:topic", "authortag:waldron", "authorname:waldron" ]

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Oftentimes, it takes a few tricks to bring a given problem into the standard form of example 38. In Pablo's case, this goes as follows.

Example 41

Pablo's variables $$x$$ and $$y$$ do not obey $$x_i\geq 0$$. Therefore define new variables

$$x_1=x-5\, , \quad x_2=y-7\, .$$

The conditions on the fruit $$15\leq x+y\leq 25$$ are inequalities,

$$x_1+x_2\geq 3\, ,\quad x_1+x_2\leq 13\, ,$$
so are not of the form $$Mx = v$$. To achieve this we introduce two new positive variables $$x_3\geq0$$, $$x_4\geq 4$$ and write

$$c_1:=x_1+x_2-x_3=3\, ,\quad c_2:=x_1 + x_2 + x_4=13\, .$$

These are called $$\textit {slack variables}$$ because they take up the "slack'' required to convert inequality to equality. This pair of equations can now be written as $$Mx=v$$,

$$\begin{pmatrix} 1 &1&\!\!-1&0\\ 1&1&0&1 \end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\\x_4\end{pmatrix}= \begin{pmatrix}3\\\!13\end{pmatrix}\, .$$

Finally, Pablo wants to minimize sugar $$s=5x+10y$$, but the standard problem maximizes $$f$$. Thus the so-called $$\textit {objective function}$$ $$f=-s+95=-5x_1-10x_2$$. (Notice that it makes no difference whether we maximize $$-s$$ or $$-s+95$$, we choose the latter since it is a linear function of $$(x_1,x_2)$$.) Now we can build an augmented matrix whose last row reflects the objective function equation $$5 x_1+10 x_2 +f=0$$:

$$\left(\begin{array}{rrrrr|r} 1&1&-1&0&0&3\\ 1&1&0&1&0&13\\\hline 5&10&\ 0&0&1&0 \end{array}\right)\, .$$

Here it seems that the simplex algorithm already terminates because the last row only has positive coefficients, so that setting $$x_1=0=x_2$$ would be optimal. However, this does not solve the constraints (for positive values of the slack variables $$x_3$$ and $$x_4$$). Thus one more (very dirty) trick is needed. We add two more, positive, (so-called) $$\textit {artificial variables}$$ $$x_5$$ and $$x_6$$ to the problem which we use to shift each constraint

$$c_1\to c_1-x_5\, ,\qquad c_2\to c_2-x_6\, .$$

The idea being that for large positive $$\alpha$$, the modified objective function $$f-\alpha x_5 - \alpha x_6$$ is only maximal when the artificial variables vanish so the underlying problem is unchanged. Lets take $$\alpha=10$$ (our solution will not depend on this choice) so that our augmented matrix reads

\begin{eqnarray*}&&
\left(\begin{array}{rrrrrrr|r}
1&1&-1&0&1&0&0&3\\
1&1&0&1&0&1&0&13\\\hline
5&10&\ 0&0&10&10&1&0
\end{array}\right)\\
&\stackrel{\small R_3'=R_3-10 R_1-10R_2 }\sim&
\left(\begin{array}{rrrrrrr|r}
1&1&-1&0&1&0&0&3\\
1&1&0&1&0&1&0&13\\\hline
\!-15&-10&\ 10&-10&0&0&1&-160
\end{array}\right)
\, .
\end{eqnarray*}

Here we performed one row operation to zero out the coefficients of the artificial variables. Now we are ready to run the simplex algorithm exactly as in section 3.3. The first row operation uses the $$1$$ in the top of the first column to zero out the most negative entry in the last row:

\begin{eqnarray*}&&
\left(\begin{array}{rrrrrrr|r}
1&1&-1&0&1&0&0&3\\
1&1&0&1&0&1&0&13\\\hline
0&5&-5&-10&15&0&1&-115
\end{array}\right)\\
&\stackrel{\small R_2'=R_2-R_1}\sim&
\left(\begin{array}{rrrrrrr|r}
1&1&1&0&1&0&0&3\\
0&0&1&1&-1&1&0&10\\\hline
0&5&-5&-10&15&0&1&-115
\end{array}\right)\\
&\stackrel{\small R_3'=R_3+10R_2}\sim&
\left(\begin{array}{rrrrrrr|r}
1&1&1&0&1&0&0&3\\
0&0&1&1&-1&1&0&10\\\hline
0&5&5&0&5&10&1&-15
\end{array}\right)
\, .
\end{eqnarray*}

Now the variables $$(x_2,x_3,x_5,x_6)$$ have zero coefficients so must be set to zero to maximize $$f$$. The optimum value is $$f=-15$$ so $$s=-f-95=110$$ exactly as before. Finally, to solve the constraints $$x_1=3$$ and $$x_4=10$$ so that $$x=8$$ and $$y=7$$ which also agrees with our previous result.

Clearly, performed by hand, the simplex algorithm was slow and complex for Pablo's problem. However, the key point is that it is an algorithm that can be fed to a computer. For problems with many variables, this method is much faster than simply checking all vertices as we did in section 3.2.