Maths in a minute: Some basic linear programming

Imagine you have an allotment and you want to make some money by planting and selling two crops, cocoa and pineapples (you're lucky to live in a warm country). You obviously want to maximise your return, but you're constrained by how much money you can spend up front and by the size of your plot. How much of each crop should you plant?

This sounds like one of those headachey word problems we all know from school, but it turns out that it has a neat graphical solution. Let's write $x$ for the amount of cocoa you'll plant and $y$ for the amount of pineapples. Suppose that when you harvest the crops you'll get a unit return of $\pounds 3$ on the cocoa, and of $\pounds 2$ on the pineapples. Your total return $P$ will therefore be \begin{equation}P=3x+2y.\end{equation} That's the amount you'd like to maximise. However, planting also comes with a cost. The unit cost of cocoa seed is $\pounds 2$, and of pineapple seed is $\pounds 1$, and there's an upfront cost $\pounds 4$ just to use the field in the first place. The total cost $C$ of growing the two crops is given by \begin{equation}C=2x+y+4.\end{equation} You only have $\pounds 50$ in the bank, so you need the total cost to be less than that: \begin{equation}C=2x+y+4 \leq 50.\end{equation} The size of the field also provides a constraint. If the amount of space taken up by a unit cocoa is $1m^2$ and by a unit pineapple is $1m^2$ then the total amount of space $S$ taken up in the field by our two crops is given by \begin{equation}S = x+y.\end{equation} The size of your plot is $30m^2$, so $S$ cannot exceed this value: \begin{equation}S = x+y \leq 30\end{equation} It's also clear that $x$ and $y$ both need to be greater than or equal to $0$ (you can't plant a negative amount of crops). Here's how to solve the problem. First, consider a Cartesian coordinate system with the $x$-axis representing cocoa and the $y$-axis representing pineapples. Rewriting inequality 3 and turning it into an equation gives $y=-2x+46,$ the equation of a line. The points $(x,y)$ satisfying inequality 3 are those points that lie underneath that line. Similarly, the points that lie underneath the line $y=-x+30$ satisfy inequality 5. Remembering that both $x$ and $y$ need to be greater than or equal to $0$, we see that the shaded line in the graph below gives us the points in the $(x,y)$-plane satisfying all constraints.

Now what about maximising $P$? Rewriting equation 1 we see that $y=-3/2x+P/2.$ Whatever the value of $P$, this equation gives a line of slope $-3/2$. By increasing the value of $P/2$ from $0$ upwards (use the slider in the Geogebra applet below), we see that the last contact point between the line $y=-3/2x+P/2$ and the shaded region occurs at the corner point $A=(16,14)$ of the shaded region. That's the point for which $P$ is maximised but the constraints are still satisfied. Hence you should plant $x=16$ units of cocoa and $y=14$ units of pineapples. Your return will be $P = 3 \times 16 + 2 \times 14 = 76.$

Even if the green line, representing the relationship of $P$ and $x$ and $y$, had a different slope, you can convince yourself that $P$ is always maximised at one of the corner points of the shaded region. This is true whatever the numbers in equations 1, 2 and 4. As long as these equations are linear (ie don't involve any powers of $x$ and $y$ or their products), you can solve the problem by finding a shaded region using the constraints, and then working out for which of its corner points $P$ is largest.

Our method is an example of a linear programming problem, which involves optimising a quantity subject to restraints, when all the relationships are linear. The method can be extended to work with more constraints (this simply gives you a shaded region possibly bounded by more lines) and also to work when more than two variables (crops) are involved. The extended method is called the simplex algorithm. It was invented in 1947 by George Dantzig and has a huge range of applications.