## 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**.

## Basic Problem

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!

## Formulation

If we let ** x** be pastries and

**be coffee, then we want to maximise the following objective function,**

*y***as a function of the decision variables:**

*c,*Subject to the following constraints:

The decision variables need to be non-negative.

Now it is time to plot these constraints!

## Plotting

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.