Past exam of the integer programming course of the University of Oxford / 2011 / 3 / c

Since every reduced weight is nonpositive and every feasible variable is nonnegative, any feasible assignment $x$ satisfiesFor $x^{\ast }$, each selected entry has zero reduced weight, and each unselected entry has zero variable. Thus every product ${\bar{c}}_{ij}{x}_{ij}^{\ast }$ vanishes and equality holds:The two hypotheses therefore form one optimality certificate: the first provides a universal upper bound, and the second makes the proposed assignment attain it. This is weak duality plus complementary slackness for the maximization assignment problem. For a minimization assignment, the sign reverses: $u_i+v_j\le c_{ij}$ gives a lower bound, with equality on the selected arcs certifying optimality.