Solving Linear Problems

Solving linear problems is easier with SciPy. It includes the function linprog (from linear programming) that allows us to solve any linear optimization problem. In this lesson, we’re going to learn how to use this special feature of SciPy.

First linear optimization problem

The best way to learn is with a practical example, so let’s solve the following linear optimization problem:

$$\min_{x, y} 4x + 3y + 1\\ s.t.: x + y < 10\\ x > 5\\$$

Note: The last term of the target function is a constant. This constant doesn’t affect the optimization problem. This means that removing it doesn’t modify the optimal value. The minimum of $4x + 3y$ is the same as the minimum of $4x + 3y + 1$.

The first step is to transform it into the form we learned earlier. Note that the second constraint has a $>$ sign instead of a $<$ sign. We need to change this to use linprog from SciPy since this function only accepts the less than or equal to ($≤$) constraints. This change is done by multiplying the constraint by $-1$.

$$\min_{x, y} 4x + 3y + 1\\ s.t.: x + y < 10\\ -x < -5\\$$ ...