7. A tailor makes two types of garment, \(A\) and \(B\). He has available \(70 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(90 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(A\) requires \(1 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(3 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(B\) requires \(2 \mathrm {~m} ^ { 2 }\) of each fabric. The tailor makes \(x\) garments of type \(A\) and \(y\) garments of type \(B\).

1. Explain why this can be modelled by the inequalities $$\begin{aligned} & x + 2 y \leq 70
   & 3 x + 2 y \leq 90
   & x \geq 0 , y \geq 0 \end{aligned}$$ (2 marks)
   The tailor sells type \(A\) for \(\pounds 30\) and type \(B\) for \(\pounds 40\). All garments made are sold. The tailor wishes to maximise his total income.
2. Set up an initial Simplex tableau for this problem.
   (3 marks)
3. Solve the problem using the Simplex algorithm.
   (8 marks) Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-004_452_828_995_356} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Obtain the coordinates of the points A, \(C\) and \(D\).
5. Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4.
   (3 marks) Answer Book (AB12)
   Graph Paper (ASG2) Items included with question papers Answer booklet Paper Reference(s)
   6689 \section*{Decision Mathematics D1 (New Syllabus)} \section*{Advanced/Advanced Subsidiary} \section*{Monday 25 June 2001 - Morning} Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates may 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 the name of the examining body (Edexcel), your centre number, candidate number, the unit title (Decision Mathematics D1), the paper reference (6689), your surname, other name and signature. Full marks may be obtained for answers to ALL questions. This paper has seven questions. 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. \section*{END}
   1. The precedence table for activities involved in a small project is shown below
6. Explain
   1. the purpose of the variables \(r , s\) and \(t\),
   2. the final row of the tableau.
7. Solve this Linear Programming problem by using the Simplex alogorithm. Increase \(y\) for your first iteration and than increase \(x\) for your second iteration.
8. Interpret your solution. \section*{Materials required for examination
   Graph Paper (ASG2)} Items included with question papers
   Answer booklet \section*{Decision Mathematics D1 (New Syllabus)
   \textbackslash section*\{Advanced/Advanced Subsidiary\}} \section*{Friday 18 January 2002 - Afternoon} Candidates may use any calculator EXCEPT those with the facility for symbolic algebra, differentiation and/or integration. Thus candidates may 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. Full marks may be obtained for answers to ALL questions.
   This paper has seven questions. 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. Ann, Bryn, Daljit, Gareth and Nickos have all joined a new committee. Each of them is to be allocated to one of five jobs \(1,2,3,4\) or 5 . The table shows each member's preferences for the jobs.

   Ann	1 or 2
   Bryn	3 or 1
   Daljit	2 or 4
   Gareth	5 or 3
   Nickos	1 or 2

   Initially Ann, Bryn, Daljit and Gareth are allocated the first job in their lists shown in the table.
9. Draw a bipartite graph to model the preferences shown in the table and indicate, in a distinctive way, the initial allocation of jobs.
10. Use the matching improvement algorithm to find a complete matching, showing clearly your alternating path.
11. Find a second alternating path from the initial allocation.
    2. (i) Use the binary search algorithm to try to locate the name SABINE in the following alphabetical list. Explain each step of the algorithm.
    1. ABLE
    2. BROWN
    3. COOKE
    4. DANIEL
    5. DOUBLE
    6. \(F E W\)
    7. OSBORNE
    8. PAUL
    9. SWIFT
    10. TURNER
        (ii) Find the maximum number of iterations of the binary search algorithm needed to locate a name in a list of 1000 names.

    	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)
    \(A\)	-	10	12	13	20	9
    \(B\)	10	-	7	15	11	7
    \(C\)	12	7	-	11	18	3
    \(D\)	13	15	11	-	27	8
    \(E\)	20	11	18	27	-	18
    \(F\)	9	7	3	8	18	-

    The table shows the distances, in metres, between six nodes \(A , B , C , D , E\), and \(F\) of a network.
12. Use Prim's algorithm, starting at \(A\), to solve the minimum connector problem for this table of distances. Explain your method and indicate the order in which you selected the edges.
13. Draw your minimum spanning tree and find its total length.
14. State whether your minimum spanning tree is unique. Justify your answer.
    (ii) A connected network \(N\) has seven vertices.
15. State the number of edges in a minimum spanning tree for \(N\). A minimum spanning tree for a connected network has \(n\) edges.
16. State the number of vertices in the network. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-010_474_737_379_367}
    \end{figure} Figure 1 shows a network of roads. Erica wishes to travel from \(A\) to \(L\) as quickly as possible. The number on each edge gives the time, in minutes, to travel along that road.
17. Use Dijkstra's algorithm to find a quickest route from \(A\) to \(L\). Complete all the boxes on the answer sheet and explain clearly how you determined the quickest route from your labelling.
18. Show that there is another route which also takes the minimum time
    5. Two fertilizers are available, a liquid \(X\) and a powder \(Y\). A bottle of \(X\) contains 5 units of chemical \(A , 2\) units of chemical \(B\) and \(\frac { 1 } { 2 }\) unit of chemical \(C\). A packet of \(Y\) contains 1 unit of \(A , 2\) units of \(B\) and 2 units of \(C\). A professional gardener makes her own fertilizer. She requires at least 10 units of \(A\), at least 12 units of \(B\) and at least 6 units of \(C\). She buys \(x\) bottles of \(X\) and \(y\) packets of \(Y\).
19. Write down the inequalities which model this situation.
20. On the grid provided construct and label the feasible region. A bottle of \(X\) costs \(\pounds 2\) and a packet of \(Y\) costs \(\pounds 3\).
21. Write down an expression, in terms of \(x\) and \(y\), for the total cost \(\pounds T\).
22. Using your graph, obtain the values of \(x\) and \(y\) that give the minimum value of \(T\). Make your method clear and calculate the minimum value of \(T\).
23. Suggest how the situation might be changed so that it could no longer be represented graphically. Figure 2 \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{6.} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-011_403_789_372_324}
    \end{figure} A company has 3 warehouses \(W _ { 1 } , W _ { 2 }\), and \(W _ { 3 }\). It needs to transport the goods stored there to 2 retail outlets \(R _ { 1 }\) and \(R _ { 2 }\). The capacities of the possible routes, in van loads per day, are shown in Fig 2. Warehouses \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\) have 14, 12 and 14 van loads respectively available per day and retail outlets \(R _ { 1 }\) and \(R _ { 2 }\) can accept 6 and 25 van loads respectively per day.
24. On Diagram 1 on the answer sheet add a supersource \(W\), a supersink \(R\) and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added.
25. State the maximum flow along
    1. \(W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R\),
    2. \(W W _ { 3 } \quad C \quad R _ { 2 } \quad R\).
26. Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from \(W\) to \(R\). Show your working on Diagram 2. List each flow-augmenting route you use, together with its flow.
27. From your final flow pattern, determine the number of van loads passing through \(B\) each day. The company has the opportunity to increase the number of vans loads from one of the warehouses \(W _ { 1 } , W _ { 2 } , W _ { 3 }\), to \(A , B\) or \(C\).
28. Determine how the company should use this opportunity so that it achieves a maximal flow.
    , 啨 \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-011_307_990_404_1690}
    \end{figure} A project is modelled by the activity network shown in Fig 3. The activities are represented by the edges. The number in brackets on each edge gives the time, in days, taken to complete the activity.
29. Calculate the early time and the late time for each event. Write these in the boxes on the answer sheet.
30. Hence determine the critical activities and the length of the critical path.
31. Obtain the total float for each of the non-critical activities.
32. On the first grid on the answer sheet, draw a cascade (Gantt) chart showing the information obtained in parts (b) and (c). Each activity requires one worker. Only two workers are available.
33. On the second grid on the answer sheet, draw up a schedule and find the minimum time in which the 2 workers can complete the project. \section*{(New Syllabus)} \section*{Advanced/Advanced Subsidiary} \section*{Thursday 23 May 2002 - Afternoon} Nil 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. 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.

    Ashford	6
    Colnbrook	1
    Datchet	18
    Feltham	12
    Halliford	9
    Laleham	0
    Poyle	5
    Staines	13
    Wraysbury	14

    The table above shows the points obtained by each of the teams in a football league after they had each played 6 games. The teams are listed in alphabetical order. Carry out a quick sort to produce a list of teams in descending order of points obtained.
    2. While solving a maximizing linear programming problem, the following tableau was obtained.

    Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
    \(r\)	0	0	\(1 \frac { 2 } { 3 }\)	1	0	\(- \frac { 1 } { 6 }\)	\(\frac { 2 } { 3 }\)
    \(y\)	0	1	\(3 \frac { 1 } { 3 }\)	0	1	\(- \frac { 1 } { 3 }\)	\(\frac { 1 } { 3 }\)
    \(x\)	1	0	- 3	0	- 1	\(\frac { 1 } { 2 }\)	1
    \(P\)	0	0	1	0	1	1	11

34. Explain why this is an optimal tableau.
35. Write down the optimal solution of this problem, stating the value of every variable.
36. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\).
    3. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-013_291_307_395_383}
    \end{figure} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-013_287_311_397_781}
    \end{figure} Five members of staff \(1,2,3,4\) and 5 are to be matched to five jobs \(A , B , C , D\) and \(E\). A bipartite graph showing the possible matchings is given in Fig. 1 and an initial matching \(M\) is given in Fig. 2. There are several distinct alternating paths that can be generated from \(M\). Two such paths are $$2 - B = 4 - E$$ and $$2 - A = 3 - D = 5 - E$$
37. Use each of these two alternating paths, in turn, to write down the complete matchings they generate. Using the maximum matching algorithm and the initial matching \(M\),
38. find two further distinct alternating paths, making your reasoning clear. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-013_380_965_374_1690}
    \end{figure} Figure 3 shows the network of paths in a country park. The number on each path gives its length in km . The vertices \(A\) and \(I\) represent the two gates in the park and the vertices \(B , C , D , E , F , G\) and \(H\) represent places of interest.
39. Use Dijkstra's algorithm to find the shortest route from \(A\) to \(I\). Show all necessary working in the boxes in the answer booklet and state your shortest route and its length. The park warden wishes to check each of the paths to check for frost damage. She has to cycle along each path at least once, starting and finishing at \(A\).
40. 1. Use an appropriate algorithm to find which paths will be covered twice and state these paths.
    2. Find a route of minimum length.
    3. Find the total length of this shortest route.
       5. An algorithm is described by the flow chart below.
       \includegraphics[max width=\textwidth, alt={}, center]{3147dad8-2d3c-42fd-b288-7017ff1fce16-014_1040_825_372_411}
41. Given that \(a = 645\) and \(b = 255\), complete the table in the answer booklet to show the results obtained at each step when the algorithm is applied.
42. Explain how your solution to part (a) would be different if you had been given that \(a = 255\) and \(b = 645\).
43. State what the algorithm achieves. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-014_711_1049_411_1640}
    \end{figure} A building project is modelled by the activity network shown in Fig. 4. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity. The left box entry at each vertex is the earliest event time and the right box entry is the latest event time.
44. Determine the critical activities and state the length of the critical path.
45. State the total float for each non-critical activity.
46. On the grid in the answer booklet, draw a cascade (Gantt) chart for the project. Given that each activity requires one worker,
47. draw up a schedule to determine the minimum number of workers required to complete the project in the critical time. State the minimum number of workers.
    7. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-015_472_766_520_342}
    \end{figure}
48. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
49. 1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
    2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
50. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
    2. Prove that your final flow is maximal.