Graphical Solutions of LP Problems (Edexcel International A Level (IAL) Maths: Decision 1): Exam Questions

Martin is making three types of cake for a picnic. The three types of cake are carrot cake, apple cake and chocolate cake. Along with other ingredients,

• each carrot cake contains 275 grams of flour, 300 grams of sugar and 5 eggs • each apple cake contains 200 grams of flour, 400 grams of sugar and 2 eggs • each chocolate cake contains 100 grams of flour, 400 grams of sugar and 3 eggs

If Martin makes only one type of cake then he has enough time to prepare 15 carrot cakes or 20 apple cakes or 30 chocolate cakes.

Martin has 5.5 kilograms of flour and 70 eggs available and he has promised the picnic organisers that he will make at least 18 cakes in total.

Martin plans to make a selection of these cakes and wants to minimise the total amount of sugar that he uses.

Let be the number of carrot cakes made, the number of apple cakes made and the number of chocolate cakes made.

Formulate this information as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients.

A further constraint is that

Explain what this constraint means in the context of the question.

The constraint = 2 reduces the problem to the following

Minimise

subject to

Represent these constraints on Diagram 1. Hence determine, and label, the feasible region, .

Use the objective line method to find the optimal number of each type of cake that Martin should make, and the amount of sugar used.

Determine how much flour and how many eggs Martin will have left over after making the optimal number of cakes.

Figure 5 shows the constraints of a linear programming problem in and , where is the feasible region. The equations of two of the lines and the three intersection points, , and , are shown. The coordinates of C are

The objective function is

When the objective is to maximise , the value of is 24

When the objective is to minimise , the value of is 10

(i) Find the coordinates of and .

(ii) Determine the inequalities that define .

An additional constraint, , where is a positive constant, is added to the linear programming problem.

Determine the greatest value of for which this additional constraint does not affect the feasible region.

A company makes three types of storage container, small, medium and large.

The company owner knows that each week she should make

• at least 40 containers in total

• at least twice as many large containers as medium containers

• at most 60% small containers

Each small container requires 1 hour to make, each medium container requires 1.5 hours to make, and each large container requires 2.5 hours to make. The company has a total of 75 hours per week available to make all the containers.

Each small container costs £9 to make, each medium container costs £12 to make and each large container costs £16 to make.

The company owner wants to minimise her total cost.

• Let represent the number of small containers made

• Let represent the number of medium containers made

• Let represent the number of large containers made

Formulate this information as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients.

The company owner now decides to make exactly 45 containers.

Explain why the minimum total cost is achieved when is maximised.

The requirement to make exactly 45 containers reduces the constraints of the problem to the following:

Represent these constraints on Diagram 1. Hence determine, and label, the feasible region, .

Use the objective line method to find the optimal vertex, , of the feasible region. You must make your objective line clear and label .

Write down the number of each type of container the company should make. Calculate the corresponding total cost.

A linear programming problem in and is described as follows.

Maximise , where is a constant

subject to:

Add lines and shading to Diagram 1 below to represent these constraints. Hence determine the feasible region and label it .

For the case when = 0.8

(i) use the objective line method to find the optimal vertex, , of the feasible region. You must draw and label your objective line and label vertex clearly.

(ii) calculate the coordinates of and hence calculate the corresponding value of at .

Given that for a different value of , is not the optimal vertex of ,

determine the range of possible values for . You must make your method and working clear.

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

It is given that

• no two arcs have the same weight

• and are positive integers

• arc CD is not in the minimum spanning tree for the graph

Explain why

It is also given that when Prim’s algorithm, starting at A, is applied to the weighted graph, AB is the first arc selected.

Show that and write down and simplify two further constraints on the values of and .

Represent these four constraints on Diagram 1.

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

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.

Determine the value of and the value of . You must make your method and working clear.

Figure 3 shows the constraints of a linear programming problem in and , where is the feasible region. The equations of two of the lines have been shown in Figure 3.

Given that is a positive constant,

determine, in terms of where necessary, the inequalities that define .

The objective is to maximise

Given that the value of is 38 at the optimal vertex of ,

determine the possible value(s) of . You must show algebraic working and make your method clear.

The graph in Figure 2 is being used to solve a linear programming problem in and . The three constraints have been drawn on the graph and the rejected regions have been shaded out. The three vertices of the feasible region are labelled A, B and C.

Determine the inequalities that define .

The objective function, , is given by

where and are positive constants.

The minimum value of is 8 and the maximum value of occurs at C.

Find the range of possible values of . You must make your method clear.

A bakery makes three types of doughnut. These are ring, jam and custard. The bakery has the following constraints on the number of doughnuts it must make each day.

• The total number of doughnuts made must be at least 200

• They must make at least three times as many ring doughnuts as jam doughnuts

• At most 70% of the doughnuts the bakery makes must be ring doughnuts

• At least a fifth of the doughnuts the bakery makes must be jam doughnuts

It costs 8 pence to make each ring doughnut, 10 pence to make each jam doughnut and 14 pence to make each custard doughnut. The bakery wants to minimise the total daily costs of making the required doughnuts.

Let represent the number of ring doughnuts, let represent the number of jam doughnuts and let represent the number of custard doughnuts the bakery makes each day.

Formulate this as a linear programming problem stating the objective and listing the constraints as simplified inequalities with integer coefficients.

On a given day, instead of making at least 200 doughnuts, the bakery requires that exactly 200 doughnuts are made. Furthermore, the bakery decides to make the minimum number of jam doughnuts which satisfy all the remaining constraints.

Given that the bakery still wants to minimise the total cost of making the required doughnuts, use algebra to

(i) calculate the number of each type of doughnut the bakery will make on that day,

(ii) calculate the corresponding total cost of making all the doughnuts.

A school is planning to run several training days next year for its new teachers, middle leaders and senior leaders.

Next year, the school will need to run

• at least 20 training days in total,

• at most twice as many training days for new teachers when compared to the total number of training days required for both middle and senior leaders,

• at most 25% of the training days for senior leaders.

The costs of running a training day for new teachers, middle leaders and senior leaders are £400, £550 and £750 respectively.

The school wants to minimise the total cost of running the training days.

Let be the number of training days required for new teachers.
Let be the number of training days required for middle leaders.
Let be the number of training days required for senior leaders.

Formulate this information as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients.

The school decides that the number of training days for middle leaders and the number of training days for senior leaders should be in the ratio 5 : 3
This reduces two of the constraints to and .

(i) Express the constraint representing the requirement for a total of at least 20 training days as a simplified inequality with integer coefficients in terms of and only.

(ii) Express the objective in the form where and are integers.

Represent the constraints in and only on Diagram 1. Hence determine, and label, the feasible region, .

Use the objective line method to locate the optimal vertex, V, of the feasible region. You must make your objective line clear and label the optimal vertex, V.

Hence, determine

(i) the total cost of running the training days,

(ii) the number of training days required for senior leaders.

A clothing shop sells a particular brand of shirt, which comes in three different sizes, small, medium and large.

Each month the manager of the shop orders small shirts, medium shirts and large shirts.

The manager forms constraints on the number of each size of shirts he will have to order.

One constraint is that for every 3 medium shirts he will order at least 5 large shirts.

Write down an inequality, with integer coefficients, to model this constraint.

Two further constraints are

and

Use these two constraints to write down statements, in context, that describe the number of different sizes of shirt the manager will order.

The cost of each small shirt is £6, the cost of each medium shirt is £10 and the cost of each large shirt is £15

The manager must minimise the total cost of all the shirts he will order.

Write down the objective function.

Initially, the manager decides to order exactly 150 large shirts.

(i) Rewrite the constraints, as simplified inequalities with integer coefficients, in terms of and only.

(ii) Represent these constraints on Diagram 1. Hence determine, and label, the feasible region .

Use the objective line method to find the optimal vertex, , of the feasible region. You must make your objective line clear and label .

Write down the number of each size of shirt the manager should order. Calculate the total cost of this order.

Later, the manager decides to order exactly 50 small shirts and exactly 75 medium shirts instead of 150 large shirts.

Find the minimum number of large shirts the manager should order and show that this leads to a lower cost than the cost found in (f).