Q:

How to find the analytical solution of this optimization problem?

I have an optimization problem of the form
$$\begin{align}
\text{maximize}\quad&\sum_{i=1}^{k}\sum_{j=1}^{n}w_{ij}x_{ij}\\\text{s.t.}\quad \quad\quad\,\,&
\sum_{i=1}^{k}x_{ij}\leq 1,\;\forall j\\&
\sum_{j=1}^{n}x_{ij}\leq 1,\;\forall i\\&
x_{ij}\in\{0,1\}
\end{align}
$$
where $w_{ij}$ is a real number.
How can I find the $x_{ij}$ that maximizes the objective function?
I know that if $w_{ij}\leq0$ then $x_{ij}=0$ is the optimal solution.

A:

You can consider two problems, one with negative weights, the other without: 
Problem 1:
$$\begin{align}
\text{maximize}\quad&\sum_{i=1}^{k}\sum_{j=1}^{n}w_{ij}x_{ij}\\\text{s.t.}\quad \quad\quad\,\,&
\sum_{i=1}^{k}x_{ij}\leq 1,\;\forall j\\&
\sum_{j=1}^{n}x_{ij}\leq 1,\;\forall i\\&
x_{ij}\in\{0,1\}
\end{align}
$$
Problem 2:
Same constraints as problem, 1, but change the objective function to: 
$$ maximize \quad \sum_{i=1}^k \sum_{j=1}^n \underbrace{\max[w_{ij},0]}_{\tilde{w}_{ij}}x_{ij} $$
You can use standard max-weight-match solvers for problem 2.  The following shows that can easily be converted to a solution of problem 1. 

Let $v_1^*$ be the optimal objective function value for problem 1.  Let $v_2^*$ be the optimal objective function value for problem 2.  Since problem 2 only changes the objective function to one that uses the same or larger weights, it is clear that $v_1^* \leq v_2^*$. 
Let $(x_{ij}^*)$ be an optimal solution to problem 2, so that $(x_{ij}^*)$ satisfies the constraints and
$$\sum_{i=1}^k \sum_{j=1}^n \max[w_{ij},0]x_{ij}^*=v_2^*$$
Let $(y_{ij})$ be a matrix defined from $(x_{ij}^*)$ by defining each entry as 
$$ y_{ij} = \left\{ \begin{array}{ll}
x_{ij}^* &\mbox{ if $w_{ij} \geq 0$} \\
0  & \mbox{ if $w_{ij}<0$} 
\end{array}
\right.$$
Claim:
$(y_{ij})$ is a solution to problem 1.  Also, $v_1^*=v_2^*$.  
Proof:
Note that $(y_{ij})$ satisfies the required constraints, so its objective value for problem 1 is no more than the optimal value $v_1^*$:
$$ \sum_{i=1}^k \sum_{j=1}^n w_{ij} y_{ij} \leq v_1^* $$
Note that for all $(i,j)$ we have
$$w_{ij}y_{ij}=\max[w_{ij},0]y_{ij}=\max[w_{ij},0]x_{ij}^*$$ 
Thus 
$$ v_1^* \geq \sum_{i=1}^k\sum_{j=1}^nw_{ij}y_{ij} = \sum_{i=1}^k\sum_{j=1}^n\max[w_{ij},0]x_{ij}^* = v_2^*  \geq v_1^* $$
Hence, $v_1^*=v_2^*$ and the $(y_{ij})$ matrix achieves an objective value that is optimal.  Thus, $(y_{ij})$ is optimal for problem 1. $\Box$
It follows that $(y_{ij})$ is optimal for both problems 1 and 2, while $(x_{ij}^*)$ might only be optimal for problem 2. 

