\section{The Basic Linear Programming Problem Formulation}\label{S:ExerciseSolutions_Prototype_Standard_Form}

\setcounter{progress_ck_counter}{0}

\be

\item Express each LP below in matrix inequality form. Then solve the LP using Maple provided it
is feasible and bounded.
	
\be
% 1a
\item
        \begin{align*}
        \mbox{maximize } z &=6x_1+4x_2  \\
	\mbox{ subject to} \notag \\
	2x_1 + 3x_2 & \leq 9 \notag\\
	x_1 \phantom{ +20y} &\geq 4 \notag\\
	\phantom{ +20x} x_2  &\leq 6  \notag\\
	x_1,x_2 &\geq 0,\notag
    % Unique solution
	\end{align*}

\noi
The second constraint may be rewritten as $-x_1 \leq -4$ so that matrix inequality form
of the LP is given by
\begin{align}\label{E:MatrixInequalityForm}
 \mbox{maximize } z &=\vecc \cdot \vecx   \\
	\mbox{ subject to} \notag\\
	A \vecx &\leq \vecb \notag \\
	\vecx &\geq \zerovec, \notag
	\end{align}
where $\ds A= \begin{bmatrix} 2 &  3 \\ -1 & 0 \\ 0 & 1 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} 6 & 4 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} 9 \\ -4 \\ 6 \end{bmatrix}$, and
$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.

\newpar
The solution is given by $\ds \vecx= \begin{bmatrix} 4.5 \\ 0 \end{bmatrix}$,
with $z=27$.

% 1b
\item \begin{align*}
		 \mbox{maximize } z &=3x_1+2x_2  \\
		\mbox{ subject to} \notag\\
		x_1 \phantom{ +20x_2} &\leq 4 \notag\\
		x_1+3x_2 &\leq 15  \notag\\
		2x_1+x_2 &= 10\notag \\
		x_1,x_2 &\geq 0.\notag
		\end{align*}
        % Unique Solution	
		
\noi
The third constraint can be replaced by the two constraints,
$\ds 2x_1+x_2 \leq 10$ and $\ds -2x_1-x_2 \leq -10$. Thus,
the matrix inequality form of the LP is (\ref{E:MatrixInequalityForm}),
with $\ds A= \begin{bmatrix} 1 & 0 \\ 1 & 3 \\ 2 & 1 \\ -2 & -1 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} 3 & 2 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} 4 \\ 15 \\ 10 \\ -10 \end{bmatrix}$, and
$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.

\newpar
The solution is given by $\ds \vecx= \begin{bmatrix} 3 \\ 4 \end{bmatrix}$,
with $z=17$.

% 1c
\item \begin{align*}
		 \mbox{maximize } z &=-x_1+4x_2  \\
		\mbox{ subject to} \notag\\
		-x_1 +x_2 &\leq 1 \notag\\
		x_1+\x &\leq 3  \notag\\
		x_1+x_2 &\geq 5 \notag \\
		x_1,x_2 &\geq 0.\notag
		\end{align*}
        % Infeasible

\noi
The third constraint is identical to $\ds -x_1-x_2 \leq -5$.
The matrix inequality form of the LP is (\ref{E:MatrixInequalityForm}),
with $\ds A= \begin{bmatrix} -1 & 1 \\ 1 & 0 \\ -1 & -1 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} -1 & 4 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} 1 \\ 3 \\ -5 \end{bmatrix}$, and
$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.

\newpar
The solution is  $\ds \vecx= \begin{bmatrix} 3 \\ 4 \end{bmatrix}$,
with $z=13$.

% 1d
\item \begin{align*}
		 \mbox{minimize } z &=-x_1+4x_2  \\
		\mbox{ subject to} \notag\\
		x_1 +3x_2 &\geq 5 \notag\\
		x_1+x_2 &\geq 4  \notag\\
		x_1-x_2 &\leq 2 \notag \\
		x_1,x_2 &\geq 0.\notag
		\end{align*}

\noi
To express the LP in matrix inequality form with the goal of maximization,
we set \newline
\begin{equation*}  \vecc=-\begin{bmatrix} -1 & 4 \end{bmatrix}=
\begin{bmatrix} 1 & -4 \end{bmatrix}.
\end{equation*}
The first two constraints may
be rewritten as $\ds -x_1-3x_2 \leq -5$ and $\ds -x_1-x_2 \leq -4$.
The matrix inequality form of the LP becomes (\ref{E:MatrixInequalityForm}),
with $\ds A= \begin{bmatrix} -1 & -3 \\ -1 & -1 \\ 1 & -1 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} 1 & -4 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} -5 \\ -4 \\ 2 \end{bmatrix}$, and
$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.

\newpar
The solution is given by $\ds \vecx= \begin{bmatrix} 3 \\ 1 \end{bmatrix}$,
with $z=-1$.

% 1e
\item \begin{align*}
		 \mbox{maximize } z &=2x_1-x_2  \\
		\mbox{ subject to} \notag\\
		x_1 +3x_2 &\geq 8 \notag\\
		x_1+x_2 &\geq 4  \notag\\
		x_1-x_2 &\leq 2 \notag \\
        x_1,x_2 &\geq 0.\notag
        \end{align*}
\noi
The first and second constraints are identical to
$\ds  -x_1 -3x_2 \leq -8$ and $\ds -x_1-x_2 \leq -4$, respectively. Thus,
$\ds A= \begin{bmatrix} -1 & -3 \\ -1 & -1 \\ 1 & -1 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} 2 & -1 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} -8 \\ -4 \\ 2 \end{bmatrix}$, and
$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.

\newpar
The LP is unbounded.

% 1f
\item \begin{align*}
	       	 \mbox{minimize } z &=2x_1+3x_2  \\
		\mbox{ subject to} \notag\\
		3x_1 +x_2 &\geq 1 \notag\\
		x_1+x_2 &\leq 6  \notag\\
		x_2 &\geq 0.\notag
        \end{align*}

\noi
Define $x_1=x_{1,+}-x_{1,-}$, where
$x_{1,+}$ and $x_{1,-}$ are nonnegative. Then, as a maximization problem,
the LP may be rewritten in terms of three decision variables as

\begin{align*}
	       	 \mbox{maximize } z &= -2(x_{1,+}-x_{1,-})-3x_2   \\
		\mbox{ subject to} \notag\\
		-3(x_{1,+}-x_{1,-}) -x_2 &\leq -1 \notag\\
		(x_{1,+}-x_{1,-})+x_2 &\leq 6  \notag\\
		x_{1,+},x_{1,-},x_2 &\geq 0.\notag
        \end{align*}

\noi
The matrix inequality form of the LP becomes (\ref{E:MatrixInequalityForm}),
with $\ds A= \begin{bmatrix} -3 & 3 & -1 \\ 1 & -1 & 1 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} -2 & 2 & -3 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} -1 \\ 6 \end{bmatrix}$, and
$\ds \vecx= \begin{bmatrix}  x_{1,+} \\ x_{1,-}\\ x_2 \end{bmatrix}$.

\newpar
The solution is given by $\ds x_{1,+}=\frac{1}{3}$ and $\ds x_{1,-}=x_2=0$, with $\ds z=-\frac{2}{3}$.
\ee

\item The LP is given by
    \begin{align*}
	       	 \mbox{minimize } z &=x_1+4x_2  \\
		\mbox{ subject to} \notag\\
		x_1 +2x_2 &\leq 5 \notag\\
		|x_1-x_2| &\leq 2  \notag\\
		x_1, x_2 &\geq 0.\notag
        \end{align*}

\noi
The constraint involving the absolute value is identical to
$\ds -2 \leq x_1-x_2 \leq 2$, which may be written as the two constraints,
$\ds x_1-x_2 \leq 2$ and $-x_1+x_2 \leq 2$. The matrix inequality form of the LP is
(\ref{E:MatrixInequalityForm}) with
$\ds A= \begin{bmatrix} 1 & 2 \\ 1 & -1 \\ -1 & 1 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} -1 & -4 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} 5 \\ 2 \\ 2 \end{bmatrix}$, and
$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.

\newpar
The solution is given by $\ds \vecx= \begin{bmatrix} 0 \\ 0 \end{bmatrix}$,
with $z=0$.


\item
If $x_1$ and $x_2$ denote the number of chairs and number of tables, respectively produced
by the company, then $z=5x_1+7x_2$ denotes the revenue, which we seek to maximize. The number
of square blocks needed to produce $x_1$ chairs is $2x_1$, and the number of square
blocks needed to produce $x_2$ tables is $2x_2$. Since six square blocks are available,
we have the constraint, $\ds 2x_1+2x_2 \leq 6$. Similar reasoning, applied to the rectangular
blocks, leads to the constraint $\ds x_1+2x_2 \leq 8$. Along with sign conditions, these results yield
the LP
\begin{align*}
		 \mbox{maximize } z &=5x_1+7x_2  \\
		\mbox{ subject to} \notag\\
		2x_1+2x_2 &\leq 6 \notag\\
		x_1+2x_2 &\leq 8  \notag\\
		x_1,x_2 &\geq 0.\notag
		\end{align*}.

\noi
For the matrix inequality form,
$\ds A= \begin{bmatrix} 2 & 2 \\ 1 & 2 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} 5 & 7 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} 6 \\ 8 \end{bmatrix}$, and
$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.

\newpar
The solution is given by $\ds \vecx= \begin{bmatrix} 0 \\ 3 \end{bmatrix}$,
with $z=21$.

\item
\be
\item If $x_1$ and $x_2$ denote the number of grams of grass and number of grams of forb,
	respectively, consumed by the vole on a given day, then
the total foraging time is given by $z=45.55x_1+21.87x_2$. Since the coefficients in this
sum have units of minutes per gram, the units of $z$ are minutes.

\newpar
The products $1.64x_1$ and
$2.67x_2$ represent the amount of digestive capacity corresponding to eating $x_1$ grams of grass
and $x_2$ grams of forb, respectively. The total digestive capacity is $31.2$ gm-wet, which yields the constraint
$\ds 1.64x_1+2.67x_2\leq 31.2$. Observe that the units of the variables, $x_1$ and $x_2$, are
gm-dry. Each coefficient in this inequality has units of gm-wet per gm-dry, so the sum
$\ds 1.64x_1+2.67x_2$ has the desired units of gm-wet.

\newpar
Similar reasoning focusing on energy requirements, leads to the constraint
$\ds 2.11x_1+2.3x_2 \geq 13.9$. Along with sign conditions, we arrive at

\begin{align*}
 \mbox{minimize } z &=45.55x_1+21.87x_2   \\
	\mbox{ subject to} \\
    1.64x_1+2.67x_2 &\leq 31.2  \\
    2.11x_1+2.3x_2 &\geq 13.9 \\
	x_1,x_2 &\geq 0.
	\end{align*}	
\item The solution, obtained using Maple's \mf{LPSolve} command, is given by
$x_1 =0$ grams of grass and $x_2 \approx 6.04$ grams of forb. The total time spent foraging
is $z \approx 132.17$ minutes.

\ee

\ee

% WAYPOINT SOLUTIONS

\hrulefill

\newpar
\textbf{Solutions to Waypoints}

\begin{waypoint}
There are of course many possible combinations. Table \ref{Ta:Waypoint111}
summarizes the outcomes for four choices.

\begin{table}[h]
	\caption{Production combinations (in gallons)}\label{Ta:Waypoint111}
	\begin{tabular}{|c|c|c|}
	Premium & Reg. Unleaded & Profit (\$)  \\ \hline
	5 & 5 & 3.5 \\
    5 & 7 & 4.1 \\
    7 & 5 & 4.3 \\
    7 & 7 & 4.9 \\
	\end{tabular}
	\end{table}

\newpar
The fourth combination requires 35 gallons of stock B, so it does not satisfy the listed constraints. Of the three that do, the combination of 7 gallons premium and 5 gallons regular unleaded results
in the greatest profit.
\end{waypoint}


\endinput 