How to write the dual problem of this maximization problem?

On this note for Shapley-Shubik model, there's a maximization problem:

$$\max_{x_{ij} \in \mathbb{R}^{M \times N}}\sum_{j \in N}\sum_{i \in M}v_{ij}x_{ij}$$ $$\text{s.t.} \ \sum_{j \in N}x_{ij} \leq 1 \ \forall i \in M$$ $$\\ \sum_{i \in M}x_{ij} \leq 1 \ \forall j \in N$$ $$x_{ij} \geq 0 \ \forall i \in M\forall j \in N$$

The dual problem of it is

$$\min_{s_j \in \mathbb{R}^N, p_i \in \mathbb{R}^M }\sum_{j \in N}s_j+\sum_{i \in M}p_i$$ $$\text{s.t.} s_j + p_i \geq v_ij \ \forall i \in M\forall j \in N$$ $$\\ s_j, p_i \geq 0 \forall i \in M\forall j \in N$$

What's the rule of writing this dual problem?

1 Answer

Everything is explained here: http://en.wikipedia.org/wiki/Linear_programming#Another_example.