17
23
38
28
16
9
12
10
The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .
- Calculate a lower bound for the number of rolls needed.
- Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
- Use full bins to find an optimal solution that uses the minimum number of rolls.
3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-3_755_624_283_283}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-3_750_620_285_1146}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Figure 1 shows the possible allocations of six workers, Charlotte (C), Eleanor (E), Harry (H), Matt (M), Rachel (R) and Simon (S) to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 2 shows an initial matching. - List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
- Explain why it is not possible to find a complete matching.
Simon (S) now has task 3 added to his possible allocation.
- Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating path you use and your complete matching.
(3)
4.
Miri
Jessie
Edward
Katie
Hegg
Beth
Louis
Philip
Natsuko
Dylan - Use the quick sort algorithm to sort the above list into alphabetical order.
(5) - Use the binary search algorithm to locate the name Louis.
5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-5_940_1419_262_322}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
[The total weight of the network is 625 m ]
Figure 3 models a network of paths in a park. The number on each arc represents the length, in m , of that path.
Rob needs to travel along each path to inspect the surface. He wants to minimise the length of his route. - Use the route inspection algorithm to find the length of his route. State the arcs that should be repeated. You should make your method and working clear.
(6)
The surface on each path is to be renewed. A machine will be hired to do this task and driven along each path.
The machine will be delivered to point G and will start from there, but it may be collected from any point once the task is complete. - Given that each path must be traversed at least once, determine the finishing point so that the length of the route is minimised. Give a reason for your answer and state the length of your route.
(3)
6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-6_899_1493_262_285}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
Figure 4 represents a network of roads. The number on each arc gives the length, in km , of that road. - Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
(6) - State the shortest distance from A to G .
(1)
7. Rose makes hanging baskets which she sells at her local market. She makes two types, large and small. Rose makes \(x\) large baskets and \(y\) small baskets.
Each large basket costs \(\pounds 7\) to make and each small basket costs \(\pounds 5\) to make. Rose has \(\pounds 350\) she can spend on making the baskets. - Write down an inequality, in terms of \(x\) and \(y\), to model this constraint.
(2)
Two further constraints are
$$\begin{aligned}
& y \leqslant 20 \text { and }
& y \leqslant 4 x
\end{aligned}$$ - Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make.
- On the grid provided, show these three constraints and \(x \geqslant 0 , y \geqslant 0\). Hence label the feasible region, R.
Rose makes a profit of \(\pounds 2\) on each large basket and \(\pounds 3\) on each small basket. Rose wishes to maximise her profit, £P.
- Write down the objective function.
- Use your graph to determine the optimal numbers of large and small baskets Rose should make, and state the optimal profit.
8.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-8_809_1541_283_262}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{figure}
A construction project is modelled by the activity network shown in Figure 5. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time. - Complete Diagram 2 in the answer book, showing the early and late event times.
- State the critical activities.
- Find the total float for activities M and H . You must make the numbers you use in your calculations clear.
- On the grid provided, draw a cascade (Gantt) chart for this project.
An inspector visits the project at 1 pm on days 16 and 31 to check the progress of the work.
- Given that the project is on schedule, which activities must be happening on each of these days?