Practice: Recurring Shapes of Linear Programs

(a) The shape. Predominantly packing: "has 480 litres and 90 worker-hours" is capacity language and the objective maximises. The contract clause, "at least 8 batches of cheese", is a requirement floor, so the problem is a hybrid carrying one covering row among its packing rows. (b) The program. Let $y$ and $c$ be batches of yoghurt and cheese this week.

The contract row stays $\ge$. Negating it to make every row read $\le$ would state a ceiling of 8 batches, which is the opposite of the obligation. (c) Testing the prediction. Set both resource rows to equalities:

From the second, $y=60-2c$. Substituting: $12(60-2c)+30c=720+6c=480$, giving $c=-40$. That is negative, so the two resource rows do not intersect in the nonnegative quadrant and the prediction fails in a specific way: the resources cannot both be exhausted. Checking which is the real limit, milk alone allows at most $480/12=40$ batches of yoghurt, needing $1.5(40)=60$ worker-hours of the 90 available; labour alone allows $90/1.5=60$ batches, needing $12(60)=720$ litres, well beyond the 480. So milk binds and labour is slack throughout the region. With the contract at $c=8$: milk leaves $480-30(8)=240$ litres, so $y=20$, using $1.5(20)+3(8)=54$ worker-hours, 36 to spare. Contribution is $9(20)+21(8)=180+168=348$. Comparing contribution per litre of milk, yoghurt earns $9/12=0.75$ and cheese $21/30=0.70$, so milk is better spent on yoghurt and the contract floor binds: the optimum is $(y,c)=(20,8)$ with contribution $348$. (d) A tighter contract. At $c=14$, milk leaves $480-30(14)=60$ litres, so $y=5$, and labour uses $1.5(5)+3(14)=49.5$ hours, still slack. Contribution falls to $9(5)+21(14)=45+294=339$. The binding pair is again the milk row and the contract row; the contract has simply moved, and each extra obliged batch of cheese costs the dairy contribution because it displaces the more milk-efficient product. What the exercise shows. The shape's prediction, that the scarce resources bind, is a prediction, not a theorem. Here one resource is slack at every feasible point, and the binding pair is one resource and the covering row. Noticing that is the useful outcome: the dairy's constraint is milk and its contract, not labour.

(a) The two shapes. The description is a covering problem: "must be covered by at least" states requirement floors, and "at least cost" minimises. The model is written as a packing problem, maximisation with $\le$ rows throughout. Every direction has been inverted. (b) What each wrong row asserts. | Row as written | What it asserts | What the description says |
|---|---|---|
| $max620n_A+700n_B$ | spend as much as possible | spend as little as possible |
| $n_A\le 4$ | at most 4 nurses may cover shift 1 | at least 4 must |
| $n_A+n_B\le 6$ | at most 6 may cover shift 2 | at least 6 must |
| $n_B\le 3$ | at most 3 may cover shift 3 | at least 3 must | Read back as sentences, the model instructs the clinic to cap its cover and maximise its wage bill. The reported answer, $n_A=3$ and $n_B=3$, leaves shift 1 with 3 nurses against a requirement of 4. The model's "optimum" is infeasible for the actual problem. (c) Why the solver was satisfied. A solver optimises the program it is handed. Reversed inequalities and a flipped objective produce a perfectly well-formed linear program: the feasible set is nonempty and bounded, so an optimum exists and is found. "Status: optimal" is a statement about the program, never about whether the program matches the description. No arithmetic check can catch this class of error, because the arithmetic is not wrong. The check that catches it is reading each row back as a sentence and asking whether the description says that, and noticing that a covering problem's model should have come out with $\ge$ rows and a minimisation. (d) The model as described.

The covering shape makes infeasibility the outcome to watch for: it cannot run to $-\mathrm{\infty }$, since costs are positive and the objective is bounded below by zero. Here it is feasible, $n_A=4$, $n_B=3$ satisfies all three rows, since $4+3=7\ge 6$, at cost $620(4)+700(3)=2480+2100=4580$. Both single-shift rows bind and the shift-2 row is slack, which is the covering shape behaving as expected: cover is bought only where it is required. A fuller answer notes that nurses come in whole numbers, so the correct model is an integer program; the linear relaxation happens to have an integral optimum here, which is luck rather than a property of the formulation.

(a) Covering. The wording is "must supply at least 40 Ml/day … at least 25 Ml/day": requirement floors, one per zone. The objective minimises pumping cost; the constraints read $\ge$. The likely failure is infeasibility, the three sources may not jointly be able to deliver 65 Ml/day, rather than unboundedness, which nonnegative costs rule out. Expect the optimum to meet both floors exactly, since any surplus is pumped and paid for without being required. (b) Packing. The wording is "has 60 press-hours and 3,000 sheets": capacities, stated as what exists. The objective maximises earnings; the constraints read $\le$. The likely failure is unboundedness, which would arise if some run consumed no limited resource, not a risk here, since both runs use press-hours and sheets. Infeasibility is near-impossible because printing nothing is feasible. Expect the binding constraints to be the press-hours, the sheets, or both. (c) Allocation. The wording is "must be placed entirely" together with per-programme floors and caps. The total is an equality, $\sum _j{w}_j=12$, and the restrictions are bounds on individual shares rather than further rows mixing the variables. The objective maximises benefit. The likely failure is infeasibility from the bounds. It would arise if the floors summed above the fund or the caps summed below it. Here four floors of 5% sum to 20% and four caps of 40% sum to 160%, so the fund is reachable and the problem is feasible. Expect the optimum to push the best programme to its 40% cap and the worst to its 5% floor. (d) One clause that changes a shape. Several answers are defensible; the requirement is that the clause changes a direction, not a coefficient. Taking (b): add "a standing contract requires at least 12 runs of posters each week." The problem becomes a hybrid, predominantly packing, with the two resource ceilings as $\le$ rows, now carrying one covering row $y_{\text{posters}}\ge 12$. It must be written with both directions present. Forcing the contract into a $\le$ row to keep the system uniform would assert a ceiling of 12 runs, which the description does not say, and the resulting program would solve cleanly while quietly breaching the contract. The hybrid also admits a failure neither pure shape has: if the contract required more poster runs than the press-hours allow, the problem would be infeasible, where a pure packing problem essentially never is. Taking (a) instead: add "no source may pump more than 30 Ml/day." That adds packing rows to a covering problem and creates the same possibility, floors that the capped sources cannot jointly reach.