%% This document created by Scientific Notebook (R) Version 3.0


\documentclass[12pt,thmsa]{article}
\usepackage{amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{makeidx}
\usepackage{sw20jart}

%TCIDATA{TCIstyle=article/art4.lat,jart,sw20jart}

%TCIDATA{<META NAME="ViewSettings" CONTENT="31">}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="Title" CONTENT="Linear Programming">}
%TCIDATA{Created=Mon Aug 19 14:52:24 1996}
%TCIDATA{LastRevised=Mon Mar 31 11:26:13 1997}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=MathHelp.cst}
%TCIDATA{<LINK REL="begin" HREF="DM12-1.tex">}
%TCIDATA{<LINK REL="contents" HREF="DM0-0.tex">}
%TCIDATA{<LINK REL="end" HREF="DM12-6.tex">}
%TCIDATA{<LINK REL="next" HREF="DM12-6.tex">}
%TCIDATA{<LINK REL="parent" HREF="DM12.tex">}
%TCIDATA{<LINK REL="previous" HREF="DM12-4.tex">}
%TCIDATA{<LINK REL="top" HREF="DM0-0.tex">}

\input{tcilatex}
\begin{document}


\section{\label{Linear programming}Linear Programming\label{Constraints}}

A 
\index{Linear programming@Linear programming}\textsl{linear programming
problem} consists of minimizing (or maximizing) a linear function subject to
certain conditions or 
\index{Constraints@Constraints}constraints expressible as linear
inequalities.

\subsection{\ \label{Simplex algorithm}The Simplex Algorithm}

The basic purpose of the simplex algorithm is to solve linear programming
problems. In the following example, the function $f(x,y)=x+y$ is to be
maximized subject to the two inequalities shown. The function $f(x,y)$ is
the 
\index{Objective function@Objective function}\label{Objective function}%
\textsl{objective function}, and the set of linear constraints is called the 
\textsl{linear system}.\medskip

\begin{quote}
$\blacktriangleright $ \label{Simplex, maximize}To enter a linear
programming problem with two constraints
\end{quote}

\begin{itemize}
\item  Create a $3\times 1$ matrix.

\item  Type the function to be maximized in the first row.

\item  Type the linear constraints in the subsequent rows.

\item  Leave the insertion point in the matrix.

\item  From the 
\index{Simplex method@Simplex method}\label{Simplex method}\textsf{Simplex}\
submenu, choose\textsf{\ Maximize}.\medskip 
\end{itemize}

\begin{quote}
$\blacktriangleright $ \textsf{Simplex +\ Maximize}
\end{quote}

\begin{quotation}
$\left[ 
\begin{array}{c}
x+y \\ 
4x+3y\leq 6 \\ 
3x+4y\leq 4
\end{array}
\right] $, Maximum is at: $\left\{ x=%
\frac{12}{7},y=-\frac{2}{7}\right\} \medskip $
\end{quotation}

\label{Simplex,minimize}Of course, these are the same coordinates that
minimize $-x-y$. In the following linear programming problem, click the
matrix, and from the \textsf{Simplex}\ submenu choose\textsf{\ Minimize}%
.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Simplex + Minimize}
\end{quote}

\begin{quotation}
$
\begin{array}{c}
-x-y \\ 
4x+3y\leq 6 \\ 
3x+4y\leq 4
\end{array}
$, Minimum is at: $\left\{ y=-\frac{2}{7},x=\frac{12}{7}\right\} $
\end{quotation}

\ 

\subsection{\ \label{Feasible system}Feasible Systems}

Two things may prevent the existence of a solution. There may be no values
of $x$ and $y$ satisfying the constraints. Even if there are such values,
there may be none maximizing the objective function. If there are values
satisfying the constraints, the 
\index{Feasible system@Feasible system} 
\index{Simplex@Simplex!feasible@feasible}system is called \textsl{feasible}.

The following example illustrates a set of inequality constraints with no
function to be maximized or minimized. You can ask whether the constraints
are feasible---that is, whether they define a nonempty set. Just click the
matrix, and from the \textsf{Simplex}\ submenu choose \textsf{%
Feasible.\medskip }

\begin{quote}
$\blacktriangleright $ \textsf{Simplex + Feasible?}
\end{quote}

\begin{quotation}
$
\begin{array}{r}
4x+3y\leq 6 \\ 
3x+4y\leq 4 \\ 
x\geq 0 \\ 
y\geq 0
\end{array}
$, Is feasible? true

$\ $

$
\begin{array}{c}
4x+3y\leq 6 \\ 
4x+3y\geq 7
\end{array}
$, Is feasible? false\medskip
\end{quotation}

Saying that the system $
\begin{array}{c}
4x+3y\leq 6 \\ 
4x+3y\geq 7
\end{array}
$ is not feasible implies, in particular, that there are no values
minimizing the objective function in the problem $
\begin{array}{c}
x+y \\ 
4x+3y\leq 6 \\ 
4x+3y\geq 7
\end{array}
\,$.\bigskip

\subsection{\ \label{Standard form}Standard Form\label{Simplex, standardize}}

A system of linear inequalities is in 
\index{Linear programming@Linear programming!standard form@standard form}%
\textsl{standard form} when all the inequalities are of the form $\leq $. To
convert a system of linear inequalities to a system in standard form, choose 
\textsf{Standardize} from 
\index{Simplex@Simplex!standardize@standardize}the \textsf{Simplex}
submenu.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Simplex + Standardize}
\end{quote}

\begin{quotation}
$
\begin{array}{r}
4x+3y\leq 6 \\ 
3x+4y\leq 4 \\ 
x\geq 0 \\ 
y\geq 0
\end{array}
$, System in standard form is: $
\begin{array}{c}
4x+3y\leq 6 \\ 
3x+4y\leq 4 \\ 
-x\leq 0 \\ 
-y\leq 0
\end{array}
$
\end{quotation}

\ 

With a linear function added, you can maximize the resulting linear
programming problem.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Simplex + Maximize}
\end{quote}

\begin{quotation}
$
\begin{array}{r}
x+3y \\ 
3x-y\leq 4 \\ 
4x+3y\leq 6 \\ 
-y\leq 0 \\ 
-x\leq 0
\end{array}
$, Maximum is at: $\left\{ x=0,y=2\right\} $
\end{quotation}

\ 

\subsection{\ \label{Dual of a linear program}The Dual of a Linear Program}

The other item on the \textsf{Simplex} menu 
\index{Simplex@Simplex!dual@dual}is \textsf{Dual}. It computes the 
\index{Dual of a linear progam@Dual of a linear progam}dual of a linear
program.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Simplex + Dual}
\end{quote}

\begin{quotation}
$
\begin{array}{r}
x+y \\ 
4x+3y\leq 6 \\ 
3x+4y\leq 4 \\ 
x\geq 0 \\ 
-y\leq 0
\end{array}
$, Dual system is: $
\begin{array}{c}
6s_{1}+4s_{2} \\ 
1\leq 3s_{1}+4s_{2}-s_{4} \\ 
1\leq 4s_{1}+3s_{2}-s_{3}
\end{array}
$
\end{quotation}

\ 

Applying the simplex algorithm to these two linear programs yields the
following results.

\begin{quote}
$\blacktriangleright $ \textsf{Simplex + Maximize}
\end{quote}

\begin{quotation}
$
\begin{array}{r}
x+y \\ 
4x+3y\leq 6 \\ 
3x+4y\leq 4 \\ 
x\geq 0 \\ 
-y\leq 0
\end{array}
$, Maximum is at: $\left\{ y=0,x=%
\frac{4}{3}\right\} $
\end{quotation}

\begin{quote}
$\blacktriangleright $ \textsf{Simplex + Minimize}
\end{quote}

\begin{quotation}
$
\begin{array}{l}
6s_{1}+4s_{2} \\ 
1\leq 4s_{1}+3s_{2}-s_{4} \\ 
1\leq 3s_{1}+4s_{2}-s_{3} \\ 
s_{1}\geq 0 \\ 
s_{2}\geq 0 \\ 
s_{3}\geq 0 \\ 
s_{4}\geq 0
\end{array}
$, Minimum is at: $\left\{ s_{4}=0,s_{1}=0,s_{2}=\frac{1}{3},s_{3}=\frac{1}{3%
}\right\} $
\end{quotation}

\ 

\subsection{\ Related topics}

\hyperref{Solving Equations}{}{}{DM12-1.tex#Integer solutions}

\hyperref{Integers Modulo m}{}{}{DM12-2.tex#Integers modulo m}

\hyperref{Other Systems Modulo m}{}{}{DM12-3.tex#Matrices modulo m}

\hyperref{Polynomials Modulo Polynomials}{}{}{DM12-4.tex#Polynomials modulo
polynomials}

\hyperref{Exercises and Solutions}{}{}{DM12-6.tex#Exercises}

\rule{0.67in}{0.01in}

\hyperref{\FRAME{itbpF}{0.5275in}{0.3399in}{0.0519in}{}{}{index.wmf}{\special%
{language "Scientific Word";type "GRAPHIC";display "PICT";valid-file
"F";width 0.5275in;height 0.3399in;depth 0.0519in;original-width
36.875pt;original-height 22.5625pt;cropleft "0";croptop "1";cropright
"1";cropbottom "0";filename 'index.wmf';file-properties "XNPEU";}}}{}{}{%
DMIndex.tex#Math Index}\quad {\small Index entries: \hyperref{Applied modern
algebra}{}{}{DMIndex.tex#Applied modern algebra}, \hyperref{Linear
programming}{}{}{DMIndex.tex#Linear programming}, \hyperref{Matrices}{}{}{%
DMIndex.tex#Matrices}, \hyperref{Simplex}{}{}{DMIndex.tex#Simplex}}

\end{document}
