Taking a look into an application of Linear Programming in supply chain operations

Photo by Guillaume Bolduc on Unsplash

If you’re looking for a jupyter notebook that goes a bit more in-depth check out this notebook

While some companies may not have physical goods in the world of today many still do and for these companies, it is important to not waste any materials as that means a waste of money.

We will look at a linear problem where given we have physical products and we only have a finite amount of materials to make those products, how do we maximize the amount of return we get back. We will do that by creating a linearly constrained optimization problem and show by example.

Now, lets set up an example problem.

1. What are we selling and for how much? In today’s day in age, it may not be the wisest move to join the furniture game but that is what we will be modeling today. Imagine we are a small furniture company and we sell two products, tables and chairs both going for $30 and $45 respectively. (These are some fancy chairs but the tables are only subpar)

2. How much material does each product take? So In order to make a table, it takes 22 wood and 15 steel and for a chair, it takes 45 wood and 10 steel. In other words, this is how much we remove from the available materials for every table and chair made.

3. How much total material available? In this problem, we will set the available materials as 5500 wood and 2500 steel to work with.

   Note: I don’t use any specific units, so standardize the units if you plan on using this method Double Note: We will be using a graphical method to solve our problem but you can use a library like CVXPY to construct your problem and use a solver to get a solution. If you want to learn more about the methods used to solve a linear or convex problem checkout the Simplex or the Interior Point methods

Now that we have a general idea of the problem we want to define the problem in a concrete form and we will do that by splitting it up into two parts the objective function (ie the part we want to maximize) and the inequalities constraints (ie the thresholds we must maintain).

The Objective function

The objective of the problem is to maximize profits. This is done by selling the correct amount of each item such that we obtain the most amount of money. We can represent this by the function below

Max f(t, c) = t30 + c45

where t and c are the amount of tables and chairs we sell respectively

We can generalize this to vectors and matrices but we will keep it this way for the sake of this toy problem

We can see that if we can get the perfect combination of values for t and c then we can maximize our profits while still efficiently using the materials at hand.

The Inequality Constraints

The inequality constraints are what tell us when we are using too much of a material that would otherwise force the problem out of the feasibility zone (ie we don’t have that much material available so it’s not possible).

Now we know we have 5500 wood and 2500 steel to use. So we can start by creating the inequality constraint for the wood. It takes 22 wood for every table and 45 wood for each chair. So we can translate this into a statement like

h1(t, c) = t22 + c45 ≤ 5500

and we can do something similar for our steel constraint

h2(t, c) = t15 + c10 ≤ 2500

and for sake of completeness, we need to include that we want zero or more or each item as negative tables and chairs don’t make sense.

h3(t, c) = t ≥ 0

h4(t, c) = c ≥ 0

We can now use these inequality constraints in our problem now.

Constructing the final problem and solving graphically

Now that we have gotten the pieces we can now finally put them all together. This is what would look like.

Maximize f(t, c) = t30 + c45

Subject to

h1(t, c) = t22 + c45 ≤ 5500

h2(t, c) = t15 + c10 ≤ 2500

h3(t, c) = t ≥ 0

h4(t, c) = c ≥ 0

Now, normally you would solve this problem with some sort of iterative methods like simplex or the interior point method. But since it is only two variables (tables and chairs) we can solve this graphically.

made on desmos

When graphing this I simply took the constraints and just arranged the variable c (chairs) to be alone on the left-hand side. Making the number of tables purchased the y-axis and chairs the x-axis

This leaves us with a feasible region in the white space which is also a polynomial.

Now when solving graphically we will take a similar (not exact) approach the simplex method takes by looking at the corner point solutions.

Note: The simplex method does not look at all the points then compares rather it uses slack variables to be able to tell if has hit an optimal point but other than that it does visit the corner points

We have 4 points we want to look at (0, 0), (166.667, 0), (126.374, 60.44), (0, 122.222). If we then plug these coordinates into our objective function we can see which one yields the best result

f(0,0) = 0

f(166.667, 0) = 5000.01

f(126.374, 60.44) = 6,511.02

f(0, 122.222) = 5499.99

We can see that the corner point of (126.374, 60.44) gives the best result. Notice that we don’t get whole values as this may be a point of improvement that can be made by doing integer programming but that’s something for another article.

Conclusion

We saw that given a problem with variables that are made up of physical materials we can maximize the amount of money we can get by using linear programming. Hopefully, this article piqued your interest in Mathematical Optimization as it is an interesting field and is useful to many real-life scenarios.

If you liked this article and want to see more of my work check out www.kevinpallikunnel.com and feel free to send me an email I’d love to chat.