\pdfpagewidth=8.5truein  \pdfpageheight=11truein
\hsize=6truein  \vsize=9truein
\pdfhorigin=1.25truein  \pdfvorigin=1truein

\headline={\hfil}  \footline={\hfil}

\def\[{[\thinspace}  \def\]{\thinspace]}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf Another interpretation of duality}

\medskip

\noindent(Based on an example in Chapter~5 of {\it Linear Programming:
Foundations and Extensions}, third edition, by Robert~J. Vanderbei.)

\medskip

\noindent Consider the following maximization problem:
$$\eqalign{
	{\rm maximize}\quad8x_1+5x_2+6x_3&\cr
	{\rm subject\ to}\quad\phantom1x_1+\phantom1x_2+\phantom1x_3&\le8\qquad{\it(1)}\cr
	4x_1+2x_2-\phantom1x_3&\le7\qquad{\it(2)}\cr
	x_1,\,x_2,\,x_3&\ge0.\cr
}$$
Let $z^*$ denote the optimal value of the objective function in this
maximization problem. We would like to determine upper and lower bounds
for~$z^*$.

Finding lower bounds is easy: every feasible solution demonstrates a lower
bound for~$z^*$. For example, the feasible solution $x_1=1$,~$x_2=2$,~$x_3=3$
yields an objective value of $8(1)+5(2)+6(3)=36$, so we know that $z^*\ge36$.
If we choose a different feasible solution, we can get another lower bound
for~$z^*$. For instance, the feasible solution $x_1=0$,~$x_2=5$,~$x_3=3$ yields
an objective value of $8(0)+5(5)+6(3)=43$, so we can now conclude that
$z^*\ge43$.

However, finding lower bounds this way is like trying to solve the maximization
problem by trial and error. A better method is to use the simplex algorithm to
solve the maximization problem. The simplex algorithm produces the optimal
solution $x_1=3$,~$x_2=0$,~$x_3=5$, with an objective value of
$8(3)+5(0)+6(5)=54$. This feasible solution demonstrates that $z^*\ge54$.

In fact we know that the simplex algorithm produces {\it optimal\/} solutions,
so we know that $z^*$ actually {\it equals\/}~54. But how could we prove this
to someone who doesn't know about the simplex algorithm, who doesn't believe
that the simplex algorithm always produces the optimal solution, or who doesn't
want to check all the work that was done in the simplex algorithm? For this we
need upper bounds for~$z^*$.

Upper bounds for~$z^*$ come from linear combinations of the constraints in the
maximization problem. For example, we can multiply constraint~({\it1\/}) by~8
and constraint~({\it2\/}) by~2 and add them together to get the following
inequality:
$$\eqalign{
	8(\phantom{01}x_1+\phantom{01}x_2+\phantom1x_3)&\le8(8)\cr
	{}+2(\phantom04x_1+\phantom02x_2-\phantom1x_3)&\le2(7)\cr
\noalign{\hrule}
	16x_1+12x_2+6x_3\phantom)&\le78.\cr
}$$
Since all of the variables $x_1$,~$x_2$, and~$x_3$ are nonnegative, and each of
the coefficients in $16x_1+12x_2+6x_3$ is at least as large as the
corresponding coefficient in the objective function $8x_1+5x_2+6x_3$, this
demonstrates that $z^*\le78$:
$$z=8x_1+5x_2+6x_3\le16x_1+12x_2+6x_3\le78.$$
The inequality $16x_1+12x_2+6x_3\le78$ is a direct consequence of the
constraints of the maximization problem, and we could show this inequality to a
skeptic (by providing the multipliers 8~and~2) in order to prove that the
objective value can be no greater than~78.

But can we do better? We can find other linear combinations of the constraints
by trying other multipliers, and as long as the coefficients of the inequality
we get are at least as large as the corresponding coefficients in the objective
function, we will get an upper bound for~$z^*$. Finding upper bounds this way,
though, is again a trial-and-error process; we would like to be more
methodical.

So let's assign variable names to the multipliers we use. We'll multiply
constraint~({\it1\/}) by~$y_1$ and multiply constraint~({\it2\/}) by~$y_2$
to get the following inequality:
$$\eqalign{
	y_1(\phantom{(y_1+4y_2)}x_1+\phantom{(y_1+2y_2)}x_2+\phantom{(y_1-y_2)}x_3)&\le y_1(8)\cr
	{}+y_2(\phantom{(y_1+4y_2)}\llap4x_1+\phantom{(y_1+2y_2)}\llap2x_2-\phantom{(y_1-y_2)}x_3)&\le y_2(7)\cr
\noalign{\hrule}
	(y_1+4y_2)x_1+(y_1+2y_2)x_2+(y_1-y_2)x_3\phantom)&\le8y_1+7y_2\rlap.\cr
}$$
This will give us an upper bound for~$z^*$ as long as the coefficients in this
new inequality are at least as large as the corresponding coefficients in the
objective function; so we need
$$\eqalign{
	y_1+4y_2&\ge8,\cr
	y_1+2y_2&\ge5,\cr
	y_1-\phantom1y_2&\ge6.\cr
}$$
We also need $y_1\ge0$,~$y_2\ge0$ so that when we multiply the constraints by
these values we don't flip the direction of the inequality.

If these conditions are satisfied, then we can conclude that
$$z^*\le8y_1+7y_2.$$
To make this upper bound as good as possible, we want to {\it minimize\/} the
value of $8y_1+7y_2$. This gives us the following minimization problem:
$$\eqalign{
	{\rm minimize}\quad8y_1+7y_2&\cr
	{\rm subject\ to}\quad\phantom1y_1+4y_2&\ge8\cr
	y_1+2y_2&\ge5\cr
	y_1-\phantom1y_2&\ge6\cr
	y_1,\,y_2&\ge0.\cr
}$$
This minimization problem is the {\it dual\/} of the original maximization
problem.

If we solve this minimization problem, we get the optimal solution
$y_1=6.4$,~$y_2=0.4$. Using these multipliers for the constraints of the
original maximization problem, we obtain the inequality
$$\eqalign{
	6.4(\phantom{01}x_1+\phantom{01.}x_2+\phantom1x_3)&\le6.4(8)\cr
	{}+0.4(\phantom04x_1+\phantom{0.}2x_2-\phantom1x_3)&\le0.4(7)\cr
\noalign{\hrule}
	8x_1+7.2x_2+6x_3\phantom)&\le54.\cr
}$$
This proves that the optimal value of the objective function of the
maximization problem can be no greater than~54, because
$$z=8x_1+5x_2+6x_3\le8x_1+7.2x_2+6x_3\le54.$$
Together with the feasible solution $x_1=3$,~$x_2=0$,~$x_3=5$ that actually
gives us an objective value of~54, this provides a proof that the optimal value
of the original maximization problem is indeed~54.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
