Practice: Formulating a Linear Program

A bakery decides how many loaves and how many cakes to bake. Flour is limited to 50 kg, each loaf uses 0.5 kg and each cake 0.2 kg. A loaf sells for £3 and a cake for £5. Which quantity should be a decision variable?

A feed supplier blends two ingredients, barley and soy, into a batch of animal feed. Each kilogram of barley costs £0.40 and supplies 8 g of protein and 2 g of fat. Each kilogram of soy costs £0.90 and supplies 35 g of protein and 6 g of fat. A batch must weigh exactly 100 kg, must supply at least 1500 g of protein, and must supply no more than 400 g of fat. The supplier has used the same two ingredients for years. Formulate the problem of producing a batch at least cost as a linear program.

Define your variables with units, write the objective, write one constraint per restriction, and state the sign restrictions.

A workshop makes chairs and desks. Each chair needs 3 hours of carpentry, each desk 5 hours, and 120 carpentry hours are available. A chair yields £40 profit and a desk £60.

A student formulates:

"Let $c$ be chairs made, $d$ be desks made, $P$ be the total profit, and $H$ be the carpentry hours used.

maximise $P$

subject to $P=40c+60d$, $H=3c+5d$, $H\le 120$, $P\ge 0$, $c,d\ge 0$."

Identify which of the student's variables are not decisions. Explain what the constraint $P\ge 0$ does to the model, and give the formulation the student should have written.

Four planning situations are described below. For each one, decide whether a linear program is an appropriate model as stated. If it is not, name the specific feature that rules it out and say what class of model the situation calls for instead. Do not formulate the programs.

(a) A refinery blends three crude streams into petrol, choosing how many barrels of each to use, subject to octane and sulphur limits expressed as averages weighted by volume.

(b) A haulier assigns whole lorries to six routes; a route either gets a lorry or it does not, and a lorry cannot be split.

(c) A shop sets the price of a single product and the quantity it stocks, seeking to maximize revenue, which is price multiplied by quantity sold.

(d) A supplier buys a raw material at £2 per kilogram for the first 500 kg and £1.60 per kilogram beyond that, choosing how much to buy and how to allocate it across two processes.

Three situations are described below. For each, say whether a linear program models it as stated. Where it does not, name the specific feature that rules it out and the class of model the situation calls for instead. Do not write any formulations.

(a) A dairy splits its milk supply between cheese and butter production. Each tonne of cheese needs 9 tonnes of milk and 3 hours of vat time; each tonne of butter needs 22 tonnes of milk and 1 hour. Milk and vat time are both limited, and the dairy maximizes contribution per tonne.

(b) A council must decide which four of eleven proposed bus shelters to build, within a fixed capital budget, maximizing the total number of passengers served.

(c) A mill blends two grades of flour so that the protein content of the mixture is at least 12 per cent, where the protein content is the mass-weighted average of the two grades' protein percentages.

A student is asked whether a linear program can model this situation:

A cooperative blends two feed grades so that the mixture's protein content, the mass-weighted average of the two grades' protein percentages, is at least 14 per cent. It chooses how many tonnes of each grade to buy, minimizing cost.

The student answers:

"No. The protein constraint is an average, so it divides one decision variable by another. Division makes it nonlinear, so this needs nonlinear programming."

The student's answer is wrong. Identify the error in the reasoning, show what the constraint becomes when handled correctly, and state the general test they should have applied instead.