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

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

# 二段階単体法
**標準最大化問題**の**等式標準形**およびその**辞書**:
$$
\begin{array}{crcrrcc}
\displaystyle\min_{\mathbf{x}, \mathbf{r}} \quad
&-c_{1} x_{1} &-\cdots &-c_{N} x_{N} &-0&=& -z\\
\text{s.t.}
&a_{11} x_{1} &+\cdots&+a_{1N} x_{N}&-b_{1}&=&-r_{1}\\
&\vdots & &\vdots& &&\vdots \\
&a_{M1} x_{1} &+\cdots&+a_{MN} x_{N}&-b_{M}&=&-r_{M}\\
&x_{1},&\cdots&x_{N}& &\geq&0\\
&r_{1},&\cdots&r_{M}&&\geq&0
\end{array}
\qquad
\begin{array}{c|ccc|c}
& x_{1} & \cdots & x_{N} & -1\\
\hline
-r_{1} & a_{11} & \cdots & a_{1N} & b_{1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
-r_{M} & a_{M1} & \cdots & a_{MN} & b_{M} \\
\hline
-z & -c_{1} & \cdots & -c_{N} & 0
\end{array}
$$
に対して**単体法**を適用するためには，**許容基底解**を初期解として与える必要がある．

- 任意の $j=1,\cdots,M$ について $b_{j} \geq 0$ の場合：
自明な**許容基底解** $(\mathbf{r}|\mathbf{x}) = (\mathbf{b}|\mathbf{0})$ が存在する．
- $b_{j} < 0$ なる行が存在する場合：
自明な**許容解**が存在しない → **補助問題**を**単体法**で解くことで**許容基底解**を探索．**許容解**が見つかれば，それを初期解として再度**単体法**を用いてもとの問題の**最適解**を求める(**2段階単体法**)．

# 二段階単体法で用いる補助問題
もとの問題：
$$
\begin{align}
\min_{\mathbf{x}, \mathbf{r}} \quad & -\mathbf{c}^{\top} \mathbf{x} = -z\\
\text{s.t.} \quad& \mathbf{A} \mathbf{x} + \mathbf{r} = \mathbf{b} \\
& \mathbf{x}, \mathbf{r} \geq \mathbf{0}
\end{align}
$$
に対して，以下の**補助問題**(auxiliary problem)を考える:
$$
\begin{align}
\min_{\mathbf{x}, \mathbf{r}, \color{red}{x_{a}}} \quad & \color{red}{x_{a}} = z_{a}\\
\text{s.t.} \quad& \mathbf{A} \mathbf{x} + \mathbf{r} \color{red}{-\mathbf{1} x_{a}}= \mathbf{b} \\
& \mathbf{x}, \mathbf{r}\color{red}{, x_{a}} \geq \mathbf{0}
\end{align}
$$
ここで，$\mathbf{1}$は全ての要素が1の$M$次元列ベクトル, $x_{a}$は**1次元(スカラ)の人工変数** (artifitial variable)．

**もとの問題**と**補助問題**との間には，以下の関係がある：
- **補助問題**は常に**実行可能**. $x_{a}$ を大きくすることで, 任意の$\mathbf{A}, \mathbf{b}$に対して**補助問題**の**許容解**を求められる．
- もとの問題が**実行可能**であり，かつその時にのみ, **補助問題**の**最適値**が0となる．

# 補助問題の初期許容基底解
補助問題の**辞書**は以下のように表される:
$$
\begin{array}{c|cccc|c}
& x_{1} & \cdots & x_{N} & x_{a} & -1 \\
\hline
-r_{1} & a_{11} & \cdots & a_{1N} & -1 & b_{1}\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
-r_{M} & a_{M1} & \cdots & a_{MN} & -1 & b_{M}\\
\hline
z_{a} & 0 & \cdots & 0 & 1 & 0
\end{array}
$$
いま，$b_{i}$が最小となる行を $h = \displaystyle\arg\min_{i=1, \cdots, M}\left\{b_{i}\right\}$ とし，**人工変数**$x_{a}$に対応する列を$k=N+1$とすると，$(h, k)$を**ピボット**とすることで，**補助問題**の**初期許容解**が得られる．

**ピボット演算**の規則：
$$
\boxed{
\begin{array}{cc}
p & r\\
c & q
\end{array}
} \Rightarrow
\boxed{
\begin{array}{cc}
1/p & r/p\\
-c/p & q-(rc/p)
\end{array}
}
$$
より，ピボット行$h$, ピボット列$k$および最終列(右辺定数)の要素は，以下のように変化する：
$$
\begin{array}{c|cc}
& x_{a} & -1\\
\hline
r_{h} & -1* & b_{h} \\
r_i & -1 & b_{i}
\end{array}
\Rightarrow
\begin{array}{c|cc}
& \color{red}{r_{h}} & -1\\
\hline
\color{red}{x_{a}} & 1 & -b_{h} \\
i & 1 & b_{i} - b_{h}
\end{array}
$$

ここで，$b_{i}$の中で最小のものが$b_{h}$であるため，$b_{h}<0$かつ$b_{i}-b_{h} \geq 0$となる．この**ピボット演算**後の**基底解**は，
$$\begin{align}
r_{i} &= b_{i} - b_{h} \quad (i\ne h),&
x_{a} &= - b_{h}
\end{align}
$$
であり，いずれも非負であるため**実行可能**である． 従って，これを**初期許容基底解**とした**単体法**によって**補助問題**を解くことができる．

# 二段階単体法の例
**例題**：
$$
\begin{alignat}{3}
\max_{x_{1}, x_{2}} && 3x_{1} &+&2x_{2}&=&z\\
\text{s.t.} && 2x_{1} &-& x_{2}&\leq& -1\\
&-&x_{1} &+&2x_{2} &\leq& 4\\
&-&x_{1} &-&x_{2} &\leq& -2\\
&&x_{1}&,&x_{2}&\geq&0
\end{alignat}
$$

**等式標準形**と**辞書**:
$$
\begin{alignat}{4}
\min_{x_{1}, x_{2}, r_{1}, r_{2}, r_{3}} &-& 3x_{1} &-&2x_{2}&&&=&-z\\
\text{s.t.} && 2x_{1} &-& x_{2}&-&(-1)&=&-r_{1}\\
&-&x_{1} &+&2x_{2} &-&4&=&-r_{2}\\
&-&x_{1} &-&x_{2} &-&(-2)&=&-r_{3}\\
&&x_{1}&,&x_{2}&,&r_{1},&r_{2}&,r_{3}\geq0
\end{alignat}
\qquad
\begin{array}{c|cc|c}
&x_{1}&x_{2}&-1\\
\hline
-r_{1}&2&-1&-1\\
-r_{2}&-1&2&4\\
-r_{3}&-1&-1&-2\\
\hline
-z & -3 &-2&0
\end{array}
$$

**人工変数**$x_{a}$を導入して**補助問題**を作成:
$$
\begin{alignat}{5}
\min_{x_{1}, x_{2}, r_{1}, r_{2}, r_{3}, x_{a}} && &&&&x_{a}&-&0&=&z_{a}\\
\text{s.t.} && 2x_{1} &-& x_{2}&-&x_{a}&-&(-1)&=& -r_{1}\\
&-&x_{1} &+&2x_{2}&-&x_{a}&-&4 &=& -r_{2}\\
&-&x_{1} &-&x_{2}&-&x_{a}&-&(-2)&=& -r_{3}\\
&&x_{1}&,&x_{2}&,&x_{a}&,&r_{1},&r_{2},&r_{3}\geq0
\end{alignat}
\qquad
\begin{array}{c|ccc|c}
&x_{1}&x_{2}&x_{a}&-1\\
\hline
-r_{1}&2&-1&-1&-1\\
-r_{2}&-1&2&-1&4\\
-r_{3}&-1&-1&-1&-2\\
\hline
\color{orange}{-z} &\color{orange}{-3} &\color{orange}{-2}&\color{orange}{0}&\color{orange}{0}\\
z_{a} & 0 & 0 & 1& 0
\end{array}
$$
**辞書**を構成する際，あとで便利なので，**もとの問題**の目的関数の行(上の例でオレンジ色で表されている行)を加えておくとよい．

右辺定数$b_{i}$が最小の行$h$と人工変数の列$k$を入れ替える**ピボット演算**を行なえば，**補助問題**の**初期許容基底解**が得られる．
$$
\begin{array}{c|ccc|c}
& x_{1} & x_{2} & x_{a} & -1\\
\hline
-r_{1} & 2 & -1 & -1 & -1\\
-r_{2} & -1 & 2 & -1 & 4\\
-r_{3} & -1 & -1 & -1* & -2\\
\hline
-z & -3 & -2 & 0 & 0 \\
z_{a} & 0 & 0 & 1 & 0
\end{array}
\Rightarrow
\begin{array}{c|ccc|c}
& x_{1} & x_{2} & r_{3} & -1\\
\hline
-r_{1} & 3 & 0 & -1 & 1\\
-r_{2} & 0 & 3 & -1 & 6\\
-x_{a} & 1 & 1 & -1* & 2\\
\hline
-z & -3 & -2 & 0 & 0 \\
z_{a} & -1 & -1 & -1 & -2
\end{array}
$$

$(r_{1}, r_{2}, x_{a}) = (1, 6, 2)$を**初期許容基底解**として, **補助問題**に対して**単体法**を適用(第1段階):
$$
\begin{array}{c|ccc|c}
& x_{1} & x_{2} & r_{3} & -1\\
\hline
-r_{1} & 3* & 0 & -1 & 1\\
-r_{2} & 0 & 3 & -1 & 6\\
-x_{a} & 1 & 1 & -1 & 2\\
\hline
-z & -3 & -2 & 0 & 0 \\
z_{a} & -1 & -1 & -1 & -2
\end{array}
\Rightarrow
\begin{array}{c|ccc|c}
& r_{1} & x_{2} & r_{3} & -1\\
\hline
-x_{1} & \tfrac{1}{3} & 0 & -\tfrac{1}{3} & \tfrac{1}{3}\\
-r_{2} & 0 & 3 & -1 & 6\\
-x_{a} & -\tfrac{1}{3} & 1* & -\tfrac{2}{3} & \tfrac{5}{3}\\
\hline
-z & 1 & -2 & -1 & 1 \\
z_{a} & \tfrac{1}{3} & -1 & \tfrac{2}{3} & -\tfrac{5}{3}
\end{array}
\Rightarrow
\begin{array}{c|ccc|c}
& r_{1} & x_{a} & r_{3} & -1\\
\hline
-x_{1} & \tfrac{1}{3} & 0 & -\tfrac{1}{3} & \tfrac{1}{3}\\
-r_{2} & 1 & -3 & 1 &1\\
-x_{2} & -\tfrac{1}{3} & 1 & -\tfrac{2}{3} & \tfrac{5}{3}\\
\hline
-z & \tfrac{1}{3} & 2 & -\tfrac{7}{3} & \tfrac{13}{3} \\
z_{a} & 0 & 1 & 0 & 0
\end{array}
$$

**補助問題**の**基底変数**の入れ替えにともなって，**もとの問題**の係数や定数も変化することに注意．

**補助問題**の**最適値**(i.e. **最適解**における**人工変数**$x_{a}$の値)が
$$
z_{a}^{\ast} = x_{a}^{\ast} = 0
$$なので，**もとの問題**は**実行可能**で，その**許容基底解**の1つが**補助問題**の**最適解**$(x_{1}, r_{2}, x_{2}) = \left(\tfrac{1}{3}, 1, \tfrac{5}{3}\right)$として求められた．

次に，これを**初期解**として**もとの問題**に**単体法**を適用する．**補助問題**の最適解に対応する**辞書**から
- 目的関数$z_{a}$に対応する行
- 人工変数$x_{a}$に対応する列

を取り除けば，$(x_{1}, r_{2}, x_{2})$を**基底変数**とする**辞書**が得られる:
$$
\begin{array}{c|cc|c}
& r_{1} & r_{3} & -1\\
\hline
-x_{1} & \tfrac{1}{3} & -\tfrac{1}{3} & \tfrac{1}{3}\\
-r_{2} & 1 & 1 &1\\
-x_{2} & -\tfrac{1}{3} & -\tfrac{2}{3} & \tfrac{5}{3}\\
\hline
-z & \tfrac{1}{3} & -\tfrac{7}{3} & \tfrac{13}{3} \\
\end{array}
$$

これを初期解として**単体法**を適用すれば，
$$
\begin{array}{c|cc|c}
& r_{1} & r_{3} & -1\\
\hline
-x_{1} & \tfrac{1}{3} & -\tfrac{1}{3} & \tfrac{1}{3}\\
-r_{2} & 1 & 1* &1\\
-x_{2} & -\tfrac{1}{3} & -\tfrac{2}{3} & \tfrac{5}{3}\\
\hline
-z & \tfrac{1}{3} & -\tfrac{7}{3} & \tfrac{13}{3} \\
\end{array}
\Rightarrow
\begin{array}{c|cc|c}
& r_{1} & r_{2} & -1\\
\hline
-x_{1} & \tfrac{2}{3} & \tfrac{1}{3} & \tfrac{2}{3}\\
-r_{3} & 1 & 1 &1\\
-x_{2} & \tfrac{1}{3} & \tfrac{2}{3} & \tfrac{7}{3}\\
\hline
-z & \tfrac{7}{3} & \tfrac{7}{3} & \tfrac{20}{3} \\
\end{array}
$$
より，**もとの問題**の**最適解**は$(x_{1}^{\ast}, r_{3}^{\ast}, x_{2}^{\ast} | r_{1}^{\ast}, r_{2}^{\ast}) = \left(\left.\tfrac{2}{3}, 1, \tfrac{7}{3} \right| 0, 0\right)$で，**最適値**は$z^{\ast} = \tfrac{20}{3}$ と求められる．

# (標準最大化問題に対する)二段階単体法の手続き
1. **等式標準形**および**初期辞書**を構築
2. $\mathbf{b} \geq \mathbf{0}$ なら，$(\mathbf{r}|\mathbf{x}) = (\mathbf{b}|\mathbf{0})$ が **もとの問題** の**初期許容基底解**
3. $\mathbf{b} \not\geq \mathbf{0}$ なら， **補助問題**に対して**単体法**を実行(==第1段階==):
3.1 $b_{i}$が最小となる行$h$と人工変数$x_{a}$の列を入れ替える**ピボット演算**により, **補助問題**に対する**許容基底解**が得られる．これを初期解として**単体法**を適用すれば，**補助問題**の**最適解**が求められる．
3.2 **補助問題**の**最適値**が正ならば，$\mathbf{A x}+\mathbf{r}=\mathbf{b}$かつ$\mathbf{x}, \mathbf{r} \geq \mathbf{0}$を満たす解$(\mathbf{x}, \mathbf{r})$は存在しない(i.e. **もとの問題**は**不能**)．
3.3 **補助問題**の**最適値**が0ならば，$x_{a}^{\ast} = 0$. このとき，**補助問題**の**最適解**$(\mathbf{x}_{B} | \mathbf{x}_{N}) = (\hat{\mathbf{b}}|\mathbf{0})$は**もとの問題**の**許容基底解**
4. **もとの問題**の許容基底解が求められたなら，それを初期解として**単体法**を実行(==第2段階==)．

# 基本定理の(構成的)証明
**二段階単体法**の手続きの特徴：
1. ==**第1段階**== (**補助問題**を解く)では，以下のいずれか一方が実現：
-- **もとの問題**が**不能**であると判定される
-- **もとの問題**の**許容基底解**の1つが見つかる
2. ==**第2段階**== (**もとの問題**を解く)では，以下のいずれか一方が実現:
-- **もとの問題**が**無界**である(制約条件を満たしながら目的関数値をどこまでも小さくできる)と判定される
-- **もとの問題**の**最適解**が見つかる．

従って，**二段階単体法**によって，どんな**線形計画問題**も
- **不能**(**許容解**を持たない)
- **無界**(**許容解**はあるが目的関数がどこまでも大きく/小さくできるため**最適解**を持たない)
- **最適解**をもつ

に分類される．これは，線形計画問題の**基本定理**の構成的証明を与える：
## 基本定理
:::success
**実行可能** で **有界** な線形計画問題は **最適解** を持つ.
:::

# 練習問題
次の問題を**二段階単体法**で解け：
$$
\begin{alignat}{4}
\max_{x_{1}, x_{2}, x_{3}} \quad & & 3x_{1} &+&4 x_{2} &+& 5 x_{3} &=&z\\
\text{s.t.} \quad
&& x_{1} &+&2x_{2}&+&2x_{3}&\leq&1\\
&-&3x_{1} &&&+&x_{3}&\leq&-1\\
&-&2x_{1} &-&x_{2}&&&\leq&-1\\
&&x_{1}&,&x_{2}&,&x_{3}&\geq&0
\end{alignat}
$$