Solution
= Solution
Introduce unrestricted row and column potentials $u_i,v_j$. The dual is
$$
\text{maximize }\sum_i u_is_i+\sum_jv_jd_j
\quad\text{subject to }u_i+v_j\leq c_{ij}.
$$
Primal and dual feasible solutions are optimal precisely when <complementary slackness> holds:
$$
x_{ij}>0\implies 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.