---
lang: ja
tags: OptMech-2021, lecture
---
# 2021年度 知的システム<br>第10回 練習問題 解答例
[ポータルへ戻る](https://hackmd.io/@nagae/OptMech_2021)
下記の2財4人からなる割当問題に対して，以下を答えよ．

1. 等価な線形計画問題の主問題および双対問題を書き下せ．
2. 主問題および双対問題の最適解が相補性条件を満足することを示せ．

||買手1|買手2|買手3|買手4|供給量|
|---|---|---|---|---|---|
|財$A$|100|50|90|120|1|
|財$B$|80|50|40|90|2|

## 主問題
$$\begin{align}
\max_{\mathbf{x}} \quad &100x_{A1}+80x_{B1}+50x_{A2}+50x_{B2}+90x_{A3}+40x_{B3}+120x_{A4}+90x_{B4}\\
\text{s.t.} \quad &
x_{A1} + x_{B1} \leq 1\\&
x_{A2} + x_{B2} \leq 1\\&
x_{A3} + x_{B3} \leq 1\\&
x_{A4} + x_{B4} \leq 1\\&
x_{A1} + x_{A2} + x_{A3} + x_{A4} \leq 1\\&
x_{B1} + x_{B2} + x_{B3} + x_{B4} \leq 2\\&
x_{A1}, x_{B1}, x_{A2}, x_{B2}, x_{A3}, x_{B3}, x_{A4}, x_{B4} \geq 0
\end{align}$$

## 双対問題
$$\begin{align}
\min_{\mathbf{p}, \mathbf{\pi}} \quad&
\pi_{1} + \pi_{2} + \pi_{3} + \pi_{4} + p_{A} + 2p_{B}\\
\text{s.t.} \quad &
\pi_{1} + p_{A} \geq 100\\&
\pi_{1} + p_{B} \geq 80\\&
\pi_{2} + p_{A} \geq 50\\&
\pi_{2} + p_{B} \geq 50\\&
\pi_{3} + p_{A} \geq 90\\&
\pi_{3} + p_{B} \geq 40\\&
\pi_{4} + p_{A} \geq 120\\&
\pi_{4} + p_{B} \geq 90\\&
\pi_{1}, \pi_{2}, \pi_{3}, \pi_{4}, p_{A}, p_{B} \geq 0
\end{align}$$

## 最適解
主問題の最適解は$x_{B1} = x_{A3} = x_{B4} = 1$で，最適値は260.
||買手1|買手2|買手3|買手4|供給量|
|---|---|---|---|---|---|
|財$A$|100|50|**90**|120|1|
|財$B$|**80**|50|40|**90**|2|

双対問題の最適解は$(p_{A}, p_{B} | \pi_{1}, \pi_{2}, \pi_{3}, \pi_{4})=(80, 50|30, 0, 10, 40)$．

これらの解が主/双対実行可能であることは明らか．相補性条件を書き下せば，
\begin{align}
x_{A1} &\left\{\pi_{1}+p_{A}-100\right\} &&= 0\cdot\left(30+80-100\right)&&=0\\
x_{B1} &\left\{\pi_{1}+p_{B}-80\right\} &&= 1\cdot\left(30+50-80\right)&&=0\\
x_{A2} &\left\{\pi_{2}+p_{A}-50\right\} &&= 0\cdot\left(0+80-50\right)&&=0\\
x_{B2} &\left\{\pi_{2}+p_{B}-50\right\} &&= 0\cdot\left(0+50-50\right)&&=0\\
x_{A3} &\left\{\pi_{3}+p_{A}-90\right\} &&= 1\cdot\left(10+80-90\right)&&=0\\
x_{B3} &\left\{\pi_{3}+p_{B}-40\right\} &&= 0\cdot\left(10+50-40\right)&&=0\\
x_{A4} &\left\{\pi_{4}+p_{A}-120\right\} &&= 0\cdot\left(40+80-120\right)&&=0\\
x_{B4} &\left\{\pi_{4}+p_{B}-90\right\} &&= 1\cdot\left(40+50-90\right)&&=0\\
\pi_{1} & \left\{1-x_{A1}-x_{B1}\right\} &&=30 \cdot\left(1-0-1\right)&&= 0\\
\pi_{2} & \left\{1-x_{A2}-x_{B2}\right\} &&=0 \cdot\left(1-0-0\right)&&= 0\\
\pi_{3} & \left\{1-x_{A3}-x_{B3}\right\} &&=10 \cdot\left(1-1-0\right)&&= 0\\
\pi_{4} & \left\{1-x_{A4}-x_{B4}\right\} &&=40 \cdot\left(1-0-1\right)&&= 0\\
p_{A} &\left\{1 - x_{A1}-x_{A2}-x_{A3}-x_{A4}\right\} &&= 80\cdot\left(1-0-0-1-0\right) &&=0\\
p_{B} &\left\{2 - x_{B1}-x_{B2}-x_{B3}-x_{B4}\right\} &&= 50\cdot\left(2-1-0-0-1\right) &&=0\\
\end{align}

ちなみに，価格が10円づつ高く各買手の最大利得が10円づつ低い解:
$$(p_{A}, p_{B} | \pi_{1}, \pi_{2}, \pi_{3}, \pi_{4}) = (90, 60|20, 0, 0, 30)
$$も双対実行可能で目的関数値が
$$20+40+90+2\times60=260
$$となることから，これもまた双対問題の最適解である（より正確には，0〜10円の範囲で価格と最大利得をシフトさせた解は全て最適解）．

このように，線形計画問題の**最適解は複数存在することがある**（第8回講義で紹介したように主問題でも配分の仕方が複数通りあることがある）が，**最適値は常に唯一**である．