Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Maths in a minute: Some basic linear programming

      26 April, 2017
      Pineapple

      How many of these should you plant?

      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 \pounds3 on the cocoa, and of \pounds2 on the pineapples. Your total return P will therefore be P=3x+2y. That's the amount you'd like to maximise. However, planting also comes with a cost. The unit cost of cocoa seed is \pounds2, and of pineapple seed is \pounds1, and there's an upfront cost \pounds4 just to use the field in the first place. The total cost C of growing the two crops is given by C=2x+y+4. You only have \pounds50 in the bank, so you need the total cost to be less than that: C=2x+y+4≤50. The size of the field also provides a constraint. If the amount of space taken up by a unit cocoa is 1m2 and by a unit pineapple is 1m2 then the total amount of space S taken up in the field by our two crops is given by S=x+y. The size of your plot is 30m2, so S cannot exceed this value: S=x+y≤30 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.
      Graphs

      The red line represents y = -2x + 46 and the blue line represents y = -x + 30. The values of x and y are both positive in the top right quadrant of the coordinate system. Hence, the shaded region contains all the values of x and y that satisfy all the 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×16+2×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.

      • Log in or register to post comments

      Read more about...

      linear programming
      graphical methods
      Maths in a minute
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms