Linear programming · Grade 12 · 3 units

In Linear programming (Grade 12 · 3 units) you practise 6 skills: From the story to the constraints · Regions of the plane · The vertices of the region · The best value · Open regions and least cost · A parameter in the objective. Linear programming looks for the best plan under limits. One variable stands for the number of items of the first kind and a second for the number of the second kind. Each limit in the story, such as hours of work or an amount of material, is an inequality, and neither variable is negative.

Each inequality describes a half plane: one side of a line. To tell which side, substitute the origin. The part shared by all the half planes is the region of possible plans, and its vertices are the points where two lines meet, or a line meets an axis. The objective, such as the profit or the cost, reaches its greatest or least value at one of the vertices. Find every vertex, substitute each in the function and choose. When the constraints say “at least”, the region is open upwards, and the least cost is found there.

Tip: Before calculating, write in one sentence what each variable stands for and exactly what should be made greater or smaller.

Practise on the site →

What you learn

From the story to the constraints

For example: A workshop makes tables and chairs. Each table takes 2 hours of work and each chair 4, and at most 160 hours of work are available. The number of tables is x , and the number of chairs is y . Which inequality describes the constraint?

Answer and solution

The answer: 2x + 4y ≤ 160

The tables use 2x and the chairs use 4y , and together they use at most 160 : 2x + 4y ≤ 160 .

Regions of the plane

For example: The inequality x + 2y ≥ 50 is given. Picture A:

Picture B: Which picture shows all the points that satisfy the inequality?

Answer and solution

The answer: Picture B

Substitute the origin: 1 × 0 + 2 × 0 = 0 , which is less than 50, so the origin does not satisfy the inequality. So shade the side away from the origin. That is Picture B.

The vertices of the region

For example: The line 7x + 3y = 210 is given. At which point does it meet the x axis?

Answer and solution

The answer: (30, 0)

Every point on the x axis has y = 0 . Substitute: 7x = 210 , so x = 30 . The point is (30, 0) .

The best value

For example: A workshop makes tables and chairs. The profit on each table is 90 shekels, and on each chair 60 shekels. The number of tables is x , and the number of chairs is y . The vertices of the region of possible plans are (0, 0) , (30, 0) , (15, 35) and (0, 45) . What is the greatest profit?

Answer and solution

The answer: 3450 shekels

The profit function is R = 90x + 60y . Substitute each vertex: at (0, 0) : 90 × 0 + 60 × 0 = 0 ; at (30, 0) : 90 × 30 + 60 × 0 = 2700 ; at (15, 35) : 90 × 15 + 60 × 35 = 3450 ; at (0, 45) : 90 × 0 + 60 × 45 = 2700 . The greatest profit is 3,450 shekels.

Open regions and least cost

For example: A company hires large and small lorries to move building materials. Each large lorry carries 4 tonnes of sand and each small lorry 5, and at least 175 tonnes of sand must be moved. Each large lorry carries 3 tonnes of gravel and each small lorry 5, and at least 150 tonnes of gravel must be moved. The plan is 25 large lorries and 40 small lorries. Does the plan meet every need?

Answer and solution

The answer: Yes

The number of large lorries is x , and the number of small lorries is y . Check 4x + 5y ≥ 175 : 4 × 25 + 5 × 40 = 300 , which is at least 175. Check 3x + 5y ≥ 150 : 3 × 25 + 5 × 40 = 275 , which is at least 150. Every need is met, so the plan meets them.

A parameter in the objective

For example:

The vertices of the region are the origin, A(50, 0) , B(25, 30) , C(15, 35) and D(0, 5) . The objective is R = 7x + ky . What is the value of the function at the vertex B ?

Answer and solution

The answer: 175 + 30k

Substitute the vertex B(25, 30) : 7 × 25 + 30k = 175 + 30k .

Not on the site yet

Parts of this topic that are not built yet: Drawing the region by hand · Software for linear programming · More than two variables.

The exercises are made by rules and the answers are worked out in code, so there are new exercises every time. The topic follows the Israeli Ministry of Education’s high school maths curriculum at 3 units (grades 10 and 11).

Practise on the site →