---
lang: ja
tags: MTNS-2020, lecture, linear programming
---
# 2020年度 交通社会システム論<br>第3回：線形計画問題(2) 双対問題
[ポータルへ戻る](https://hackmd.io/@nagae/MTNS_2020)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：
<code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2020-Ch02</code>

</div>

# 双対問題
## A君ふたたび
バイトとデートへの時間配分を直接考えるのではなく，以下の3つの制約だけから「どこまで高いリア充度が実現できるか」を考えてみる：
- 時間制約: $x_{1} + x_{2} \leq 8$
- 予算制約: $-2x_{1}+x_{2} \leq 2$
- 体力制約: $2x_{1} + 3x_{2} \leq 18$

なお，リア充度は$Z(x_{1}, x_{2}) = x_{1} + 2x_{2}$ である．

## 制約条件からリア充度の上限を推定する
まず，時間制約$x_{1}+x_{2} \leq 8$ の両辺を2倍してみる：
$$
2x_{1} + 2 x_{2} \leq 16
$$
このとき，
- この不等式左辺の$x_{1}, x_{2}$の係数$(2,2)$は，リア充度$x_{1} + 2x_{2}$ の係数$(1,2)$以上
- $x_{1}, x_{2} \geq 0$

であることから，上記不等式の左辺は， ==**リア充度と同じかそれより大きい**==. 従って，
$$
\text{リア充度}=x_{1} + 2 x_{2} \leq 2x_{1} + 2x_{2} \leq 16
$$
が成り立つ．これは，==**時間制約**== を満たす限り，==**16より高いリア充度**== は実現できないことを意味する．

次に，体力制約$2x_{1} + 3x_{2} \leq 18$ の両辺を$2/3$倍してみる．
$$
\frac{4}{3} x_{1} + 2x_{2} \leq 12
$$
この不等式左辺の係数$(\frac{4}{3},2)$は，リア充度$x_{1} + 2x_{2}$ の係数$(1,2)$以上．従って，
$$
\text{リア充度}=x_{1} + 2 x_{2} \leq \frac{4}{3}x_{1} + 2x_{2} \leq 12
$$
が成り立つ．つまり，==**体力制約**== を満たす限り，==**12より高いリア充度**== は実現できない．

ここで得られたリア充度の上限($=12$)は，時間制約から得られた上限($=16$)より小さい(i.e. ==**より精度が高い**==)．

もっと精度の高い(小さい)上限はないだろうか?

予算制約と体力制約の両辺に，それぞれ，$1/8$および$5/8$を乗じる：
- 予算制約: $-2x_{1}+x_{2} \leq 2 \, (\times \frac{1}{8}) \rightarrow -\frac{1}{4} x_{1} + \frac{1}{8} x_{2} \leq \frac{1}{4}$
- 体力制約: $2x_{1}+3x_{2} \leq 18 \, (\times \frac{5}{8}) \rightarrow \frac{5}{4} x_{1} + \frac{15}{8} x_{2} \leq \frac{45}{4}$

得られた不等式を足し合わせれば，
$$
\text{リア充度} = x_{1} + 2x_{2} \leq \frac{23}{2} = 11.5
$$
となり，より小さい ==**リア充度の上限 11.5**== が得られる． 実は，これは最小の上限となっている(どのように制約条件を組み合わせても，これより小さい上限は実現できない)．

## リア充度の上限推定問題
ここまでで見てきた「制約条件からリア充度の上限を探る問題」を定式化してみよう．

:::info
**問題の概要**
- 「時間制約」「予算制約」「体力制約」を定数倍(重みづけ)したものを足し合わせて($x_{1}, x_{2}$についての) ==**線形式$\leq$ 定数**== 型の ==**不等式**== を構成する．
- ここで，
- 各不等式に乗ずる ==**重み**== が非負
- 不等式左辺の$x_{1}, x_{2}$についての係数が，いずれも，リア充度の係数$(1,2)$を下回らない

とすることで，不等式左辺が ==**リア充度以上**== となることが保証できる．
- 不等式右辺の定数(リア充度)が ==**なるべく小さくなる**==(精度が高くなる)ように，各制約への ==**重み**== を決定．
:::

### 未知変数と非負制約
- 求めたいのは，時間制約，予算制約および体力制約に対する ==**重み**==． それぞれ, $y_{1}, y_{2}, y_{3}$とする． これらの重みは，いずれも非負でなければならない．
$$
y_{1}, y_{2}, y_{3} \geq 0
$$

### 各制約の加重線形和から得られる不等式
各制約に重み$y_{1}, y_{2}, y_{3}$ を乗じて得られる不等式は，
$$
\begin{array}{rrcrcll}
y_{1} \times (& x_{1} &+& x_{2} &\leq& 8 &) \\
y_{2} \times (&-2 x_{1} &+& x_{2} &\leq& 2 &) \\
y_{3} \times (& 2 x_{1} &+& 3 x_{2} &\leq& 18 &) \\
\hline
&(y_{1} -2 y_{2} + 2 y_{3}) x_{1} &+& (y_{1} + y_{2} + 3 y_{3}) x_{2} &\leq& 8 y_{1} + 2 y_{2} + 18 y_{3}
\end{array}
$$
となる．

### 不等式の左辺がリア充度以上となるための制約
加重線形和として得られた不等式の左辺：
$$
(y_{1} -2 y_{2} + 2 y_{3}) x_{1} + (y_{1} + y_{2} + 3 y_{3}) x_{2}
$$
が，常にリア充度:
$$
x_{1} + 2 x_{2}
$$
以上となるためには，前者の$x_{1}, x_{2}$の係数が，いずれも後者のそれ以上となる必要がある：
- $x_{1}$の係数: $y_{1} - 2y_{2} + 2 y_{3} \geq 1$
- $x_{2}$の係数: $y_{1} + y_{2} + 3 y_{3} \geq 2$

### 目的関数
加重線形和として得られた不等式の右辺：
$$
8 y_{1} + 2 y_{2} + 18 y_{3}
$$
は ==**リア充度の上限**== を表しており，これをなるべく小さく(==**最小化**==)したい．

### 線形計画問題として定式化されたリア充度の上限推定問題
$$
\begin{alignat*}{3}
\min_{y_{1}, y_{2}, y_{3}} \quad & 8 y_{1} + 2 y_{2} + 18 y_{3} && \text{(目的関数=リア充度の上限)}\\
\text{s.t.} \quad
& y_{1} - 2 y_{2} + 2 y_{3} &\geq 1 \quad & \text{(バイト時間の係数が満たすべき条件)}\\
& y_{1} + y_{2} + 3 y_{3} &\geq 2 \quad & \text{(デート時間の係数が満たすべき条件)}\\
& y_{1}, y_{2}, y_{3} &\geq 0 \quad & \text{(非負制約)}
\end{alignat*}
$$

# もとの問題と比べてみる
<table>
<tr><th style="text-align:center">もとの問題</th><th style="text-align:center">リア充度推定問題</th>
</tr>
<tr><td style="vertical-align:top">

$$
\begin{array}{rl}
\displaystyle
\max_{x_{1}, x_{2}} & x_{1} + 2 x_{2}\\
\text{s.t.}
& x_{1} + x_{2} \leq 8 \\
& -2x_{1} + x_{2} \leq 2 \\
& 2x_{1} + 3 x_{2} \leq 18\\
& x_{1}, x_{2} \geq 0
\end{array}
$$

</td><td style="vertical-align:top">

$$
\begin{array}{rl}
\displaystyle
\min_{y_{1}, y_{2}, y_{3}} & 8 y_{1} + 2 y_{2} + 18 y_{3}\\
\text{s.t.}
& y_{1} - 2 y_{2} + 2 y_{3} \geq 1 \\
& y_{1} + y_{2} + 3 y_{3} \geq 2\\
& y_{1}, y_{2}, y_{3} \geq 0
\end{array}
$$

</td>
</tr>
</table>

係数と定数だけ並べてみると
<table>
<tr><th style="text-align:center">もとの問題</th><th style="text-align:center">リア充度推定問題</th>
</tr>
<tr><td style="vertical-align:top">

$$
\begin{array}{lrr|l}
& (x_{1}) & (x_{2})\\
\max & \color{red}{1} & \color{red}{2} \\
\hline
\text{s.t.}
& 1 & 1 & \color{blue}{8}\\
& -2 & 1 & \color{blue}{2}\\
& 2 & 3 & \color{blue}{18}
\end{array}
$$

</td><td style="vertical-align:top">

$$
\begin{array}{lrrr|l}
& (y_{1}) & (y_{2}) & (y_{3})\\
\min & \color{blue}{8} & \color{blue}{2} &\color{blue}{18}\\
\hline
\text{s.t.}
& 1 & -2 & 2 & \color{red}{1}\\
& 1 & 1 & 3 & \color{red}{2}\\
\end{array}
$$

</td></tr>
</table>

以下の関係が見てとれる：
- もとの問題の制約条件の左辺係数の転置 = 推定問題の制約条件の左辺係数
- もとの問題の目的関数の係数(の転置) = 推定問題の制約条件の右辺定数
- もとの問題の制約条件の右辺定数(の転置) = 推定問題の目的関数の係数

これは，偶然なのだろうか?

# 双対問題
$N$次元列ベクトル$\mathbf{c}, \mathbf{x}$, $M$次元列ベクトル$\mathbf{b}, \mathbf{y}$および$M\times{N}$行列$\mathbf{A}$が与えられた時，標準最大化問題
$$
\text{(P)} \qquad \max_{\mathbf{x}}
\left\{
\left.\mathbf{c}^{\top} \mathbf{x}\right|
\mathbf{A} \mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}
\right\}
$$
に対して，標準最小化問題
$$
\text{(D)} \qquad \min_{\mathbf{y}}
\left\{
\left.\mathbf{y}^{\top}\mathbf{b}\right|
\mathbf{y}^{\top} \mathbf{A} \geq \mathbf{c}^{\top}, \mathbf{y} \geq \mathbf{0}
\right\}
$$
を, ==**双対問題 (dual problem)**== と呼ぶ．双対問題 $\text{(D)}$ に対して，もとの問題 $\text{(P)}$ を ==**主問題 (primal problem)**== と呼ぶ．

「双対問題の双対問題」は主問題と等価である．

# 双対問題の解釈
双対問題は，それ自身が ==**何らかの意味を持った問題**== として解釈できることが多い．リア充問題の双対問題は，A君が持つ「時間」「資金」「体力」という3つの ==**資源**== のそれぞれの「(リア充度で測った)==**価値**==」を求める問題として解釈できる．

## 未知変数と非負制約
$y_{1}, y_{2}, y_{3}$ は，それぞれ，時間，資金，体力の各資源の ==**価値**== とする． 非負制約$y_{1}, y_{2}, y_{3}\geq 0$は，価値が負の値にはならない自然な条件と解釈できる．
## 目的関数
双対問題の目的関数
$$
8 y_{1} + 2y_{2} + 18 y_{3}
$$
は，(リア充度で測った) ==**総資産価値**== と見なせる．双対問題は ==**最小化問題**== であることから， ==**総資産価値の上限**== を推定する問題と解釈できる．

## $x_{1}$の係数に関する不等式制約
「1時間のバイト」は，

- ==**1単位**== の「時間」 と ==**2単位**== 「体力」 を**投入** して, ==**2単位**== の「資金」 と ==**1単位**== の「リア充度」 を **生産** する活動

と見なせる(「==**2単位**== の資金の**生産**」は，「==**-2単位**== の資金の**投入**」と読み替えてもよい．)
このとき，バイトに従事する時間$x_{1}$の係数に関する双対問題の不等式制約:
$$
y_{1} - 2 y_{2} + 2 y_{3} \geq 1
$$
は， ==**投入される資源の総価値**== (左辺)が，少なくともその対価として得られる ==**リア充度**== (右辺)を下回らなってはいけない条件と解釈できる．

## $x_{2}$の係数に関する不等式制約
バイトと同様，「1時間のデート」は，
- 「時間」「資金」および「体力」を，それぞれ ==**$(1,1,3)$ 単位**== づつ **投入** して ==**2単位**== の「リア充度」を **生産** する活動

と解釈できるから，デートに費す時間$x_{2}$ の係数に関する双対問題の不等式制約:
$$
y_{1} + y_{2} + 3 y_{3} \geq 2
$$
は，==**投入される資源の総価値**== (左辺)が，少なくともその対価として得られる ==**リア充度**== (右辺)を下回らなってはいけない条件と解釈できる．

## 双対問題： 保有資源の総価値の上限を推定する問題
結局，リア充問題の双対問題は，

- A君が保有する 「時間」「資金」「体力」という ==**資源の総価値**== を，バイトとデートというそれぞれの ==**生産活動**== に おいて「投入資源の総価値が, 生産されるリア充度を下回らない」という条件の下で見積る問題

と解釈できる．

## リア充問題よりリアル(?)な問題
ある地域に，以下の3種類の ==**再生可能資源**== を投入要素とする発電機とボイラーを導入する．
- 畜産由来の ==**8単位**== のバイオガス
- 地熱由来の ==**2単位**== の温水
- 間伐材由来の ==**18単位**== の木質バイオマス

発電機とボイラーの性能(稼働時間1単位に対する投入と生産):
<table>
<tr><th>発電機</th><th>ボイラー</th></tr>
<tr><td>

- ==**1単位**== のバイオガス
- ==**2単位**== の木質バイオマス

を**投入**すると
- ==**2単位**== の温水
- ==**1単位**== の電気

を**生産**する

</td><td>

- ==**1単位**== のバイオガス
- ==**1単位**== の温水
- ==**3単位**== の木質バイオマス

を**投入**すると
- ==**1単位**== の熱

を**生産**する．

</td>
</tr>
</table>

生産された ==**電気**== は1単位あたり1万円, ==**熱**== は1単位あたり2万円で売却できるとする．

<table>
<tr><th>主問題</th><th>双対問題</th></tr>
<tr><td>

発電機とボイラーの稼働時間$x_{1}, x_{2}$を ==**未知変数**== とし，各資源について
$$
\text{投入量}\leq\text{賦存量}
$$
なる制約を満たしながら，エネルギーの総売上を ==**最大化**==:
$$
\begin{align*}
\max_{x_{1},x_{2}} \quad & x_{1} + 2 x_{2}\\
\text{s.t.} \quad
& x_{1} + x_{2} \leq 8\\
& - 2 x_{1} + x_{2} \leq 2\\
& 2 x_{1} + 3 x_{2} \leq 18\\
& x_{1}, x_{2} \geq 0
\end{align*}
$$

</td>
<td>

各資源の価値$y_{1}, y_{2}, y_{3}$を ==**未知変数**== とし，各変換技術(発電機とボイラー)について ，
$$
\text{投入資源の価値}\geq\text{生産されるエネルギー価値}
$$
なる制約を満たしながら，資源の総価値の上限を ==**最小化**==:
$$
\begin{align*}
\min_{y_{1},y_{2},y_{3}} \quad & 8 y_{1} + 2y_{2} + 18 y_{3}\\
\text{s.t.} \quad
& y_{1} - 2y_{2} + 2 y_{3} \geq 1\\
& y_{1} + y_{2} + 3 y_{3} \geq 2 \\
& y_{1}, y_{2}, y_{3} \geq 0
\end{align*}
$$

</td></tr>
</table>

# 等式制約を持つ / 非負制約を持たない問題に対する双対問題
## 主問題が等式制約を持つ場合

### 等式制約を持つ線形計画問題
$$
\begin{align*}
\max_{x_{1}, x_{2}, x_{3}} \quad &
3 x_{1} + 4 x_{2} + x_{3} \\
\text{s.t.} \quad &
\color{red}{x_{1} + 3x_{2} + 2x_{3} = 4} \\&
x_{1} - 2 x_{2} + 3x_{3} \leq 5 \\&
x_{1}, x_{2}, x_{3} \geq 0
\end{align*}
$$
### 標準最大化問題
$$
\begin{alignat*}{3}
\max_{x_{1}, x_{2}, x_{3}} \quad &
3 x_{1} + 4 x_{2} + x_{3} \\
\text{s.t.} \quad &
\color{red}{x_{1} + 3x_{2} + 2x_{3} \leq 4} && (y_{1}^{+})\\&
\color{red}{- x_{1} - 3x_{2} - 2x_{3} \leq -4} \quad && (y_{1}^{-})\\&
x_{1} - 2 x_{2} + 3x_{3} \leq 5 && (y_{2})\\&
x_{1}, x_{2}, x_{3} \geq 0
\end{alignat*}
$$

ただし，各制約について，末尾の括弧内は，対応する双対問題の未知変数(双対変数)を表す．

### 双対問題
$$
\begin{align*}
\min_{y_{1}^{+}, y_{1}^{-}, y_{2}} \quad &
4 \color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} + 5 y_{2} \\
\text{s.t.} \quad &
\color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} + y_{2} \geq 3 \\&
3 \color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} - 2 y_{2} \geq 4 \\&
2 \color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} + 3 y_{2} \geq 1 \\&
y_{1}^{+}, y_{1}^{-}, y_{2} \geq 0
\end{align*}
$$

### $y_{1} = y_{1}^{+} - y_{1}^{-}$ とおく
$$
\begin{align*}
\min_{\color{red}{y_{1}}, y_{2}} \quad &
4 \color{red}{y_{1}} + 5 y_{2} \\
\text{s.t.} \quad &
\color{red}{y_{1}} + y_{2} \geq 3 \\&
3 \color{red}{y_{1}} - 2 y_{2} \geq 4 \\&
2 \color{red}{y_{1}} + 3 y_{2} \geq 1 \\&
\color{red}{y_{1} \text{ is free}}, y_{2} \geq 0
\end{align*}
$$

==**等式制約**== に対応する ==**双対変数**== は _非負制約を持たない_

## 主問題の未知変数が非負制約を持たない場合
### 非負制約を持たない未知変数を持つ線形計画問題
$$
\begin{align*}
\min_{\color{red}{y_{1}}, y_{2}} \quad &
4 \color{red}{y_{1}} + 5 y_{2} \\
\text{s.t.} \quad &
\color{red}{y_{1}} + y_{2} \geq 3 \\&
3 \color{red}{y_{1}} - 2 y_{2} \geq 4 \\&
2 \color{red}{y_{1}} + 3 y_{2} \geq 1 \\&
\color{red}{y_{1} \text{ is free}}, y_{2} \geq 0
\end{align*}
$$

### 標準最小化問題
$$
\begin{alignat*}{3}
\min_{y_{1}^{+}, y_{1}^{-}, y_{2}} \quad &
4 \color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} + 5 y_{2} \\
\text{s.t.} \quad &
\color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} + y_{2} \geq 3 &&(x_{1})\\&
3 \color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} - 2 y_{2} \geq 4 &&(x_{2})\\&
2 \color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} + 3 y_{2} \geq 1 &&(x_{3})\\&
y_{1}^{+}, y_{1}^{-}, y_{2} \geq 0
\end{alignat*}
$$

ただし，各制約について，末尾の括弧内は，対応する双対問題の未知変数(双対変数)を表す．

### 双対問題
$$
\begin{align*}
\max_{x_{1}, x_{2}, x_{3}} \quad &
3 x_{1} + 4 x_{2} + x_{3} \\
\text{s.t.} \quad &
\color{red}{x_{1} + 3x_{2} + 2x_{3} \leq 4} \\&
\color{red}{- x_{1} - 3x_{2} - 2x_{3} \leq -4} \\&
x_{1} - 2 x_{2} + 3x_{3} \leq 5 \\&
x_{1}, x_{2}, x_{3} \geq 0
\end{align*}
$$

### 線形式 $\lesseqgtr$ 定数→線形式$=$定数
$$
\begin{align*}
\max_{x_{1}, x_{2}, x_{3}} \quad &
3 x_{1} + 4 x_{2} + x_{3} \\
\text{s.t.} \quad &
\color{red}{x_{1} + 3x_{2} + 2x_{3} = 4} \\&
x_{1} - 2 x_{2} + 3x_{3} \leq 5 \\&
x_{1}, x_{2}, x_{3} \geq 0
\end{align*}
$$

==**非負制約を持たない変数**== に対応した双対問題の ==**制約条件**== (双対制約)は _等式になる_.

# 練習 (提出は不要)
前回の講義で紹介した3つの問題：
1. 食生活問題
2. 輸送問題
3. 割当問題

のそれぞれについて，双対問題を導出せよ．