Back to the on-screen lesson ·
Writing a situation down as a model, telling a parameter from a variable, and reading slack.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to turn a situation described in words into a model in standard form — sets, parameters, decision variables, one objective, and every constraint including the ones too obvious to write — and to say for any sentence in the description which part it became. You will also be able to compute the slack in a constraint at a given point and say which constraints are binding, which is the short list of things worth changing.
From the last lesson: a decision problem has three parts, and naming them is most of the work. You have also solved systems of linear inequalities and shaded regions on a plane. Here the three parts get written down properly, in the notation the rest of the course uses, on the problem the SCIP book opens with — a workshop deciding what to make.
Parameter: a number the world gives you — a price, a capacity, a demand. Written as a symbol so the model can be re-solved when it changes.
Decision variable: a number you choose. The difference from a parameter is not the notation but the permission.
Standard form: $\max\ c^\top x$ subject to $Ax \le b$, $x \ge 0$ — the shape every method in this course expects.
Coefficient matrix $A$: one row per constraint, one column per variable.
Slack: right-hand side minus left-hand side at a feasible point; what is left of that resource.
Binding: a constraint with zero slack. It is touching, and it is what stops the answer improving.
Non-negativity: the constraints $x \ge 0$, too obvious to write and the ones most often left out.
A model has five kinds of thing in it, and confusing the second with the third is the most common formulation error there is.
| Part | What it is | Example |
|---|---|---|
| Sets | what the model is about | products, machines, weeks |
| Parameters | numbers you are given | profit per unit, hours available |
| Decision variables | numbers you choose | how many of each product |
| Objective | the one number being optimised | total profit |
| Constraints | rules any answer must satisfy | machine hours used $\le$ hours available |
A parameter is data; a variable is a choice. "There are $24$ machine-hours" is a parameter — you do not get to pick it. "We make $x$ of product one" is a variable.
The standard form. Written out, the workshop is
$$\max\ 5x + 4y \quad\text{subject to}\quad 6x + 4y \le 24,\ \ x + 2y \le 6,\ \ x, y \ge 0.$$
That is the whole model. Everything after it — every method in units 3 and 4 — operates on an object of this shape and knows nothing about workshops.
Slack. For a feasible point, the slack in a constraint is the right-hand side minus the left. A constraint with zero slack is binding: it is touching, and it is what stops the answer improving. The binding constraints are the short list of things worth changing, and identifying them is often more useful to the person who asked than the optimum itself.
Another way: picture
Each constraint is a line, and the side of it the inequality allows is shaded. The feasible region is where every shading overlaps — a polygon. The binding constraints at a point are the lines the point is sitting on.
Another way: steps
To formulate:
Every linear model is a table of coefficients, and writing it as one before writing it as algebra catches errors that algebra hides.
| per unit of $x$ | per unit of $y$ | available | |
|---|---|---|---|
| Machine hours | 6 | 4 | 24 |
| Finishing hours | 1 | 2 | 6 |
| Profit | 5 | 4 | — |
Read a row: one unit of $x$ uses 6 machine-hours, one unit of $y$ uses 4, and there are 24. Read a column: one unit of $x$ uses 6 machine-hours and 1 finishing hour, and earns 5. A blank where a number belongs is a question nobody has asked yet, and the table makes the blank visible.
The profit row has no right-hand side, because it is not a limit. That is the one structural difference between the objective and a constraint, and it is why the objective sits apart in the algebra too.
Making a parameter a variable. If the model is allowed to choose how many machine-hours exist, it will choose infinitely many. Anything the model may choose must be something the world lets you choose.
Leaving out non-negativity. The most common missing constraint by a wide margin. A solver has no idea that making $-3$ chairs is not a thing.
Units that do not match. A constraint in hours with a coefficient in minutes is not caught by any solver; it produces a confident wrong answer. Writing the unit next to every parameter is cheap insurance.
Two objectives. "Maximise profit and minimise risk" is not a model; it is two models and a decision nobody has made. Unit 5 says what to do about it. Until then, one objective.
The goal is usually something like run the workshop well. The objective is one number standing in for it, and the solver will maximise the number with complete indifference to the goal. If the objective is profit and nothing constrains overtime, the answer will spend unlimited overtime. Everything you care about has to appear either in the objective or in a constraint; anything in neither is invisible, and a model is silent about what it cannot see. The habit worth forming is to read a solution back and ask what did this do that I would object to — the answer names the constraint you forgot.
A workshop makes two products. Product one earns 5 and uses 6 machine-hours and 1 finishing hour; product two earns 4 and uses 4 and 2. There are 24 machine-hours and 6 finishing hours.
The situation, in words.
Variables: $x, y \ge 0$, the number of each made. Parameters: the six coefficients and the two limits. Objective: $\max\ 5x + 4y$.
Choices, data, and the one number judged.
Constraints: $6x + 4y \le 24$ (machine), $x + 2y \le 6$ (finishing), $x, y \ge 0$. Three inequalities, and the third is the one most often forgotten.
Every rule, including the obvious.
At $x = 3$, $y = 1$: machine hours used are $6(3) + 4(1) = 22$, against $24$ available. Slack $2$.
Not binding — there is room.
Finishing hours used are $3 + 2 = 5$, against $6$. Slack $1$. Also not binding.
Room here too.
Neither is binding, so this point is in the interior and cannot be optimal for a linear objective: moving in a direction that improves profit is still allowed. Slack is therefore a test as well as a report.
Interior points are never optimal in a linear program.
"Each lorry holds 12 pallets." A number you are given, describing the world. Parameter, and it will appear as a coefficient.
Given, not chosen.
"We must deliver at least 40 pallets to the north depot." A rule an answer must satisfy. Constraint, with $\ge$ rather than $\le$.
"How many lorries go to each depot?" The thing being chosen — a decision variable per depot, and since half a lorry is not a thing, one that will have to be an integer. That turns out to change everything, which is lesson 5.
Match each workshop statement to the part of the optimization model it describes.
| Decision variables | Objective | Constraint | |
|---|---|---|---|
| How many units of each product should we make? | |||
| Each unit of x earns $5 and each unit of y earns $4. | |||
| Only 24 machine-hours are available this week. |
The workshop's rules are $2x + 1y \le 10$ and $1x + 1y \le 6$. Write the constraint matrix $A$, one row per constraint and one column per variable.
This task has no paper form; do it on a device.
One unit of the first product earns $4$ and one unit of the second earns $2$. Write the objective to be maximised, as an expression in $x$ and $y$.
Answer:
A plan makes $3$ of the first product and none of the second. How much of the second resource is left over, given $1x + 3y \le 6$?
Answer:
Fill in the model: how much of each resource one unit of each product uses, and what each product earns.
| per unit of $x$ | per unit of $y$ | available | |
|---|---|---|---|
| First resource | 4 | ||
| Second resource | 6 | ||
| Profit per unit | — |
A model of the workshop is written with the two resource limits and nothing else, and the solver returns $x = 3$, $y = -1$. What was left out?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
One unit of the first product earns $2$ and one unit of the second earns $3$. Write the objective to be maximised, as an expression in $x$ and $y$.
Answer:
You can write a described situation in standard form, tell a parameter from a decision variable, and find the slack in each constraint at a point. Next: what the constraints together make — the feasible region, and the four things it can turn out to be.
10. Your turn: which part does each sentence become?, step 3