Why optimization — when do we need it
Build the habit of splitting a story about profit into three parts: variables, objective, and constraints.
"Make more of the profitable one" is not the end of the story
Suppose product A gives ¥30,000 profit per lot and product B gives ¥50,000 per lot. Looking only at profit, you want to make more B, but in practice there are upper limits on process time.
| Item | A | B |
|---|---|---|
| Profit | ¥30,000 / lot | ¥50,000 / lot |
| Cutting stage | 2 hours | 1 hour |
| Finishing stage | 1 hour | 2 hours |
The key point here is that you have to look at both the level of profit and the amount of time each stage consumes, at the same time.
"Programming" here is not computer programming
The "programming" in linear programming does not mean writing code on a computer. It refers to making a plan (planning) — a mathematical-programming term that goes back to mid-20th-century operations research.
So linear programming is "a method for solving planning problems expressed in linear equations". Python implementation does appear in Chapter 6, but it is just a tool to assist the calculation, not the essence of linear programming itself.
Work it out 1
First, confirm that both the profit equation and the constraint equation are "just plug the numbers in and compute".
Compute the profit of a plan
For the plan (x, y) = (2, 3), compute the profit z = 3x + 5y.
Show hint
3×2 + 5×3 = 6 + 15 = 21. Start by confirming in numbers that the objective function is just the "total profit".
If you only make B, by how much do you go over?
Suppose you make 8 lots of product B and nothing else. The time used by the finishing stage is x + 2y, so by how many hours do you exceed the 14-hour limit?
Show hint
Making 8 lots of B alone means x=0, y=8. The finishing stage uses 0 + 2×8 = 16 hours, so 16 - 14 = 2 hours over the limit.
Split every optimization problem into three parts
In any LP, the very first thing to separate out is just three elements.
| Aspect | Meaning in this example |
|---|---|
| Decision variables | x = number of lots of A, y = number of lots of B |
| Objective function | Maximize 3x + 5y |
| Constraints | 2x + y ≤ 16, x + 2y ≤ 14, x ≥ 0, y ≥ 0 |
Even as the number of equations grows, it stays easy to read as long as you can split it into these three groups.
Work it out 2
The left-hand side of a constraint is "the amount that plan actually uses". Plug numbers in and check.
The left-hand side of a constraint is "what you used"
For the plan (x, y) = (3, 4), how many hours does the cutting stage use, i.e. what is 2x + y?
Show hint
2×3 + 4 = 6 + 4 = 10. A useful habit: read the left-hand side of a constraint as "the amount of resource that plan actually consumes".
Why "linear"?
Linear means the coefficients are fixed, and doubling a quantity doubles the profit or the resource use.
3x + 5yis linear2x + y ≤ 16is also linear- Adding
x²orxymakes it nonlinear
Linear programming is a way to organize — in equations and diagrams — the tug-of-war between "I want more" (the objective) and "I can't have more" (the constraints).
Work it out 3
You develop a feel for "linear" by being able to restate the coefficients in plain numeric terms.
Put linearity in concrete numbers
The profit formula is 3x + 5y. If you hold y fixed and increase x by 2 lots, by how many ten-thousand yen does the profit rise?
Show hint
The coefficient of x is 3, so each additional lot adds ¥30,000 of profit. Two lots gives 3×2 = 6, i.e. ¥60,000.
Key takeaways from this chapter
- Split every optimization problem into decision variables, objective function, and constraints.
- The left-hand side of a constraint is exactly the amount of resource that plan consumes.
- Linear means that profit and consumption grow in proportion to the quantity you add.