Formulating linear programsEdexcel International A Level Maths: Revision notes

Linear programming finds the best value of a quantity (for example profit or cost) subject to limits on resources. A formulated problem has three parts:

• the decision variables, such as $x$ and $y$: the quantities you can choose;
• the objective function, a linear expression in the variables to be maximised (profit) or minimised (cost);
• the constraints, linear inequalities that the variables must satisfy. 'Linear' means each term is a number times a single variable, with no products like $xy$ or powers like $x^2$. Formulation is the translation of the words into this form; solving comes later.

Read the question to find what is being decided, and define one variable for each: the number of batches of loaf A and B, the kilograms of each feed, the number of tables and chairs. Write the units in the definition. The objective function comes from what the question wants to optimise. Total profit $=$ (profit per unit) $\times$ (number made), summed over products: $P=20x+30y$. Total cost has the same form: $C=0.4x+0.6y$. People fed, items sold and so on follow the same pattern. State clearly 'maximise' or 'minimise'. Take care to attach each coefficient to the right variable.

Each limit in the question becomes an inequality. For a resource (flour, hours, money) the amount used is a sum of (amount per unit) $\times$ (number of units): in the bakery example, flour is $3x+2y\le60$ and oven time is $2x+4y\le80$. Use these words as a guide:

• 'at most', 'no more than', 'up to', 'a maximum of': $\le$;
• 'at least', 'no fewer than', 'a minimum of', 'must provide': $\ge$;
• 'at least twice as many $y$ as $x$': $y\ge2x$;
• 'the number of $y$ must not exceed the number of $x$': $y\le x$;
• 'at least 25% of the total is $y$': $y\ge0.25(x+y)$, which simplifies to $3y\ge x$. Check every constraint with a test value to make sure the inequality points the right way. Where the question gives a requirement (a minimum amount of protein) the inequality uses $\ge$.

Quantities such as the number of items made cannot be negative, so you must state non-negativity: $x\ge0$ and $y\ge0$. Some problems have a stronger lower limit, such as $x\ge40$; then this replaces $x\ge0$, but you still state $y\ge0$. If the items are indivisible (tables, parcels, people) the variables must be integers, so state '$x$ and $y$ are integers'. If they are continuous (kilograms of feed, litres) they need not be. This matters when the problem is later solved: the best integer point may differ from the best point in the region.

A bakery makes batches $x$ of A and $y$ of B. A needs 3 kg flour and 2 hours oven time; B needs 2 kg and 4 hours; there are 60 kg and 80 hours; profit is £20 and £30. Maximise $P=20x+30y$ subject to $3x+2y\le60$, $2x+4y\le80$, $x\ge0$, $y\ge0$. To test whether a plan is feasible, substitute it into every constraint. For $x=10$, $y=10$: flour $50\le60$, oven $60\le80$, so it is feasible and gives $P=500$. For $x=20$, $y=10$: flour $80>60$, so it is not feasible. A feasible plan which is not the best possible is not optimal. New conditions, such as a budget, are just extra inequalities added to the list.