\section{Linear Programming: A Graphical Perspective in $\R^2$}\label{S:LP_Graphical}
\setcounter{progress_ck_counter}{0}

\noi In Section \ref{S:LP_Prototype_Standard_Form} we formulated the \LP problem and obtained its solution with the aid of Maple's \mf{Optimization} package. Now we develop a graphical approach for obtaining the same solution, one that provides deeper insight into the nature of the solutions to LPs in general. Recall the \LP problem\index{FuelPro LP}:

\begin{align}
 \mbox{maximize } z &=f(x_1,x_2)=4x_1+3x_2  \label{E:LP_Prototype_Standard_Form_FuelPro_LP} \\
	\mbox{ subject to} \notag\\
	x_1 \phantom{ +20x_2} &\leq 8 \notag\\
	2x_1+2x_2 &\leq 28  \notag\\
	3x_1+2x_2 &\leq 32 \notag \\
	x_1,x_2 &\geq 0. \notag
	\end{align}	

\noi
The points in the $x_1x_2$-plane that satisfy all the constraints and sign conditions in
(\ref{E:LP_Prototype_Standard_Form_FuelPro_LP}) form the \emph{feasible region}\index{feasible region} for the
\LP model.
\begin{progress_ck}%\label{Th:feasible_sketch}
Sketch and shade the graph of the feasible region in the $x_1x_2$-plane. While this task is easily accomplished by hand, Maple can also do so through the use of the \mf{inequal} command\index{Maple!\mf{inequal}}
as described in Appendices \ref{C:Maple_Getting_Started} and \ref{C:Maple_Appendix}.
The list of inequalities
used within this command is given by
\mf{[x1<=8, 2*x1+2*x2<=28, 3*x1+2*x2<=32,x1>=0,x2>=0 ]} . The resulting graph
should resemble that in Figure \ref{Fi:f02x02x01}
\end{progress_ck}


\begin{figure}[h]
\centering
\psfrag{x1_axis_label}[Bc][Bc]{$x_1$}
\psfrag{x2_axis_label}[Bc][Bc]{$x_2$}
\includegraphics[width=.7\linewidth]{images/f02x02x01.eps}
\caption{Feasible region for \LP LP.}\label{Fi:f02x02x01}
\end{figure}

\newpar
The function $f=4x_1+3x_2 $ from (\ref{E:LP_Prototype_Standard_Form_FuelPro_LP}) is a multivariate function whose graph consists of a surface in $\R^3$. Recall
that a \emph{contour}\index{contour} or \emph{level curve}\index{level curve} of such a function
is a curve in the $x_1x_2$-plane that results from holding $z$ constant. In other words, it is a curve that results from slicing the surface with a horizontal plane of the form $z=c$, where $c$ is a constant. A \emph{contour diagram}\index{contour diagram} is merely a collection of contours plotted on a single set of axes.

\newpar
Maple produces contour diagrams through its \mf{contourplot} command\index{Maple!\mf{contourplot}}, located
in the \mf{plots} package. The general form of the command is
\mf{contourplot(\emph{expression in x1 and x2},\emph{x1=a..b},\emph{x2=c..d},\emph{options})}.
Various options include specifying the output values used for the contours, specifically via
\mf{contours=L}, where \mf{L} is a list of contour values. Figure \ref{Fi:f02x02x02} illustrates an example, using the expression $\ds x_1^2+x_2^2$, along with contour values of 0, 1, 2, 3, and 4:

\begin{maplelist}
\item \mf{contourplot(x1\^{}2+x2\^{}2,x1=-3..3,x2=-3..3,contours=[1,2,3,4]);}
\end{maplelist}

\begin{figure}[h]
\centering
\includegraphics[width=.7 \linewidth]{images/f02x02x02.eps}
\caption{Sample contour diagram produced by Maple.}\label{Fi:f02x02x02}
\end{figure}

\noi
For the \LP problem, the objective function $f$ is
a \emph{linear function} of two variables so that its contours form \emph{parallel lines}.

\begin{progress_ck} Superimpose on your
feasible region from the previous Waypoint the graphs of several contours of the
objective function
$f(x_1,x_2)=4x_1+3x_2$.
(Recall from Appendices \ref{C:Maple_Getting_Started} and \ref{C:Maple_Appendix} that plot structures
can be superimposed by use of the \mf{display} command.) Then
use these contours to determine the amounts of premium and regular unleaded fuel types in the feasible region that correspond to the maximum profit. Your solution should of course agree
with that obtained by using the \mf{LPSolve} command in Section \ref{S:LP_Prototype_Standard_Form}.
\end{progress_ck}

\newpar
Recall from Section \ref{S:LP_Prototype_Standard_Form} that the solution of an LP can take one of four possible forms.
	\be
    \item The LP can be
    \emph{infeasible}\index{infeasible LP|see{linear programming problem!infeasible}}, meaning that its feasible region is the empty set.
	\item The LP can have a \emph{unique optimal solution}, as is the case for the \LP problem.
	\item The LP can have \emph{alternative optimal solutions}\index{alternative optimal solutions|see{linear programming problem!alternative optimal solutions}}. That is, there exists at least
    two optimal solutions.
	\item The LP can be \emph{unbounded}\index{unbounded LP|see{linear programming problem!unbounded}}. For a problem in which one seeks to maximize the
	objective function, this
	means that the objective function can be made as large as one likes. For a minimization problem,
	this means that the objective function can be made as small as one likes.
	\ee

\noi While constraints and sign conditions alone determine whether an LP is infeasible, contours provide a graphical means for determining whether an LP has alternative optimal solutions or is unbounded. The following LP provides one such example:
\begin{align}
 \mbox{maximize } z &=f(x_1,x_2)=6x_1+4x_2  \label{E:LP_Graphical_Alternative_Optimal} \\
	\mbox{ subject to} \notag \\
	3x_1 + 2x_2 & \leq 18 \notag \\
	x_1 \phantom{ +20y} &\leq 4 \notag \\
	\phantom{ +20x} x_2  &\leq 6  \notag \\
	x_1,x_2 &\geq 0.\notag
	\end{align}	
The feasible region for (\ref{E:LP_Graphical_Alternative_Optimal}), together with objective function contours $z=32$, $z=34$ and $z=36$,
is shown in Figure \ref{Fi:LP_graphical_alternative_solutions}.

\begin{figure}[h]
\centering
\includegraphics[width=.7\linewidth]{images/f02x02x03.eps}
\caption{LP with alternative optimal solutions.}\label{Fi:LP_graphical_alternative_solutions}
\end{figure}

\newpar
In this example, contours of the objective function $f$ are parallel to the boundary of the constraint $3x_1 + 2x_2 \leq 9$. Moreover, objective values corresponding to these contours illustrate how all points on the segment from $(2,6)$ to $(4,3)$ yield the same optimal objective value, $z=36$. One way to represent this segment
is through a parametric representation as follows:
\begin{equation*}
(x_1,x_2)= t\cdot (2,6) + (1-t)\cdot (4,3) = (4-2t,3+3t), \mbox{ where } 0 \leq t \leq 1.
\end{equation*}	

\newpar
The preceding example illustrates how contours can be used to identify an LP having alternative optimal
solutions. Namely, such solutions arise when the contour that intersects the feasible region and corresponds to the optimal objective value also contains a segment of the feasible region boundary. That contours can also be used to identify unbounded LPs is left as an exercise.

\section*{Exercises Section \protect\ref{S:LP_Graphical}}
\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_LP_Graphical}

\endinput
