= Solution
Since every reduced weight is nonpositive and every feasible variable is nonnegative, any feasible assignment $x$ satisfies
$$
\sum_{i,j}c_{ij}x_{ij}
=\sum_i u_i+\sum_jv_j+\sum_{i,j}\bar c_{ij}x_{ij}
\leq\sum_i u_i+\sum_jv_j.
$$
For $x^*$, each selected entry has zero reduced weight, and each unselected entry has zero variable. Thus every product $\bar c_{ij}x^*_{ij}$ vanishes and equality holds:
$$
\boxed{c\cdot x^*=\sum_i u_i+\sum_jv_j=\max c\cdot x.}
$$
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\leq c_{ij}$ gives a lower bound, with equality on the selected arcs certifying optimality.
Back to article page
