 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ib/paper-4/18h/a/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

Introduce unrestricted row and column potentials

u_{i}, v_{j}

. The dual is

maximize \sum_{i} u_{i} s_{i} + \sum_{j} v_{j} d_{j} subject to u_{i} + v_{j} \leq c_{ij} .

Primal and dual feasible solutions are optimal precisely when complementary slackness holds:

x_{ij} > 0 ⟹ u_{i} + v_{j} = c_{ij} .

Indeed, the primal--dual objective gap is

\sum_{ij} x_{ij} (c_{ij} - u_{i} - v_{j})

, a sum of nonnegative terms.

 New to topics? Read the docs here!