D1 5.1 - Formulating linear programs | Edexcel A-Level Further Mathematics

A useful linear program starts with precise variables and faithful translations of its conditions. You will formulate objectives and constraints, handle proportions and exact totals, and explain the roles of slack, surplus and artificial variables (D1 5.1).

Decide what the variables actually count

A workshop is told to make at least three products A for every product B, but also at most twice as many A as B. Can any positive production satisfy both instructions?

The words sound like ordinary production rules. Once translated, they will reveal a conflict that a clever optimisation algorithm cannot repair. First decide exactly what your symbols measure.

You already know

From A-level Mathematics, inequalities express bounds, and a solution must satisfy every simultaneous condition. Multiplying an inequality by a negative number reverses its direction. Keep units consistent before combining terms.

For example, “let $x$ be the number of A products made each day” identifies a count, a product and a time period. “Let $x$ be A” does not tell the reader whether it means items, kilograms or profit.

Linear program

A linear program maximises or minimises a linear objective subject to linear constraints and specified variable domains. The objective and every constraint have constant coefficients: terms such as $3x+2y$ are linear, whereas $xy$ , $x^2$ and $1/x$ are not.

The three ingredients have different jobs:

Ingredient	Example	Meaning
Decision variables	$x,y$ products per day	Quantities you can choose
Objective	Maximise $P=5x+4y$	What makes one feasible choice better
Constraints and domain	$2x+3y\le24$ , $x,y\ge0$ , integers	What choices are permitted

Whole desks require integer variables. Kilograms of a divisible ingredient can usually be continuous. Do not add integer restrictions merely because the numerical data are integers, or omit them when the quantities must be whole objects.

Non-negativity means zero is allowed. It is a condition on the variables, not a substitute for the resource and relationship constraints. A fixed setup charge applying only when production is positive also needs more than an ordinary linear expression in the production quantity; do not pretend it is a constant unit cost.

Key idea

Define each variable with its meaning and unit, state whether the objective is maximised or minimised, then list every constraint and the variable domain. Formulating a model does not require solving it.

This check separates a valid linear model from expressions involving products or powers of the decisions.

Turn a resource table into a model

For a limited resource, multiply each unit's requirement by its production quantity and bound the total by what is available.

Suppose a workshop makes whole products A and B. Its daily data are:

	One A	One B	Available per day
Cutting time, hours	$2$	$3$	$24$
Assembly time, hours	$3$	$1$	$18$
Profit, pounds	$5$	$4$

The available hours constrain production; the profit row defines the objective. Check that all entries in one resource row use the same unit before writing its inequality.

Worked example 1: capacity is an upper bound

Question. Formulate a linear programming model for the workshop, defining your variables clearly. Do not solve it.

Plan. Define daily product counts, maximise total profit and use one inequality for each resource.

Let $x,y$ be the numbers of products A and B made each day. Then

\begin{aligned} \text{maximise }P&=5x+4y &&\text{total daily profit in pounds}\\ 2x+3y&\le24 &&\text{cutting capacity}\\ 3x+y&\le18 &&\text{assembly capacity}\\ x,y&\ge0,\quad x,y\text{ integers} &&\text{whole non-negative product counts} \end{aligned}

Why this step? “Available” gives a maximum use, not a requirement to consume every hour. Writing equalities would exclude feasible plans that leave unused capacity.

Answer. The displayed objective, two constraints and integer domain form the required model.

Check. The plan $x=3,y=6$ uses $24$ cutting hours and $15$ assembly hours, so it is feasible and gives profit $39$ pounds. This check does not claim that the plan is optimal.

Worked example 2 changes only the cutting capacity, from $24$ to $30$ hours per day. Unit requirements and assembly capacity remain fixed.

Worked example 2: one resource becomes more plentiful

Question. Formulate the new model when $30$ cutting hours are available each day.

Plan. Change the cutting bound while retaining the same variables, objective and remaining conditions.

\begin{aligned} \text{maximise }P&=5x+4y &&\text{unchanged unit profits}\\ 2x+3y&\le30 &&\text{new cutting capacity}\\ 3x+y&\le18 &&\text{unchanged assembly capacity}\\ x,y&\ge0,\quad x,y\text{ integers} &&\text{unchanged product domain} \end{aligned}

Why this step? The resource limit is the right-hand side. Changing the coefficients would incorrectly change how long each product takes to make.

Answer. Replace only the cutting constraint by $2x+3y\le30$ .

Check. The plan $x=3,y=8$ uses $30$ cutting hours and $17$ assembly hours, giving profit $47$ pounds. It fits the new model but exceeds the old cutting capacity.

A lower production commitment would instead use $\ge$ , while an exact order would use $=$ . Each inequality's direction must come from its own wording, not from a belief that every linear program uses capacity constraints.

Watch out

Wrong: use $2x+3y=30$ just because $30$ hours are available, or swap the cutting and assembly coefficients. Right: read across one resource row at a time and preserve its units and upper-bound meaning.

Increase the same resource limit once more.

Model proportions without reversing their meaning

Write a statement about a proportion using the whole relevant total, then simplify to a linear inequality.

If at least a fraction $f$ of a two-ingredient blend is A, with quantities $x,y$ , the A amount must be at least $f$ times the total amount. The condition is not a comparison with B alone.

A minimum proportion of a total

For non-negative quantities $x,y$ and fixed $0<f<1$ ,

x\ge f(x+y) \quad\Longleftrightarrow\quad (1-f)x-fy\ge0

For a positive total this says that A is at least proportion $f$ of the blend. At total zero the linear inequality holds, but a percentage composition is undefined; a required positive batch size excludes that case.

Not in the formula booklet: learn it.

Similarly, “at most twice as much A as B” means $x\le2y$ . Multiplying the B quantity by two gives the largest permitted A quantity. Writing $2x\le y$ expresses a different relationship.

Worked example 3: an exact blend with a minimum share

Question. A blend must contain exactly $12$ kg of ingredients A and B. A costs $4$ pounds per kilogram and B costs $3$ pounds per kilogram. At least one quarter of the blend must be A, and there must be at most twice as much A as B. Formulate a model minimising cost.

Plan. Define continuous masses, use an equality for the total, and translate each composition statement separately.

Let $x,y$ be the kilograms of A and B. Then

\begin{aligned} \text{minimise }C&=4x+3y &&\text{cost in pounds}\\ x+y&=12 &&\text{exact required mass}\\ x&\ge\frac14(x+y) &&\text{A share of the whole blend}\\ 3x-y&\ge0 &&\text{simplify the share condition}\\ x-2y&\le0 &&\text{upper ratio of A to B}\\ x,y&\ge0 &&\text{continuous non-negative masses} \end{aligned}

Why this step? One quarter of the blend is $(x+y)/4$ , not $y/4$ . Using the exact total, the share condition is also equivalent to $x\ge3$ .

Answer. Minimise $C=4x+3y$ subject to $x+y=12$ , $3x-y\ge0$ , $x-2y\le0$ and non-negativity.

Check. At $x=4,y=8$ , the total is $12$ , A exceeds the required $3$ kg and $4\le2(8)$ . The cost is $40$ pounds; feasibility alone does not establish minimum cost.

Continue this lesson.

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

Create free account

Last Accessed

Core Pure Mathematics

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Statistics 1

Further Statistics 2

Further Mechanics 1

Further Mechanics 2

Decision Mathematics 1

Decision Mathematics 2

D1 5.1 - Formulating linear programs

Decide what the variables actually count

Turn a resource table into a model

Model proportions without reversing their meaning

Continue this lesson.

Learn faster with Nova