Back to the on-screen lesson ·
Writing a model that grows with its data, and reading which index is summed and which is free.
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 write a transport-shaped model with indices and summation, say how many variables and how many constraints it stands for, and read any indexed constraint back into words by asking which index is summed and which is free. You will also be able to check a shipment plan against its supply and demand families, and to say why supply and demand equalities together make a model infeasible unless the data happens to balance.
You can write a two-variable model and solve it at its corners. That method stops working almost immediately: a model with two factories and three customers already has six variables and no picture. What replaces the picture is notation — indices and summation — and it is the notation, not the method, that makes a model scale.
Index set: what the model has one of each of — factories $i$, customers $j$, weeks $t$.
Indexed variable: $x_{ij}$, one decision per pair. The count of them is the product of the index sets.
Constraint family: one inequality per index, written once — $\sum_j x_{ij} \le s_i$ for every $i$.
Free index: the index not summed over. It says which family the constraint belongs to and how many members that family has.
Supply constraint: summed over destinations, one per source, about what leaves.
Demand constraint: summed over sources, one per destination, about what arrives.
Balanced: total supply equals total demand — which is exactly what equalities on both sides demand.
The transport problem is the smallest model that needs indices. Factories $i = 1, \ldots, m$ have supplies $s_i$; customers $j = 1, \ldots, n$ have demands $d_j$; shipping one unit from $i$ to $j$ costs $c_{ij}$.
$$\min \sum_{i}\sum_{j} c_{ij} x_{ij}$$ $$\text{subject to}\quad \sum_j x_{ij} \le s_i \ \ (\text{each } i), \qquad \sum_i x_{ij} \ge d_j \ \ (\text{each } j), \qquad x_{ij} \ge 0.$$
Four lines describe a model of any size. With three factories and four customers it is twelve variables and seven constraints; with three hundred and four hundred it is a hundred and twenty thousand variables and seven hundred constraints, and the four lines are unchanged.
How to read a constraint. The index that is summed over is the one being added up; the index that is free says how many constraints this line stands for.
Getting those the wrong way round is the commonest error in indexed modelling, and it produces a model that solves cleanly and answers a different question.
Sizes. Variables multiply across index sets; constraint families add. A model is almost always much wider than it is tall.
Another way: picture
A grid with a row per factory and a column per customer. Each cell is one variable — how much goes along that route. A supply constraint is a row of the grid added up; a demand constraint is a column added up. The whole model is the grid, its row sums and its column sums.
Another way: steps
To write an indexed model:
For two factories and two customers, a plan is four numbers:
| to customer 1 | to customer 2 | supply | |
|---|---|---|---|
| Factory 1 | $x_{11}$ | $x_{12}$ | $s_1$ |
| Factory 2 | $x_{21}$ | $x_{22}$ | $s_2$ |
| demand | $d_1$ | $d_2$ |
Row sums are the supply constraints; column sums are the demand constraints. A plan is feasible when every row sum is within its supply and every column sum reaches its demand.
This is also the fastest way to check a plan by hand, and the fastest way to spot that a model is impossible before running anything: if total supply is less than total demand, no grid can satisfy both families, however the routes are arranged.
Transposed indices. $x_{ij}$ and $x_{ji}$ are different variables. A model with the indices the wrong way round in one constraint is not an error a solver can see.
Reading a sum as a per-term rule. $\sum_j x_{ij} \le s_i$ limits the total out of factory $i$. It does not say each route carries at most $s_i$; that would be a much weaker model.
Equalities on both sides. Supply equalities and demand equalities together force total supply to equal total demand. Unless the data happens to balance, that is an infeasible model, and the fix is to decide which side is allowed slack.
Forgetting a route exists. Leaving $x_{ij}$ out of the model is a hard constraint that route $i \to j$ may not be used. That may be what you meant; if it is, write $x_{ij} = 0$ so the reader can see the decision.
It is tempting to read $\sum_j x_{ij} \le s_i$ as an instruction: go through the customers and check each one. It is not an instruction, it is a single statement about a single number — the total. The difference matters when the constraint is violated: a solver does not report which $j$ failed, because no $j$ failed; the sum did. Debugging an indexed model means printing the sums, not the terms. And when a constraint really does need to hold per term, it is written with the index free rather than summed, which is a visibly different line.
$\min \sum_i \sum_j c_{ij} x_{ij}$ — total cost over every route, since both indices are summed and none is free.
The objective involves every variable.
$\sum_j x_{2j} \le s_2$ — $j$ summed, $i$ fixed at 2. Everything leaving factory 2, at most what factory 2 has.
One constraint, about one factory.
$\sum_i x_{i3} \ge d_3$ — $i$ summed, $j$ fixed at 3. Everything arriving at customer 3, at least what customer 3 needs. Note the direction flipped with the family: supply is an upper limit and demand a lower one.
The inequality direction carries meaning too.
Two products instead of one: add an index $k$, so the variable becomes $x_{ijk}$ and the cost $c_{ijk}$.
A new index, not a new model.
The demand constraint becomes $\sum_i x_{ijk} \ge d_{jk}$: one per customer and product, since both $j$ and $k$ are now free.
Free indices multiply the family.
But the supply constraint is the interesting one: $\sum_j \sum_k x_{ijk} \le s_i$ says the factory's capacity is shared across products. Writing it as $\sum_j x_{ijk} \le s_{ik}$ instead would say each product has its own capacity. The notation forces you to decide which is true, and that is what makes it worth writing.
The notation asks a question the words hid.
Both indices are summed on the left, so it is the total shipped over all routes.
Start with what each side counts.
The right side sums demands over customers: total demand.
So it says the plan ships exactly the total demanded and not a unit more. It is not one of the two families — it is a single constraint implied by them when every demand is met with equality, and adding it explicitly to a model that already has them is harmless but tells the solver nothing new.
Match each indexed transport constraint to the statement it makes.
| Factory i ships no more than its supply | Customer j receives its demand | |
|---|---|---|
| $\sum_j x_{ij} \le s_i$ | ||
| $\sum_i x_{ij} = d_j$ |
A transport model ships from $4$ factories to $3$ customers, with $x_{ij}$ the amount on route $i$ to $j$. How many decision variables are there?
Answer:
Two factories ship to two customers, with the variables in the order $x_{11}, x_{12}, x_{21}, x_{22}$. Write the two supply rows of the constraint matrix — one row per factory.
This task has no paper form; do it on a device.
Two factories ship to two customers. Factory 1 has $6$ units and factory 2 has $3$; customer 1 needs $4$ and customer 2 needs $5$. Route $1{\to}1$ carries $4$ and route $2{\to}2$ carries $3$. Complete the plan.
| to customer 1 | to customer 2 | |
|---|---|---|
| Factory 1 | 4 | |
| Factory 2 | 3 |
Route $1{\to}1$ carries $6$ units at $2$ each and route $1{\to}2$ carries $5$ at $8$ each. Route $2{\to}1$ carries nothing. What does factory 1's shipping cost?
Answer:
A warehouse network has total supply $11$, and every supply and demand constraint is written as an equality. For which total demands $d$ is the model feasible? Give the set.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Two factories ship to two customers. Factory 1 has $11$ units and factory 2 has $4$; customer 1 needs $7$ and customer 2 needs $8$. Route $1{\to}1$ carries $7$ and route $2{\to}2$ carries $4$. Complete the plan.
| to customer 1 | to customer 2 | |
|---|---|---|
| Factory 1 | 7 | |
| Factory 2 | 4 |
You can write and read an indexed model, count its variables and constraints, and check a plan against both constraint families. Next: what changes when the answer has to be a whole number.
10. Your turn: what does $\sum_i \sum_j x_{ij} = \sum_j d_j$ say?, step 3