Linear programming

Linear programming

IB MYP Maths Extended: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Each limit becomes a constraint, an inequality; counts also satisfy x≥0x\ge0, y≥0y\ge0.
  • Draw each boundary: solid for ≤\le, ≥\ge and dashed for <<, >>; test (0,0)(0,0) to shade.
  • The feasible region is where all constraints are met; its corners are vertices.
  • The best value of the objective function is at a vertex.
  • Answer in a sentence in context.

Forming inequalities

Choose variables, then turn each limit into a constraint using the correct inequality sign.

Each limit becomes a constraint. Counts cannot be negative, so also write x≥0x\ge0 and y≥0y\ge0.

A ratio statement becomes an inequality: "children at most three times the adults" is y≤3xy\le3x.

Resource limits add up each item's use: 4x+2y≤404x+2y\le40.

24681012142468101214161820xy(6, 8)x + y = 144x + 2y = 40
The boundary lines x + y = 14 and 4x + 2y = 40 meet at (6, 8). Each constraint (≤) allows the region below its line, with x ≥ 0 and y ≥ 0.

At most, no more than

Symbol:
≤\le
Example:
x+y≤14x+y\le14

At least, no fewer than

Symbol:
≥\ge
Example:
x≥2x\ge2

Fewer than

Symbol:
<<
Example:
x<5x<5

More than

Symbol:
>>
Example:
y>3y>3

A café bakes x cakes and y pies. It must bake at least twice as many pies as cakes. Which inequality is correct?

Graphing an inequality

Draw the boundary line, solid for ≤ or ≥ and dashed for < or >, then shade the side where a test point makes it true.

  1. Change the inequality to an equals sign and draw the boundary line using two points, such as the axis intercepts.
  2. Solid line for ≤\le, ≥\ge; dashed for <<, >>.
  3. Test (0,0)(0,0) and shade the side where the inequality is true.

For 2x+y≤162x+y\le16 the boundary passes through (8,0)(8,0) and (0,16)(0,16). 0≤160\le16 is true, so shade the side containing the origin.

−2246810−224681012141618xy(8, 0)(0, 16)2x + y = 16
The region 2x+y≤162x+y\le16 (for x≥0x\ge0) is shaded

Worked example

Show x+y≥5x+y\ge5 on a graph.

What kind of boundary line does y<3x−2y<3x-2 need?

The feasible region and its vertices

The feasible region is where all the shaded regions overlap; find each vertex by solving the two boundary equations that meet there.

Every point inside satisfies every constraint. Take 2x+y≤162x+y\le16, x+2y≤14x+2y\le14, x≥0x\ge0 and y≥0y\ge0. The vertices on the axes are (0,0)(0,0), (8,0)(8,0) and (0,7)(0,7); the fourth is where the two lines cross.

−11234567891024681012141618xy(0, 7)(6, 4)(8, 0)2x + y = 16x + 2y = 14
The feasible region and its vertices

Worked example

Find the vertex where 2x+y=162x+y=16 and x+2y=14x+2y=14 meet.

Is the point (5,5)(5,5) in the feasible region?

The objective function

Evaluate the objective function at every vertex and choose the largest (to maximise) or smallest (to minimise).

The objective function is the quantity to maximise or minimise, such as P=30x+20yP=30x+20y.

For vertices (0,0),(8,0),(0,7),(6,4)(0,0),(8,0),(0,7),(6,4) the values are 0,240,140,2600,240,140,260. The maximum profit is \260atat(6,4)$.

Minimising works the same way: for C=2x+3yC=2x+3y with vertices (1,5)(1,5) and (5,1)(5,1), the minimum is 1313 at (5,1)(5,1).

050100150200250(0, 0)(8, 0)(0, 7)(6, 4)VertexProfit
Profit P = 30x + 20y at each vertex

The vertices are (0,0),(4,0),(0,3),(2,2)(0,0),(4,0),(0,3),(2,2) and P=5x+4yP=5x+4y. Where is PP largest?

Solving a real-life problem

Define variables, write the constraints and objective, find the vertices, evaluate and answer in context.

If the variables must be whole numbers, check that the optimal vertex is a whole-number point; if not, test nearby whole-number points inside the region.

  1. 1

    Define the variables

    for example x and y

  2. 2

    Write the constraints

    and the objective function

  3. 3

    Draw the feasible region

    or find its vertices

  4. 4

    Evaluate at each vertex

    the objective function

  5. 5

    Answer in context

    a sentence about the real situation

Solving a linear programming problem
246810125101520xy(0, 12)(6, 8)(10, 0)4x + 2y = 402x + 3y = 36
The charity problem: feasible region and vertices

Worked example

A charity has 40 kg of rice and 36 kg of lentils. A Type A parcel uses 4 kg rice and 2 kg lentils. A Type B parcel uses 2 kg rice and 3 kg lentils. Type A feeds 5 people and Type B feeds 4. Find the plan that feeds the most people.

Why must the final answer be written as a sentence in context?

Try an exam question

The vertices of a feasible region are (0,0)(0,0), (8,0)(8,0), (0,7)(0,7) and (6,4)(6,4). Find the maximum value of P=30x+20yP=30x+20y.

[3 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which inequality shows that the minibus carries at most 14 people?

1 mark, marked against the mark scheme

Revision notes