8. A chemical company produces two products \(X\) and \(Y\). Based on potential demand, the total production each week must be at least 380 gallons. A major customer's weekly order for 125 gallons of \(Y\) must be satisfied.
Product \(X\) requires 2 hours of processing time for each gallon and product \(Y\) requires 4 hours of processing time for each gallon. There are 1200 hours of processing time available each week. Let \(x\) be the number of gallons of \(X\) produced and \(y\) be the number of gallons of \(Y\) produced each week.
- Write down the inequalities that \(x\) and \(y\) must satisfy.
It costs \(\pounds 3\) to produce 1 gallon of \(X\) and \(\pounds 2\) to produce 1 gallon of \(Y\). Given that the total cost of production is \(\pounds C\),
- express \(C\) in terms of \(x\) and \(y\).
The company wishes to minimise the total cost.
- Using the graphical method, solve the resulting Linear Programming problem. Find the optimal values of \(x\) and \(y\) and the resulting total cost.
- Find the maximum cost of production for all possible choices of \(x\) and \(y\) which satisfy the inequalities you wrote down in part (a).
\section*{(New Syllabus)}
\section*{Advanced/Advanced Subsidiary}
\section*{Tuesday 5 November 2002 - Morning}
\section*{Materials required for examination
Graph Paper (ASG2)}
Items included with question papers
Answer booklet
Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates must NOT use calculators such as the Texas Instruments TI 89, TI 92, Casio CFX 9970G, Hewlett Packard HP 48G.
In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
When a calculator is used, the answer should be given to an appropriate degree of accuracy.
Full marks may be obtained for answers to ALL questions.
This paper has eight questions. Page 8 is blank.
You must ensure that your answers to parts of questions are clearly labelled.
You must show sufficient working to make your methods clear to the Examiner. Answers without working may gain no credit.
1.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-016_312_446_360_1873}
\end{figure}
A Hamilton cycle for the graph in Fig. 1 begins \(A , X , D , V , \ldots\). - Complete this Hamiltonian cycle.
- Hence use the planarity algorithm to determine if the graph is planar.
2. The precedence table for activities involved in manufacturing a toy is shown below.
A bipartite graph showing this information is drawn in the answer booklet.
Initially, \(A , B , D\) and \(E\) are allocated to tasks 2, 1, 3 and 5 respectively.
Starting from the given initial matching, use the matching improvement algorithm to find a complete matching, showing your alternating paths clearly.
2. (a) Explain why it is impossible to draw a network with exactly three odd vertices.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-024_460_700_1160_388}
\end{figure}
The Route Inspection problem is solved for the network in Fig. 1 and the length of the route is found to be 100 . - Determine the value of \(x\), showing your working clearly.
3. (a) Describe the differences between Prim's algorithm and Kruskal's algorithm for finding a minimum connector of a network.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-024_415_800_383_1720}
\end{figure} - Listing the arcs in the order that you select them, find a minimum connector for the network in Fig. 2, using
- Prim's algorithm,
- Kruskal's algorithm.
4. The following list gives the names of some students who have represented Britain in the International Mathematics Olympiad.
Roper ( \(R\) ), Palmer ( \(P\) ), Boase ( \(B\) ), Young ( \(Y\) ), Thomas ( \(T\) ), Kenney ( \(K\) ), Morris ( \(M\) ), Halliwell ( \(H\) ), Wicker ( \(W\) ), Garesalingam ( \(G\) ).
- Use the quick sort algorithm to sort the names above into alphabetical order.
- Use the binary search algorithm to locate the name Kenney.
5.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 3}
\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-025_330_1059_315_214}
\end{figure}
The network in Fig. 3 shows the activities involved in the process of producing a perfume. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity. - Calculate the early time and the late time for each event, showing them on Diagram 1 in the answer booklet.
- Hence determine the critical activities.
- Calculate the total float time for \(D\).
Each activity requires only one person.
- Find a lower bound for the number of workers needed to complete the process in the minimum time.
Given that there are only three workers available, and that workers may not share an activity,
- schedule the activities so that the process is completed in the shortest time. Use the time line in the answer booklet. State the new shortest time.
6. A company produces two types of self-assembly wooden bedroom suites, the 'Oxford' and the 'York'. After the pieces of wood have been cut and finished, all the materials have to be packaged. The table below shows the time, in hours, needed to complete each stage of the process and the profit made, in pounds, on each type of suite. - On the diagram in the answer book draw straight lines to show which components need to be connected.
- Starting with the Hamiltonian cycle \(A B C D E F A\), use the planarity algorithm to determine whether it is possible to build this product on a circuit board.
(4)
3.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-028_997_458_285_468}
\end{figure}
The bipartite graph in Fig. 2 shows the possible allocations of people \(A , B , C , D , E\) and \(F\) to tasks \(1,2,3,4,5\) and 6 .
An initial matching is obtained by matching the following pairs
A to 3,
B to 4,
\(C\) to 1,
\(F\) to 5 . - Show this matching in a distinctive way on the diagram in the answer book.
- Use an appropriate algorithm to find a maximal matching. You should state any alternating paths you have used.
4. (a) Draw an activity network described in this precedence table, using as few dummies as possible.
Initially Alan, Geoff, Laura and Nicola are assigned to the first checkpoint in their individual list. - Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
- Starting from this initial matching, use the maximum matching algorithm to find an improved matching. Clearly list any alternating paths you use.
- Explain why it is not possible to find a complete matching.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-037_385_1072_283_1658}
\end{figure}
Figure 1 shows a network of roads. The number on each edge gives the time, in minutes, to travel along that road. Avinash wishes to travel from \(S\) to \(T\) as quickly as possible. - Use Dijkstra's algorithm to find the shortest time to travel from \(S\) to \(T\).
- Find a route for Avinash to travel from \(S\) to \(T\) in the shortest time. State, with a reason, whether this route is a unique solution.
On a particular day Avinash must include \(C\) in his route.
- Find a route of minimal time from \(S\) to \(T\) that includes \(C\), and state its time.
3.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-038_430_497_251_452}
\end{figure} - Describe a practical problem that could be modelled using the network in Fig. 2 and solved using the route inspection algorithm.
- Use the route inspection algorithm to find which paths, if any, need to be traversed twice.
- State whether your answer to part (b) is unique. Give a reason for your answer.
- Find the length of the shortest inspection route that traverses each arc at least once and starts and finishes at the same vertex.
Given that it is permitted to start and finish the inspection at two distinct vertices,
- find which two vertices should be chosen to minimise the length of the route. Give a reason for your answer.
4.
- Glasgow
- Newcastle
- Manchester
- York
- Leicester
- Birmingham
- Cardiff
- Exeter
- Southampton
- Plymouth
A binary search is to be performed on the names in the list above to locate the name Newcastle. - Explain why a binary search cannot be performed with the list in its present form.
- Using an appropriate algorithm, alter the list so that a binary search can be performed. State the name of the algorithm you use.
- Use the binary search algorithm on your new list to locate the name Newcastle.