%-----------------------------------------------------------------------
% Beginning of chap5.tex
%-----------------------------------------------------------------------
%
% AMS-LaTeX 1.2 sample file for a monograph, based on amsbook.cls.
% This is a data file input by chapter.tex.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\part{This is a Part Title Sample}
\chapter{Linear Programming}
Linear programming, like its nonlinear counterpart, is a method for
making decisions based on solving a mathematical optimization problem.
The general field of linear programming has been a major
area of applied mathematical research in the last 50 years. A combination
of new algorithms, e.g., the simplex method, and widely available computing
power now make this an indispensible tool for the mathematical modeler.
We begin our discussion of linear programming by presenting the
basic mathematical formulation and terminology in general terms. We will
follow this with a number of examples of problems that may be formulated
in terms of linear programs. Our goal here is to obtain an abstract
understanding of what a linear program is and to develop an intuition
that will assist the modeler in assessing whether linear programming
is the right tool for a given problem.
Consider a linear function of the variables $x = (x_1, \dots, x_n )$
$$f(x) = a_1x_1 +a_2x_2 +\cdots + a_n x_n$$
where the parameters $a_i$ are known. We seek to pick the values of
all the $x_i$, referred to as {\it decision variables},
so as to maximize $f(x)$ which is referred to as the {\it objective
function}. Clearly picking each $x_i = \infty$ (or even
just one) would provide a maximum, albeit meaningless. The interest arises when the
values of the $x_i$ are constrained, e.g.,
$$c_{11} x_1 + \cdots + c_{1n} x_n \le b_1$$
Based on the application many constraints are possible so we
write
$$c_{i1} x_1 + \cdots + c_{in} x_n \le b_i$$
for $i = 1, \dots, m$. Note that these constraints are also
linear in the decision variables.
We may interpret this system of constraints geometrically as defining a
region, i.e., a continuum of points such that all the constraints
are simultaneaously satisfied. This region is referred to as the
{\it feasible set} S. So now we may view the optimization problem as one
to find the maximum value of the objective function over the
feasible set S.
In summary, a linear programming problem is defined as
$$\max a^T x$$
subject to the constraints
$$(Cx)_i \le b_i$$
where
$(C)_{ij} = c_{ij}$.
\section{Examples of Linear Programs}
In this section we survey a variety of applications that fit exactly into
the formulation of the abstract linear program.
\subsection{Red or White?}
A winemaker would like to decide how many bottles of red wine and how many bottles
of white wine to produce. Given his expertise is in red wine making he can sell
a bottle of red wine for \$12 while he can only sell a bottle of white wine for
\$7. Clearly the winemaker would seek to maximize his profits, and, having recently
completed a course in mathematical modeling, proceeds to construct
the objective function
$$f(x_1, x_2) = 12 x_1 + 7 x_2$$
where the decision variables are the number of bottles of red wine
to produce $x_1$ and the number of bottles of white wine to produce, i.e.,
$x_2$.
Aging wine in wooden or glass-lined vats is an integral component of the production process but do to
limited space the wine must be aged for a limited time. The wine maker has
determined that red wine should be aged two years per bottle
and white wine one year per bottle and his facilities allow that each batch
is limited to 10,000 bottle-years (5 bottles of red and 3 bottles of white
require a total of 13 bottle years ripening time).
Thus the winemaker formulates a constraint
$$2x_1 +x_2 \le 10000$$
Also the volume of grapes that may be processed is limited and it takes 3 gallons
of grapes to make a bottle of red wine and two gallons of grapes to make a bottle
of white wine. Furthermore, the winery can only process a total of 16,000 gallons of
grapes for each batch. Thus, the winemaker produces the additional constraint
$$3x_1 + 2x_2 \le 16000$$
Now the winemaker would like to determine how many bottles of each wine to
produce as well as how much money he will expect to make. Note that we must also require that
negative bottles of wine are not allowed so
$$x_1 \ge 0$$
and
$$x_2 \ge 0$$
\subsection{How Many Fish?}
\label{fish}
A child with a new 29 gallon fish tank asks her daddy to put as many fish in the tank as
possible. Sensing that too many fish is not a good thing, the dad asks the pet shop owner
how many fish can go into a tank. The answer was more complex than anticipated. "You can
put one inch of fish in per gallon of water." The little girl then added that she wanted only the
big orange fish (Gouramis) and the small stripey fish (Zebra Dannios).
As the child seeks to maximize the total number of fish her objective function is
$$f(x_1, x_2) = x_1 + x_2$$
where $x_1$ is the number of Gouramis and $x_2$ is the number of Zebra Dannios.
Additionally, a full grown Gourami is two inches long while a Danio is just one inch long.
The constraint of not exceeding 29 inches of total fish length can now be written
$$2x_1 + x_2 \le 29$$
Danios are very active fish and actually require twice as much food as Gouramis. Each Dannio eats
4 grams/day of fish flakes while the slower Gourami eats 2 grams/day.
The dad decides that he would perfer not to go broke buying fish food and thus wants to
limit the tank to 50 grams/day. Thus, we have the constraint
$$2x_1 + 4x_2 \le 50$$
The pet shop owner adds, by the way, that Danios need to live in schools of at least 5 fish or
they don't do well. Thus
$$ x_2 \ge 5 $$
Additionaly, the little girl stipulates that she must have at least two Gouramis
as they are known to kiss (hence the term Kissing Gouramis) so we add
$$x_2 \ge 2$$
How many Gouramis and Dannios can the little girl have in her tank?
%\subsection{Bombs Away}
%Submarines versus destroyers.
%\subsection{Financial Advice}
\begin{figure}[tp!]
\centering
{\epsfig{file=rw_wine.eps,width=4.7in}}
\hfill
\caption{Geometric picture of the linear programming problem.}
\label{wine-LP}
\end{figure}
\section{Geometric Solution of a 2D Linear Program}
Let us now solve the winemaker's linear programming problem using graphical techniques.
Recalling the problem:
\begin{itemize}
\item Objective function: $f(x_1, x_2) = 12 x_1 + 7 x_2$
\item Constraint 1: $3x_1 + 2x_2 \le 16000$
\item Constraint 2: $2x_1 +x_2 \le 10000$
\item Constraint 3: $x_1 \ge 0$
\item Constraint 4: $x_2 \ge 0$
\end{itemize}
First, let us identify the feasible set. Again, this is the intersection
of all the regions defined by the constraints. (Note that this set is
independent of the objective function.) The boundary of the first constraint
is defined by the equality
$$x_2 = 8000 - \frac{3}{2} x_1$$
The constraint may be viewed as a half-plane with this line
dividing the region of allowed points from the unallowed points.
It is easy to identify which region is the allowed region by considering
a single point. For example, is the origin a point that satisfies
the first constraint? Since the answer is clearly yes we know that the
set of points that satisfies constraint 1 consists of the halfplane defined by
$x_2 = 8000 - \frac{3}{2} x_1$ that contains origin.
Similarly, the second constraint defines a halfplane of points
containing the origin and bounded by the line
$$x_2 = 10000 - 2x_1$$
The intersection of contraints 3 and 4 is the first quadrant of the $x_1 x_2$ plane.
The intersection of all of these constraints as shown in
Figure \ref{wine-LP} constitutes the feasible set. Now we must pick
the point in the feasible set that maximizes the objective function.
We can define an {\it isoprofit line} to be
$$12 x_1 + 7 x_2 = c$$
For all points on this line the profit is the same. We can see that as
$c$ decreases the line shifts towards the origin. So the goal is to pick the
isoprofit line with the largest value of $c$ such that $x_1, x_2$ is a point in
the feasible set. Graphically we see that the first point the descending isoprofit
line will touch is the vertex of the intersection of constraints 1 and 2.
This is easily calculated to be $(4000, 2000)$.
Thus, the solution to the winemaker's linear programming problem is
that he should produce $4000$ bottles of red and 2000 bottles of white
and that this will lead to a maximum profit of \$62,000.
%\section{Basic Theory}
%Convex sets, solutions at vertices.
\section{Sensitivity Analysis}
Often the coefficients in a linear programming model are known only
approximately. Thus, it is interesting to know what the impact of modifying
the terms present in the model. How is the objective function impacted? How
does the optimal solution change? These questions are the subject of
{\it sensitivity analysis}.
\subsection{Price Sensitivity}
First we examine how changing the price of a bottle of white wine impacts the optimal
solution. Letting the price of the white wine be a variable $w$ we now have the linear program
\begin{itemize}
\item Objective function: $f(x_1, x_2) = 12 x_1 + w x_2$
\item Constraint 1: $3x_1 + 2x_2 \le 16000$
\item Constraint 2: $2x_1 +x_2 \le 10000$
\item Constraint 3: $x_1 \ge 0$
\item Constraint 4: $x_2 \ge 0$
\end{itemize}
From our graphical solution we know that any isoprofit line with slope
between -2 and -3/2 will produce the same optimal solution of $(4000, 2000)$.
Since the slope of the isoprofit line is $-12/w$ this condition is
$$-2 < \frac{12}{w} < -\frac{3}{2}$$
from which we conclude that the price of the white wine may vary as
$$6 < w < 8$$
with the solution unchanged as $(4000, 2000)$. Further examination produces
Table \ref{tab-wine}. The double arrows here mean that any point on the isoprofit
curve containing these points produces the same profit.
\begin{table}[pht!]
\begin{center}
\begin{tabular}{|c|c|} \hline
cost of white wine & optimal solution \\ \hline
$6 < w< 8$ & (4000, 2000)\\
$w=6$ & $ (4000,2000) \leftrightarrow (5000, 0)$\\
$w=8$ & $ (4000,2000) \leftrightarrow (0, 8000)$\\
$w< 6$ & (5000, 0)\\
$ w> 8$ & (0, 8000)\\
\hline
\end{tabular}
\end{center}
\caption{The effect of pricing the white wine on the optimal
solution.}
\label{}
\end{table}
\subsection{Resource Sensitivity}
Now we left the number of gallons of grapes $\alpha$ and the
number of bottle-years storage capacity $\beta$ be variable.
Now the linear program becomes
\begin{itemize}
\item Objective function: $f(x_1, x_2) = 12 x_1 + 7 x_2$
\item Constraint 1: $3x_1 + 2x_2 \le \alpha$
\item Constraint 2: $2x_1 +x_2 \le \beta$
\item Constraint 3: $x_1 \ge 0$
\item Constraint 4: $x_2 \ge 0$
\end{itemize}
Now the relative values of $\alpha$ and $\beta$ determine
the geometry of the solution. For example, if $\alpha/2 > \beta$
then constraint 1 becomes irrelevant. When the intersection of constraints
1 and 2 determines the optimal solution it is readily shown that
$$x_1 = -\alpha + 2 \beta$$
and
$$x_2 = 2 \alpha - 3 \beta$$
Now the optimal solution to the objective function can be expressed
as
$$f(x_1, x_2) = 2 \alpha + 3 \beta$$
Hence if $\alpha$ is increased by one unit then $f(x_1, x_2)$ is
increased by 2, while if $\beta$ is increased by one unit then $f(x_1, x_2)$ is
increased by 3. So if a winemaker considers expanding his winery he realizes
that the cost of increasing grape processing must be less than \$2 and
the expense of increasing wine storage must be less than \$3. Otherwise
expansion will lose money.
\subsection{Constraint Coefficient Sensitivity}
Now we consider the problem of adjusting one of the
coefficients in one of the constraint equations. In
particular consider the amount of time $\gamma$ we age
a bottle of red wine to be allowed to vary.
\begin{itemize}
\item Objective function: $f(x_1, x_2) = 12 x_1 + 7 x_2$
\item Constraint 1: $3x_1 + 2x_2 \le 16000$
\item Constraint 2: $\gamma x_1 +x_2 \le 10000$
\item Constraint 3: $x_1 \ge 0$
\item Constraint 4: $x_2 \ge 0$
\end{itemize}
To simplify the discussion, let's examine the effect
of reducing the amount of time we age the red wine
from 2 years to 1.95 years. The solution to the resulting
linear program suggests that now 4444 bottles of red
can be sold while 1333 bottles of white can be sold for
a total profit of \$62,659, increasing the income
by almost \$700. Of course, for this to be advisable
it must be true that all the bottles of this "younger"
red wine can still be sold at the same price, i.e., the taste has
not suffered enough to reduce its popularity.
\section{Data Fitting and the Uniform Approximation}
\label{unif-app}
Now let us reconsider the topic of fitting a model to a data set.
This can also be put into the framework of a linear program.
Again, if we have a data set of domain (input) values
$\{ x_i \}$ and associated range (output) values $\{ y_i \}$ we would like
to determine the parameters $\{ w_1, \dots, w_k \}$ such that
$$y_i = f(x_i; w_1, \dots, w_k)$$
An alternative to requiring that the sum of the squares
of the residuals be zero is to simply minimize the maximum
residual. This approach is known as the {\it uniform
approximation}, or {\it Chebyshev} criterion.
Since large negative residuals would make this meaningless
we minimize the maximum absolute value of the residual.
To implement this idea, we first compute each residual
$\epsilon_i$ as
$$\epsilon_i= y_i - f(x_i; w_1, \dots, w_k)$$
and from all these determine the largest
$$\epsilon_{\max} = \underset{i}{\max}| \epsilon_i|$$
which will serve as our objective function.
So the programming problem is
$$\underset{i}{\min} \epsilon_{\max}$$
where based on the definition of $\epsilon_{\max}$ we
have the side constraints
$$|\epsilon_i| \le \epsilon_{\max}$$
So, for a linear model, $f(x) = ax+b$ we have
$$\epsilon_i = y_i - ax_i-b$$
so the constraints become
$$|y_i - ax_i-b| \le \epsilon_{\max}$$
or
$$-\epsilon_{\max} \le y_i - ax_i-b \le \epsilon_{\max}$$
Thus the linear program is to
$$\min{\epsilon_{\max}}$$
subject to the constraints
$$-\epsilon_{max} - y_i + ax_i+b \le 0$$
$$-\epsilon_{\max} + y_i - ax_i-b \le 0$$
where $i=1, \dots, P$.
In matrix notation we may rewrite the constraints as
$$
\left(
\begin{array}{ccc}
-x_1 & -1 & -1 \\
x_1 & +1 & -1 \\
\vdots & \vdots & \vdots\\
-x_1 & -1 & -1 \\
x_1 & +1 & -1 \\
\vdots & \vdots & \vdots\\
-x_P & -1 & -1 \\
x_P & +1 & -1
\end{array}
\right)
\left(
\begin{array}{c}
a \\
b \\
\epsilon_{\max}
\end{array}
\right)\le
\displaystyle
\left(
\begin{array}{c}
-y_1 \\
+y_1 \\
\vdots\\
-y_i \\
+y_i \\
\vdots\\
-y_P \\
+y_P
\end{array}
\right)
$$
Now solving this linear program to implement
the uniform approximation approach on the uniform noise data produces
the linear model equation
$$y = 0.9937x-0.275$$
while the least squares error criterion produces the model
$$y = 0.8923x-0.5466$$
For the uniform noise data the squared error was found to be
11.543 for the uniform approximation model while for the least squares model it is 9.998.
Please see the errors in Table \ref{table-error-comp} and the comparitive plot
of the two models in Figure \ref{lscheby_unif}.
\begin{figure}[tp!]
\centering
{\epsfig{file=lscheby_unif.ps,width=4.7in}}
\hfill
\caption{Least squares and uniform approximation to a linear trend
with uniformly distributed additive noise.}
\label{lscheby_unif}
\end{figure}
\begin{table}[pht!]
\begin{center}
\begin{tabular}{|c|c|r|r|} \hline
$x_i$ & $y_i$ & $\epsilon_i$ uniform & $\epsilon_i$ least squares\\ \hline
1& 2.3525 & \underline{1.6338} & 0.9136\\
2& 0.0786 & \underline{-1.6338} & \underline{-2.2527}\\
3& 3.7251 & 1.0191 & 0.5016\\
4& 3.5179 & -0.1818 & -0.5979\\
5& 6.3272 & \underline{1.6338} & 1.3190\\
6& 6.0113 & 0.3242 & 0.1108 \\
7& 7.8379 & 1.1571 & 1.0451\\
8& 7.7156& 0.0411 & 0.0305\\
9& 8.2185 & -0.4496 & -0.3589\\
10& 8.7586 & -0.9032& -0.7111\\ \hline
\end{tabular}
\end{center}
\caption{The data to be fit comprise the first two columns. The pointwise
error for the uniform approximation and least squares approximation are
in columns three and four, respectively. The underlined errors
are those with maximum magnitude for each model. As expected, the
uniform approximation has a smaller maximum error.}
\label{table-error-comp}
\end{table}
\subsection{Error Model Selection?}
Now we have seen that there is no unique way to compute
the coefficients that fit a given model to data. The model
is dependent on the way we measure the error (note that if our model
is exact--e.g., the interpolation condition is satisfied--then
the coefficients are unique and the error is zero). So the natural
question arises: given a collection of data what is the appropriate
error measure. The answer to this question lies partly in the nature
of the data. If your data is very accurate, then a uniform approximation
is indeed appropriate. If your data contains statistical outliers
or lots of noise, a least squares approximation may be more robust.
The ultimate decision factor in what error term to use
is in the added value of the model. If the predictive value
of the model is superior in one error measure than another
the choise is clear. Establishing superiority can often
be challenging in practice.
%\section{Projects}
\newpage
\begin{problem}
Think of an optimization problem that can be written as a linear program
with two decision variables.
Specify the objective function as well as the constraints.
Avoid constructing a problem the solution to which is
that one of the decision variables is zero.
Can you extend your problem to more decision variables and constraints?
\end{problem}
\begin{problem}
Solve the question of how many Zebra Dannios and Gouramis should be purchased
for the fish tank modeled in section \ref{fish}.
\end{problem}
\begin{problem}
A new burger chain, the EcoliExpress, has has two new products: the large
1/3 pound "Big Whoopie" burger and the smaller 1/4 pound "Wimpy Whoopie" burger.
It has been determined in test market trials that the Big Whoopie can be
sold at a profit of 45 cents per burger and the Wimpy Whoopie at a profit
of 25 cents. Furthermore, a chain knows that it can sell all its burgers if
it uses 100 pounds of meat per week. In addition, the preparation time
for a Big Whoopie is two minutes and for a Wimpy Whoopie is one minute and the chain
has one employee working 40 hours per week preparing both types of Whoopies.
Assuming the owner of the EcoliExpress wishes to maximize profits formulate a solution
using linear programming. Using this model, answer the following:
\begin{itemize}
\item[a)] How many Big Whoopies and Wimpy Whoopies should be sold?
\item[b)] Assuming the unit profit of the Big Whoopie is fixed at 45 cents, for what range of
prices of the Wimpy Whoopie is the solution in a) optimal?
\item[c)] Assuming the unit profit of the Wimpy Whoopie is fixed at 25 cents,
how large does the unit profit for the Big Whoopie have to be to justify
making only this type of burger?
\item[d)] What should the cost of meat be (per pound) to justify
purchasing additional quantities? Hint: the profit must increase.
\end{itemize}
\end{problem}
\begin{problem}
\label{hand-cheby}
Fit the model $y = ax$ to the data in Table \ref{tab-prob}
using the uniform approximation criterion. Identify the decision
variables and the objective function and graphically solve this
linear programming problem. Finally, draw a graph of
the model with the errors labeled for each point and comment.
\end{problem}
\begin{table}[pht!]
\begin{center}
\begin{tabular}{|c|ccc|} \hline
$x_i$ & 8 & 16 & 32 \\ \hline
$y_i$ & 10 & 14 & 31\\ \hline
\end{tabular}
\end{center}
\caption{Data for model in Problem \ref{hand-cheby}.}
\label{tab-prob}
\end{table}
\begin{problem}
If in Problem \ref{hand-cheby} the values $y_i$ where each increased by
one unit how would the coefficient $a$ change? Consider the three cases
separately.
\end{problem}
\begin{problem}
Consider the data in Table \ref{tab-prob2} and the model
$$y = ax^2 + bx + c$$
Write down the linear program to compute $a, b, c$ according to
uniform approximation criterion developed in Section \ref{unif-app}.
Identify the decision variables and reformulate the linear program
in matrix notation.
\begin{table}[pht!]
\begin{center}
\begin{tabular}{|c|cccc|} \hline
$x_i$ & 1 & 2 & 3 & 4 \\ \hline
$y_i$ & 2.3 & 5.3 & 8.7 & 16.1\\ \hline
\end{tabular}
\end{center}
\caption{Data for model in Problem \ref{hand-cheby}.}
\label{tab-prob2}
\end{table}
\end{problem}
\begin{problem} {\it Data Fitting.} Construct a linear program
to fit the model $y = ax + b$ to the
data set $\{ (x_i, y_i) \}$ using the $l_1$ error criterion
$$\underset{a,b}{\min} \sum_i | y_i -ax_i -b |$$
%see Braun and reference or find primary reference.
\end{problem}
\end{document}
%-----------------------------------------------------------------------
% End of chap4.tex
%-----------------------------------------------------------------------