---
lang: ja
tags: MTNS-2022, lecture, linear programming
---
# 2022年度 交通社会システム論<br>第11回 練習問題 解答例 | Report #6 Answer
[ポータルへ戻る](https://hackmd.io/@nagae/MTNS_2022)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：

<code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2022-Ch10-answer</code>
</div>

## 最適配分 | Optimal Assignment
以下のいずれの配分でも最適値は490である．
Each of the following assignments achieves the optimal value 490.
### 学生4にソーダが配分される場合 (Case 1: Soda is assigned to Student 4):
||学生1|学生2|学生3|学生4|学生5|学生6|
|---|---|---|---|---|---|---|
|ソーダ($S$)|<div style="background-color:orange">100</div>|60|90|<div style="background-color:orange">120</div>|150|<div style="background-color:orange">110</div>|
|コーラ($C$) |30|<div style="background-color:orange">60</div>|40|70|<div style="background-color:orange">100</div>|50

### 学生5にソーダが配分される場合 (Case 2: Soda is assigned to Student 5):
||学生1|学生2|学生3|学生4|学生5|学生6|
|---|---|---|---|---|---|---|
|ソーダ($S$)|<div style="background-color:orange">100</div>|60|90|120|<div style="background-color:orange">150</div>|<div style="background-color:orange">110</div>|
|コーラ($C$) |30|<div style="background-color:orange">60</div>|40|<div style="background-color:orange">70</div>|100|50

## 学生1 のVCG価格 | VCG Price of Student 1
- 学生1が不在のときの評価値: 480
- 最適配分における学生1以外の評価値: 390
- VCG価格 $p_{1} = 90$

## 学生2 のVCG価格 | VCG Price of Student 2
- 学生2が不在のときの評価値: 470
- 最適配分における学生1以外の評価値: 430
- VCG価格 $p_{2} =40$

## 学生4の VCG価格 | VCG Price of Student 4
(学生4にソーダが配分される場合)
- 学生4が不在のときの評価値:460
- 最適配分における学生4以外の評価値:370
- VCG価格 $p_{4} = 90$

(学生4にコーラが配分される場合)

- 学生4が不在のときの評価値:460
- 最適配分における学生4以外の評価値:420
- VCG価格 $p_{4} = 40$

## 学生5の VCG価格 | VCG Price of Student 4
(学生5にコーラが配分される場合)
- 学生5が不在のときの評価値:430
- 最適配分における学生5以外の評価値:390
- VCG価格 $p_{5} = 40$

(学生5にソーダが配分される場合)
- 学生5が不在のときの評価値:490
- 最適配分における学生5以外の評価値:340
- VCG価格 $p_{5} = 90$

## 学生6 のVCG価格 | VCG Price of Student 6
- 学生6が不在のときの評価値: 470
- 最適配分における学生1以外の評価値: 380
- VCG価格 $p_{6} =90$

# 双対問題$(\boldsymbol{p}, \boldsymbol{\pi})$ | Dual Problem
双対問題は以下のように定式化できる:
The dual of the LP-equivalent assignment problem is formulated as
$$\begin{align}
\min_{\boldsymbol{p}, \boldsymbol{\pi}} \quad &
\pi_{1} + \pi_{2} + \pi_{3} + \pi_{4} + \pi_{5} + \pi_{6} + 3p_{S} + 2p_{C}\\
\text{s.t.} \quad
&\pi_{1} + p_{S} \geq 100 \qquad (x_{S1})\\
&\pi_{1} + p_{C} \geq 30 \qquad (x_{C1})\\
&\pi_{2} + p_{S} \geq 60 \qquad (x_{S2})\\
&\pi_{2} + p_{C} \geq 60 \qquad (x_{C2})\\
&\pi_{3} + p_{S} \geq 90 \qquad (x_{S3})\\
&\pi_{3} + p_{C} \geq 40 \qquad (x_{C3})\\
&\pi_{4} + p_{S} \geq 120 \qquad (x_{S4})\\
&\pi_{4} + p_{C} \geq 70 \qquad (x_{C4})\\
&\pi_{5} + p_{S} \geq 150 \qquad (x_{S5})\\
&\pi_{5} + p_{C} \geq 100 \qquad (x_{C5})\\
&\pi_{6} + p_{S} \geq 110 \qquad (x_{S6})\\
&\pi_{6} + p_{C} \geq 50 \qquad (x_{C6})\\
&\pi_{1}, \pi_{2}, \pi_{3}, \pi_{4}, \pi_{5}, \pi_{6}, p_{S}, p_{C} \geq 0
\end{align}$$

双対最適解は，主最適化(最適配分)と相補性定理から求められる．
The dual optimal solution can be obtained from the primal optimal solution (optimal assignment) and the complementarity theorem.
## 学生4にソーダが割当てられる場合 | Case 1: Soda is assigned to Student 4
相補性定理より，配分$x_{S1}=x_{C2}=x_{S4}=x_{C5}=x_{S6}=1$に対応する双対制約が等式で成り立つから，
From the complementarity theorem, the dual constraints corresponding to the optimal assignment hold equality:
$$\begin{align}
\pi_{1} + p_{S} &= 100\\
\pi_{2} + p_{C} &= 60\\
\pi_{4} + p_{S} &= 120\\
\pi_{5} + p_{C} &= 100\\
\pi_{6} + p_{S} &= 110
\end{align}$$
未知変数が7つで方程式が5本のため，これだけでは双対最適解を一意に定めることはできない(実際，双対制約を満足する範囲で$(p_{S}, p_{C})$をシフトさせたものも全て双対最適解となる)．
There are 5 equations for 7 unknown variables and thus dual optimal solution is not unique (every dual solution obtained by shifting $(ps_{S}, p_{C})$ is optimal).

そこで，双対最適解のもので価格が最小となるものを探そう．具体的には，買手3には財が配分されない($x_{S3}=x_{C3}=0$)であるため，相補性条件より$\pi_{3}=0$． これより，財価格は
We therefore find the dual optimal solution with minimum price. Since no item is assigned to Buyer 3 ($x_{S3}=x_{C3}=0$), $\pi_{3} = 0$ from the complementarity condition. This implies that the prices should satisfy:
$$\begin{align}
p_{S} &\geq 90 &
p_{C} &\geq 40
\end{align}$$
を満足する．この中で最小のものは，当然
and the minimum price is obviously
$$(p_{S}, p_{C}) = (90, 40)$$となる．これを上述の方程式に代入すれば，
Substituting this to the equations above, we can obtain the optimal dual solution that achieves the optimal value, 490.
$$\begin{align}
\pi_{1} &= 10\\
\pi_{2} &= 20\\
\pi_{3} &= 0\\
\pi_{4} &= 30\\
\pi_{5} &= 60\\
\pi_{6} &= 20
\end{align}$$を得る．これが最適解であることは，双対実行であり，目的関数が490となることから明らか．

## 学生5にソーダが割り当てられる場合
相補性定理より，配分$x_{S1}=x_{C2}=x_{C4}=x_{S5}=x_{S6}=1$に対応する双対制約が等式で成り立つから，
\begin{align}
\pi_{1} + p_{S} &= 100\\
\pi_{2} + p_{C} &= 60\\
\pi_{4} + p_{C} &= 70\\
\pi_{5} + p_{S} &= 150\\
\pi_{6} + p_{S} &= 110
\end{align}
上述と同様に
$$(p_{S}, p_{C})=(90, 40)$$として代入すれば，
\begin{align}
\pi_{1} &=100\\
\pi_{2} &= 20\\
\pi_{3} &= 0\\
\pi_{4} &= 30\\
\pi_{5} &= 60\\
\pi_{6} &= 20
\end{align}と，上述と全く同じ利得パターンとなる．学生4，5はソーダが割り当てられてもコーラが割り当てられても利得が変わらない(=無差別)だったからアタリマエである．これが最適解であることは，双対実行であり，目的関数が490となることから明らか．

2つの配分における双対最適解$(p_{S}, p_{C}) = (90, 40)$とVCG価格を比較してみると，
- 学生4にソーダが配分される場合
|買手|配分される財|VCG価格|
|---|---|--|
|1|ソーダ|90|
|2|コーラ|40|
|4|ソーダ|90|
|5|コーラ|40|
|6|ソーダ|90|

- 学生5にソーダが配分される場合
|買手|配分される財|VCG価格|
|---|---|--|
|1|ソーダ|90|
|2|コーラ|40|
|4|コーラ|40|
|5|ソーダ|90|
|6|ソーダ|90|

となり，それぞれが支払うべきVCG価格が，それぞれが割り当てられた財に応じた双対最適解$p_{S}$または$p_{C}$に一致していることが判る．