Edexcel A-Level Mathematics AS D1.5 Linear Programming Questions

Practise linear programming by formulating constraints, graphing feasible regions and choosing optimal continuous or integer solutions.

Exam points

Translate resource, ratio and total conditions into simplified linear inequalities.
Graph constraints, label the feasible region and test vertices with the objective function.
Adjust the optimum when variables must be integers and check feasibility in context.

Covered syllabus points

D1.5.1 - Formulation of problems as linear programs D1.5.2 - Graphical solution of two variable problems D1.5.3 - Consideration of problems where solutions must have integer

[Maximum number: 12]

The head of a Mathematics department needs to order three types of paper. The three types of paper are plain, lined and graph.

All three types of paper are sold in reams. (A ream is 500 sheets of paper.)
Based on the last academic year the head of department formed the following constraints.
- At least half the paper must be lined
- No more than 15% of the paper must be graph paper
- The ratio of plain paper to graph paper must be 5: 2

The cost of each ream of plain, lined and graph paper is £ 5, £ 12 and £ 15 respectively. The head of department has at most £ 834 to spend on paper.

The head of department wants to maximise the total number of reams of paper ordered.
Let x, y and z represent the number of reams of plain paper, lined paper and graph paper ordered respectively.

(a)

Formulate this information as a linear programming problem in x and y only, stating the objective and listing the constraints as simplified inequalities with integer coefficients.

The head of department decides to order exactly 42 reams of lined paper and still wishes to maximise the total number of reams of paper ordered.

[ 7 ]

$\frac12(x+y+z)\le y \quad(\Rightarrow x-y+z\le0)$ $\frac3{20}(x+y+z)\ge z \quad(\Rightarrow 3x+3y-17z\ge0)$ 2x=5z $5x+12y+15z\le834$
Eliminating z from the objective x+y+z and at least one correct constraint, or stating the objective and eliminating z from at least two correct constraints.
Maximise P=1.4x+y, subject to
$\begin{aligned} 11x+12y&\le834\\ 7x-5y&\le0\\ 19x-15y&\le0\\ x&\ge0,\quad y\ge0 \end{aligned}$
(7)

(b)

Determine

[ 5 ]

(i)

the total number of reams of paper to be ordered,

[ 2 ]

Substitute y=42 into the LP:
$x\le30,\quad x\le30,\quad x\le\frac{630}{19}$
so x=30.
Total number of reams ordered:
1.4(30)+42=84

(ii)

the number of reams of graph paper to be ordered.

[ 3 ]

[Maximum number: 6]

Figure 5

Figure 5 shows a weighted graph that contains 12 arcs and 8 vertices.

It is given that
- no two arcs have the same weight
- x and y are positive integers
- arc CD is not in the minimum spanning tree for the graph

(a)

Represent these four constraints on Diagram 1 in the answer book.

[ 4 ]

y=2x,\quad y=x+7,\quad x=1,\quad 3y=4x+8

Shade the common feasible region satisfying the four strict inequalities.

Figure for Answer to Question (a) — Edexcel A-Level Mathematics AS

(b)

Using Diagram 1 only, write down the possible pairs of values that x and y can take in the form (x, y).

The minimum spanning tree for the weighted graph in Figure 5 has total weight 73 Six of the seven arcs in the minimum spanning tree are AB, AD, BC, CE, EF and GH.

[ 2 ]

All question bank results loaded

Covered syllabus points

Question 1

Question (a)

Question (b)

Question (i)

Question (ii)

Question 2

Question (a)

Question (b)