Questions D2 - A-Level Maths

The printed answer book shows the initial tables and the results of iterations $1,2,3$ and 5 when Floyd's algorithm is applied to the network.
(A) Complete the two tables for iteration 4.
(B) Use the final route table to give the shortest route from vertex 5 to vertex 2.
(C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
Use the nearest neighbour algorithm, starting at vertex $\mathbf { 4 }$, to produce a Hamilton cycle in the complete network. Give the length of your cycle.
Interpret your Hamilton cycle from part (ii) in terms of towns actually visited.
Find an improved Hamilton cycle by applying the nearest neighbour algorithm starting from one of the other vertices.
Using the complete network of shortest distances (excluding loops), find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 4 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
Given that the sum of the road lengths in the original network is 43 , give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Show your methodology. Give the length of your walk.

OCR MEI D2 2013 June Q4

4 Colin has a hobby from which he makes a small income. He makes bowls, candle holders and key fobs.
The materials he uses include wood, metal parts, polish and sandpaper. They cost, on average, $\pounds 15$ per bowl, $\pounds 6$ per candle holder and $\pounds 2$ per key fob. Colin has a monthly budget of $\pounds 100$ for materials. Colin spends no more than 30 hours per month on manufacturing these objects. Each bowl takes 4 hours, each candle holder takes 2 hours and each key fob takes half an hour.

Let $b$ be the number of bowls Colin makes in a month, $c$ the number of candle holders and $f$ the number of key fobs. Write out, in terms of these variables, two constraints corresponding to the limit on monthly expenditure on materials, and to the limit on Colin's time. Colin sells the objects at craft fairs. He charges $\pounds 30$ for a bowl, $\pounds 15$ for a candle holder and $\pounds 3$ for a key fob.
Set up an initial simplex tableau for the problem of maximising Colin's monthly income subject to your constraints from part (i), assuming that he sells all that he produces.
Use the simplex algorithm to solve your LP, and interpret the solution from the simplex algorithm. Over a spell of several months Colin finds it difficult to sell bowls so he stops making them.
Modify and solve your LP, using simplex, to find how many candle holders and how many key fobs he should make, and interpret your solution. At the next craft fair Colin takes an order for 4 bowls. He promises to make exactly 4 bowls in the next month.
Set up this modified problem either as an application of two-stage simplex, or as an application of the big-M method. You are not required to solve the problem. The solution now is for Colin to produce 4 bowls, $6 \frac { 2 } { 3 }$ candle holders and no key fobs.
What is Colin's best integer solution to the problem?
Your answer to part (vi) is not necessarily the integer solution giving the maximum profit for Colin. Explain why.

OCR MEI D2 2014 June Q1

1 marks

1 Keith is wondering whether or not to insure the value of his house against destruction. His friend Georgia has told him that it is a waste of money. Georgia argues that the insurance company sets its premiums (how much it charges for insurance) to take account of the probability of destruction, plus an extra fee for its profit. Georgia argues that house-owners are, on average, simply paying fees to the insurance company. Keith's house is valued at $\pounds 400000$. The annual premium for insuring its value against destruction is $\pounds 100$. Past statistics show that the probability of destruction in any one year is 0.0002 .

Draw a decision tree to model Keith's decision and the possible outcomes.
Compute Keith's EMV and give the course of action which corresponds to that EMV.
What would be the insurance premium if there were no fee for the insurance company? For the remainder of the question the insurance premium is still $\pounds 100$.
Suppose that, instead of EMV, Keith uses the utility function utility $= ( \text { money } ) ^ { 0.5 }$.
Compute Keith's utility and give his corresponding course of action. Keith suspects that it may be the case that he lives in an area in which the probability of destruction in a given year, $p$, is not 0.0002 .
Draw a decision tree, using the EMV criterion, to model Keith's decision in terms of $p$, the probability of destruction in the area in which Keith lives.
Find the value of $p$ which would make it worthwhile for Keith to insure his house using the EMV criterion.
Explain why Keith may wish to insure even if $p$ is less than the value which you found in part (vi). [1]
(a) A national Sunday newspaper runs a "You are the umpire" series, in which questions are posed about whether a batsman in cricket is given "out", and why, or "not out". One Sunday the readers were told that a ball had either hit the bat and then the pad, or had missed the bat and hit the pad; the umpire could not be sure which. The ball had then flown directly to a fielder, who had caught it. The LBW (leg before wicket) rule is complicated. The readers were told that this batsman should be given out (LBW) if the ball had not hit the bat. On the other hand, if the ball had hit the bat, then he should be given out (caught). Readers were asked what the decision should be. The answer given in the newspaper was that this batsman should be given not out because the umpire could not be sure that the batsman was out (LBW), and could not be sure that he was out (caught).

OCR MEI D2 2014 June Q3

Explain how the initial feasible tableau shown in Fig. 3 models this problem. \begin{table}[h]
P a b c s 1 s 2 s 3 RHS
1 - 4 - 3 - 1 0 0 0 0
0 10 5 12 1 0 0 12000
0 5 5 7 0 1 0 12000
0 5 3 5 0 0 1 9000
\captionsetup{labelformat=empty} \caption{Fig. 3}
\end{table}
Use the simplex algorithm to solve this problem, and interpret the solution.
In the solution, one of the basic variables appears at a value of 0 . Explain what this means. There is a contractual requirement to provide at least 500 kg of product A .
Show how to incorporate this constraint into the initial tableau ready for an application of the two-stage simplex method. Briefly describe how the method works. You are not required to perform the iterations.

OCR MEI D2 2015 June Q1

1 A furniture manufacturer is planning a production run. He will be making wardrobes, drawer units and desks. All can be manufactured from the same wood. He has available $200 \mathrm {~m} ^ { 2 }$ of wood for the production run. Allowing for wastage, a wardrobe requires $5 \mathrm {~m} ^ { 2 }$, a drawer unit requires $3 \mathrm {~m} ^ { 2 }$, and a desk requires $2 \mathrm {~m} ^ { 2 }$. He has 200 hours available for the production run. A wardrobe requires 4.5 hours, a drawer unit requires 5.2 hours, and a desk requires 3.8 hours. The completed furniture will have to be stored at the factory for a short while before being shipped. The factory has $50 \mathrm {~m} ^ { 3 }$ of storage space available. A wardrobe needs $1 \mathrm {~m} ^ { 3 }$, a drawer unit needs $0.75 \mathrm {~m} ^ { 3 }$, and a desk needs $0.5 \mathrm {~m} ^ { 3 }$. The manufacturer needs to know what he should produce to maximise his income. He sells the wardrobes at $\pounds 80$ each, the drawer units at $\pounds 65$ each and the desks at $\pounds 50$ each.

Formulate the manufacturer's problem as an LP.
Use the Simplex algorithm to solve the LP problem.
Interpret the results.
An extra $25 \mathrm {~m} ^ { 2 }$ of wood is found and is to be used. The new optimal solution is to make 44 wardrobes, no drawer units and no desks. However, this leaves some of each resource (wood, hours and space) left over. Explain how this can be possible.
Given that $x$ and $y$ are propositions, draw a 4-line truth table for $x \Rightarrow y$, allowing $x$ and $y$ to take all combinations of truth values. If $x$ is false and $x \Rightarrow y$ is true, what can be deduced about the truth value of $y$ ? A story has it that, in a lecture on logic, the philosopher Bertrand Russell (1872-1970) mentioned that a false proposition implies any proposition. A student challenged this, saying "In that case, given that $1 = 0$, prove that you are the Pope."
Russell immediately replied, "Add 1 to both sides of the equation: then we have $2 = 1$. The set containing just me and the Pope has 2 members. But $2 = 1$, so the set has only 1 member; therefore, I am the Pope." Russell's string of statements is an example of a deductive sequence. Let $a$ represent " $1 = 0$ ", $b$ represent " $2 = 1$ ", $c$ represent "Russell and the Pope are 2" and $d$ represent "Russell and the Pope are 1". Then Russell's deductive sequence can be written as $( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d$.
Assuming that $a$ is false, $b$ is false, $a \Rightarrow b$ is true, $c$ is true, and that $d$ can take either truth value, draw a 2-line truth table for $( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d$.
What does the table tell you about $d$ with respect to the false proposition $a$ ?
Explain why Russell introduced propositions $b$ and $c$ into his argument.
Russell could correctly have started a deductive sequence:
$a \wedge [ a \Rightarrow ( ( 0.5 = - 0.5 ) \Rightarrow ( 0.25 = 0.25 ) ) ]$.
Had he have done so could he correctly have continued it to end at $d$ ?
Justify your answer.
Draw a combinatorial circuit to represent $( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d$. 3 Floyd's algorithm is applied to the incomplete network on 4 nodes drawn below. The weights on the arcs represent journey times.
\includegraphics[max width=\textwidth, alt={}, center]{4b5bc097-1052-4e44-8623-a84ceaab0289-4_400_558_347_751} The final matrices are shown below. \begin{table}[h] \begin{center} \captionsetup{labelformat=empty} \caption{final time matrix} \begin{tabular}{ | l | r | r | r | r | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{$\mathbf { 1 }$} & $\mathbf { 2 }$ & $\mathbf { 3 }$ & \multicolumn{1}{c|}{$\mathbf { 4 }$}
\hline $\mathbf { 1 }$ & 6 & 5 & 3 & 10
\hline

OCR MEI D2 2015 June Q3

3 Floyd's algorithm is applied to the incomplete network on 4 nodes drawn below. The weights on the arcs represent journey times.
\includegraphics[max width=\textwidth, alt={}, center]{4b5bc097-1052-4e44-8623-a84ceaab0289-4_400_558_347_751} The final matrices are shown below. \begin{table}[h] \begin{center} \captionsetup{labelformat=empty} \caption{final time matrix} \begin{tabular}{ | l | r | r | r | r | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{$\mathbf { 1 }$} & $\mathbf { 2 }$ & $\mathbf { 3 }$ & \multicolumn{1}{c|}{$\mathbf { 4 }$}
\hline $\mathbf { 1 }$ & 6 & 5 & 3 & 10
\hline $\mathbf { 2 }$ & 5 & 4 & 2 & 5
\hline $\mathbf { 3 }$ & 3 & 2 & 4 & 7
\hline

OCR MEI D2 2015 June Q4

$\mathbf { 4 }$ & 10 & 5 & 7 & 10
\hline \end{tabular} \end{center} \end{table} \begin{table}[h]

\captionsetup{labelformat=empty} \caption{final route matrix}

\cline { 2 - 5 } \multicolumn{1}{c\|}{}	$\mathbf { 1 }$	$\mathbf { 2 }$	$\mathbf { 3 }$	$\mathbf { 4 }$
$\mathbf { 1 }$	3	3	3	3
$\mathbf { 2 }$	3	3	3	4
$\mathbf { 3 }$	1	2	2	2
$\mathbf { 4 }$	2	2	2	2

\end{table}

Draw the complete network of shortest times.
Explain how to use the final route matrix to find the quickest route from node $\mathbf { 4 }$ to node $\mathbf { 1 }$ in the original incomplete network. Give this quickest route. A new node, node 5, is added to the original incomplete network. The new journey times are shown in the table. \begin{center} \begin{tabular}{ | l | c | c | c | c | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$
\hline

OCR MEI D2 2015 June Q5

$\mathbf { 5 }$ & 4 & - & - & 2
\hline \end{tabular} \end{center} (iii) Draw the complete 5-node network of shortest times. (You are not required to use an algorithm to find the shortest times.)
(iv) Write down the final time matrix and the final route matrix for the complete 5 -node network. (You do not need to apply Floyd's algorithm.)
(v) (A) Apply the nearest neighbour algorithm to the complete 5-node network of shortest times, starting at node 1. Give the time for the cycle you produce.
(B) Starting at node 3, a possible cycle in the complete 5-node network of shortest times is $\mathbf { 3 2 1 5 4 3 . }$ Give the actual cycle to which this corresponds in the incomplete 5-node network of journey times.
(vi) By deleting node 5 and its arcs from the complete 5 -node network of shortest times, and then using Kruskal's algorithm, produce a lower bound for the solution to the associated practical travelling salesperson problem. Show clearly your use of Kruskal's algorithm.
(vii) In the incomplete 5-node network of journey times, find a quickest route starting at node $\mathbf { 5 }$ and using each of the 7 arcs at least once. Give the time of your route. 4 Helen has a meeting to go to in London. She has to travel from her home in G on the south coast to KC in London. She can drive from G to the west to A to catch a train, or she can drive to the east to W to catch a train on a different line. From both A and W she can travel to mainline terminuses V or LB in London. She will then travel by tube either from V to KC , or from LB to KC . The times for the various steps of her journey are shown in the tables. Both train services and tube services are subject to occasional delays, and these are modelled in the tables.

Driving times	to A	to W
From G	20 min	15 min

\multirow{2}{*}{Train journey}	To V			To LB
	normal time	probability of delay	delay	normal time	probability of delay	delay
From A	1 hr 40 min	0.05	10 min	1 hr 45 min	0.05	10 min
From W	1 hr 30 min	0.10	20 min	1 hr 35 min	0.10	20 min

Helen wants to choose the route which will give the shortest expected journey time.
(i) Draw a decision tree to model Helen's decisions and the possible outcomes.
(ii) Calculate Helen's shortest expected journey time and give the route which corresponds to that shortest expected journey time. As she gets into her car, Helen hears a travel bulletin on the radio warning of a broken escalator at V. This means that routes through V will take Helen 10 minutes longer.
(iii) Find the value of the radio information, explaining your calculation.
(iv) Why might the shortest expected journey time not be the best criterion for choosing a route for Helen?

OCR MEI D2 2016 June Q1

1 Martin is considering paying for a vaccination against a disease. If he catches the disease he would not be able to work and would lose $\pounds 900$ in income because he would have to stay at home recovering. The vaccination costs $\pounds 20$. The vaccination would reduce his risk of catching the disease during the year from 0.02 to 0.001 .

Draw a decision tree for Martin.
Evaluate the EMV of Martin's loss at each node of your tree, and give the action that Martin should take to minimise the EMV of his loss. Martin can answer a medical questionnaire which will give an estimate of his susceptibility to the disease. If he is found to be susceptible, then his chance of catching the disease is 0.05 . Vaccination will reduce that to 0.0025 . If he is found not to be susceptible, then his chance of catching the disease is 0.01 and vaccination will reduce it to 0.0005 . Historically, $25 \%$ of people are found to be susceptible.
What is the EMV of this questionnaire? Martin decides not to answer the questionnaire. He also decides that there is more than just his EMV to be considered in deciding whether or not to have the vaccination. The vaccination itself is likely to have side effects, but catching the disease would be very unpleasant. Martin estimates that he would find the effects of the disease 1000 times more unpleasant than the effects of the vaccination.
Analyse which course of action would minimise the unpleasantness for Martin.

OCR MEI D2 2016 June Q2

Emelia: 'I won't go out for a walk if it's not dry or not warm.'
Gemma: ‘It’s warm. Let’s go!’
Will what Gemma has said convince Emelia, and if not, why not?
If it is daytime and the car headlights are on, then it is raining. If the dashboard lights are dimmed then the car headlights are on.
It is daytime.
It is not raining.
1. What can you deduce?
2. Prove your deduction.
In this part of the question the switch X is represented by
\includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_104_138_824_1226} The switch can be wired into a circuit so that current flows when
the switch is up
\includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_103_177_1005_593}
but does not flow when it is down
\includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_111_167_1000_1334} Or the switch can be wired so that current flows when
the switch is down
\includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_109_172_1228_639}
but does not flow when it is up
\includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_109_174_1228_1327}
1. Explain how the following circuit models $( \mathrm { A } \wedge \mathrm { B } ) \Rightarrow \mathrm { C }$.
  \includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_365_682_1484_694} In the following circuit B1 and B2 represent 'ganged' switches. This means that the two switches are either both up or both down.
  \includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_364_1278_2042_397}
2. Given that A is down, C is up and current is flowing, what can you deduce?

OCR MEI D2 2016 June Q3

3 Neil is refurbishing a listed building. There are two types of paint that he can use for the inside walls. One costs $\pounds 1.45$ per $\mathrm { m } ^ { 2 }$ and the other costs $\pounds 0.95$ per $\mathrm { m } ^ { 2 }$. He must paint the lower half of each wall in the more expensive paint. He has $350 \mathrm {~m} ^ { 2 }$ of wall to paint. He has a budget of $\pounds 400$ for wall paint. The more expensive paint is easier to use, and so Neil wants to use as much of it as possible. Initially, the following LP is constructed to help Neil with his purchasing of paint.
Let $x$ be the number of $\mathrm { m } ^ { 2 }$ of wall painted with the expensive paint.
Let $y$ be the number of $\mathrm { m } ^ { 2 }$ of wall painted with the less expensive paint. $$\begin{array} { l l } \text { Maximise } & P = x + y
\text { subject to } & 1.45 x + 0.95 y \leqslant 400
& y - x \leqslant 0
& x \geqslant 0
& y \geqslant 0 \end{array}$$

Explain the purpose of the inequality $y - x \leqslant 0$.
The formulation does not include the inequality $x + y \geqslant 350$. State what this constraint models and why it has been omitted from the formulation.
Use the simplex algorithm to solve the LP. Pivot first on the "1" in the $y$ column. Interpret your solution. The solution shows that Neil needs to buy more paint. He negotiates an increase in his budget to $\pounds 450$.
Find the solution to the LP given by changing $1.45 x + 0.95 y \leqslant 400$ to $1.45 x + 0.95 y \leqslant 450$, and interpret your solution. Neil realises that although he now has a solution, that solution is not the best for his requirements.
Explain why the revised solution is not optimal for Neil. In order to move to an optimal solution Neil needs to change the objective of the LP and add another constraint to it.
Write down the new LP and the initial tableau for using two-stage simplex to solve it. Give a brief description of how to use two-stage simplex to solve it.
\includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-5_497_558_269_751}
(a) Solve the route inspection problem in the network above, showing the methodology you used to ensure that your solution is optimal. Show your route.
(b) Floyd's algorithm is applied to the same network to find the complete network of shortest distances. After three iterations the distance and route matrices are as follows. \begin{center} \begin{tabular}{ | c | c | c | c | c | c | } \cline { 2 - 6 } \multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ & $\mathbf { 5 }$
\hline $\mathbf { 1 }$ & 48 & 24 & 28 & 11 & 15
\hline $\mathbf { 2 }$ & 24 & 8 & 4 & 11 & 16
\hline $\mathbf { 3 }$ & 28 & 4 & 8 & 7 & 12
\hline

OCR MEI D2 2016 June Q4

$\mathbf { 4 }$ & 11 & 11 & 7 & 14 & 14
\hline

OCR MEI D2 2016 June Q5

$\mathbf { 5 }$ & 15 & 16 & 12 & 14 & 24
\hline \end{tabular} \end{center}

\cline { 2 - 6 } \multicolumn{1}{c\|}{}	$\mathbf { 1 }$	$\mathbf { 2 }$	$\mathbf { 3 }$	$\mathbf { 4 }$	$\mathbf { 5 }$
$\mathbf { 1 }$	2	2	2	4	5
$\mathbf { 2 }$	1	3	3	3	3
$\mathbf { 3 }$	2	2	2	4	5
$\mathbf { 4 }$	1	3	3	3	5
$\mathbf { 5 }$	1	3	3	4	3

Perform the fourth iteration of the algorithm, and show that there is no change to either matrix in the final iteration.
Show how to use the matrices to give the shortest distance and the shortest route from vertex $\mathbf { 1 }$ to vertex 2.
Draw the complete network of shortest distances.
Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
By temporarily deleting vertex $\mathbf { 1 }$ and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.

Edexcel D2 Q1

The payoff matrix for player $A$ in a two-person zero-sum game is shown below.

\cline { 3 - 5 } \multicolumn{2}{c\|}{}	$B$
\cline { 3 - 5 } \multicolumn{2}{c\|}{}	I	II	III
\multirow{3}{*}{$A$}	I	- 3	4	0
\cline { 2 - 5 }	II	2	2	1
\cline { 2 - 5 }	III	3	- 2	- 1

Find the optimal strategy for each player and the value of the game.

Edexcel D2 Q2

2. A supplier has three warehouses, $A , B$ and $C$, at which there are 42,26 and 32 crates of a particular cereal respectively. Three supermarkets, $D , E$ and $F$, require 29, 47 and 24 crates of the cereal respectively. The supplier wishes to minimise the cost in meeting the requirements of the supermarkets. The cost, in pounds, of supplying one crate of the cereal from each warehouse to each supermarket is given in the table below.

\cline { 2 - 4 } \multicolumn{1}{c\|}{}	$D$	$E$	$F$
$A$	19	22	13
$B$	18	14	26
$C$	27	16	19

Formulate this information as a linear programming problem.

State your decision variables.
Write down the objective function in terms of your decision variables.
Write down the constraints, explaining what each one represents.

Edexcel D2 Q3

3. This question should be answered on the sheet provided. A couple are making the arrangements for their wedding. They are deciding whether to have the ceremony at their church, a local castle or a nearby registry office. The reception will then be held in a marquee, at the castle or at a local hotel. Both the castle and hotel offer catering services but the couple are also considering using Deluxe Catering or Cuisine, who can both provide the food at any venue. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{f662b4da-12c1-4f30-ab5d-fb132f19e643-3_944_1504_605_258} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} The network in Figure 1 shows the costs incurred (including transport), in hundreds of pounds, according to the choice the couple make for each stage of the day. Use dynamic programming to find how the couple can minimise the total cost of their wedding and state the total cost of this arrangement.
(9 marks)

Edexcel D2 Q4

4. This question should be answered on the sheet provided. A travelling salesman problem relates to the network represented by the following table of distances in kilometres. You may assume that the network satisfies the triangle inequality.

	A	B	$C$	D	$E$	$F$	G	$H$
A	-	85	59	31	47	52	74	41
B	85	-	104	73	51	68	43	55
C	59	104	-	54	62	88	61	45
D	31	73	54	-	40	59	65	78
E	47	51	62	40	-	56	71	68
$F$	52	68	88	59	56	-	53	49
G	74	43	61	65	71	53	-	63
H	41	55	45	78	68	49	63	-

Showing your method clearly, use

the nearest neighbour algorithm, beginning with $A$,
Prim's algorithm with $H$ deleted,
to show that the minimum distance travelled, $d \mathrm {~km}$, satisfies the inequality $357 \leq d \leq 371$.
(11 marks)

Edexcel D2 Q5

5. The payoff matrix for player $X$ in a two-person zero-sum game is shown below.

\cline { 3 - 5 } \multicolumn{2}{c\|}{}	$Y$
\cline { 2 - 5 } \multicolumn{2}{c\|}{}	$Y _ { 1 }$	$Y _ { 2 }$	$Y _ { 3 }$
\multirow{2}{*}{$X$}	$X _ { 1 }$	10	4	3
\cline { 2 - 5 }	$X _ { 2 }$	${ } ^ { - } 4$	${ } ^ { - } 1$	9

Using a graphical method, find the optimal strategy for player $X$.
Find the optimal strategy for player $Y$.
Find the value of the game.

Edexcel D2 Q6

6. Four sales representatives ( $R _ { 1 } , R _ { 2 } , R _ { 3 }$ and $R _ { 4 }$ ) are to be sent to four areas ( $A _ { 1 } , A _ { 2 } , A _ { 3 }$ and $A _ { 4 }$ ) such that each representative visits one area. The estimated profit, in tens of pounds, that each representative will make in each area is shown in the table below.

\cline { 2 - 5 } \multicolumn{1}{c\|}{}	$A _ { 1 }$	$A _ { 2 }$	$A _ { 3 }$	$A _ { 4 }$
$R _ { 1 }$	37	29	44	51
$R _ { 2 }$	45	30	43	41
$R _ { 3 }$	32	27	39	50
$R _ { 4 }$	43	25	51	55

Use the Hungarian method to obtain an allocation which will maximise the total profit made from the visits. Show the state of the table after each stage in the algorithm.
(13 marks)

Edexcel D2 Q7

7. A distributor has six warehouses. At one point the distributor needs to move 25 lorries from warehouses $W _ { 1 } , W _ { 2 }$ and $W _ { 3 }$ to warehouses $W _ { \mathrm { A } } , W _ { \mathrm { B } }$ and $W _ { \mathrm { C } }$ for the minimum possible cost. The transportation tableau below shows the unit cost, in tens of pounds, of moving a lorry between two warehouses, and the relevant figures regarding the number of lorries available or required at each warehouse.

	$W _ { \text {A } }$	$W _ { \mathrm { B } }$	$W _ { \mathrm { C } }$	Available
$W _ { 1 }$	7	8	10	10
$W _ { 2 }$	9	6	5	8
$W _ { 3 }$	11	5	7	7
Required	5	12	8

Write down the initial solution given by the north-west corner rule.
Obtain improvement indices for the unused routes.
Use the stepping-stone method to find an improved solution and state why it is degenerate.
Placing a zero in cell $( 2,2 )$, show that the improved solution is optimal and state the transportation pattern.

Find the total cost of the optimal solution. \section*{Please hand this sheet in for marking}

Stage	State	Destination	Cost	Total cost
\multirow[t]{3}{*}{1}	Marquee	Deluxe Cuisine
	Castle	Deluxe Castle Cuisine
	Hotel	Deluxe Cuisine Hotel
\multirow[t]{3}{*}{2}	Church	Marquee Castle Hotel
	Castle	Marquee Castle
	Registry Office	Marquee Castle Hotel
3	Home	Castle Church Registry

\section*{Please hand this sheet in for marking}

A B $C$ D $E$ $F$ $G$ $H$
A - 85 59 31 47 52 74 41
B 85 - 104 73 51 68 43 55
C 59 104 - 54 62 88 61 45
D 31 73 54 - 40 59 65 78
E 47 51 62 40 - 56 71 68
$F$ 52 68 88 59 56 - 53 49
$G$ 74 43 61 65 71 53 - 63
$H$ 41 55 45 78 68 49 63 -
A $B$ $C$ D $E$ $F$ $G$ $H$
A - 85 59 31 47 52 74 41
B 85 - 104 73 51 68 43 55
C 59 104 - 54 62 88 61 45
D 31 73 54 - 40 59 65 78
E 47 51 62 40 - 56 71 68
$F$ 52 68 88 59 56 - 53 49
G 74 43 61 65 71 53 - 63
$H$ 41 55 45 78 68 49 63 -

Edexcel D2 Q1

1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{4e50371b-0c1c-4b4e-b21d-60858ae160df-2_659_986_203_479} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} The network in Figure 1 shows the shortest distance by road, in kilometres, between five villages. Find the best achievable upper bound for a tour of the network, of minimum length, using the nearest neighbour algorithm.

Edexcel D2 Q2

2. A school entrance examination consists of three papers - Mathematics, English and Verbal Reasoning. Three teams of markers are to mark one style of paper each. The table below shows the average time, in minutes, taken by each team to mark one script for each style of paper.

\cline { 2 - 4 } \multicolumn{1}{c\|}{}	Maths	English	Verbal
Team 1	3	9	2
Team 2	4	7	1
Team 3	5	8	3

It is desired that the scripts are marked as quickly as possible.
Formulate this information as a linear programming problem.

State your decision variables.
Write down the objective function in terms of your decision variables.
Write down the constraints, explaining what each one represents.

Edexcel D2 Q3

3. A two-person zero-sum game is represented by the payoff matrix for player $A$ shown below.

\cline { 3 - 5 } \multicolumn{2}{c\|}{}	$B$
\cline { 3 - 5 } \multicolumn{2}{c\|}{}	I	II	III
\multirow{2}{*}{$A$}	I	1	- 1	2
\cline { 2 - 5 }	II	3	5	- 1

Represent the expected payoffs to $A$ against $B$ 's strategies graphically and hence determine which strategy is not worth considering for player $B$.
Find the best strategy for player $A$ and the value of the game.

Edexcel D2 Q4

4. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{4e50371b-0c1c-4b4e-b21d-60858ae160df-3_771_1479_1178_237} \captionsetup{labelformat=empty} \caption{Fig. 2}

\end{figure} A salesman is planning a four-day trip beginning at home and ending at town $I$. He will spend the first night in town $A , B$ or $C$, the second night in town $D , E$ or $F$ and the third night in town $G$ or $H$. The network in Figure 2 shows the expected net profit, in tens of pounds, that he will gain on each day according to the route he chooses. Use dynamic programming to find the route which should maximise the salesman’s net profit. State the expected profit from using this route.
(10 marks)

Edexcel D2 Q5

5. A construction company has three teams of workers available, each of which is to be assigned to one of four jobs at a site. The following table shows the estimated cost, in tens of pounds, of each team doing each job:

	Windows	Conservatory	Doors	Greenhouse
Team A	27	80	8	81
Team B	28	60	5	71
Team C	30	90	7	73

Use the Hungarian algorithm to find an allocation of jobs which will minimise the total cost. Show the state of the table after each stage in the algorithm and state the cost of the final assignment.
(13 marks)

\cline { 2 - 5 } \multicolumn{1}{c\|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)
\(\mathbf { 1 }\)	3	3	3	3
\(\mathbf { 2 }\)	3	3	3	4
\(\mathbf { 3 }\)	1	2	2	2
\(\mathbf { 4 }\)	2	2	2	2

\cline { 2 - 6 } \multicolumn{1}{c\|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)	\(\mathbf { 5 }\)
\(\mathbf { 1 }\)	2	2	2	4	5
\(\mathbf { 2 }\)	1	3	3	3	3
\(\mathbf { 3 }\)	2	2	2	4	5
\(\mathbf { 4 }\)	1	3	3	3	5
\(\mathbf { 5 }\)	1	3	3	4	3

\cline { 3 - 5 } \multicolumn{2}{c\|}{}	\(Y\)
\cline { 2 - 5 } \multicolumn{2}{c\|}{}	\(Y _ { 1 }\)	\(Y _ { 2 }\)	\(Y _ { 3 }\)
\multirow{2}{*}{\(X\)}	\(X _ { 1 }\)	10	4	3
\cline { 2 - 5 }	\(X _ { 2 }\)	\({ } ^ { - } 4\)	\({ } ^ { - } 1\)	9

P	a	b	c	s 1	s 2	s 3	RHS
1	- 4	- 3	- 1	0	0	0	0
0	10	5	12	1	0	0	12000
0	5	5	7	0	1	0	12000
0	5	3	5	0	0	1	9000

\cline { 3 - 5 } \multicolumn{2}{c\|}{}	\(B\)
\cline { 3 - 5 } \multicolumn{2}{c\|}{}	I	II	III
\multirow{3}{*}{\(A\)}	I	- 3	4	0
\cline { 2 - 5 }	II	2	2	1
\cline { 2 - 5 }	III	3	- 2	- 1

\cline { 2 - 4 } \multicolumn{1}{c\|}{}	\(D\)	\(E\)	\(F\)
\(A\)	19	22	13
\(B\)	18	14	26
\(C\)	27	16	19

\cline { 2 - 5 } \multicolumn{1}{c\|}{}	\(A _ { 1 }\)	\(A _ { 2 }\)	\(A _ { 3 }\)	\(A _ { 4 }\)
\(R _ { 1 }\)	37	29	44	51
\(R _ { 2 }\)	45	30	43	41
\(R _ { 3 }\)	32	27	39	50
\(R _ { 4 }\)	43	25	51	55

	\(W _ { \text {A } }\)	\(W _ { \mathrm { B } }\)	\(W _ { \mathrm { C } }\)	Available
\(W _ { 1 }\)	7	8	10	10
\(W _ { 2 }\)	9	6	5	8
\(W _ { 3 }\)	11	5	7	7
Required	5	12	8

Questions D2 (547 questions)

Browse by module

Browse by board

OCR MEI D2 2013 June Q3

OCR MEI D2 2013 June Q4

OCR MEI D2 2014 June Q1

OCR MEI D2 2014 June Q3

OCR MEI D2 2015 June Q1

OCR MEI D2 2015 June Q3

OCR MEI D2 2015 June Q4

OCR MEI D2 2015 June Q5

OCR MEI D2 2016 June Q1

OCR MEI D2 2016 June Q2

OCR MEI D2 2016 June Q3

OCR MEI D2 2016 June Q4

OCR MEI D2 2016 June Q5

Edexcel D2 Q1

Edexcel D2 Q2

Edexcel D2 Q3

Edexcel D2 Q4

Edexcel D2 Q5

Edexcel D2 Q6

Edexcel D2 Q7

Edexcel D2 Q1

Edexcel D2 Q2

Edexcel D2 Q3

Edexcel D2 Q4

Edexcel D2 Q5