\chapter{An Introduction to Linear Programming}\label{C:Intro_Linear_Programming}

\section{The Basic Linear Programming Problem Formulation}\label{S:LP_Prototype_Standard_Form}
\setcounter{progress_ck_counter}{0}
%\setcounter{activity}{0}

\noi Any student who has completed a first-semester calculus course recalls solving
optimization problems. A contrived, yet typical example of such is given by
the following:
\begin{quote}
Farmer Smith has 100 yards of fence to build a rectangular corral, one of whose sides will consist of the side of a barn. What should be the dimensions of the corral if Farmer Smith wishes to maximize the possible enclosed area?
\end{quote}

\noi
Of course, the calculus provides one means of solving this problem. If we let $x$ and $y$
denote the dimensions of the corral, then the available fence length
dictates $2x+2y=100$, and the area, $A$, is given by $A=xy$.
Rewriting $A$ as a function of a single variable, say $x$, and solving the
equation, $\ds \frac{dA}{dx}=0$, for $x$, we deduce that Farmer Brown maximizes
the enclosed area by using 50 feet of fence opposite the barn and 25 feet for each of the opposite
two sides.

\newpar
Linear programming, the main focus of this chapter, is another optimization tool having components analogous to those of the preceding calculus problem. First, there is a function to be maximized or minimized. Whereas in calculus, one works with smooth functions of a single variable, linear programming involves optimizing linear functions of several variables. In calculus, one frequently constrains the input values of the function to fall within a certain interval. In linear programming, input values must satisfy several constraints, each of which takes the form of a linear inequality. Calculus optimization problems rely upon the derivative; linear programming utilizes linear algebra as a tool.
The goal of Part \ref{P:Linear_Programming} of this text is to expand upon these ideas and to apply them to solve a variety of real-world
linear programming problems.

\newpar
\subsection{A Prototype Example: The Blending Problem}\label{S:LP_Prototype_Standard_Form_LinPro}

\noi One sector of the economy that has made extensive use of linear programming is the petroleum industry. Texaco, for example, used linear programming to address \emph{blending problems}\index{blending problem} in the early 1980s; doing so saved the company an estimated \$30 million per year \cite{DeWitt_Texaco}. The idea of a blending problem is fairly simple. A company produces various grades of gasoline, e.g., regular unleaded, mid-grade, and premium, which have various octane ratings. Various stocks are used to produce these grades. Such stocks are the intermediate products produced by the refineries and include straight-run gasoline, formate, and catalytic gasoline. The question becomes, given a particular quantity the company wishes to optimize, e.g., revenue earned on the various gasoline grades, how does it do so while satisfying numerous constraints on stock demand and quality specifications?

\newpar
A fictitious, yet simple and illuminating example used throughout this chapter is that of the
\LPC\index{FuelPro Petroleum Company}, a small refinery that sells two grades of fuel, premium and regular unleaded. For purposes of simplicity, we will assume that
only two stocks, stock A and stock B, are used
to produce the two grades and that 28 and 32 gallons of each stock,
respectively, are available. The following table summarizes how much of each stock is required for each
grade. (Assume all quantities are measured in gallons.)

\begin{table}[h]
	\caption{\LP production data}\label{Ta:t02x01x01}
	\begin{tabular}{|l|c|c|c|}
	Stock & Premium & Reg. Unleaded & Available Stock \\ \hline
	Type A & 2 & 2 & 28  \\ \hline
	Type B & 3 & 2 & 32  \\
	\end{tabular}
	\end{table}
\newpar
Production facility limitations dictate that at most 8 gallons of premium grade fuel can be made available each hour. The net profit per gallon of premium grade is \$.40 and that of regular unleaded is \$.30. \LP is fortunate to sell all the fuel it refines.

\newpar
Some logical questions the company might wish to address are the following:
	\be
	\item What are the possible production combinations of fuel types that will satisfy the above conditions
	or \emph{set of constraints}?
	\item What combinations of fuel types will \emph{maximize} \emph{FuelPro}'s profit?
	\item How \emph{sensitive} is the answer to the preceding question to the various parameters in the model?
	For example, by how much will the price of unleaded regular need to change before the optimal fuel production
	combination from (2) will change as well?
	\ee
Linear programming is a powerful tool for addressing such questions!

\begin{progress_ck} In the preceding example, experiment and list four combinations of
premium and regular unleaded fuel types, three of which satisfy the listed constraints and one
of which does not. Of those three that do,
which produces the largest profit?
\end{progress_ck}

\newpar Mere experimentation with points as a means of determining the combination of fuel types that maximizes profit for \LP  naturally leads to the question of whether there is a mathematically more systematic approach to solving this problem. In this section we take a first step toward developing such an approach by introducing basic terminology and by interpreting the problem situation using the language of multivariate functions and linear algebra.

\newpar
Let us denote the number of gallons of premium grade and regular unleaded produced in a given hour by the variables $x_1$ and $x_2$, respectively. Using information regarding the production of the two fuel grade types, we can construct inequalities relating these two variables.
	\be
	\item From information provided in the first row of Table \ref{Ta:t02x01x01}, we know that each gallon of premium requires 2 gallons of stock A and
	each gallon of regular unleaded requires 2 gallons of stock A. Since only 28 gallons of stock
	A are available to \LP each hour, we obtain the inequality:
		\[ 2x_1 + 2 x_2 \leq 28.\]
	\item By similar reasoning, the maximum availability of stock B dictates that
		\[ 3x_1 + 2 x_2 \leq 32.\]
	\item At most 8 gallons of premium grade fuel can be sold each hour. Thus $x_1 \leq 8$.
	\item Only nonnegative values of $x_1$ and $x_2$ make sense for the problem situation. Therefore,
	$x_1,x_2 \geq 0$.
	\ee

\newpar
\LP desires to maximize its profit subject to the preceding constraints. Given the profit per gallon amounts for the premium and unleaded fuels, the function to be maximized is simply $.4x_1 + .3x_2$. For the mere
sake of working with integer-valued coefficients, we shall instead maximize
	\[ z = f(x_1,x_2)= 4x_1 + 3x_2.\]
Combining this function with the above constraints, the optimization
problem faced by \LP can be written as follows:\index{FuelPro LP}
\begin{align}\label{E:Prototype_Standard_Form_FuelPro_LP}
 \mbox{maximize } z &=f(x_1,x_2)=4x_1+3x_2  \\
	\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}	


\newpar
System (\ref{E:Prototype_Standard_Form_FuelPro_LP}) is an example of a \emph{linear programming problem}\index{linear programming problem!general form} (LP).
\begin{definition}\label{Th:LP_definition}
A linear programming problem is a mathematical problem that consists of the following components:
	\be
	\item An \emph{objective function}, $f$, of $n$ \emph{decision variables},
	$x_1, x_2, \ldots, x_n$, that is to be maximized or
	minimized. This function is linear; that is it can be written in the form
	\begin{equation}\label{E:objective}
	z=f(x_1,x_2,\ldots,x_n)=c_1x_1+c_2x_2+ \cdots +c_nx_n,
	\end{equation}
	where each $c_i$ belongs to $\R$.
	\item A set of $m$ \emph{constraints} or inequalities. Each constraint is linear
	in that it takes the form,
	\begin{equation}\label{E:constraint}
	a_{i1}x_1+a_{i2}x_2+ \cdots +a_{in}x_n \leq b_i,
	\end{equation}
	where $1 \leq i \leq m$ and where each $a_{ij}$ and $b_i$ belongs to $\R$.
	\item Possible \emph{sign restrictions}\index{linear programming problem!sign restrictions} placed on any of the decision variables.
	\ee
\end{definition}

\noi
We will define the vector $\ds \vecx=\begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n\end{bmatrix}$
in $\R^n$ to be a \emph{feasible solution}\index{linear programming problem!feasible solution} of the LP if it satisfies all constraints and sign
restrictions of the LP. The \emph{feasible region}\index{linear programming problem!feasible region} is the set of all feasible solutions, and an
\emph{optimal solution}\index{linear programming problem!optimal solution} is a feasible solution whose corresponding objective function value is greater than or equal to
that of any other feasible solution for a maximization problem and less than or equal to that
of any other feasible solution for a minimization problem.

\newpar
While Definition \ref{Th:LP_definition} appears to stipulate that all constraints are of inequality type, equations are permissible as well, as long as the constraint equations
are linear in the variables $x_1, x_2, \ldots, x_n$. However, in Section \ref{S:LP_Prototype_Standard_Form_Matrix_Form} we will discover how the set of constraints of any LP can be expressed entirely in terms of inequalities.

\newpar
It is important to note that any LP has hidden assumptions due to its linear nature. For example, in our petroleum model we assume that there is no interaction between the amounts of premium and regular unleaded, e.g., no product terms $x_1x_2$.
We are also assuming that the objective function is linear. In certain other situations, the function $f$ might be better modeled by a quadratic function, in which case the problem is not an LP but a quadratic
programming problem. Finally, we are assuming that the decision variables can take on fractional, noninteger values, which may not always be realistic for the application at
hand. In Chapter \ref{C:Integer_Linear_Programming}
we discuss problems in which we desire only integer-valued solutions for one or more of our decision variables.

\subsection{Maple's \mf{LPSolve} Command}\label{S:LP_Prototype_Standard_Form_LPSolve}\index{Maple!\mf{LPSolve}}

\noi Maple's \mf{Optimization} package provides a convenient means for solving an LP such as
(\ref{E:Prototype_Standard_Form_FuelPro_LP}). A simple worksheet for doing so is given as follows:

\begin{maplelist}
\item restart;
\item with(Optimization);
\mo{[ImportMPS, Interactive, LPSolve, LSSolve, Maximize, Minimize, NLPSolve, QPSolve]}
\item \mf{f:=(x1,x2)->4*x1+3*x2;}
\mo{f:=(x1,x2) \rightarrow 4x_1+3x_2}
\item \mf{constraints:=[x1<=8,2*x1+2*x2<=28,3*x1+2*x2<=32];}
\mo{constraints:=[x_1\leq8,2x_1+2x_2\leq28,3x_1+2x_2\leq 32]}
\item \mf{LPSolve(f(x1,x2),constraints,`maximize', assume=nonnegative);}
\mo{\left[46., [x_1 = 4.000000000, x_2 = 9.999999999]\right] }
\end{maplelist}

\noi Maple's \mf{LPSolve} command yields a floating-point representation of the optimal
solution, $x_1=4$ and $x_2=10$, which corresponds to an objective value $z=f(4,10)=46$. Hence, \LP should produce 4 gallons of premium grade and 10 gallons of regular unleaded each hour in order to
maximize its profit, which equals \$ 4.60.

\newpar The general form of the \mf{LPSolve} command is given by
\begin{center}
\mf{LPSolve}(\mf{\emph{objective function}},\mf{\emph{list of constraints}},\mf{\emph{options}}).
\end{center}

\noi If no options are given, Maple minimizes the objective function by default and makes no assumptions regarding sign values of decision variables. In the preceding example, we have added options that maximize the objective function and require
nonnegative decision variables. Doing so
guarantees that \mf{LPSolve} obtains a solution coinciding with that of (\ref{E:LP_Prototype_Standard_Form_FuelPro_LP}).
In subsequent sections, we will elaborate on features of this command and how it can be used
to solve more complicated problems.

\newpar
In the \LP example, the LP has a unique optimal solution,
$\ds x_1=4  $ and $\ds x_2=10 $. As we shall discover
in Section \ref{S:LP_Graphical}, the solution of any
LP takes one of four general forms:
	\be
    \item The LP can be \emph{infeasible}\index{linear programming problem!infeasible}, meaning that its feasible region is the empty set.
	\item The LP can have a \emph{unique optimal solution}.
	\item The LP can have more than one optimal solution, in which case we say that it has \emph{alternative optimal solutions}\index{linear programming problem!alternative optimal solutions}.
	\item The LP can be \emph{unbounded}\index{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
When an LP is infeasible, Maple's \mf{LPSolve} command returns an error message, and
when the LP is unbounded, Maple returns a feasible solution along with a warning message.
When an LP has more than one solution, Maple returns one solution, overlooking the others.


\subsection{The Matrix Inequality Form of an LP}\label{S:LP_Prototype_Standard_Form_Matrix_Form}

\noi Matrix notation provides a convenient means for restating a linear programming problem such
as (\ref{E:Prototype_Standard_Form_FuelPro_LP}) in more compact form. Let us denote the matrix
	\[ A= \begin{bmatrix} 1 &  0 \\ 2 & 2 \\ 3 & 2 \end{bmatrix}\]
and the vectors
	$\ds  \vecc=\begin{bmatrix} 4 & 3 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} 8 \\ 28 \\32 \end{bmatrix}$, and
		$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.
Then (\ref{E:Prototype_Standard_Form_FuelPro_LP}) becomes

\begin{align}\label{E:LPStandardMatrixInequalityForm}
 \mbox{maximize } z &=\vecc \cdot \vecx   \\
	\mbox{ subject to} \notag\\
	A \vecx &\leq \vecb \notag \\
	\vecx &\geq \zerovec. \notag
	\end{align}
In this notation, a vector inequality such as $\ds A\vecx \leq \vecb$ means that the inequality is valid for every pair of corresponding entries in the
vectors. We shall refer to (\ref{E:LPStandardMatrixInequalityForm}) as the \emph{matrix inequality form}\index{linear programming problem!matrix inequality form} of
the LP.

\newpar
Maple's \mf{LPSolve} command accepts LP's expressed in matrix inequality form.\index{Maple!\mf{LPSolve}-matrix form} For example
(\ref{E:LPStandardMatrixInequalityForm}), can be solved as follows:

\begin{maplelist}
\item \mf{c:=Vector[row]([4,3]);}
\mo{c:=\begin{bmatrix} 4 & 3 \end{bmatrix}}
\item \mf{A:=Matrix(3,2,[1,0,2,2,3,2]);}
\mo{A:=\begin{bmatrix} 1 & 0 \\ 2 & 2 \\ 3 & 2 \end{bmatrix}}
\item \mf{b:=<8,28,32>;}
\mo{b:=\begin{bmatrix} 8 \\ 28 \\ 32 \end{bmatrix}}
\item \mf{LPSolve(c, [A, b], assume = nonnegative,'maximize');}
\mo{\begin{bmatrix} 46 & \begin{bmatrix} 4 \\ 10 \end{bmatrix} \end{bmatrix}}
\end{maplelist}

\noi Observe that Maple's output consists of a list. The first entry is the optimal objective value; the second entry is the corresponding vector of decision variable values.

\newpar
Through simple algebraic manipulations, we can express every LP in inequality form. For example, the LP given in (\ref{LP_Prototype_Standard_Form_Equality_Constraint}) has constraints
involving inequalities and equations.

\begin{align}
 \mbox{maximize } z &=f(x_1,x_2)=2x_1+3x_2  \label{LP_Prototype_Standard_Form_Equality_Constraint} \\
	\mbox{ subject to} \notag\\
	x_1+x_2 &\leq 6  \notag\\
	x_1+5x_2 &\geq 10 \notag \\
    2x_1-x_2 &= 3 \notag \\
	x_1,x_2 &\geq 0. \notag
	\end{align}	

\noi
The second constraint can be rewritten as $\ds -x_1-5x_2 \leq -10$. The third is the combination of two constraints, $\ds 2x_1-x_2 \leq 3$
and $-2x_1+x_2 \leq -3$. Thus, (\ref{LP_Prototype_Standard_Form_Equality_Constraint}) becomes

\begin{align*}
 \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} 1 &  1 \\ -1 & -5 \\ 2 & -1 \\ -2 & 1 \end{bmatrix}$,
$\ds \vecc=\begin{bmatrix} 2 & 3 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} 6 \\ -10 \\3 \\ -3 \end{bmatrix}$, and
		$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.

\noi Exercises in this section demonstrate other means for expressing LPs in matrix inequality form,
including those containing variables unrestricted in sign or those whose constraints
involve absolute values.

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

\input{Exercises/Exercises_Prototype_Standard_Form}
\endinput 