How linprog solves a linear program
The function linprog in the Python library SciPy solves a linear program for you. You give it the objective and the limits as lists of numbers, and it returns the best plan.
Drawing corners works for two variables. A solver handles hundreds, so this is the tool to know.
By the end of this lesson
Note
I can solve a linear program with SciPy and read its answer.
Key words
| Word | What it means | Example |
|---|---|---|
| Solver | a program that finds the best plan of a model | |
| linprog | the SciPy solver for linear programs | linprog(c, A_ub=A, b_ub=b) |
| Minimise | make the objective as small as possible | |
| Status | a number that says how the solver ended | |
| Infeasible | having no plan that obeys every limit |
The cells students fill in are left blank in this preview.
linprog minimises, so a profit goes in negated
Most solvers only minimise. To maximise a profit, give the solver the profit with a minus sign. Making -20x - 30y as small as possible is the same as making 20x + 30y as large as possible.
The answer is also negated, so you put a minus in front of fun to read the profit.
The bakery as a linprog call
from scipy.optimize import linprog
# linprog always MINIMISES, so a profit goes in with a minus sign.
profit = [-20, -30]
# One row per limit: a * x + b * y <= limit.
limits_left = [[1, 2], [3, 2]]
limits_right = [8, 18]
answer = linprog(profit, A_ub=limits_left, b_ub=limits_right)
print(-answer.fun, answer.x)
Worked example: which input is which
| Argument | Holds | In the bakery |
|---|---|---|
| c | The objective, one number per variable | [-20, -30] |
| A_ub | One row per limit, the numbers beside x and y | [[1, 2], [3, 2]] |
| b_ub | The limit of each row | [8, 18] |
| bounds | The range of each variable, from 0 up by default | Left out |
The cells students fill in are left blank in this preview.
Solve the bakery
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-20, -30], A_ub=[[1, 2], [3, 2]], b_ub=[8, 18]); print(-r.fun, r.x)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people pass the profits as they are, then read the answer as a maximum. linprog minimises, so it would find the plan with the smallest profit, which is to make nothing. Negate the objective going in, and negate fun coming out.
The status says whether there was an answer
A solver can fail for honest reasons. If no plan obeys every limit, the problem is infeasible and linprog gives status 2. If the profit can grow for ever, the problem is unbounded and the status is 3.
Status 0 means a best plan was found. Always read success or status before you trust x.
Ask for at least 6 loaf batches
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-20, -30], A_ub=[[1, 2], [3, 2], [1, 0]], b_ub=[8, 18, -6]); print(r.status, r.success)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A problem with no ceiling
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-1, -1], A_ub=[[1, -1]], b_ub=[1]); print(r.status, r.success)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: what each status means
| Status | Meaning | Seen above |
|---|---|---|
| 0 | A best plan was found | The bakery |
| 2 | No plan obeys every limit | The row x <= -6 cannot be met with x >= 0 |
| 3 | The objective can improve without end | Only one limit, and it points the wrong way |
The cells students fill in are left blank in this preview.
Going further
Change the numbers in the command so a cake batch earns 50 pounds. Does the best plan move to a different corner?
Then add a third limit: at most 3 cake batches a day. Add it as a new row in the two lists and read the new answer.