\chapterimage{./small/co2}
\chaptertext{Linear programming is a simple technique where we depict complex
relationships through linear functions and then find the optimum points. A
linear programming problem involves a particular function, whose maximum (or
minimum) is of interest. But other restrictions apply to the situation which
could complexify our problem.}
\chapter{Linear Programming}
\section{Linear functions}
\subsection{Slope-intercept equation}
The graph of a linear function is a straight line. A linear function looks like
$f(x)=mx+b$, where $m$ and $b$ are constants. These constants are very
significant:
\begin{itemize}
\item the number $m$ is the \emph{slope} of the line
\item the number $b$ is its \emph{$y$-intercept}. The $y$-intercept of any graph
is the place where it crosses the $y$-axis and the $x$-intercept is of course
the place where it crosses the $x$-axis.
\end{itemize}
The $y$-intercept is found by setting $x=0$ and then determining what $y$ is.
\begin{recherche}
Does any line have a slope?
\end{recherche}
Now, to see the significance of the slope, set $x=1$ and substitute:
\begin{itemize}
\item when $x=1$, $y=1$
\item when $x=1$, $y=m+b$
\end{itemize}
This says that a one-unit change in $x$ results in a $m$-unit change in
$y$. This is why $m$ is called the \emph{slope} of the line: it tells how
steep it is. If you look at any two points on your line and measure the
horizontal change and the vertical change from one point to the other, then
the slope is:
$$m=\frac{\mathrm{vertical\ change}}{\mathrm{horizontal\ change}}$$
\setindent{0cm}
\begin{multicols}{2}
%\begin{figure}
\begin{center}
\includegraphics[height=4cm]{./small/taxicab}
\end{center}
% \end{figure}
%\begin{figure}
\begin{center}
\includegraphics[height=4cm]{./small/pacmove}
\end{center}
% \end{figure}
\end{multicols}
\setindent{\indentationcours}
Think about the taxicab geometry or pacman geometry...
Hence the formula, knowing two points $(x_1,y_1$ and $(x_2,y_2$:
$$m=\frac{y_2-y_1}{x_2-x_1}$$
%\begin{figure}
\begin{center}
\includegraphics[height=5cm]{./small/slope}
\end{center}
%\end{figure}
Let us sum up what we saw so far:
\begin{itemize}
\item if $m>0$ the linear function is increasing, i.e. the graph is rising from
left to right;
\item if $m<0$ then the linear function is decreasing, or its graph is falling
as you go from left to right;
\item if $m=0$, then the line is horizontal; the linear function is constant.
\end{itemize}
\begin{NB}
The slope is also called the \emph{gradient}.
\end{NB}
\subsection{Graphs}
Linear finctions have, of course, the easiest kind of graph. All you need are
two points, and any two points uniquely determine a line.
We just saw one way to graph a linear function: the slope-intercept way. Start
at the $y$-intercept, move right 1 unit, then move up or down $m$ units to get
your second point.
\sm
Another way to graph a line is to determine both the $y$-intercept and the
$x$-intercept.
\begin{recherche}
There may be a problem with graphing by using the two intercepts: which one?
\end{recherche}
%\begin{figure}
\begin{center}
\includegraphics[height=7cm]{./small/paths}
\end{center}
%\end{figure}
You can of course use your calculator and press the magic \texttt{graph} key.
\begin{recherche}
Graph $y=\num{10000} - \num{0.2}x$ on your calculator and show intercepts.
\end{recherche}
\begin{exemple}
Find the slope and both the $y$-intercept and the
$x$-intercept for the line with the following equation:
$$5x+2y=10$$
$5x+2y=10$ may be written as $y=-2.5x+5$
Gradient $=-2.5$ and $y$-intercept is (0,5).
Let the $x$-intercept be $(d,0)$. Then from the original equation:
\begin{align*}
5d+2×0&=10\\
5d&=10\\
d&=2
\end{align*}
The line intersects with the $x$-axis at $(2,0)$.
\end{exemple}
\begin{recherche}
For each of the following equations, sketch a graph marking where the line
crosses each of the axes and state its gradient.
\begin{multicols}{2}
\begin{enumerate}
\item $x+2y+7=0$
\item $\frac{1}{8}x+\frac{5}{4}y=6$
\item $1654.3x -2412.4y=120$
\item $y=7$
\end{enumerate}
\end{multicols}
\end{recherche}
\section{Systems of Linear Equations}
When solving a system of linear equations, the following three operations are
used:
\begin{enumerate}
\item interchange two equations;
\item Replace any equation by a non-zero multiple of that equation;
\item Replace any equation by itself plus a multiple of another.
\end{enumerate}
Solving a system of equations using these operations is called solving by
elimination of variables.
\begin{exemple}
Solve the $2×2$ system:
\begin{cases}
x+y=5\\
3x-4y=1
\end{cases}
The variable $y$ can be eliminated by replacing the second equation by
itself plus 4 times the first equation:
\begin{cases}
x+y=5\\
4(x+y) + 3x-4y= 4×5 + 1
\end{cases}
\begin{cases}
x+y=5\\
4x+4y + 3x-4y= 21
\end{cases}
\begin{cases}
x+y=5\\
7x= 21
\end{cases}
and hence
\begin{cases}
x+y=5\\
x= 3
\end{cases}
To find $y$, we substitute $x=3$ into the first equation. We get:
\begin{cases}
3+y=5\\
x= 3
\end{cases}
so
\begin{cases}
y=2\\
x= 3
\end{cases}
The solution to the system is $x=3$, $y=2$.
Geometrically, this solution gives
the coordinates of the point of intersection of the graph of the two equations.
\end{exemple}
\begin{recherche}
Write your own problem involving solving a system of linear equations
\end{recherche}
\section{Graphing linear inequalities in two variables}
\begin{recherche}
What could be the solution set of $5x+2y \leqslant 17$?
\end{recherche}
When graphing an equation, the solution are all the points on the line. When
graphing an inequality, the solution are all the points above or below the
line. One method of determining which side to shade is to choose any convenient
test point (the origin...) anywhere on the graph (except the line!). Then
substitute to determine if it makes the inequality true at the test point. Then
shade the incorrect side of the boundary line.
\section{Linear programming: a graphical approach}
%$
\subsection{The origin: the diet problem}
In the 1930's, the U.S. military wanted to find the minimum-cost diet that would
satisfy a soldier's nutritional requirements. An economist, George
\textsc{Stigler} considered 77 different foods, and nine nutritional
requirements. He used an empirical method to estimate the solution at
\$39.93/year. He published his solution in 1945. In 1947, an algorithm was
published by George \textsc{ Danzig}. He had to wait for the war to finish
before making his \textit{simplex algorithm} public. Leonid \textsc{Kantorovich}
made the same discoveries a little bit in Soviet Union but had to give up his
work...
\subsection{Formulating the diet problem as a linear program}
Introduce a variable for each food: $x_1,\, x_2,\dots, x_{77}$. Variable $x_j$
represents the number of units of food $j$ in the diet. For instance $x_1$ might
denote the number of pounds of navy beans to be consumed per day. For each
variable $x_j$ we have an associated cost $c_j$. For example, $c_1$ might be the
cost in dollars of a single pound of navy beans.
The \textit{objective function} is the cost $c_1x_1+c_2x_2+\cdots c_{77}x_{77}$
and the goal is to \textit{minimize} the cost subject to the \textit{constrains}.
To represent each nutritional requirement, we have a linear inequality which can
be written as:
$$a_1x_1+\cdots+a_{77}x_{77}\geqslant b$$
Suppose we want to represent the requirement that someone take in 2000 calories
a day. The number $a_1$ should be the number of calories in a pound of navy
beans,..., $a_{77}$ should be the number of calories in one unit of food 77, and
$b$ should be 2000.
In this context, a linear inrquality is called a linear \textit{constraint}
because it constrains the solution. We have a similar constraint for calcium,
Vitamin A, Riboflavin, ascorbic acid,...
It turns out that the formulation so far is insufficient, because it doesn't
prevent the solution from including negative amounts of some of the foods. No
problem: just add a new linear constraint for each variable $x_j$:
$$x_j \geqslant 0$$
\paragraph{Terminology}
\begin{itemize}
\item A ``vector'' $(x_1, x_2,\dots, x_{77})$ that satisfies the constraint is said to
be a \textit{feasible} solution of the LP.
\item The LP is said to be \textit{feasible} if there exists a feasible solution.
\item The \textit{value} of a feasible solution $(x_1, x_2,\dots, x_{77})$ is
$(x_1, x_2,\dots, x_{77})$.
\item The \textit{value} of a LP is the minimum value of a feasible solution.
\item A feasible solution is said to be an \textit{optimal} solution if its
value is that of the LP.
\end{itemize}
\begin{DANGER}
\textbf{No strict inequalities!} Strict inequalities are not allowed.
\end{DANGER}
\subsection{geometry of LP: polyhedra and vertices}
In order to draw the situation, we will consider only two kinds of food: lard
and rice. Let $x$ be the number of pounds of lard, and let $y$ be the number of
pounds of rice.
The nutritional requirements are for instance at least 5 units of iron knowing
that lard has got 20 units of iron by pound and rice 2 units by pound. This
nutritional requirement is expressed by the constraints $10x+2y \geqslant 5$.
Let $x+2y \geqslant 1$ and $x+8y \geqslant 2$ be two other constraints.
The
cost, which is to minimise, is 13 cents per pound of lard and 8 cents per pound
of rice. Thus the objective function is $13x+8y$.
There are two other constraints: $x \geqslant 0$ and $y \geqslant 0$.
Consider a linear constraint. It divides the space into two halves, which are
called \textit{half-spaces}. One half-space is allowed by the constraint and the
other is forbidden.
When you have several linear constraints, each one defining an allowed
half-space, the feasible region is the intersection of these half-spaces. The
intersection of a finite set of half-spaces is called a \textit{polyhedron}.
In our situation, the space is a plane and therefore the polyhedron is a polygon.
A \textit{vertex} of the polyhedron is the intersection of two
\textit{boundaries} that is feasible.
The big result is the following:
\begin{center}
\begin{quote}
\textbf{There is an optimal solution that is a vertex of the polyhedron}
\end{quote}
\end{center}
How to find it graphically?
%\begin{figure}
\begin{center}
\includegraphics[height=10cm]{diet1}
\end{center}
% \end{figure}
\begin{recherche}[Bac 2015]
A company produces and sells two models of lamps, L1 and L2. To produce each
lamp, the manual work needed for model L1 is 20 minutes and for model L2, 30
minutes.
The machine needs 20 minutes to produce L1 and 10 minutes to produce L2.
The manual work available per month is 100 hours and the machine is limited to
only 80 hours per month.
The profit per unit for L1 is \$15 and \$10 for L2. The company wants to
maximise its profit.
\begin{enumerate}
\item Write the objective function.
\item Write the constraints as a system of inequalities.
\item Use a graph to find the set of feasible solutions.
\item Deduce the quantities of each lamp that should be produced to obtain
the maximum profit.
\end{enumerate}
\end{recherche}
\begin{recherche}[Bac 2015]
School is about to start again. A store is planning to sell school
material. They have 600 notebooks, 500 folders and 400 pens in stock, which
they will pack in two different ways. In the first package, there will be 2
notebooks, 1 folder and 2 pens, and in the second one 3 notebooks, 1 folder
and 1 pen. The price of each package will be £6.50 and £7.00 respectively.
The store wants to maximise their profit.
\begin{enumerate}
\item Write the objective function.
\item Write the constraints as a system of inequalities.
\item Use a graph to find the set of feasible solutions that graphically
represent the constraints.
\item How many packages of each type should they put together to obtain
maximum profit?
\end{enumerate}
\end{recherche}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "PolyDNLTS2018_19"
%%% End: