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

Table of contents
- Solution 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.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version