# Solving Linear Problems

Learn to use SciPy to solve linear problems.

## We'll cover the following

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\\$

The second step is to define the problem using matrix notation. Here we have a problem. The one that we sum in the target function is just a scalar and it doesn’t multiply any variable. How do we write the target function as $\mathbf{c}\mathbf{x}^\top$ then? For that, we’ll add an artificial variable and constrain it to always be one.

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

Now $b$ is an additional variable but it’s always one. To write the problem in matrix notation, we have $\mathbf{a} = (4, 3, 1)$, $\mathbf{x} = (x, y, b)$, $\mathbf{p} = (10, -5)$, and $\mathbf{q} = (1)$. We also have $Q =(\begin{smallmatrix} 0 & 0 & 1 \end{smallmatrix})$ and $P = \big(\begin{smallmatrix}1 & 1 & 0\\ -1 & 0 & 0\end{smallmatrix}\big)$. Remember we added a new variable and that’s why we have three columns in the matrices.

Get hands-on with 1200+ tech skills courses.