logo

シンプレックス法のブランドのルール 📂最適化理論

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

要旨

辞書において、i=1,⋯ ,mi = 1 , \cdots , mに対する以下の形式の方程式の組み合わせを辞書dictionaryという。 ζ=∑j=1ncjxjxn+i=bi−∑j=1naijxj \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と呼ぶ。それらのインデックスは以下のように表される。 B:={n+1,n+2,⋯ ,n+m}N:={1,2,⋯ ,n} \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のインデックスをN\mathcal{N}から最小のものを選択し、出る変数leaving variableのインデックスをB\mathcal{B}から最小のものを選択することをブランドのルールBrand’s ruleと呼ぶ。ブランドのルールによると、シンプレックス法はサイクルに陥らない。

説明

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

証明 1

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

Part 1. ζ=v+∑j=1n+mcj∗xj\zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j}

一般性を失わずに、サイクリングが発生した時点から証明を始めよう。あるk∈Nk \in \mathbb{N}に対して、辞書が以下のように循環する。 D0,D1,⋯ ,Dk−1,D0,D1,⋯ D_{0} , D_{1} , \cdots, D_{k-1} , D_{0} , D_{1} , \cdots この辞書の中で、あるものでは基底であり、あるものでは基底でない変数を移り気な変数fickleと呼ぼう。中でxtx_{t}が最大のインデックスを持つ移り気な変数とし、xtx_{t}を出る変数として持つ辞書をDDとするとき、一般性を失わずにD=D0D = D_{0}としたとき、DDは∀i∈B\forall i \in \mathcal{B}に対して以下のように書ける。 ζ=v+∑j∈Ncjxjxn+i=bi−∑j∈Naijxj \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*} ここでxsx_{s}が入る変数であればxtx_{t}が出る変数であり、まだt∈Bt \in \mathcal{B}でありs∈Ns \in \mathcal{N}である。今、D∗D^{\ast}をxtx_{t}が基底に入る辞書とし、∀i∈B∗\forall i \in \mathcal{B}^{\ast}に対して以下のように書けるとする。 ζ=v∗+∑j∈N∗cj∗xjxn+i=bi∗−∑j∈N∗aij∗xj \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*} シンプレックス法がサイクルに陥ったことは、すべてのD1,⋯ ,Dk−1D_{1} , \cdots, D_{k-1}が退化しているdegeneratedことを意味し、v∗=vv^{\ast} = vであるため、目的関数 ζ\zetaはcj∗=0c_{j}^{\ast} = 0としてj∈B∗j \in \mathcal{B}^{\ast}に対して以下のように書ける。 ζ=v+∑j=1n+mcj∗xj \zeta = v + \sum_{j = 1}^{n+m} c_{j}^{\ast} x_{j}

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

方程式の形で行ったように、入る変数xsx_{s}を増やし、他のN\mathcal{N}にある変数を00で固定して、どの変数も負にならない状況を考えよう。数式で表すと xs=yxj=0,j∈N∖{s}xi=bi−aisy,i∈B \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*} であり、これはyyを増やすことである。目的関数ζ\zetaに対してこれをもう一度書き直すと、以下を得る。 ζ=v+csy \zeta = v + c_{s} y

Part 3.

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

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

Part 4. r<tr < t

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

  • xtx_{t}がD∗D^{\ast}の入る変数であるため、ct∗>0c_{t}^{\ast} > 0である。
  • xtx_{t}がDDの出る変数であるため、ats>0a_{ts} > 0である。

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

Part 5.

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

■

参照

線形計画法の基本定理

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

  1. Vanderbei. (2020). Linear Programming(5th Edition): p34~36。 ↩︎