Formulating linear programs
Studying this course? Keep your progress in one place.
Key facts
- A linear program has decision variables, an objective function to maximise or minimise, and constraints.
- Define each variable with units: "let be the number of …".
- Everything is linear: no products like and no powers like .
- "At most" gives and "at least" gives .
- State non-negativity (, ) and say when variables must be integers.
What a linear program is
Linear programming finds the best value of a quantity, such as profit or cost, subject to limits on resources. Formulating means translating the words into variables, an objective and constraints.
Linear programming finds the best value of a quantity subject to limits on resources. A formulated problem has three parts:
- the decision variables, such as and : the quantities you can choose
- the objective function, a linear expression to be maximised (profit) or minimised (cost)
- the constraints, linear inequalities the variables must satisfy.
"Linear" means each term is a number times one variable, with no or .
- 1
Define the variables
with units
- 2
Write the objective
maximise or minimise
- 3
Write the constraints
one inequality per limit
- 4
Add non-negativity
and integer conditions if needed
Which of these is NOT allowed in a linear program?
Variables and the objective
Define one variable for each quantity being decided, with units, then write the objective as the sum of each variable multiplied by its profit or cost.
Read the question to find what is being decided and define one variable for each, such as batches of loaf A and B. Write the units.
The objective comes from what is to be optimised. Total profit is (profit per unit) × (number made), summed over products.
Total cost has the same form. State clearly "maximise" or "minimise", and attach each coefficient to the right variable.
- 1
Define variables with units
x = batches of loaf A, y = batches of loaf B
- 2
Write the objective
profit = (profit per batch of A) × x + (profit per batch of B) × y
- 3
Write the constraints
flour and oven time limits
- 4
State non-negativity
x ≥ 0, y ≥ 0
| Loaf A | Loaf B | |
|---|---|---|
| Variable | ||
| Profit per batch | £20 | £30 |
Loaf A
- Variable:
- Profit per batch:
- £20
Loaf B
- Variable:
- Profit per batch:
- £30
- Maximise
A loaf of A makes £20 and a loaf of B makes £30. With x batches of A and y of B, what is the profit?
Writing constraints
Each limit in the question becomes an inequality. A resource used is the sum of (amount per unit) × (number of units).
For the bakery, A needs 3 kg flour and 2 hours oven time, and B needs 2 kg and 4 hours. With 60 kg and 80 hours, flour gives and oven time gives .
Check each constraint with a test value to make sure the inequality points the right way.
Where a question gives a requirement, such as a minimum amount of protein, the inequality uses .
| Inequality | Key phrase | |
|---|---|---|
| At most 60 kg of flour | 3x + 2y ≤ 60 | at most |
| At least twice as many y as x | y ≥ 2x | at least |
| y must not exceed x | y ≤ x | must not exceed |
| At least 25% of the total is y | 3y ≥ x | at least |
Inequality
- At most 60 kg of flour:
- 3x + 2y ≤ 60
- At least twice as many y as x:
- y ≥ 2x
- y must not exceed x:
- y ≤ x
- At least 25% of the total is y:
- 3y ≥ x
Key phrase
- At most 60 kg of flour:
- at most
- At least twice as many y as x:
- at least
- y must not exceed x:
- must not exceed
- At least 25% of the total is y:
- at least
- at most, no more than, up to≤
- at least, no fewer than, a minimum of≥
"The number of chairs must be at least three times the number of tables." With tables and chairs, which is right?
Non-negativity and integers
Quantities cannot be negative, so state and . If the items are indivisible, also state that the variables are integers.
Quantities such as the number of items made cannot be negative, so you must state non-negativity: and .
Some problems have a stronger lower limit, such as ; then this replaces , but you still state .
If the items are indivisible (tables, parcels, people) the variables must be integers. If they are continuous (kilograms, litres) they need not be.
This matters later: the best integer point may differ from the best point in the region.
Continuous
- Kilograms of feed, litres
- Need not be integers
Indivisible
- Tables, parcels, people
- State that x and y are integers
Which variable needs an integer condition?
Worked example and checking
A plan is feasible if it satisfies every constraint. Substitute the values into each inequality in turn.
A bakery makes batches of A and of B. Maximise subject to , , and .
New conditions, such as a budget, are just extra inequalities.
A plan is feasible if it satisfies every constraint. A feasible plan that is not the best possible is not optimal.
Worked example
Is the plan , feasible? What about , ?
- 1
Test , : flour .
- 2
Oven time . Both hold, so it is feasible, with .
- 3
Test , : flour . This fails, so it is not feasible.
A plan breaks one constraint but satisfies all the others. Is it feasible?
Try an exam question
A furniture maker makes x chairs and y tables each week. A chair needs 2 hours of cutting and 1 hour of finishing; a table needs 3 hours of cutting and 2 hours of finishing. There are 120 hours of cutting and 70 hours of finishing available. The profit is £15 per chair and £40 per table, and at least twice as many chairs as tables must be made. Formulate this as a linear programming problem.
[5 marks]
- [1]Let x be the number of chairs and y the number of tables made each week.
- [1]Maximise P = 15x + 40y.
- [1]Cutting: 2x + 3y ≤ 120.
- [1]Finishing: x + 2y ≤ 70 and chairs: x ≥ 2y.
- [1]x ≥ 0, y ≥ 0, with x and y integers.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which inequality represents the flour available?
1 mark, marked against the mark scheme
Which inequality represents the flour available?
1 mark, marked against the mark scheme