QCAA General Mathematics Networks and decision mathematics 2

Calculate $x$ (distance from A to P):
Angular distance $= 28^\circ - 20^\circ = 8^\circ$
$D = 111.2 \times 8^\circ \approx 890$ km

Calculate $y$ (distance from A to R):
Angular distance $= 147^\circ - 136^\circ = 11^\circ$
$D = 111.2 \times \cos 20^\circ \times 11^\circ \approx 1149$ km

Row reduction:
$\begin{bmatrix} 290 & 0 & 549 \\ 105 & 145 & 0 \\ 210 & 400 & 0 \end{bmatrix}$

Column reduction:
$\begin{bmatrix} 185 & 0 & 549 \\ 0 & 145 & 0 \\ 105 & 400 & 0 \end{bmatrix}$

Number of lines needed to cover all zeros = number of tasks ($3 = 3$), so allocate planes.
For minimum distance, the plane allocation is airbase A to site Q, airbase B to site P and airbase C to site R.

Minimum total distance flown $= 600 + 445 + 770$
$= 1815$ km

Row reduction
Store 1: 19 17 24 (-17) -> 2 0 7
Store 2: 15 14 22 (-14) -> 1 0 8
Store 3: 23 16 40 (-16) -> 7 0 24

$\begin{bmatrix} 2 & 0 & 7 \\ 1 & 0 & 8 \\ 7 & 0 & 24 \end{bmatrix}$

Column reduction (-1 0 -7)
$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 6 & 0 & 17 \end{bmatrix}$

Therefore for minimum distance, Store 1 must deliver to C, Store 2 must deliver to A and Store 3 must deliver to B.

Minimum total distance = 24 + 15 + 16 = 55 km

Matrix form
$\begin{pmatrix} 3 & 3 & 1 \\ 4 & 7 & 2 \\ 4 & 4 & 1 \end{pmatrix}$

row reduction: $R_1 - 1, R_2 - 2, R_3 - 1$
$\begin{pmatrix} 2 & 2 & 0 \\ 2 & 5 & 0 \\ 3 & 3 & 0 \end{pmatrix}$

only need 1 line to cover all the 0s,
$\therefore$ column reduction: $C_1 - 2, C_2 - 2$
$\begin{pmatrix} 0 & 0 & 0 \\ 0 & 3 & 0 \\ 1 & 1 & 0 \end{pmatrix}$

need 3 lines to cover all the 0s, $\therefore$ bipartite graph:

contractor task cost
A 2 3
B 1 4
C 3 1
Total 8
$\therefore$ Minimum cost is ＄8000.

$\begin{matrix} & \text{S} & \text{C} & \text{R} \\ \text{J} & 40 & 56 & 66 \\ \text{K} & 36 & 60 & 72 \\ \text{L} & 25 & 48 & 78 \end{matrix}$

column reduction $-25 \quad -48 \quad -66$

row reduction
$\begin{bmatrix} 15 & 8 & 0 \\ 11 & 12 & 6 \\ 0 & 0 & 12 \end{bmatrix} \begin{matrix} -0 \\ -6 \\ -0 \end{matrix}$

$\begin{bmatrix} 15 & 8 & 0 \\ 5 & 6 & 0 \\ 0 & 0 & 12 \end{bmatrix}$

Number of lines needed to cover all zeroes < number of tasks
$2 < 3$, so continue algorithm steps.
Smallest uncovered number is 5. Subtract 5 from all uncovered numbers and add 5 to number covered twice.

$\begin{bmatrix} 10 & 3 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 17 \end{bmatrix}$

Number of lines needed to cover all zeroes = number of tasks
$3 = 3$, so assign tasks.
To minimise the total relay time, assign Jane to run, Knox to swim and Levi to cycle.
Predicted minimum total relay time
$= 66 + 36 + 48$
$= 150 \text{ min}$
$= 2 \text{ h } 30 \text{ min}$