AL1–AL5 - Formulating linear programs | OCR A-Level Further Mathematics B (MEI)

Translate a practical decision into numerical variables, a linear objective and constraints. Recognise standard and augmented forms, interpret slack variables and state when fractions of a decision are not allowed.

Decisions, objectives and constraints

A planning program recommends making $2.5$ tables. Has it made an arithmetic mistake, or have we asked the wrong mathematical question?

The arithmetic might be perfectly correct. A continuous linear program permits fractional quantities; a furniture plan must say that whole tables are required.

You already know

A linear expression adds constant multiples of variables. Inequalities such as $2x+y\le8$ describe restrictions. Multiplying two decision variables together would produce a nonlinear expression.

A good formulation starts with what can be chosen, then separates the aim from the restrictions.

Linear programming

A linear program, or LP, optimises a linear objective function subject to linear constraints. Maximisation seeks the largest objective value; minimisation seeks the smallest. Constraints restrict the decisions, rather than describing what you are trying to optimise.

A feasible plan satisfies every constraint and variable restriction. An optimal plan gives the best objective value among feasible plans.

For example, profit $P=3x+2y$ is linear. Profit $P=xy$ , or a constraint $x^2+y\le8$ , would not define an LP of this kind. A fixed cost per unit is compatible with linearity; a unit cost that itself depends on the chosen quantity may not be.

Decision variables

Decision variables represent numerical quantities chosen in the model. Define each variable with its meaning and units: “ $x$ is the number of kilograms of blend $X$ ”, rather than “ $x$ is blend $X$ ”.

The word “programming” here means planning the decisions. A mathematical formulation can be solved on paper or supplied to software.

Key idea

State the decisions, the objective to maximise or minimise, and every restriction, including the variable domains.

Distinguish an objective from a resource restriction.

Building a model from a context

Write one expression for each limited resource. Every coefficient must describe the resource used by one unit of the corresponding decision.

A small blending business produces two saleable mixtures. Quantities can be measured continuously in kilograms.

Per kilogram produced	Blend $X$	Blend $Y$	Available
Machine $A$ , minutes	$2$	$1$	$8$
Machine $B$ , minutes	$1$	$2$	$8$
Profit, pounds	$3$	$2$	—

Each blend needs time on both machines. The two time limits are separate restrictions, even though their available amounts happen to be equal.

Worked example 1: two resource limits

Question. Formulate an LP for the table, aiming to maximise total profit.

Plan. Define kilograms of each blend, add profit contributions and impose one availability inequality per machine.

Let $x$ and $y$ be the kilograms of $X$ and $Y$ produced.

\begin{aligned} \text{Maximise }P&=3x+2y&&\text{profit in pounds}\\ 2x+y&\le8&&\text{machine }A\\ x+2y&\le8&&\text{machine }B\\ x,\ y&\ge0&&\text{production cannot be negative} \end{aligned}

Both variables are continuous.

Why this step? The availability is an upper bound. It is permissible to leave some machine time unused, so equality is not required.

Answer. The displayed objective, constraints and continuous non-negative domains give the LP.

Check. Producing $x=2$ , $y=1$ uses $5$ minutes on $A$ and $4$ minutes on $B$ , both within the available $8$ minutes.

Now change only the business requirement by adding a minimum order.

Worked example 2: a lower-bound requirement

Question. The same business must produce at least $1\,\mathrm{kg}$ of blend $Y$ . Formulate the modified LP.

Plan. Retain the resource model and add the contract as a lower bound.

\begin{aligned} \text{Maximise }P&=3x+2y&&\text{same profit}\\ 2x+y&\le8&&\text{first availability}\\ x+2y&\le8&&\text{second availability}\\ y&\ge1&&\text{minimum order}\\ x,\ y&\ge0&&\text{continuous non-negative amounts} \end{aligned}

Why this step? “At least” means a lower bound, whereas the available machine times still give upper bounds.

Answer. Add $y\ge1$ ; the other resource inequalities and objective are unchanged.

Check. $(2,1)$ meets the order exactly. $(2,0.5)$ meets both resource limits but fails the contract, so the new constraint is doing useful work.

Read “at most”, “at least” and “exactly” carefully. They mean an upper bound, a lower bound and an equality respectively.

Watch out

Wrong: put all resource inequalities in the same direction without reading their meaning, or omit $x,y\ge0$ . Right: test a concrete allowed and forbidden plan against each expression.

Modify one availability while retaining the minimum order.

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

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

AL1–AL5 - Formulating linear programs

Decisions, objectives and constraints

Building a model from a context

Continue this lesson.

Learn faster with Nova