DD1 - Formulating linear programmes

DD1 - Formulating linear programmes

A profitable product can still use too much of a scarce ingredient. You will turn a practical decision into variables, an objective and constraints, then check the units and assumptions that make the model meaningful. A good formulation says exactly what can be chosen and what must be respected.

Variables, objectives and constraints

How can a drinks maker with 40 kg of fruit and 50 kg of sugar describe every possible production plan without listing them one by one? Let xx and yy be the litres of two drinks made each day. A pair such as (6,10)(6,10) describes one plan; inequalities describe all permitted plans together.

An objective function measures the quantity to maximise, such as profit, or minimise, such as cost. A constraint restricts the permitted choices. A profit expression is not a limit on production.

Linear programme

A linear programme optimises a linear objective subject to linear equality or inequality constraints. A term such as 3x+5y3x+5y is linear; xyxy, x2x^2 and a variable unit price are not linear terms. A decision variable is a quantity whose value the model is choosing.

“At most” includes equality and gives ≤\leq; “at least” gives ≥\geq. “Exactly” gives ==. Nonnegative constraints such as x≥0x\geq0 matter: negative production is not an available choice.

Worked example 1: ingredients limit production

Question. Each litre of drink A earns £3 and uses 2 kg of fruit and 1 kg of sugar. Each litre of drink B earns £5 and uses 1 kg of fruit and 2 kg of sugar. At most 40 kg of fruit and 50 kg of sugar are available each day. Formulate a model for maximum daily profit. Any nonnegative real number of litres may be made.

Plan. Define daily quantities, add contributions to profit, and write one capacity inequality per ingredient.

Let xx be litres of A per day and yy litres of B per day. Then

maximiseP=3x+5ypounds per day,subject to2x+y≤40fruit stock,x+2y≤50sugar stock,x≥0,y≥0nonnegative production.\begin{aligned} \text{maximise}\quad &P=3x+5y &&\text{pounds per day},\\ \text{subject to}\quad &2x+y\leq40 &&\text{fruit stock},\\ &x+2y\leq50 &&\text{sugar stock},\\ &x\geq0,\quad y\geq0 &&\text{nonnegative production}. \end{aligned}

Answer. The objective and all four inequalities form the model; x,yx,y are real quantities.

Check. The trial plan (6,10)(6,10) uses 2222 kg of fruit and 2626 kg of sugar, and earns 3(6)+5(10)=£683(6)+5(10)=£68. Direct calculation from the wording agrees with each expression. This checks translation, not optimality.

Change just one feature: the maker now promises a minimum quantity of A. This narrows the choices without changing profit per litre.

Worked example 2: adding a minimum order

Question. Use the same drinks, profit rates and stocks as in Worked example 1, but require at least 4 litres of A daily. Formulate the revised model.

Plan. Retain the objective and stock limits, and translate the new lower bound.

maximiseP=3x+5y,subject to2x+y≤40,x+2y≤50,x≥4,y≥0.\begin{aligned} \text{maximise}\quad &P=3x+5y,\\ \text{subject to}\quad &2x+y\leq40,\\ &x+2y\leq50,\\ &x\geq4,\quad y\geq0. \end{aligned}

Why not x≤4x\leq4? A promise of at least 4 litres permits 5 litres and forbids 3 litres. Also, x≥4x\geq4 already implies x≥0x\geq0.

Answer. Replace the lower bound on xx by x≥4x\geq4; retain the other limits.

Check. (6,10)(6,10) still meets every constraint. The plan (3,10)(3,10) meets both stock limits but breaks the promise, as the revised model correctly detects.

A few inequalities can describe infinitely many plans. The model describes the choices before you search for the best one.

Watch out

Wrong: “at least 4 litres” means x≤4x\leq4. Test a permitted value such as 5 to decide the direction. State what each variable measures and whether to maximise or minimise the objective.

Translate a fresh situation before doing any optimisation.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account