Lesson · Linear Programming Models · The four model families

Covering and Diet Models

A requirement is a ≥ row and the gap it leaves is a surplus: over-fulfilment rather than an unused remainder. The region such rows cut out runs on forever, and that is harmless while every direction it runs in costs money. Unboundedness is a property of the objective along those directions, not of the region — and it is decided rather than sampled.

Open the interactive lesson Practice

supply ≥ requirement surplus = usage − requirement, over-fulfilment minimise 2G + 3P G + 3P ≥ 9 2G + P ≥ 8 d is a recession direction: x + td feasible for every t ≥ 0 the cost runs away ⇔ some recession direction d has c·d negative

A requirement row, its surplus, and the test for a runaway cost

Core ideas

What this lesson establishes

The model is the packing model with the inequality turned round. The care goes into one question that looks alarming in a picture and is settled by arithmetic.

A requirement is a ≥ row and its gap is a surplus

G + 3P ≥ 9 says the ration supplies at least 9 grams of protein. At a point that satisfies it, usage − requirement is the over-fulfilment: grams of protein more than were asked for. It is not slack — nothing is being left unused — and “Standard Form, Slack and Surplus” is where the sign of that distinction stops being a name and starts mattering.

A covering region has no ceiling

Feed more of everything and every requirement still holds, so the region extends forever to the north-east. In a picture that looks like a problem without an answer. It is not: the picture has no top, and the question is what the objective does out there.

Unboundedness belongs to the objective, along the directions the region runs in

A direction d is a recession direction when x + td stays feasible for every t ≥ 0. The cost runs away exactly when some recession direction lowers it, which is a statement about c·d and not about the shape of the region. With non-negative costs, every step out costs money and the minimum sits at a corner.

The material

Requirements, surpluses, and why an unbounded region is harmless

The ≥ row and what its gap measures, the corners of a covering model, and the recession test that certifies the minimum exists.

A feed merchant blends grain and pellets into a ration. Each kilogram of grain supplies 1 gram of protein and 2 of fibre; each kilogram of pellets supplies 3 grams of protein and 1 of fibre. The ration must carry at least 9 grams of protein and at least 8 of fibre. Grain costs 2 a kilogram and pellets 3.

grain (G) pellets (P) at least protein 1 3 9 grams fibre 2 1 8 grams cost a kilogram 2 3 — minimise 2G + 3P subject to G + 3P ≥ 9 2G + P ≥ 8 G, P ≥ 0

Definition · Surplus

For a row a·x ≥ b and a point x, the surplus of the row at x is a·x − b. It is at or above zero exactly where the row holds, and the row is tight at x when the surplus is zero.

At (4, 2) the protein surplus is 1 gram and the fibre surplus is 2 grams: the ration over-delivers both. At the cheapest ration (3, 2) both surpluses are zero, which is the usual outcome when nothing is gained by exceeding a requirement.

The corners are (0, 8) at a cost of 24, (3, 2) at 12 and (9, 0) at 18. The cheapest is (3, 2): three kilograms of grain and two of pellets, supplying exactly 9 grams of protein and exactly 8 of fibre. Both requirements are met exactly, and neither is exceeded, because exceeding one would cost money and buy nothing.

The region runs on forever, and the minimum still exists

There is no boundary to the north-east: feed ten kilograms of each and both requirements are still satisfied. A reader who has been warned about unbounded problems will reach for that observation, and it is the wrong observation. Being able to walk forever is a fact about the region; whether the cost falls forever as you walk is a fact about the objective.

Theorem · When a minimum exists

Let the feasible region be non-empty, and let d be any direction in which it runs on forever — a direction with x + td feasible for every t ≥ 0. If c·d is at or above zero for every such d, then the objective c·x has a smallest value on the region, and it is attained at a corner.

The contrapositive is the whole diagnostic: the cost runs away exactly when some direction the region contains lowers it. This is the ray check of “Systems of Inequalities and Linear Programming” written for a cost rather than for a picture.

Along (1, 0) the cost changes by 2 a step, along (0, 1) by 3, and along (1, 1) by 5. All three are directions the region runs in, and all three cost money, so walking out never helps and the smallest cost is at one of the three corners. The lab reports each direction it tested and then, separately, a verdict over every direction at once — because three directions that rise are evidence and not a proof.

Example · A disposal credit, and the same region with no minimum

Suppose the merchant is paid 1 a kilogram to take pellets away, so the cost is 2G − P. Nothing about the region changes: the two requirements are the same two rows and it still runs to the north-east. But (0, 1) now changes the cost by −1 a step, so the cost falls forever along a direction the region contains, and there is no cheapest ration at all. The lab reports no value rather than the last point its search stood on.

That is the shape of the answer to keep. An unbounded region with a non-negative cost is a covering model behaving normally. An unbounded problem needs a recession direction along which the objective improves, and finding one is a computation.

Interactive

A covering model, and whether the cost runs away

Requirements are ≥ rows, their surplus is over-fulfilment

Method

Working a covering model

Requirements first, then the certificate, then the answer. The middle step is the one that is usually assumed.

Write one ≥ row per requirement, and check its units

Grams of protein per kilogram times kilograms is grams of protein, and the requirement is grams of protein. A requirement written as ≤ is a different model with a cheapest answer of zero, and zero looks like an answer.

Ask what the region does far away from the origin

List the directions in which it runs on forever. For a model whose rows are all ≥ with non-negative coefficients, every non-negative direction is one of them.

Certify the objective along those directions

Compute c·d for each. If all of them are at or above zero the minimum exists and sits at a corner; if one is negative there is no minimum and the model, not the solver, is what needs changing.

Solve, then read the surpluses

Name the requirements met exactly — surplus zero — and the ones over-delivered, each in its own unit. A requirement with surplus at the optimum is one the cheapest plan could not avoid exceeding.

Requirements, surpluses and runaway costs

Score 0 / 0

Choose the answer you can justify.

The cheapest ration, with the certificate first

The certificate is written before the corners on purpose. If the cost ran away, the corner arithmetic would be work spent on a question with no answer.

minimise 2G + 3P pounds G + 3P ≥ 9 grams of protein 2G + P ≥ 8 grams of fibre G, P ≥ 0 does the cost run away? the region runs on forever along every non-negative direction (1, 0): cost change 2(1) + 3(0) = 2 rises (0, 1): cost change 2(0) + 3(1) = 3 rises (1, 1): cost change 2(1) + 3(1) = 5 rises over every direction at once: no recession direction lowers the cost so a minimum exists, and it is at a corner the corners (0, 8) cost 2(0) + 3(8) = 24 (3, 2) cost 2(3) + 3(2) = 12 cheapest (9, 0) cost 2(9) + 3(0) = 18 at (3, 2) protein 3 + 6 = 9 ≥ 9 surplus 0 grams met exactly fibre 6 + 2 = 8 ≥ 8 surplus 0 grams met exactly

Both requirements are met exactly, which is what a cost minimiser does when exceeding a requirement costs money and buys nothing. The surpluses are the structural reading of the answer: this ration has no room in it anywhere.

For a faded rehearsal, raise the protein requirement from 9 grams to 12 and leave everything else alone. The supplied first move is the certificate: the costs have not changed, so the verdict cannot have changed, and the minimum still exists at a corner. Find the new cheapest ration and its cost as exact fractions, then say which requirements are met exactly at it — and check both against the lab before believing either.

Common mistakes

Concluding that an unbounded region means an unbounded problemThe region of every covering model runs on forever, and almost none of them is unbounded. What decides the question is whether some direction the region contains lowers the objective, which is arithmetic on c·d rather than a look at a diagram.

Testing a few directions and calling the result a certificateThree named directions that all raise the cost are evidence about those three. The claim needed is about every direction the region runs in at once, and it is decidable: the lab prints the named rows and then the verdict over the whole cone, separately, because they are different statements.

Writing a requirement as a ceiling≤ where ≥ was meant leaves a model that is feasible and bounded and whose cheapest answer is to do nothing at all. Nothing in the solve objects. Reading each row aloud with its units — “the ration supplies at least 9 grams” — is what catches it.

Check your understanding

✓

Finish when you certify that the cost cannot run away before you enumerate anything.

You should be able to write requirements as ≥ rows with matching units, say which directions the region runs in and what the objective does along them, produce the cheapest point as exact fractions, and name the requirements it meets exactly.

Note: Both families so far compare a quantity with a number. The next one compares a quantity with a fraction of a total that the decisions themselves make up — which puts a decision in the denominator, and looks for a moment as though it has left the linear class altogether.