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}$$ 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. Solve the problem using the Simplex algorithm. Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-008_686_1277_1319_453} \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. 6689 Decision Mathematics 1 (New Syllabus) Order of selecting edges
   Final tree
6. Minimum total length of cable
   Question 4 to be answered on this page
7. \(A\)
   • Monday (M)
     \(B\) ◯
   • Tuesday (Tu)
     \(C \odot\)
   • Wednesday (W)
     \(D\) ◯
   • Thursday (Th)
     \(E\) -
   • Friday (F)
   Question 5 to be answered on this page
   Key
8. Early
   Time
   Late
   Time
   \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_433_227_534_201}
   \(F ( 3 )\)
   \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_117_222_1016_992}
   H(4) K(6)
9. Critical activities
   Length of critical path \(\_\_\_\_\)
10. 
    \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_492_1604_1925_266} Question 6 to be answered on pages 4 and 5
11. 1. SAET \(\_\_\_\_\)
    2. SBDT \(\_\_\_\_\)
    3. SCFT \(\_\_\_\_\)
12. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-012_691_1307_893_384} \captionsetup{labelformat=empty} \caption{Diagram 1}
    \end{figure}
13. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_699_1314_167_382} \captionsetup{labelformat=empty} \caption{Diagram 2}
    \end{figure} Flow augmenting routes
14. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_693_1314_1368_382} \captionsetup{labelformat=empty} \caption{Diagram 3}
    \end{figure}
15. \(\_\_\_\_\)
    \section*{Decision Mathematics D1
    (New Syllabus)
    Advanced/Advanced Subsidiary } Monday 25 June 2001 - Morning
    Time: 1 hour 30 minutes Materials required for examination
    Answer Book (AB12)
    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 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.
    1. The precedence table for activities involved in a small project is shown below
16. Explain
    1. the purpose of the variables \(r , s\) and \(t\),
    2. the final row of the tableau.
17. Solve this Linear Programming problem by using the Simplex alogorithm. Increase \(y\) for your first iteration and than increase \(x\) for your second iteration.
18. Interpret your solution. Initially Ann, Bryn, Daljit and Gareth are allocated the first job in their lists shown in the table.
19. Draw a bipartite graph to model the preferences shown in the table and indicate, in a distinctive way, the initial allocation of jobs.
20. Use the matching improvement algorithm to find a complete matching, showing clearly your alternating path.
21. 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. FEW
    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.
    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

22. Explain why this is an optimal tableau.
23. Write down the optimal solution of this problem, stating the value of every variable.
24. 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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-045_438_475_403_494}
    \end{figure} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-045_442_476_403_1108}
    \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$$
25. 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\),
26. find two further distinct alternating paths, making your reasoning clear. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-046_577_1476_367_333}
    \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.
27. 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.
    (5) 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\).
28. 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)
       5. An algorithm is described by the flow chart below.
       \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-047_1590_1264_363_539}
29. 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.
30. Explain how your solution to part (a) would be different if you had been given that \(a = 255\) and \(b = 645\).
31. State what the algorithm achieves.
    6. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-048_1083_1608_421_259}
    \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.
32. Determine the critical activities and state the length of the critical path.
33. State the total float for each non-critical activity.
34. On the grid in the answer booklet, draw a cascade (Gantt) chart for the project. Given that each activity requires one worker,
35. 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.
    (3)
    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]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-049_719_1170_590_438}
    \end{figure}
36. 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.
37. 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,
38. 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.