Modeling — turning a problem into LP
Translate prose requirements into x, y, maximize, and ≤.
Pull the example out of natural language
Restated in prose, the running example looks like this.
We want to decide how much of product A and product B to make in a day. A gives ¥30,000 profit per lot, B gives ¥50,000 profit per lot. The cutting stage uses 2 hours per lot of A and 1 hour per lot of B, up to a total of 16 hours. The finishing stage uses 1 hour per lot of A and 2 hours per lot of B, up to a total of 14 hours.
From this, we extract what to decide, what to maximize, and what the upper limits are.
First, introduce the variables
Only the quantities that the analyst can choose become variables.
x = number of lots of product Ay = number of lots of product BOnce the variables are fixed, every later sentence turns into "how do we write this in terms of x and y?"
Work it out 1
Start by copying the profit coefficients from the prose into the equation.
Fill in the objective coefficients
Product A gives ¥30,000 profit and product B gives ¥50,000 profit. Enter the coefficients c_x and c_y of the objective z = c_x x + c_y y.
Show hint
The profit per additional lot is exactly the coefficient of the objective: 3 for A and 5 for B.
Write the objective function
Since A gives ¥30,000 per lot and B gives ¥50,000 per lot, total profit can be written as follows.
maximize z = 3x + 5yWhether it is maximize or minimize is a question of direction; the skeleton of the equation is the same.
Write the constraints
The upper limit on "how much of each stage you may use" becomes an inequality.
2x + y ≤ 16x + 2y ≤ 14x ≥ 0, y ≥ 0| Prose | Equation | Meaning |
|---|---|---|
| Cutting stage is limited to 16 hours | 2x + y ≤ 16 | A consumes 2 hours, B consumes 1 hour |
| Finishing stage is limited to 14 hours | x + 2y ≤ 14 | A consumes 1 hour, B consumes 2 hours |
| Negative production is not allowed | x ≥ 0, y ≥ 0 | Consider only the first quadrant |
Work it out 2
Build a constraint for each stage, being careful not to swap the right-hand side and a coefficient.
Build the cutting-stage constraint
In the cutting stage, A uses 2 hours, B uses 1 hour, and there are 16 hours available in total. Enter a, b, and r for a x + b y ≤ r.
Show hint
The coefficient of A is 2, the coefficient of B is 1, and the right-hand side is the 16 hours available. That gives 2x + y ≤ 16.
Build the finishing-stage constraint
In the finishing stage, A uses 1 hour, B uses 2 hours, and there are 14 hours available in total. Enter the coefficients and the right-hand side in the form a x + b y ≤ r.
Show hint
Reading the sentence off directly gives x + 2y ≤ 14. The important thing is not to swap the coefficients of A and B.
The boundary between linear and nonlinear
In linear programming, the variables may appear only in first-degree (linear) expressions.
| Expression | Linear? | Why |
|---|---|---|
3x + 5y | Yes | Constant coefficients and no products of variables |
2x + y ≤ 16 | Yes | Even as an inequality, the left-hand side is a linear expression |
x² + y | No | Contains a square |
xy ≤ 10 | No | Two variables are multiplied together |
Linear programming itself allows x and y to be real numbers. Restricting them to integers moves you into integer programming.
Work it out 3
Once you have the equations, make sure you can actually read off values by plugging numbers in.
Plug numbers into the equation and read off the objective value
For the plan (x, y) = (4, 5), what is the objective value z = 3x + 5y?
Show hint
3×4 + 5×5 = 12 + 25 = 37. It helps to think of the objective function as a formula that scores each candidate plan.
Read off the axis intercepts first
Consider the boundary line x + 2y = 14 of the constraint x + 2y ≤ 14. Find y at x = 0.
Show hint
Substituting x=0 gives 2y = 14, so y = 7. The intercepts are the first landmarks you use when sketching the feasible region.
The finished formulation
maximize z = 3x + 5ysubject to 2x + y ≤ 16 x + 2y ≤ 14 x ≥ 0, y ≥ 0Once you can write this much down, the next step is to see what shape these equations make in the plane.
Key takeaways from this chapter
- The first thing you decide are the quantities that the analyst can choose — the decision variables.
- The objective function expresses "what you want to make better"; the constraints express "what the limits are".
- Linear means that variables appear only in first-degree (linear) expressions.