 Solution

Separate the forced integer portion from the choice of rounding direction. Put $p_{ij}=\lfloor a_{ij}\rfloor$ and $q_{ij}=a_{ij}-p_{ij}$. Define residual demandsThese are nonnegative integers, since the original row and column sums are integers. Also ${\sum }_i{r}_i={\sum }_j{c}_j=:T$. Each fractional part satisfies $0\le q_{ij}<1$.

Construct a flow network with a vertex for each row and column, source-to-row arcs of flow network edge capacity $r_i$, row-to-column arcs of flow network edge capacity one exactly where $q_{ij}>0$, and column-to-sink arcs of flow network edge capacity $c_j$. The amounts $q_{ij}$ themselves define a fractional feasible flow of flow value $T$. No flow can exceed $T$, the total source flow network edge capacity. Because all constructed flow network edge capacities are integers, an integral maximum flow also has flow value $T$ and saturates every source and sink arc.

Let $h_{ij}$ be its middle-arc flow, taking $h_{ij}=0$ when that arc is absent. Then $h_{ij}\in \{0,1\}$, and the required answer isAt an already integral entry no middle arc exists, so that entry stays fixed. At a nonintegral entry the two possibilities are precisely its floor and ceiling. Flow conservation gives ${\sum }_j{h}_{ij}=r_i$ and ${\sum }_i{h}_{ij}=c_j$, preserving every original row and column sum.

This is matrix rounding with fixed margins. There are $m+n+2$ vertices and at most $mn+m+n$ arcs. Exact rational arithmetic computes the floors and residual demands in polynomial time in the encoded input length; the resulting flow network edge capacities are small integers, so there is no need to scale by a potentially large common denominator.