= Solution
For any feasible assignment, the unit row and column sums give
$$
\begin{aligned}
\sum_{i,j}\bar c_{ij}x_{ij}
&=\sum_{i,j}c_{ij}x_{ij}-\sum_i u_i\sum_jx_{ij}-\sum_jv_j\sum_ix_{ij}\\
&=\sum_{i,j}c_{ij}x_{ij}-\sum_iu_i-\sum_jv_j.
\end{aligned}
$$
Thus the transformed objective differs by the fixed constant
$$
\boxed{-\sum_i u_i-\sum_jv_j.}
$$
Every feasible assignment shifts by that same amount, so all objective comparisons and all optimal assignments remain unchanged. The calculation also holds for fractional feasible points of the assignment LP relaxation. The numbers $u_i,v_j$ are <assignment dual potentials>.
Back to article page
