<p>Everything is explained here: <a href="http://en.wikipedia.org/wiki/Linear_programming#Another_example" rel="nofollow">http://en.wikipedia.org/wiki/Linear_programming#Another_example</a>.</p>

CC BY-SA 3.0
2015-06-03T07:19:54.187Z
2015-06-03T07:19:54.187Z
Oliv
<p>On this <a href="https://theoryclass.files.wordpress.com/2012/01/mktdesign11.pdf" rel="noreferrer">note</a> for  Shapley-Shubik model, there's a maximization problem:</p>
<blockquote>
<p><span class="math-container">$$\max_{x_{ij} \in \mathbb{R}^{M \times N}}\sum_{j \in N}\sum_{i \in M}v_{ij}x_{ij}$$</span>
<span class="math-container">$$\text{s.t.}  \ \sum_{j \in N}x_{ij} \leq 1 \ \forall i \in M$$</span>
<span class="math-container">$$\\ \sum_{i \in M}x_{ij} \leq 1 \ \forall j \in N$$</span>
<span class="math-container">$$x_{ij} \geq 0 \ \forall i \in M\forall j \in N$$</span></p>
</blockquote>
<p>The dual problem of it is</p>
<blockquote>
<p><span class="math-container">$$\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$$</span>
<span class="math-container">$$\text{s.t.} s_j + p_i \geq v_ij \ \forall i \in M\forall j \in N$$</span>
<span class="math-container">$$\\ s_j, p_i \geq 0 \forall i \in M\forall j \in N$$</span></p>
</blockquote>
<p>What's the rule of writing this dual problem?</p>

<microeconomics><reference-request><academic-graduate><linear-programming>
How to write the dual problem of this maximization problem?
Metta World Peace
# How to write the dual problem of this maximization problem?

(Asked by: username_0 on 2015-06-03)

On this [note](https://theoryclass.files.wordpress.com/2012/01/mktdesign11.pdf) 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?

**Tags:** microeconomics, reference-request, academic-graduate, linear-programming

---

## 1 answers

### Answer by username_1 on 2015-06-03. Score: 2 | Accepted answer

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


---

