Brain Dump

Linear Programming

Tags
math

Is a decision making process where you form constraints from a problem that needs to be solved, plot it and then use a sliding line or corner checking to optimise some reward or minimise some cost.

The actual process is:

  1. Identify the decision variables: These are the quantities we need to find to solve the problem, we denote them by \( x, y \).
  2. Identify the objective to be maximised/minimised: For example the maximum profit or minimum cost.
  3. Identify the constraints; These will be in the form of inequalities.
  4. Draw the graph: with a line for each inequality and shading in the unwanted-region.
  5. Find at what point the decision is optimal: This can involve either:
    • Drawing an objective line and then sliding to the extreme to find the optimal solution.
    • Check corners of the required region to find the solution which achieves the objective. You may have to check nearby integer solutions.

Formulating Constraints example

This is kind of an involved process, but in general you'll want to look out for keywords restricting the objective of the problem.

For example

A supermarket has 20 checkouts which are staffed by experienced or trainee till operators. Experienced operators serve an average of 15 customers per hour, trainees an average of 10. The store needs a serving capacity of at least 210 customers per hour. Union regulations dictate there must be fewer trainees than experienced staff on the tills at any time. Management policy is that the ratio of trainees to experienced staff is at least \( 1:3 \) to keep costs down. Experienced till operators are paid £7.50 per hour and trainees £5.00 per hour.

Formulate this is a linear programming problem.

First we must establish our objective, in this case we want to minimise costs which is \[ C = 7.5E + 5T \]

The store wants a serving rate of at least 210 customers per hour, meaning the training and experienced workers together must supply a capacity of at least this \[ 15E + 10T \geq 210 \]

Each employee can only serve one till and at max there're 20 tills therefore \[ E + T \leq 20 \]

There must be at least 1 experienced operator for every 3 trainees \[ E \leq 3T \]

And the store must have at least one employee operating each till \[ E \geq 0, T \geq 0 \]

These are all the constraints for this problem.

Optimising the Goal sec:opt-goal example

For example

Becky's bird food company makes two typess of bird food,one type is for bird feeders and the other for bird tables. Let \( x \) represetn the quantity of food made for bird feeders and \( y \) represetn the quantity of food made for bird tables. Due to restrictions in the production prodcess and known demand, the following constraints apply:

\begin{align} \label{eq:lp.1} x + y \leq 12cm \
\label{eq:lp.2} y \leq 2x \
\label{eq:lp.3} 2y \geq 7 \
\label{eq:lp.4} y + 3x \geq 15 \end{align}

The cost that we want to minimise is

\begin{align} \label{eq:lp.obj} C = 2x + 5y \end{align}

First we can establish the constraints that \( x \geq 0 \) and \( y \geq 0 \).

\begin{figure}
  \centering
  \begin{tikzpicture}
    \def\width{10}
    \def\height{15}
    \def\step{0.1}
    \def\shadeh{0.4}
    \begin{axis}[xmin=0, ymin=0, domain=0:\width, xmax=\width, ymax=\height,
		 axis lines=left, xlabel=\( x \), ylabel=\( y \)]
      \addplot[black, ultra thick, mark=none, forget plot] coordinates {(0, \height) (0, 0)};
      \addplot[black, ultra thick, mark=none, forget plot] coordinates {(\width, 0) (0, 0)};

      \addplot[blue] {12 - x};
      \addlegendentry{\( x + y \leq 12 \)}
      \pgfplotsinvokeforeach{0, \step,...,10}{
	\draw[blue] (#1, 12 - #1) -- (#1 + \step, {12 - ( #1 + \step ) + \shadeh});
      }

      \addplot[red] {2 * x};
      \addlegendentry{\( y = 2x \)}
      \pgfplotsinvokeforeach{0, \step,...,10}{
	\draw[red] (#1, 2 * #1) -- (#1 - \step, {(2 * ( #1 + \step )) + \shadeh});
      }

      \addplot[magenta] {7/2};
      \addlegendentry{\( 2y = 7 \)}
      \pgfplotsinvokeforeach{0, \step,...,10}{
	\draw[magenta] (#1, 7 / 2) -- (#1 - \step, {(7 / 2) - \shadeh});
      }

      \addplot[green] {- 3 * x + 15};
      \addlegendentry{\( y + 3 x \geq 15 \)}
      \pgfplotsinvokeforeach{0, \step,...,10}{
	\draw[green] (#1, - 3 * #1 + 15) -- (#1 - \step, {(- 3 * (#1 + \step) + 15) - \shadeh});
      }

      \node at (5,5) {R};
    \end{axis}
  \end{tikzpicture}
  \caption{A plot of the constraints outlined in \autoref{sec:opt-goal}.
The shaded directions indicate which direction the inequality affects.
The direction across the line that isn't shaded is the active region where the
inequality holds.}
  \label{fig:shaded-lp-eg}
\end{figure}

You can see a plot of these constraints including the direction of the inequality in fig:shaded-lp-eg. The shaded region R is the area remaining after removing the regions excluded by all the constraints. The \( x, y \) values which give the optimum value of \( C \) lies within this area.

Now we can either find the intersection points between constraints forming the line \( R \) and exhaustively calculate \( C \) for each of them to get the point which minimises cost, or we can plot the cost-line. The latter approach has us draw a straight matching the formula of the cost equation \( y = - \frac{2}{5} x \). We intend to vary the value of \( C \) so we can disregard it while plotting this line. Our goal is to minimise \( C \) so we take an outline of this line and drag it downwards, recording where the cost-line last touches \( R \), that is the point that minimises cost.

\begin{figure}
  \centering
  \begin{tikzpicture}
    \def\width{10}
    \def\height{15}
    \begin{axis}[xmin=0, ymin=0, domain=0:\width, xmax=\width, ymax=\height,
		 axis lines=left, xlabel=\( x \), ylabel=\( y \)]
      \addplot[black, ultra thick, mark=none, forget plot] coordinates {(0, \height) (0, 0)};
      \addplot[black, ultra thick, mark=none, forget plot] coordinates {(\width, 0) (0, 0)};

      \addplot[blue, forget plot] {12 - x};
      \addplot[red, forget plot] {2 * x};
      \addplot[magenta, forget plot] {7/2};
      \addplot[green, forget plot] {- 3 * x + 15};

      \addplot[black, ultra thick] {7 - 2 * x / 5};
      \addlegendentry{\( C = 2x + 5y \)}
      \draw [->, black, ultra thick] (5, {7 - 2 * 5 / 5}) -- (5 - 0.1, {7 - ((2 - 0.1) * 5 / 5) - 1.2});

      \node at (4.1,7) {R};
      \node [draw, circle] at ({(15 - (7 / 2)) / 3}, 7 / 2) {Z};
    \end{axis}
  \end{tikzpicture}
  \caption{Variant of \autoref{fig:shaded-lp-eg} with the shading removed and the
cost-line drawn on with an initial cost of 7.
The point \( Z \) is marked as the point where the cost is minimised.}
  \label{fig:shaded-lp-fit-line}
\end{figure}

In figure fig:shaded-lp-fit-line you can see fig:shaded-lp-eg with the cost-line and direction you need to travel to minimise cost drawn on. If you travel along the cost-line the last corner of the region \( R \) that you'll meet is \( Z \). This is the point that minimises the cost.