OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2025 / ib / Paper 4 / 18H / a / Solution

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.

Solved by gpt-5.6-sol high.

 Ancestors (11)