An introduction to linear programming and how to solve it using the graphical and simplex algorithms
Linear programming (LP) is an optimisation technique that is used to find the best solution, from a specified objective function, subject to some constraints. It is applied in sundry industries ranging from finance to e-commerce, so it’s well worth knowing if you are a Data Scientist. The key feature of LP is the linear part, which means that the constraints and objective function are all formulated as a linear relationship. In this post, we will run through an example LP problem and how it can be solved using the simplex algorithm and the graphical method.
We will start with the graphical method as thats the simplest to understand and gives us real intuition behind LP.
Let’s say we run a small business selling smoothies for £3 and coffees for £2, these are our two decision variables. Due to our ingredient constraints, we can only produce 75 smoothies and 100 coffees daily. Furthermore, we only have 140 cups available each day to serve our smoothies and coffees. Now, let’s formulate this as an LP problem!
If we let x be pastries and y be coffee, then we want to maximise the following objective function, c, as a function of the decision variables:
Subject to the following constraints:
The decision variables need to be non-negative.
Now it is time to plot these constraints!
As this is a two-dimensional problem, we can plot the constraints on a cartesian graph as straight lines (the linear part!):
The grey area is known as the feasible region, where any solution is valid as it satisfies the constraint.