Formulating linear programs

Formulating linear programs

Spec 5.1 · Edexcel International A Level Maths: Revision notes

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 xx be the number of …".
  • Everything is linear: no products like xyxy and no powers like x2x^2.
  • "At most" gives ≤\le and "at least" gives ≥\ge.
  • State non-negativity (x≥0x\ge0, y≥0y\ge0) 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 xx and yy: 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 xyxy or x2x^2.

  1. 1

    Define the variables

    with units

  2. 2

    Write the objective

    maximise or minimise

  3. 3

    Write the constraints

    one inequality per limit

  4. 4

    Add non-negativity

    and integer conditions if needed

Formulating a problem

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. 1

    Define variables with units

    x = batches of loaf A, y = batches of loaf B

  2. 2

    Write the objective

    profit = (profit per batch of A) × x + (profit per batch of B) × y

  3. 3

    Write the constraints

    flour and oven time limits

  4. 4

    State non-negativity

    x ≥ 0, y ≥ 0

Formulating the bakery problem.

Loaf A

Variable:
xx
Profit per batch:
£20

Loaf B

Variable:
yy
Profit per batch:
£30
The bakery example
  • MaximiseP=20x+30yP=20x+30y

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 3x+2y≤603x+2y\le60 and oven time gives 2x+4y≤802x+4y\le80.

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 ≥\ge.

51015202530354051015202530xy(0, 30)(20, 0)(0, 20)(40, 0)(10, 15)3x + 2y = 602x + 4y = 80
Flour: 3x + 2y ≤ 60 and oven time: 2x + 4y ≤ 80. The boundary lines meet at (10, 15).

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
From words to inequalities
  • 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 xx tables and yy chairs, which is right?

Non-negativity and integers

Quantities cannot be negative, so state x≥0x\ge0 and y≥0y\ge0. 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: x≥0x\ge0 and y≥0y\ge0.

Some problems have a stronger lower limit, such as x≥40x\ge40; then this replaces x≥0x\ge0, but you still state y≥0y\ge0.

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.

−3−2−101234560

Continuous

  • Kilograms of feed, litres
  • Need not be integers

Indivisible

  • Tables, parcels, people
  • State that x and y are integers
When integers are needed

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 xx batches of A and yy of B. Maximise P=20x+30yP=20x+30y subject to 3x+2y≤603x+2y\le60, 2x+4y≤802x+4y\le80, x≥0x\ge0 and y≥0y\ge0.

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.

510152025303540510152025303540xy(10, 15)3x + 2y = 602x + 4y = 80
The flour and oven limits meet at (10, 15)

Worked example

Is the plan x=10x=10, y=10y=10 feasible? What about x=20x=20, y=10y=10?

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]

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

Revision notes