Introduction to Linear Programming

https://miro.medium.com/max/1200/0*uJ8czSiS3nwAa_07

Original Source Here

Well, yes! There is some nice theory now that says the following:

The optimal solution is always in a corner of the feasible region.

Let us check the other corner at around A ≈ 65, S = 0. The costs here are around 0.3*65 = 19.5 €, again higher than the costs of the other corner. Thus, we have found the optimal solution graphically. And it wasn’t even that difficult.

Using CVXPY to solve the problem

As I said before, we could solve it because we have two variables. In higher dimensions, we cannot draw some lines and check out corners. In these cases, we need to rely on algorithms that solve these kinds of problems. Some of them being the simplex algorithm of Dantzig or the family of interior point methods, which I won’t describe here. Instead, let us use the Python library CVXPY to do the heavy lifting.

After a pip install cvxpy you can solve the diet problem above with the following few lines:

import cvxpy as cpA = cp.Variable()
S = cp.Variable()
objective = cp.Minimize(0.3*A + 0.4*S)constraints = [
4.6*A + 58.8*S >= 300,
52*A + 33*S >= 2000,
A >= 0,
S >= 0
]
linear_program = cp.Problem(objective, constraints)result = linear_program.solve()print(f'A = {A.value:.2f}, S = {S.value:.2f}, costs = {result:.2f}')

This short program outputs A = 37.06, S = 2.20, costs = 12.00, which confirms that our graphical solution was indeed correct!

And just look how beautiful the interface of the CVXPY library is. It can’t get much leaner than that. You tell it to minimize and give it the formula, you provide a simple list of constraints that you can write easily and you create a problem instance, which you then solve. You can clearly see all of the formulas we have used before already.

AI/ML

Trending AI/ML Article Identified & Digested via Granola by Ramsey Elbasheer; a Machine-Driven RSS Bot

%d bloggers like this: