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.
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.