MetadataPastPaper.sampleTitle

### Part (a)
We perform a forward pass to find the early event times, \(E(i)\), for each node \(i\):
* \(E(0) = 0\)
* \(E(1) = 0 + 4 = 4\)
* \(E(2) = 0 + 6 = 6\)
* \(E(3) = \max(E(1) + 0, E(2) + 0) = \max(4, 6) = 6\)
* \(E(4) = E(3) + 3 = 6 + 3 = 9\)
* \(E(5) = \max(E(1) + 5, E(4) + 0) = \max(9, 9) = 9\)
* \(E(6) = E(2) + 7 = 6 + 7 = 13\)
* \(E(7) = \max(E(5) + 2, E(4) + 4, E(6) + 5) = \max(11, 13, 18) = 18\)
* \(E(8) = E(7) + 3 = 18 + 3 = 21\)

Thus, the minimum completion time of the project is 21 days.

We perform a backward pass to find the late event times, \(L(i)\), for each node \(i\):
* \(L(8) = 21\)
* \(L(7) = 21 - 3 = 18\)
* \(L(6) = 18 - 5 = 13\)
* \(L(5) = 18 - 2 = 16\)
* \(L(4) = \min(L(5) - 0, L(7) - 4) = \min(16, 14) = 14\)
* \(L(3) = L(4) - 3 = 14 - 3 = 11\)
* \(L(2) = \min(L(3) - 0, L(6) - 7) = \min(11, 6) = 6\)
* \(L(1) = \min(L(3) - 0, L(5) - 5) = \min(11, 11) = 11\)
* \(L(0) = \min(L(1) - 4, L(2) - 6) = \min(7, 0) = 0\)

An activity \(X\) from node \(i\) to node \(j\) is critical if \(E(i) = L(i)\), \(E(j) = L(j)\), and \(E(j) - E(i) = \text{duration}(X)\).
Applying this, the critical path is: \(0 \xrightarrow{B} 2 \xrightarrow{E} 6 \xrightarrow{H} 7 \xrightarrow{I} 8\).
So, the critical activities are B, E, H, I.

### Part (b)
The total float for an activity \(X\) starting at node \(i\) and ending at node \(j\) with duration \(d\) is given by:
\(\text{Float}(X) = L(j) - E(i) - d\)

* Activity C (Node 1 to Node 5, duration 5):
\(\text{Float}(C) = L(5) - E(1) - 5 = 16 - 4 - 5 = 7\) days.

* Activity D (Node 3 to Node 4, duration 3):
\(\text{Float}(D) = L(4) - E(3) - 3 = 14 - 6 - 3 = 5\) days.

* Activity G (Node 4 to Node 7, duration 4):
\(\text{Float}(G) = L(7) - E(4) - 4 = 18 - 9 - 4 = 5\) days.

### Part (c)
(i) A valid 2-worker schedule to complete the project in 21 days is:
* Worker 1: B [0, 6], E [6, 13], H [13, 18], I [18, 21].
* Worker 2: A [0, 4], C [4, 9], D [9, 12], F [12, 14], G [14, 18].

(ii) The sequence of critical activities B, E, H, and I has a total duration of 21 days (6 + 7 + 5 + 3 = 21). Because E depends on B, H depends on E, and I depends on H, these activities must be performed in series. Therefore, even with more workers, the project cannot be completed in less than 21 days.

Part (a)
* M1: Clear evidence of finding early times at key nodes (e.g. Node 3 = 6, Node 5 = 9, Node 7 = 18).
* A1: Correct minimum completion time of 21 days.
* A1: Correct critical activities: B, E, H, I.

Part (b)
* M1: Uses the correct total float formula: \(\text{Float}(X) = L(\text{end}) - E(\text{start}) - \text{duration}\).
* A1: Correct float for C = 7 days.
* A1: Correct float for D = 5 days.
* A1: Correct float for G = 5 days.

Part (c)(i)
* M1: Attempting a 2-worker schedule with some activities assigned correctly according to predecessors.
* A1: Critical path activities scheduled sequentially with no gaps or overlaps on one worker: B [0, 6], E [6, 13], H [13, 18], I [18, 21].
* A1: Remaining activities scheduled on the second worker without any time overlaps: A [0, 4], C [4, 9], D [9, 12], F [12, 14], G [14, 18].
* A1: Complete, fully correct schedule satisfying all precedence constraints.

Part (c)(ii)
* M1: Identification of the sequential/dependent nature of the critical activities (B, E, H, I).
* A1: Clear explanation that because these critical activities are in series, their total sum of 21 days cannot be reduced by introducing more workers.

(a) Prim's algorithm starting at \(A\):
- Select vertex \(D\) with edge \(AD\) (weight 12).
- Next, from \(\{A, D\}\), select vertex \(B\) with edge \(DB\) (weight 10).
- Next, from \(\{A, D, B\}\), select vertex \(C\) with edge \(DC\) (weight 14).
- Next, from \(\{A, D, B, C\}\), select vertex \(E\) with edge \(CE\) (weight 11).

Order of selection of vertices: \(A, D, B, C, E\).
Edges added in order: \(AD, DB, DC, CE\).

The minimum spanning tree is:
\[
\begin{aligned}
&A - D \quad \text{(weight 12)} \\
&| \\
&B \quad \text{(weight 10)} \\
&| \\
&C \quad \text{(weight 14)} \\
&| \\
&E \quad \text{(weight 11)}
\end{aligned}
\]

Total weight of the minimum spanning tree is:
\(12 + 10 + 14 + 11 = 47\).

(b) Nearest neighbour algorithm starting at \(A\):
- From \(A\), the nearest unvisited vertex is \(D\) (weight 12).
- From \(D\), the nearest unvisited vertex is \(B\) (weight 10).
- From \(B\), the nearest unvisited vertex is \(C\) (weight 18).
- From \(C\), the nearest unvisited vertex is \(E\) (weight 11).
- From \(E\), return to the starting vertex \(A\) (weight 20).

Tour: \(A - D - B - C - E - A\).
Length of tour: \(12 + 10 + 18 + 11 + 20 = 71\).

(c) Deleting vertex \(A\) and its incident edges leaves the network with vertices \(B, C, D, E\).
The minimum spanning tree of the remaining network consists of edges:
- \(BD\) (weight 10)
- \(CE\) (weight 11)
- \(CD\) (weight 14)

Weight of MST of the remaining network: \(10 + 11 + 14 = 35\).

The two shortest edges incident to \(A\) are:
- \(AD\) (weight 12)
- \(AB\) (weight 15)

Sum of these two shortest edges: \(12 + 15 = 27\).

Lower Bound = Weight of remaining MST + two shortest edges incident to \(A\)
\(35 + 27 = 62\).

(d) The best inequality using the results of (b) and (c) is:
\(62 \le L \le 71\) (where \(L\) is the length of the optimal tour).

(a)
- **M1**: Prim's algorithm applied starting at \(A\). Selects at least three vertices in the correct order: \(A, D, B...\)
- **A1**: Correct order of vertices: \(A, D, B, C, E\) and correct edges listed: \(AD, DB, DC, CE\).
- **A1**: Correctly drawn MST showing vertices \(A, B, C, D, E\) and only the edges \(AD, DB, DC, CE\).
- **A1**: Correct total weight of 47.

(b)
- **M1**: Nearest neighbour algorithm applied correctly from \(A\), visiting all vertices once and returning to \(A\).
- **A1**: Correct tour \(A - D - B - C - E - A\) (or equivalent list of vertices) and correct length of 71.

(c)
- **M1**: Attempting to find the MST of the remaining network \(\{B, C, D, E\}\) (must see at least two correct edges of \(BD, CE, CD\)).
- **A1**: Correct weight of 35 for the remaining MST (or list of edges with weights).
- **M1**: Finding the two shortest edges incident to \(A\) (weights 12 and 15) and adding them to their MST weight.
- **A1**: Correct lower bound of 62.

(d)
- **B1**: Follow through their values from (b) and (c), provided lower bound < upper bound: \(62 \le L \le 71\) (accept strict inequality on the lower bound side if specified, i.e., \(62 < L \le 71\)).

(a) Applying Dijkstra's algorithm starting at \(A\):

| Vertex | Order of labelling | Final value | Working values |
| :---: | :---: | :---: | :---: |
| \(A\) | 1 | 0 | |
| \(B\) | 3 | 12 | 12 |
| \(C\) | 4 | 16 | 20, 16 |
| \(D\) | 2 | 10 | 10 |
| \(E\) | 6 | 26 | 26, 27 |
| \(F\) | 5 | 23 | 23, 25 |
| \(G\) | 7 | 35 | 35, 36 |
| \(H\) | 8 | 39 | 39, 43 |

Shortest Path: \(A - D - F - H\)
Length of Shortest Path: \(39\text{ km}\)

(b) (i) Route Inspection Algorithm (or Chinese Postman Algorithm).

(ii) Sum of all edge weights in the network:
\(12 + 10 + 8 + 14 + 6 + 11 + 9 + 13 + 7 + 10 + 12 + 16 + 8 = 136\)

The odd vertices are \(B\), \(D\), \(F\), and \(G\).

We consider the three possible pairings of these odd vertices:
- \(BD\) and \(FG\):
\(BD = BC + CD = 8 + 6 = 14\)
\(FG = 12\)
\(\text{Sum} = 14 + 12 = 26\)

- \(BF\) and \(DG\):
\(BF = BC + CF = 8 + 9 = 17\)
\(DG = DF + FG = 13 + 12 = 25\)
\(\text{Sum} = 17 + 25 = 42\)

- \(BG\) and \(DF\):
\(BG = BE + EG = 14 + 10 = 24\)
\(DF = 13\)
\(\text{Sum} = 24 + 13 = 37\)

The minimum sum of paired edges is \(26\), corresponding to pairing \(BD\) and \(FG\).
Therefore, the edges that must be repeated are \(BC\), \(CD\), and \(FG\).

Length of shortest route: \(136 + 26 = 162\text{ km}\).

(c) (i) Unchanged. The current shortest path from \(A\) to \(H\) is \(A - D - F - H\) of length \(39\). To use the new road \(BD\), we would need to go via \(B\), giving a path like \(A - B - D\) which has length \(12 + 15 = 27\), whereas the direct path \(A - D\) has length \(10\). Thus, the new road does not form part of a shorter route to \(H\).

(ii) Adding the road \(BD\) adds a new edge of length \(15\text{ km}\), which must be traversed by the inspector. This increases the sum of all edges to \(136 + 15 = 151\). However, adding the edge \(BD\) changes the degrees of both \(B\) and \(D\) from \(3\) to \(4\), making them even. The only remaining odd vertices are now \(F\) and \(G\). The shortest path between \(F\) and \(G\) is \(FG\) of length \(12\). Therefore, only the edge \(FG\) needs to be repeated.
New shortest route length: \(151 + 12 = 163\text{ km}\).
Since \(163 > 162\), the length of the shortest inspection route increases by \(1\text{ km}\).

(a)
- M1: Standard Dijkstra grid attempted with correct working values at \(B\) and \(D\) from starting node \(A\).
- A1: Order of labeling correct at \(A\), \(D\), \(B\), and \(C\).
- A1: Order of labeling correct at all 8 vertices: \(A(1), D(2), B(3), C(4), F(5), E(6), G(7), H(8)\).
- A1: All working values correct at each node.
- A1: Final values correct: \(A(0), D(10), B(12), C(16), F(23), E(26), G(35), H(39)\).
- A1: Correct path \(A - D - F - H\) and length \(39\text{ km}\) stated.

(b)
- B1: Correctly names the 'Route Inspection' or 'Chinese Postman' algorithm.
- M1: Finds the sum of all edges (\(136\)) and identifies the four odd vertices: \(B, D, F, G\).
- M1: Lists all three pairings of the four odd vertices with their respective shortest path values.
- A1: Correct values for the pairings: \(BD+FG = 26\), \(BF+DG = 42\), and \(BG+DF = 37\).
- A1: Correctly identifies repeated edges (\(BC, CD, FG\)) and calculates the total length as \(162\text{ km}\).

(c)
- B1: Explains that the shortest path is unchanged because using \(BD\) (e.g. \(A-B-D = 27\)) is longer than existing paths (e.g. \(A-D = 10\)).
- B1: Explains that \(B\) and \(D\) become even, leaving only \(F\) and \(G\) odd. Shows calculation of new length \(151 + 12 = 163\text{ km}\) and concludes that the length increases by \(1\text{ km}\).

### Part (a)
To construct the activity network with the minimum number of dummy activities, we analyze the dependencies:
1. \(A\) and \(B\) have no predecessors, so they start from a single start node (Node 1).
2. \(C\) and \(D\) depend only on \(A\). \(E\) depends on both \(A\) and \(B\).
- Let \(A\) end at Node 2, and \(B\) end at Node 3.
- Activities \(C\) and \(D\) start from Node 2.
- To allow \(E\) to depend on both, we draw a dummy activity (Dummy 1, \(D_1\)) from Node 2 to Node 3. Now Node 3 is preceded by both \(A\) (via the dummy) and \(B\). Activity \(E\) starts from Node 3.
3. \(F\) depends only on \(C\).
- Let \(C\) end at Node 5. Activity \(F\) starts from Node 5 and goes to the sink node (Node 7).
4. \(G\) and \(H\) depend on \(C\), \(D\), and \(E\).
- Since \(F\) depends only on \(C\), we cannot merge the end of \(C\) directly with the ends of \(D\) and \(E\).
- Therefore, we end \(D\) and \(E\) at Node 6, and draw a dummy activity (Dummy 2, \(D_2\)) from Node 5 (end of \(C\)) to Node 6.
- Node 6 now represents the completion of \(C\) (via \(D_2\)), \(D\), and \(E\).
5. Both \(G\) and \(H\) start from Node 6 and have no succeeding activities, so they must end at the sink node (Node 7).
- To prevent two activities from having the same start and end nodes, we introduce a dummy activity (Dummy 3, \(D_3\)) from Node 6 to a new node (Node 8).
- Activity \(G\) can go from Node 6 to Node 7, and activity \(H\) can go from Node 8 to Node 7 (or vice versa, with \(D_3\) from Node 6 to Node 8 and \(H\) starting from Node 8).

**Network Summary:**
- **Node 1 (Start)**
- **Arc \(A\)**: Node 1 \(\to\) Node 2
- **Arc \(B\)**: Node 1 \(\to\) Node 3
- **Dummy 1 (\(D_1\))**: Node 2 \(\to\) Node 3
- **Arc \(C\)**: Node 2 \(\to\) Node 5
- **Arc \(D\)**: Node 2 \(\to\) Node 6
- **Arc \(E\)**: Node 3 \(\to\) Node 6
- **Dummy 2 (\(D_2\))**: Node 5 \(\to\) Node 6
- **Arc \(F\)**: Node 5 \(\to\) Node 7 (Sink)
- **Arc \(G\)**: Node 6 \(\to\) Node 7 (Sink)
- **Dummy 3 (\(D_3\))**: Node 6 \(\to\) Node 8
- **Arc \(H\)**: Node 8 \(\to\) Node 7 (Sink)

### Part (b)
(i) A dummy is needed because activity \(E\) depends on both \(A\) and \(B\), but activities \(C\) and \(D\) depend on \(A\) only. Without the dummy, \(C\) and \(D\) would incorrectly depend on \(B\) as well.
(ii) A dummy is needed because both \(G\) and \(H\) depend on the exact same set of preceding activities (\(C, D, E\)) and both end at the sink node. In an activity-on-arc network, each activity must be uniquely identifiable by a unique pair of start and end nodes.

### Part (a) [5 Marks]
* **M1**: Unique start node (Node 1) and unique end node (Node 7). Activities \(A\) and \(B\) start at the start node. Activity \(F\) correctly starts after \(C\) and ends at the final node.
* **M1**: Correct precedence logic for \(A\), \(B\), \(C\), \(D\), and \(E\). This requires a dummy activity directed from the end of \(A\) to the end of \(B\).
* **A1**: Fully correct representation of the first half of the network including the first dummy (from Node 2 to Node 3 with arrow in correct direction).
* **M1**: Correct precedence logic for \(F\), \(G\), and \(H\). This requires a dummy from the end of \(C\) to the start of \(G/H\) (to separate the dependency of \(F\) on \(C\) from the dependency of \(G, H\) on \(C, D, E\)), and a third dummy to separate parallel activities \(G\) and \(H\).
* **A1**: Completely correct activity network containing exactly 3 dummy activities with all arrows and labels correctly placed.

### Part (b) [2 Marks]
* **B1**: For explaining that \(E\) depends on both \(A\) and \(B\) while \(C\) and \(D\) depend on \(A\) only (or equivalent phrasing stating that we must avoid \(C\) and \(D\) depending on \(B\)).
* **B1**: For explaining that \(G\) and \(H\) share the same set of predecessors and both must go to the sink node, meaning a dummy is required to ensure they are uniquely defined by different start and end nodes.

To find the range of values of \(k\) for which the optimal vertex is \((8, 8)\), we can use either the vertex method or the gradient method. Method 1 (Vertex Method): The vertices adjacent to \((8, 8)\) on the boundary of the feasible region are \((12, 0)\) and \((0, 12)\). The value of the objective function \(P = kx + 3y\) at each of these three vertices is: At \((8, 8)\): \(P = 8k + 24\). At \((12, 0)\): \(P = 12k\). At \((0, 12)\): \(P = 36\). For \((8, 8)\) to be the optimal (maximum) vertex, we must have: 1) \(8k + 24 \ge 12k \implies 4k \le 24 \implies k \le 6\). 2) \(8k + 24 \ge 36 \implies 8k \ge 12 \implies k \ge 1.5\). Since \(k > 0\), the range of values is \(1.5 \le k \le 6\) (or \(\frac{3}{2} \le k \le 6\)). Method 2 (Gradient Method): The two boundary lines intersecting at \((8, 8)\) are \(x + 2y = 24\) (which has gradient \(-\frac{1}{2}\)) and \(2x + y = 24\) (which has gradient \(-2\)). The objective function \(P = kx + 3y\) can be rewritten as \(y = -\frac{k}{3}x + \frac{P}{3}\), so its gradient is \(-\frac{k}{3}\). For the maximum to occur at \((8, 8)\), the gradient of the objective line must lie between the gradients of the two boundary lines: \(-2 \le -\frac{k}{3} \le -\frac{1}{2}\). Multiplying the inequality by \(-3\) and reversing the inequality signs gives: \(1.5 \le k \le 6\).

M1: Finding the coordinates of the adjacent vertices \((12, 0)\) and \((0, 12)\), OR finding the gradients of the two intersecting boundary lines (which are \(-2\) and \(-\frac{1}{2}\)). M1: Formulating inequalities to compare the objective value at \((8,8)\) with the adjacent vertices, OR setting up the gradient inequality \(-2 \le -\frac{k}{3} \le -\frac{1}{2}\). A1: Obtaining one correct limit for \(k\) (either \(k \le 6\) or \(k \ge 1.5\)). A1: Obtaining the second correct limit for \(k\). A1: Combining to give the correct final range: \(1.5 \le k \le 6\) (or equivalent fraction form \(\frac{3}{2} \le k \le 6\)).

(a) We select the pivot as the middle item (or the item immediately to the left of the middle for an even number of items).
Initial list: [17, 8, 24, 11, 5, 19, 13, 15]. There are 8 items, so the pivot is the 4th item, which is 11.
Items greater than 11 go to the left (preserving order) and items less than 11 go to the right:
Pass 1: 17, 24, 19, 13, 15, [11], 8, 5
We now have two sublists: [17, 24, 19, 13, 15] and [8, 5].
For the left sublist (length 5), the pivot is the 3rd item, which is 19. For the right sublist (length 2), the pivot is the 1st item, which is 8.
Pass 2: 24, [19], 17, 13, 15, [11], [8], 5
We now have sublists [24] (sorted), [17, 13, 15] (pivot is the 2nd item, which is 13), and [5] (sorted).
Pass 3: [24], [19], 17, 15, [13], [11], [8], [5]
We now have sublist [17, 15] (pivot is the 1st item, which is 17).
Pass 4: [24], [19], [17], [15], [13], [11], [8], [5]
Sorting is complete. Sorted list is: 24, 19, 17, 15, 13, 11, 8, 5.

(b)(i) First-fit algorithm on original list: [17, 8, 24, 11, 5, 19, 13, 15] with capacity 35.
- 17 fits in Bin 1 (space left: 18)
- 8 fits in Bin 1 (space left: 10)
- 24 fits in Bin 2 (space left: 11)
- 11 fits in Bin 2 (space left: 0)
- 5 fits in Bin 1 (space left: 5)
- 19 fits in Bin 3 (space left: 16)
- 13 fits in Bin 3 (space left: 3)
- 15 fits in Bin 4 (space left: 20)
Allocations:
Bin 1: 17, 8, 5
Bin 2: 24, 11
Bin 3: 19, 13
Bin 4: 15

(b)(ii) First-fit decreasing algorithm on sorted list: [24, 19, 17, 15, 13, 11, 8, 5] with capacity 35.
- 24 fits in Bin 1 (space left: 11)
- 19 fits in Bin 2 (space left: 16)
- 17 fits in Bin 3 (space left: 18)
- 15 fits in Bin 2 (space left: 1)
- 13 fits in Bin 3 (space left: 5)
- 11 fits in Bin 1 (space left: 0)
- 8 fits in Bin 4 (space left: 27)
- 5 fits in Bin 3 (space left: 0)
Allocations:
Bin 1: 24, 11
Bin 2: 19, 15
Bin 3: 17, 13, 5
Bin 4: 8

(c) Lower bound = \(\lceil \frac{\text{Sum of all items}}{\text{Capacity}} \rceil = \lceil \frac{17+8+24+11+5+19+13+15}{35} \rceil = \lceil \frac{112}{35} \rceil = \lceil 3.2 \rceil = 4\) bins.

Part (a):
M1: Standard Quick Sort algorithm applied. Pivot chosen correctly as 11, partition correct (items > 11 on LHS, items < 11 on RHS, original relative order of elements preserved within partitions).
A1: Pass 1 correct (17, 24, 19, 13, 15, [11], 8, 5).
A1ft: Pass 2 correct (pivots 19 and 8 chosen and partitioned correctly).
A1: Pass 3 and Pass 4 correct, all pivots identified, final sorted list correct.

Part (b)(i):
M1: First-fit algorithm applied, at least 5 items placed correctly in bins.
A1: Fully correct allocation of all 8 items (Bin 1: 17, 8, 5; Bin 2: 24, 11; Bin 3: 19, 13; Bin 4: 15).

Part (b)(ii):
M1: First-fit decreasing algorithm applied, first 5 items placed correctly.
A1: Fully correct allocation of all 8 items (Bin 1: 24, 11; Bin 2: 19, 15; Bin 3: 17, 13, 5; Bin 4: 8).

Part (c):
B1: Correct sum of 112, divided by 35 showing calculation leading to 4 bins.

### Part (a)
Let \(x\) be the number of Castles made each week and \(y\) be the number of Fortresses made each week.

The objective is to maximize weekly profit, \(P\) (in £):
\[ \text{Maximize } P = 15x + 18y \]

Subject to the constraints:
- Carving: \[ 2x + y \le 160 \]
- Sanding: \[ 3x + 4y \le 320 \]
- Painting: \[ x + 2y \le 140 \]
- Non-negativity: \[ x \ge 0, \quad y \ge 0 \]

### Part (b)
To represent the constraints graphically, we first find the intercepts for each boundary line:
1. For \(2x + y = 160\):
- When \(x = 0\), \(y = 160\)
- When \(y = 0\), \(x = 80\)
2. For \(3x + 4y = 320\):
- When \(x = 0\), \(y = 80\)
- When \(y = 0\), \(x = \frac{320}{3} \approx 106.7\)
3. For \(x + 2y = 140\):
- When \(x = 0\), \(y = 70\)
- When \(y = 0\), \(x = 140\)

The lines are plotted on the axes with suitable scales (e.g., \(x\) from 0 to 150, \(y\) from 0 to 170).
The unwanted regions (where the inequalities are violated) are shaded out, leaving the unshaded region \(R\) bounded by the vertices:
- \((0, 0)\)
- \((80, 0)\)
- \((64, 32)\) [Intersection of \(2x + y = 160\) and \(3x + 4y = 320\)]
- \((40, 50)\) [Intersection of \(3x + 4y = 320\) and \(x + 2y = 140\)]
- \((0, 70)\)

### Part (c)
We draw a representative objective line (profit line) on the graph, for example:
\[ 15x + 18y = 900 \quad \text{or} \quad 5x + 6y = 300 \]
This line passes through \((0, 50)\) and \((60, 0)\).

Sliding this line parallel to itself outwards in the direction of increasing profit (up and to the right), the last point within the feasible region \(R\) that the line passes through is the vertex \((64, 32)\).

Therefore, the optimal weekly production plan is:
- **Castles (\(x\)):** 64
- **Fortresses (\(y\)):** 32

The maximum weekly profit is:
\[ P = 15(64) + 18(32) = 960 + 576 = \text{£1536} \]

### Part (d)
Under the new profit conditions, the new profit function is:
\[ P_{\text{new}} = 12x + 18y \]

We evaluate this new profit at the candidate vertices near the top-right of the feasible region:
- At \((64, 32)\):
\[ P_{\text{new}} = 12(64) + 18(32) = 768 + 576 = \text{£1344} \]
- At \((40, 50)\):
\[ P_{\text{new}} = 12(40) + 18(50) = 480 + 900 = \text{£1380} \]
- At \((0, 70)\):
\[ P_{\text{new}} = 12(0) + 18(70) = \text{£1260} \]

Since \(1380 > 1344\), the optimal weekly production plan changes.
The new optimal plan is to make **40 Castles** and **50 Fortresses** (yielding a profit of **£1380**).

### Part (a) [4 Marks]
- **B1**: Correct objective function: Maximize \(P = 15x + 18y\) (or equivalent, e.g., in pence).
- **M1**: At least two correct constraints formulated from the carving, sanding, or painting requirements.
- **A1**: All three main constraints correct: \(2x + y \le 160\), \(3x + 4y \le 320\), and \(x + 2y \le 140\).
- **A1**: Clear statement of non-negativity: \(x \ge 0, y \ge 0\) (or represented by equivalent context in their variable definitions).

### Part (b) [7 Marks]
- **B1**: Line \(2x + y = 160\) correctly drawn (must pass through \((80,0)\) and \((0,160)\) within reasonable tolerance).
- **B1**: Line \(3x + 4y = 320\) correctly drawn (must pass through \((106.7,0)\) and \((0,80)\) within reasonable tolerance).
- **B1**: Line \(x + 2y = 140\) correctly drawn (must pass through \((140,0)\) and \((0,70)\) within reasonable tolerance).
- **B1**: Lines \(x = 0\) and \(y = 0\) represented (usually the axes).
- **M1**: Evidence of testing points to determine the region, leading to shading/identifying a bounded region.
- **A1**: Fully correct feasible region \(R\) identified, bounded by the five vertices: \((0,0)\), \((80,0)\), \((64,32)\), \((40,50)\), and \((0,70)\).
- **B1**: Both axes clearly labelled (e.g., \(x\) and \(y\), or Castles and Fortresses) with appropriate, consistent linear scales.

### Part (c) [4 Marks]
- **M1**: Draw a straight line with gradient \(-0.83\) (representing \(15x+18y=c\)) or clearly show the use of the vertex testing method for all five vertices.
- **A1**: The objective line is drawn accurately, passing through points with the correct slope and clearly labelled.
- **A1**: Identify the optimal vertex \((64, 32)\) (either by graphical indication or by showing it has the highest profit of £1536).
- **A1**: Correctly state the optimal production numbers (64 Castles, 32 Fortresses) and the maximum profit of **£1536** (units must be clear).

### Part (d) [2 Marks]
- **M1**: Calculate the new profit \(P_{\text{new}} = 12x + 18y\) at \((64, 32)\) and \((40, 50)\) (or use gradients of the boundary lines to show that the new gradient \(-\frac{2}{3}\) lies between \(-\frac{3}{4}\) and \(-\frac{1}{2}\)).
- **A1**: Conclude that the optimal weekly production plan changes, and identify the new plan (40 Castles and 50 Fortresses) with correct justification.

### Part (a)
Let \(x\) be the number of Castles made each week and \(y\) be the number of Fortresses made each week.

The objective is to maximize weekly profit, \(P\) (in £):
\[ \text{Maximize } P = 15x + 18y \]

Subject to the constraints:
- Carving: \[ 2x + y \le 160 \]
- Sanding: \[ 3x + 4y \le 320 \]
- Painting: \[ x + 2y \le 140 \]
- Non-negativity: \[ x \ge 0, \quad y \ge 0 \]

### Part (b)
To represent the constraints graphically, we first find the intercepts for each boundary line:
1. For \(2x + y = 160\):
- When \(x = 0\), \(y = 160\)
- When \(y = 0\), \(x = 80\)
2. For \(3x + 4y = 320\):
- When \(x = 0\), \(y = 80\)
- When \(y = 0\), \(x = \frac{320}{3} \approx 106.7\)
3. For \(x + 2y = 140\):
- When \(x = 0\), \(y = 70\)
- When \(y = 0\), \(x = 140\)

The lines are plotted on the axes with suitable scales (e.g., \(x\) from 0 to 150, \(y\) from 0 to 170).
The unwanted regions (where the inequalities are violated) are shaded out, leaving the unshaded region \(R\) bounded by the vertices:
- \((0, 0)\)
- \((80, 0)\)
- \((64, 32)\) [Intersection of \(2x + y = 160\) and \(3x + 4y = 320\)]
- \((40, 50)\) [Intersection of \(3x + 4y = 320\) and \(x + 2y = 140\)]
- \((0, 70)\)

### Part (c)
We draw a representative objective line (profit line) on the graph, for example:
\[ 15x + 18y = 900 \quad \text{or} \quad 5x + 6y = 300 \]
This line passes through \((0, 50)\) and \((60, 0)\).

Sliding this line parallel to itself outwards in the direction of increasing profit (up and to the right), the last point within the feasible region \(R\) that the line passes through is the vertex \((64, 32)\).

Therefore, the optimal weekly production plan is:
- **Castles (\(x\)):** 64
- **Fortresses (\(y\)):** 32

The maximum weekly profit is:
\[ P = 15(64) + 18(32) = 960 + 576 = \text{£1536} \]

### Part (d)
Under the new profit conditions, the new profit function is:
\[ P_{\text{new}} = 12x + 18y \]

We evaluate this new profit at the candidate vertices near the top-right of the feasible region:
- At \((64, 32)\):
\[ P_{\text{new}} = 12(64) + 18(32) = 768 + 576 = \text{£1344} \]
- At \((40, 50)\):
\[ P_{\text{new}} = 12(40) + 18(50) = 480 + 900 = \text{£1380} \]
- At \((0, 70)\):
\[ P_{\text{new}} = 12(0) + 18(70) = \text{£1260} \]

Since \(1380 > 1344\), the optimal weekly production plan changes.
The new optimal plan is to make **40 Castles** and **50 Fortresses** (yielding a profit of **£1380**).

### Part (a) [4 Marks]
- **B1**: Correct objective function: Maximize \(P = 15x + 18y\) (or equivalent, e.g., in pence).
- **M1**: At least two correct constraints formulated from the carving, sanding, or painting requirements.
- **A1**: All three main constraints correct: \(2x + y \le 160\), \(3x + 4y \le 320\), and \(x + 2y \le 140\).
- **A1**: Clear statement of non-negativity: \(x \ge 0, y \ge 0\) (or represented by equivalent context in their variable definitions).

### Part (b) [7 Marks]
- **B1**: Line \(2x + y = 160\) correctly drawn (must pass through \((80,0)\) and \((0,160)\) within reasonable tolerance).
- **B1**: Line \(3x + 4y = 320\) correctly drawn (must pass through \((106.7,0)\) and \((0,80)\) within reasonable tolerance).
- **B1**: Line \(x + 2y = 140\) correctly drawn (must pass through \((140,0)\) and \((0,70)\) within reasonable tolerance).
- **B1**: Lines \(x = 0\) and \(y = 0\) represented (usually the axes).
- **M1**: Evidence of testing points to determine the region, leading to shading/identifying a bounded region.
- **A1**: Fully correct feasible region \(R\) identified, bounded by the five vertices: \((0,0)\), \((80,0)\), \((64,32)\), \((40,50)\), and \((0,70)\).
- **B1**: Both axes clearly labelled (e.g., \(x\) and \(y\), or Castles and Fortresses) with appropriate, consistent linear scales.

### Part (c) [4 Marks]
- **M1**: Draw a straight line with gradient \(-0.83\) (representing \(15x+18y=c\)) or clearly show the use of the vertex testing method for all five vertices.
- **A1**: The objective line is drawn accurately, passing through points with the correct slope and clearly labelled.
- **A1**: Identify the optimal vertex \((64, 32)\) (either by graphical indication or by showing it has the highest profit of £1536).
- **A1**: Correctly state the optimal production numbers (64 Castles, 32 Fortresses) and the maximum profit of **£1536** (units must be clear).

### Part (d) [2 Marks]
- **M1**: Calculate the new profit \(P_{\text{new}} = 12x + 18y\) at \((64, 32)\) and \((40, 50)\) (or use gradients of the boundary lines to show that the new gradient \(-\frac{2}{3}\) lies between \(-\frac{3}{4}\) and \(-\frac{1}{2}\)).
- **A1**: Conclude that the optimal weekly production plan changes, and identify the new plan (40 Castles and 50 Fortresses) with correct justification.