I have the following problem:
For the given natural $n$ find the maximum value of the target function $\sum_{i=1}^n u_i + \sum_{j = 1}^n v_j \rightarrow max$ subject to $u_i + v_j \leq 2^{i + j}$ for $1 \leq i, j \leq n$
As far as I know such kind of problems are called dual transportation problem. There are number of algorithms for finding solution, including Simplex algorithm, but I'm struggling to apply them to the case of arbitrary $n$.
Any idea how can I approach this? Thanks!
Maybe it would help to consider its dual, which is to minimize $\sum_{i,j} 2^{i+j} x_{i,j}$ subject to \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ \sum_i x_{i,j} &= 1 &&\text{for all $j$}\\ x_{i,j} &\ge 0 &&\text{for all $i$ and $j$} \end{align} Indeed this is a transportation problem, specifically a linear assignment problem. The objective here encourages $x_{i,j}=0$ for large $i+j$. So take $x^*_{i,n+1-i}=1$ for all $i$ and $x^*_{i,j}=0$ otherwise. Now find a corresponding primal solution $(u^*,v^*)$ that certifies optimality of this dual solution.
