\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:
