Let $W = (w_{ij})$ be a $n \times n$ non-negative matrix and define a function $f$ in the set of all doubly stochastic matrices $n \times n$ by setting for $A = (a_{ij})$,
$$f(A) = \sum_{i,j} a_{ij}w_{ij}$$
Show that $f$ attains its maximum value at a permutation matrix.
I tried to reorder $W$'s rows and columns to form a matrix $W'$ whose diagonal entries are greater or equal than the following entries in the same row and column so that I wanted to prove that the analogous function $f'$ (with respect to $W'$ instead of $W$) reaches its maximum value at the identity matrix. If I can accomplish that, then by reordering in the inverse order the rows and columns of the identity matrix, I can form a permutation matrix for which $f$ attains its maximum value.
But I can't manage to proceed in the case where the maximum value of a $j$-th row of $W'$ is in the first $j-1$ entries, because then the scalar product of that row by the correspoding row in the identity matrix may not be greater than the correspoding scalar product of that row of $W'$ by an arbitrary doubly stochastic matrix, so that I shall have to argument based in the previous rows, but I don't really know how.
I've been given an hint to use the Birkhoff-von Neumann Theorem but made no progress regarding this.
Can someone give me an hint on how to proceed in any of these two possibilities in order to achieve a proof?
Hint. The set of all doubly stochastic matrices is convex and its extreme points are precisely those permutation matrices. And your $f$ is linear.