Linear Programming (LP) Problems (Edexcel International AS Maths: Decision 1): Exam Questions

A linear programming problem in , and is described as follows.

Maximise

subject to

(i) Eliminate from the first two inequality constraints, simplifying your answers

(ii) Hence state the maximum possible value of

Given that takes the maximum possible value found in (a)(ii),

(i) determine the maximum possible value of

(ii) Hence find a solution to the linear programming problem.

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.

Chris has been asked to design a badge in the shape of a triangle subject to the following constraints.

• Angle should be at least three times the size of angle

• Angle should be at least 50° larger than angle

• Angle must be at most 120°

Chris has been asked to maximise the sum of the angles and .

Let be the size of angle in degrees.

Let be the size of angle in degrees.

Let be the size of angle in degrees.

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

You are not required to solve this problem.

A restaurant sells two sizes of pizza, small and large. The restaurant owner knows that, each evening, she needs to make

• at least 85 pizzas in total

• at least twice as many large pizzas as small pizzas

In addition, at most 80% of the pizzas must be large.

Each small pizza costs £2 to make and each large pizza costs £3 to make.

The restaurant owner wants to minimise her costs.

Let represent the number of small pizzas made each evening and let represent the number of large pizzas made each evening.

Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.

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