# Question 5:

## Part (a)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Valid loop using $\theta$: e.g. $A \to P = 74-\theta$, $A \to Q = \theta$, $C \to P = 13+\theta$, $C \to Q = 50-\theta$ giving solution $A:24, B:58, C:63, D$ with $Q=50, R=7, R=78$ | M1 A1 | **(2)** a1M1: Valid route, only one empty square, AQ used, $\theta$'s balance. a1A1: Correct route, up to improved solution (six numbers, no zeros) |

## Part (b)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Shadow costs: $0, -13, -11, 11$ for rows $A,B,C,D$; $20, 5, -1$ for cols $P,Q,R$; Improvement indices: $P:X, Q:X, R:14$ for $A$; $P:X, Q:23, R:22$ for $B$; $P:X, Q:20, R:33$ for $C$; $P:-9, Q:X, R:X$ for $D$ | M1 A1 | b1M1: Finding 7 shadow costs and 6 improvement indices. b1A1: Shadow costs correct |
| New solution: $A:P=24-\theta$, $A:Q=50+\theta$, $D:\theta$, $D:Q=7-\theta$ giving $A:17, B:58, C:63, D:7$ with $Q=57, R=78$ | M1 A1 | **(4)** b2M1: Valid route, most negative II chosen, only one empty square, $\theta$'s balance. Entering cell DP, exiting cell DQ |

## Part (c)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Shadow costs: $0, -13, -11, 2$ for rows; $20, 5, 8$ for cols; Improvement indices: $A:P=X, Q=X, R=5$; $B:P=X, Q=23, R=13$; $C:P=X, Q=20, R=24$; $D:P=X, Q=9, R=X$ | M1 A1 A1 | **(3)** c1M1: Finding 7 shadow costs **and** all 6 IIs **or** at least 1 negative II found. c1A1: Shadow costs correct. c2A1: CSO + reason + optimal |
| Optimal since no negative improvement indices | | |

## Part (d)

| Answer | Marks | Guidance |
|--------|-------|----------|
| $(\pounds)\ 2532$ | B1 | **(1)** d1B1: CAO |

## Part (e)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Let $x_{ij}$ be the number of units transported from $i$ to $j$ | B1 | e1B1: $x_{ij}$ defined correctly (must include 'number of' and 'from $i$ to $j$') |
| where $i \in \{A,B,C,D\}$, $j \in \{P,Q,R\}$ and $x_{ij} \geq 0$ | B1 | e2B1: Defining set of values for $i$ and $j$ **including** non-negativity constraint |
| Minimise $C = 20x_{AP} + 5x_{AQ} + 13x_{AR} + 7x_{BP} + 15x_{BQ} + 8x_{BR} + 9x_{CP} + 14x_{CQ} + 21x_{CR} + 22x_{DP} + 16x_{DQ} + 10x_{DR}$ | M1 A1 | e1M1: Objective function (allow one error in coefficient **or** variable). e1A1: CAO and minimise |
| $x_{AP} + x_{AQ} + x_{AR} \leq 74$ | | |
| $x_{BP} + x_{BQ} + x_{BR} \leq 58$ | | |
| $x_{CP} + x_{CQ} + x_{CR} \leq 63$ | M1 | e2M1: At least 3 constraints with unit coefficients, rhs values correct |
| $x_{DP} + x_{DQ} + x_{DR} \leq 85$ | A1 | e2A1: At least 5 correct constraints |
| $x_{AP} + x_{BP} + x_{CP} + x_{DP} \leq 145$ | A1 | **(7)** e3A1: All 7 constraints correct |
| $x_{AQ} + x_{BQ} + x_{CQ} + x_{DQ} \leq 57$ | | |
| $x_{AR} + x_{BR} + x_{CR} + x_{DR} \leq 78$ | | |

**Total: 17 marks**

---