Questions

Question T1_Q1
1. A shop sells two types of watch, analogue watches and digital watches.

The shop manager knows that, each month, she should order at least 60
watches in total.
In addition, at most 80% of the watches she orders must be digital.

Let x be the number of analogue watches ordered and let y be the number of
digital
watches ordered.

(a) Write down inequalities, in terms of x and y, to model these constraints.

(2)

Two further constraints are

y + 3x 140

4y + x 80

(b) Represent all these constraints on Diagram 1 in the answer book. Hence
determine,
and label, the feasible region, R.
(4)

The cost to the shop of ordering an analogue watch is five times the cost of
ordering a
digital watch. The shop manager wishes to minimise the total cost.

(c) Determine the number of each type of watch the shop manager should
order.
You must make your method clear.
(3)

Given that the minimum total cost of ordering the watches is £4455

(d) determine the cost of ordering one analogue watch and the cost of
ordering one
digital watch. You must make your method clear.
(3)
(Total for Question 1 is 12 marks)

1
Question T1_Q2
2.

Figure 5
Figure 5 shows the constraints of a maximisation linear programming
problem in x and y,
where R is the feasible region. An objective line is also shown and labelled on
Figure 5.

A student decides to find the optimal vertex of R by using the two-stage

Simplex algorithm.

Set up an initial tableau for the two-stage Simplex algorithm. (You should not
solve the
linear programming problem.)

(Total for Question 2 is 10 marks)

2
Question T1_Q3
3. A maximisation linear programming problem in x, y and z is to be solved using
the two-stage simplex method.

The partially completed initial tableau is shown below.

Basic
variabl x y z s1 s2 s3 a1 a2 Value
e
s1 1 2 3 1 0 0 0 0 45
a1 3 2 0 0 –1 0 1 0 9
a2 –1 0 4 0 0 –1 0 1 4
P –2 –1 –3 0 0 0 0 0 0
A

(a) Using the information in the above tableau, formulate the linear
programming problem.
State the objective and list the constraints as inequalities.
(4)
(b) Complete the bottom row of Table 1 in the answer book. You should make
your method and working clear.
(2)

The following tableau is obtained after two iterations of the first stage of the
two-stage
simplex method.

(c) (i) Explain how the above tableau shows that a basic feasible solution
has been found for the original linear programming problem.

(ii) Write down the basic feasible solution for the second stage.
(3)
(d) Taking the most negative number in the profit row to indicate the
pivot column, perform one complete iteration of the second stage of the two-
stage simplex method, to obtain a new tableau, T. Make your method clear by
stating the row operations you use.
(5)

3
(e) (i) Explain, using T, whether or not an optimal solution to the original
linear programming problem has been found.

(ii) Write down the value of the objective function.

(iii) State the values of the basic variables.

(3)
(Total for Question 3 is 17 marks)

4
Question T1_Q4
4. Dale is planning a production run of three types of desk. The three types are
lectern desk,
roll top desk and writing desk.

In total, Dale has 400 m2 of wood available; each lectern desk requires 3 m 2,
each
roll top desk requires 5 m2, and each writing desk requires 8 m2

In total, Dale has 350 hours available; each lectern desk requires 3 hours,
each
roll top desk requires 6 hours, and each writing desk requires 10 hours.

Once complete, the desks need to be stored in a warehouse. The warehouse

has 75 m3 of
storage space available; each lectern desk requires 1 m 3, each roll top desk
requires 1.5 m3
and each writing desk requires 1.25 m3

The profit on each lectern desk sold is £40, the profit on each roll top desk
sold is £50
and the profit on each writing desk sold is £65

Dale wants to maximise his profit.

Let x, y and z be the number of lectern desks, roll top desks and writing desks
made
respectively during the production run.

(a) Formulate this situation as a linear programming problem, giving your

constraints as
inequalities.
(4)

(b) Complete the initial tableau in the answer book for this linear
programming problem.
(2)

(c) Taking the most negative number in the profit row to indicate the pivot
column,
perform one complete iteration of the Simplex algorithm. Give an explanation
of the
method by clearly stating the row operations you use.
(4)

After a second iteration, the exact values in the tableau are

5
(d) Use algebra to explain how you know that this tableau is optimal.
(1)

(e) (i) State the optimal number of each type of desk that should be made.
(ii) State the maximum total profit.
(2)

6
(f) Explain, in context, the meaning of the 90 in the value column.
(2)

(g) Give a reason why the profit may be less than the value stated in (e)(ii).
(1)
(Total for Question 4 is 16 marks)

7
Question T1_Q5
5. A linear programming problem in x, y and z is described as follows.

(a) Explain why the Simplex algorithm cannot be used to solve this
linear
programming problem.
(1)
(b) Set up the initial tableau for solving this linear programming problem
using the
big-M method.
(7)

After a first iteration of the big-M method, the tableau is

(c) State the value of each variable after the first iteration.
(1)
(d) Explain why the solution given by the first iteration is not feasible.
(1)

Taking the most negative entry in the profit row to indicate the pivot column,

(e) obtain the most efficient pivot for a second iteration. You must give
reasons for your answer.
(2)
(Total for Question 5 is 12 marks)

8
Question T1_Q6
6.

Figure 3 shows the constraints of a linear programming problem in x and y,

where R is the feasible region.

(a) Write down the inequalities that define R.

(2)

The objective is to maximise P, where P = 3x + y

(b) Obtain the exact value of P at each of the three vertices of R and hence
find the optimal vertex, V.
(4)

The objective is changed to maximise Q, where Q = 3x + ay. Given that a is

a constant and the optimal vertex is still V,

(c) find the range of possible values of a.

(4)
(Total for Question 6 is 10 marks)

9
Question T1_Q7
7. Susie is preparing for a triathlon event that is taking place next month. A triathlon
involves three activities: swimming, cycling and running.
Susie decides that in her training next week she should
 maximise the total time spent cycling and running
 train for at most 39 hours
 spend at least 40% of her time swimming
 spend a total of at least 28 hours of her time swimming and running
Susie needs to determine how long she should spend next week training for each activity. Let
 x represent the number of hours swimming
 y represent the number of hours cycling
 z represent the number of hours running

(a) Formulate the information above as a linear programming problem. State the objective and
list the constraints as simplified inequalities with integer coefficients.
(5)
Susie decides to solve this linear programming problem by using the two-stage Simplex method.

(b) Set up an initial tableau for solving this problem using the two-stage Simplex method.
As part of your solution you must show how
 the constraints have been made into equations using slack variables, exactly one surplus
variable and exactly one artificial variable
 the rows for the two objective functions are formed
(6)
The following tableau T is obtained after one iteration of the second stage of the two-stage
Simplex method.

b.v. x y z s1 s2 s3 Value
y 0 1 0 1 0 1 11
s2 0 0 5 −2 1 −5 62
x 1 0 1 0 0 −1 28
P 0 0 −1 1 0 1 11

(c) Obtain a suitable pivot for a second iteration. You must give reasons for your answer.
(2)
(d) Starting from tableau T, solve the linear programming problem by performing one further iteration
of the second stage of the two-stage Simplex method. You should make your method clear by
stating the row operations you use.
(5)
(Total for Question 7 is 18 marks)

1
0
Answer sheets
Question T1_Q1
1.

1
1
Question T1_Q2
2.

1
2
Question T1_Q3
3.

1
3
Question T1_Q4
4.

1
4
Question T1_Q5
5.

1
5
Question T1_Q6
6.

1
6
Question T1_Q7
7.

1
7