📂最適化理論

シンプレックス法のブランドのルール

要旨

辞書において、$i = 1 , \cdots , m$に対する以下の形式の方程式の組み合わせを辞書^dictionaryという。 $$ \begin{align*} \zeta &=& & & \sum_{j=1}^{n} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j=1}^{n} a_{ij} x_{j} \end{align*} $$ $\zeta$を除いた左辺の変数を基底変数^{basic variable}、右辺の変数を非基底変数^{nonbasic variable}と呼ぶ。それらのインデックスは以下のように表される。 $$ \begin{align*} \mathcal{B} :=& \left\{ n+1 , n+2 , \cdots , n+m \right\} \\ \mathcal{N} :=& \left\{ 1 , 2 , \cdots , n \right\} \end{align*} $$

線形計画法の シンプレックス法では、入り変数^{entering variable}のインデックスを$\mathcal{N}$から最小のものを選択し、出る変数^{leaving variable}のインデックスを$\mathcal{B}$から最小のものを選択することをブランドのルール^{Brand’s rule}と呼ぶ。ブランドのルールによると、シンプレックス法はサイクルに陥らない。

説明

線形計画問題を解く方法はシンプレックス法だけではなく、シンプレックス法で辞書を更新するピボットルール^{pivot rule}も一つだけではないが、ブランドのルールがあることでシンプレックス法は必ず線形計画問題を解けることが保証される点が重要である。この定理を理解すれば、実質的に線形計画法で最も重要な二つのコンセプト、その中でもシンプレックス法をマスターしたと見なしても良い。

証明 ¹

戦略: 難しい。ブランドのルールでピボットを行ってサイクルに陥ることが矛盾であることを示す。

---

Part 1. $\zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j}$

一般性を失わずに、サイクリングが発生した時点から証明を始めよう。ある$k \in \mathbb{N}$に対して、辞書が以下のように循環する。 $$ D_{0} , D_{1} , \cdots, D_{k-1} , D_{0} , D_{1} , \cdots $$ この辞書の中で、あるものでは基底であり、あるものでは基底でない変数を移り気な変数^fickleと呼ぼう。中で$x_{t}$が最大のインデックスを持つ移り気な変数とし、$x_{t}$を出る変数として持つ辞書を$D$とするとき、一般性を失わずに$D = D_{0}$としたとき、$D$は$\forall i \in \mathcal{B}$に対して以下のように書ける。 $$ \begin{align*} \zeta &=& v &+& \sum_{j \in \mathcal{N}} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j \in \mathcal{N}} a_{ij} x_{j} \end{align*} $$ ここで$x_{s}$が入る変数であれば$x_{t}$が出る変数であり、まだ$t \in \mathcal{B}$であり$s \in \mathcal{N}$である。今、$D^{\ast}$を$x_{t}$が基底に入る辞書とし、$\forall i \in \mathcal{B}^{\ast}$に対して以下のように書けるとする。 $$ \begin{align*} \zeta &=& v^{\ast} &+& \sum_{j \in \mathcal{N}^{\ast}} c_{j}^{\ast} x_{j} \\ x_{n+i} &=& b_{i}^{\ast} &-& \sum_{j \in \mathcal{N}^{\ast}} a_{ij}^{\ast} x_{j} \end{align*} $$ シンプレックス法がサイクルに陥ったことは、すべての$D_{1} , \cdots, D_{k-1}$が退化している^degeneratedことを意味し、$v^{\ast} = v$であるため、目的関数 $\zeta$は$c_{j}^{\ast} = 0$として$j \in \mathcal{B}^{\ast}$に対して以下のように書ける。 $$ \zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j} $$

---

Part 2. $\zeta = v + c_{s} y$

方程式の形で行ったように、入る変数$x_{s}$を増やし、他の$\mathcal{N}$にある変数を$0$で固定して、どの変数も負にならない状況を考えよう。数式で表すと $$ \begin{align*} x_{s} =& y \\ x_{j} =& 0 & , j \in \mathcal{N} \setminus \left\{ s \right\} \\ x_{i} =& b_{i} - a_{is} y & , i \in \mathcal{B} \end{align*} $$ であり、これは$y$を増やすことである。目的関数$\zeta$に対してこれをもう一度書き直すと、以下を得る。 $$ \zeta = v + c_{s} y $$

---

Part 3.

Part 1の$\zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j}$を$y$に対して再度書き直すと $$ \zeta = v + c_{s}^{\ast} y + \sum_{i \in \mathcal{B}} c_{i}^{\ast} \left( b_{i} - a_{is} y \right) $$ であり、左辺をPart 2の$\zeta = v + c_{s} y$で置き換えると $$ \left( c_{s} - c_{s}^{\ast} + \sum_{i \in \mathcal{B}} c_{i}^{\ast} a_{is} \right) y = \sum_{i \in \mathcal{B}} c_{i}^{\ast} b_{i} $$ を得る。この方程式は、右辺が何であれ、すべての$y$に対して常に成立し、これにより括弧内が常に$0$であることが分かる。 $$ \begin{equation} c_{s} - c_{s}^{\ast} + \sum_{i \in \mathcal{B}} c_{i}^{\ast} a_{is} = 0 \end{equation} $$ つまり、入る変数が$x_{s}$ならば $$ \begin{equation} c_{s} > 0 \end{equation} $$ であることが分かる。一方で$x_{t}$は最大インデックスを持つ移り気な変数であり、$x_{s}$も移り気な変数だったので、$s < t$が成り立つ。$D^{\ast}$の入る変数は$x_{t}$だったので、$x_{s}$は入る変数ではなく、 $$ \begin{equation} c_{s}^{\ast} \le 0 \end{equation} $$

$(1), (2), (3)$により $$ \sum_{i \in \mathcal{B}} c_{i}^{\ast} a_{is} < 0 $$ であり、以下を満たす$r \in \mathcal{B}$が存在しなければならない。 $$ c_{r}^{\ast} a_{rs} < 0 $$ 結果として$c_{r}^{\ast} \ne 0$であり$r \in \mathcal{N}^{\ast}$であるため、$x_{r}$は移り気な変数であり$r \le t$である。

---

Part 4. $r < t$

シンプレックス法を考えているので、以下の二つを話すことができる。

• $x_{t}$が$D^{\ast}$の入る変数であるため、$c_{t}^{\ast} > 0$である。
• $x_{t}$が$D$の出る変数であるため、$a_{ts} > 0$である。

したがって、$c_{t}^{\ast} a_{ts} > 0$であるが、$c_{r}^{\ast} a_{rs} < 0$であるため、$r \ne t$、すなわち$r < t$まで言い切ることができる。

---

Part 5.

$r < t$ならば、$c_{r}^{\ast} \le 0$であるべきであるが、そうではなく$c_{r}^{\ast} > 0$であった場合、Part 3により、$r$が$D^{\ast}$に対する入る変数であるべきだったからである。これとPart 3の$c_{r}^{\ast} a_{rs} < 0$により、 $$ \begin{equation} a_{rs} > 0 \end{equation} $$ である。一方、辞書がサイクルに陥ったということは、事実上すべて同じ解^solutionを表していることを意味し、それによりすべての移り気な変数はその辞書で$0$であることが分かり、特に$x_{r} = 0$である。しかし、$D$で$x_{r}$は基底変数^{basic variable}であるため、 $$ \begin{equation} b_{r} = 0 \end{equation} $$ である。$(4)$、$(5)$により、$x_{r}$は$D$で出る変数の候補の一つであり、Part 4では$r < t$であるため、ブランドのルールに従ったのであれば、$x_{t}$の代わりに早く選択（出る）されていたはずである。この矛盾により、ブランドのルールを使用したにもかかわらず辞書がサイクルに陥っているという前提が偽であることが分かる。

■

参照

線形計画法の基本定理

この定理は線形計画法の基本定理の証明に使用される。