\chapter{Standard Applications of Linear Programming}\label{C:Standard_Applications}
\section{The Diet Problem}\label{S:Maple_Diet_Problem}
\setcounter{progress_ck_counter}{0}

\noi Within the field of linear programming, there exist certain classes of closely related problems. In the vast majority of them, efficiently formulating the LP itself so that it can be solved using Maple or other available software is a challenge. In this chapter, we investigate several problem types.

\subsection{Eating for Cheap on a Very Limited Menu}\label{SS:Maple_Diet_Problem_Problem_Formulation}

\noi A sandwich shop has a menu consisting of four items: turkey breast on a bun, a club sandwich, a veggie sub, and a breakfast sandwich. Nutritional data for each is summarized in Table
\ref{Ta:Maple_Diet_Problem_Nutritional_Data}.\index{diet problem}

\begin{table}[h]
\caption{Sandwich nutritional data}\label{Ta:Maple_Diet_Problem_Nutritional_Data}
\begin{tabular}{|l|c|c|c|c|}
\hline
Sandwich &
Turkey Breast
& Club
& Veggie Sub
&  $\ds \begin{matrix} \mbox{Breakfast} \\ \mbox{Sandwich} \end{matrix}$
\\ \hline
Calories &  280   &  320        &  230      &    470    \\ \hline
Fat (gm.)   &   4.5  &   6          &  3        &    19    \\ \hline
Cholesterol (gm.)& 20  &  35         &   0      &     200  \\ \hline
%Sodium (gm.)     &  1000   &  1290    &  500      &     1500   \\ \hline
Carbohydrates (gm.)  &  46   &  47    &  44       &     53   \\ \hline
Fiber (gm.)     &   5  & 5            &   5       &    5    \\ \hline
Protein (gm.)     &  18   &  24       &  9        &    28    \\ \hline
Vitamin A (pct. RDA)    &   8  &  8       &   8       &    10    \\ \hline
Vitamin C (pct. RDA)     &  35   &  35     &   35      &   15     \\ \hline
Calcium (pct. RDA)     &  6   &   8        &  6        &    25    \\ \hline
Iron (pct. RDA)      &  25   &  30         &   25      &   25     \\
\hline
\end{tabular}
\end{table}

\noi Daily nutritional guidelines for each category in Table \ref{Ta:Maple_Diet_Problem_Nutritional_Data}
are summarized in Table \ref{Ta:Maple_Diet_Problem_Daily_Requirements}. The listed minimum requirements for vitamins A and C, calcium, and iron are based upon the assumption that deficiencies are remedied through beverages and daily vitamin supplements.

\begin{table}[h]
\caption{Daily nutritional guidelines}\label{Ta:Maple_Diet_Problem_Daily_Requirements}
\begin{tabular}{|l|c|c|}
\hline
Category & Daily Minimum & Daily Maximum \\
\hline
Calories    &      2000          &   3000    \\ \hline
Fat (gm.)   &   0             &   65           \\ \hline
Cholesterol (gm.)& 0  &  300           \\ \hline
Carbohydrates (gm.)  &  50   &  300       \\ \hline
Fiber (gm.)     &   25  & 50                \\ \hline
Protein (gm.)     &  50   &  200        \\ \hline
Vitamin A (pct. RDA)    &   40  &  200           \\ \hline
Vitamin C (pct. RDA)     &  40   &  200       \\ \hline
Calcium (pct. RDA)     &  40   &   200           \\ \hline
Iron (pct. RDA)      &  40   &  200          \\
\hline
\end{tabular}
\end{table}

\newpar
Suppose that sandwiches cost \$6.00 (turkey breast), \$5.00 (club sandwich), \$3.50 (veggie sub), and \$5.00 (breakfast sandwich). We seek to minimize the total daily cost of maintaining a diet that is comprised solely of these four sandwiches and fulfills the previously stated nutritional guidelines. We will permit partial consumption of any sandwich and assume that the purchase price of any such sandwich is pro-rated on the basis of the fraction consumed. For example, consumption of one-half of a club will contribute only \$2.50 to total cost. Certainly this last assumption is unrealistic in that the number of purchased sandwiches of each type must be integer-valued. In
Chapter \ref{C:Integer_Linear_Programming}, we will learn how to account for this fact.

\subsection{The Problem Formulation and Solution, with Help from Maple}\label{SS:Maple_Diet_Problem_Maple_Solution}\index{diet problem!Maple formulation}

\noi The LP whose solution minimizes total cost in this situation will have numerous constraints, and listing these constraints individually within Maple's \mf{LPSolve} can prove extremely tedious. We therefore seek a more efficient manner for constructing them. Key to doing so are Maple's array, sequence, and adding commands as introduced in Section \ref{S:Maple-Arrays_Sequences}. What follows is merely one of many means of combining these commands in a manner that leads to the correct LP solution.

\newpar
We first define decision variables, $x_1$, $x_2$, $x_3$, and $x_4$, to be the number of consumed
turkey breast sandwiches, club sandwiches, veggie subs, and breakfast sandwiches,
respectively. Since these decision variables will appear in our objective function and throughout our constraints, we define them in Maple through use of an array as follows:

\begin{maplelist}
\item \mf{restart: with(LinearAlgebra):with(Optimization):}
\item \mf{x:=array(1..4);}
\mo{x:=array(1..4,[])}
\end{maplelist}

\newpar
Each column of Table \ref{Ta:Maple_Diet_Problem_Nutritional_Data} can be viewed as a vector in $\R^{10}$ recording nutritional information for a particular sandwich. One means of storing this information in Maple is to first construct a ``nutrition vector'' for each sandwich and then to use the resulting vectors to form
a ``nutrition matrix.'' The following syntax performs this task:

\begin{maplelist}
\item \mf{TurkeyBreast:=<280,4.5,20,46,5,18,8,35,6,25>:}
\item \mf{Club:=<320,6,35,47,5,24,8,35,8,30>:}
\item \mf{VeggieSub:=<230,3,0,44,5,9,8,35,6,25>:}
\item \mf{BreakfastSandwich:=<470,19,200,53,5,28,10,15,25,25>:}
\item \mf{A:=<TurkeyBreast | Club | VeggieSub | BreakfastSandwich>:}
\end{maplelist}

\newpar
In a similar manner, each column of Table \ref{Ta:Maple_Diet_Problem_Daily_Requirements} can also be
entered as a vector in $\R^{10}$. The terms
\mf{Maximum}, \mf{maximum}, \mf{max}, as well as corresponding terms for minima, have reserved
meanings in Maple, so we must choose names for these vectors with care. Here we call them
\mf{MinimumAmount} and \mf{MaximumAmount}. The first of these is given as follows:

\begin{maplelist}
\item \mf{MinimumAmount :=<2000,0,0,50,25,50,40,40,40,40>:}
\end{maplelist}

\noi The vector \mf{MaximumAmount} is defined similarly.

\newpar
While the total cost, in dollars, can be expressed in Maple as
\newline
\mf{6*x[1]+5*x[2]+3.5*x[3]+5*x[4]}, we will enter sandwich costs in the form of a vector. Doing so illustrates a convenient tool for larger-scale problems.
\begin{maplelist}
\item \mf{Prices:=<6,5,3.5,5>:}
\item \mf{TotalCost:=add(Prices[i]*x[i],i=1..4);}
\mo{TotalCost:=6x_1+5x_2+3.5x_3+5x_4}
\end{maplelist}

\newpar
Constraints can be formulated in terms of the array, \mf{x}, the matrix, \mf{A}, and
the vectors \mf{MinimumAmount} and \mf{MaximumAmount}. For example, the maximum number of
calories can
be expressed as follows:

\begin{maplelist}
\item \mf{add(A[1,j]*x[j],j=1..4)<=3000;}
\mo{280x_1+320x_2+230x_3+470x_4 \leq 3000}
\end{maplelist}

\noi We wish to ensure that analogous guidelines hold for other categories. One means of accomplishing this efficiently in Maple is through use of the sequence command, \mf{seq}\index{Maple!\mf{seq}}. What follows is syntax illustrating how this command can be used to produce all model constraints:

\begin{maplelist}
\item \mf{MinimumGuidelines:= \newline seq(MinimumAmount[i]<=add(A[i,j]*x[j],j=1..4),i=1..10):}
\item \mf{MaximumGuidelines:= \newline seq(add(A[i,j]*x[j],j=1..4)<=MaximumAmount[i],i=1..10):}
\end{maplelist}

\newpar
These preceding two command lines produce the LP constraints in the form of two sequences, whose results can be used to create the constraint list for purposes of invoking the \mf{LPSolve} command. Here is the command line that combines the previous results to determine the optimal solution of the LP.

\begin{maplelist}
\item \mf{LPSolve(TotalCost,[MinimumGuidelines,MaximumGuidelines],\newline assume='nonnegative');}
\end{maplelist}


\begin{progress_ck}
Use Maple to verify that the cheapest, four-sandwich diet costs approximately
 \$29.81 per day and consists of no turkey breast sandwiches, approximately 5.14 club
sandwiches, .314 veggie subs, and .6 breakfast sandwiches.
\end{progress_ck}

\newpar
Maple structures of sequences, sums, vectors, matrices, and arrays all played a role in solving
the diet LP in this section. It is important to note that in many problems more than one structure can be used to perform a task. For example, \mf{Prices} was entered as a vector but, for purposes of computing total cost, could also be entered as a list, \mf{Prices:=[6,5,3.5,5]}. Choosing this approach would not affect subsequent command lines. A matrix was chosen over an array to record
 nutritional data for all sandwiches merely due to the fact nutritional information for each sandwich was presented in tabular form (as one would expect from reading product labels) and could be easily entered as a vector. These vectors were combined to produce the matrix \mf{A}. In other problem types, use of an array is more appropriate. When confronted with choices such as these, two important points to be bear in mind are the following: Which method permits the easiest entry of data relevant to the problem, and which method permits the greatest flexibility in terms of needed operations for constructing the LP? For example, a \mf{Matrix} can be multiplied by a column \mf{Vector}, but not by a list structure, unless
 the list is first converted to a \mf{Vector} through use of the \mf{convert}\index{Maple!\mf{convert}} command.


\section*{Exercises Section \protect\ref{S:Maple_Diet_Problem}}

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_Maple_Diet_Problem}

\endinput 