シンプレックス法(simplex method)とは、線形計画問題を解く反復法で、実行可能領域の頂点から出発し、目的関数の値を下げずに隣の頂点へ移ることを繰り返すものであり、単体法ともいう。各段は基底変数を非基底変数で解いた辞書の書き換え(ピボット)で、最適性と非有界性は辞書から判定でき、最初の実行可能な辞書は 2 段階法で作る。退化があると計算が巡回することがあるが、Bland の規則を使えば有限回で止まる。一方、Klee–Minty の例では最大係数の規則に指数回のピボットが要る。
条件に $x\ge0$ を含む線形計画問題は、最適解をもつなら 多面体 の頂点のどれかが最適解になる(線形計画法 の定理「最適解は頂点でとれる」)。しかし頂点の個数は急に増えるので、全部は比べられない。シンプレックス法(単体法、simplex method)は、頂点から出発して、目的関数の値を下げずに隣の頂点へ移ることを繰り返す計算法である。
たとえば「$x_1+x_2+2x_3\le8$、$2x_1+x_2+x_3\le10$、$x_1+3x_2+x_3\le12$、$x\ge0$ で $4x_1+2x_2+5x_3$ を最大化する」問題では、余りの変数を入れて式を解いた形(辞書)を作る。$z$ の式の正の係数の変数を増やし、最初にぶつかる条件まで進むと、2 回の計算で $z$ の式の係数がすべて負になり、最適解 $(4,0,2)$、最適値 $26$ が読み取れる(ex-spx-three)。
$A$ を $m\times n$ 実行列($m,n\ge1$)、$b\in\mathbb{R}^m$、$c\in\mathbb{R}^n$ とし、$a_i^{\mathsf T}$ を $A$ の第 $i$ 行とする。ベクトルの不等式は成分ごとの不等式で、内積を $c\cdot x$ と書く。扱う問題は不等式標準形
$$
\text{(P)}\qquad\text{最大化 } c\cdot x\quad\text{条件 } Ax\le b,\ x\ge0
$$
である。実行可能領域を $P:=\{x\in\mathbb{R}^n\mid Ax\le b,\ x\ge0\}$ と書く。ほかの形の問題を (P) に直す方法は 線形計画法 の節「定義」にある。
余りの変数(スラック変数)$s_i:=b_i-a_i\cdot x$($i=1,\dots,m$)を入れ、$w:=(x,s)\in\mathbb{R}^{n+m}$ の成分を $w_j=x_j$($j\le n$)、$w_{n+i}=s_i$ と番号付ける。$M:=(A\ \ I)$、$\tilde c:=(c,0)\in\mathbb{R}^{n+m}$ とすると、
$$
s=b-Ax\iff Mw=b,\qquad z:=c\cdot x=\tilde c\cdot w
$$
である。$x\mapsto w=(x,b-Ax)$ により、$P$ は「$Mw=b$、$w\ge0$」の解の全体と 1 対 1 に対応する。
添字の集合 $\{1,\dots,n+m\}$ を、$m$ 個からなる $B$ と $n$ 個からなる $N$ に分ける。連立方程式
$$
w_i=\beta_i-\sum_{j\in N}\alpha_{ij}w_j\quad(i\in B),\qquad z=\zeta+\sum_{j\in N}\gamma_jw_j
$$
の解 $(w,z)$ の全体が「$Mw=b$、$z=\tilde c\cdot w$」の解の全体に等しいとき、これを基底 $B$ の 辞書(dictionary)という。$w_i$($i\in B$)を 基底変数、$w_j$($j\in N$)を 非基底変数 という。$w_N=0$、$w_B=\beta$ で決まる点を辞書の 基底解 という。$\beta\ge0$ のとき辞書は 実行可能 であるという。実行可能な辞書で $\beta_i=0$ となる $i\in B$ があるとき、辞書は 退化 しているという。
辞書の係数を、行 $i$ を $w_i+\sum_j\alpha_{ij}w_j=\beta_i$、最後の行を $z-\sum_j\gamma_jw_j=\zeta$ として表に並べたものを タブロー という。下のピボットはその表の Gauss の消去法である。
シンプレックス法を使える条件は次のとおりである。
$M_B$、$M_N$ を $M$ の $B$、$N$ の列からなる行列とする。
要点:1 は $Mw=b$ を $w_B$ について解く。2・3 は、$w_j=0$($j\in N$)が不等式の等号にあたることと、多面体 の定理「頂点の特徴づけ」の 3 を $M_B$ の正則性で読み替える。
1:$Mw=b$ は $M_Bw_B+M_Nw_N=b$ と書ける。$M_B$ が正則なら $w_B=M_B^{-1}b-M_B^{-1}M_Nw_N$ で、これを $z=\tilde c_B\cdot w_B+\tilde c_N\cdot w_N$ に代入すると示した形の辞書を得る。逆に辞書があるとする。$M_Bu=0$ なら、基底解に $w_B$ の部分だけ $u$ を足した点も $Mw=b$ の解で、$w_N=0$ は同じなので辞書の式により $w_B$ も同じであり、$u=0$ である。よって $M_B$ は正則である。同じ基底の 2 つの辞書は、$w_N$ を任意に動かしたときに $w_B$ と $z$ の値が一致するので、定数項と係数が等しい。
2:$P$ は $n+m$ 本の不等式 $a_i\cdot x\le b_i$、$-x_j\le0$ の解の全体である。$j\in N$ について $w_j=0$ は、そのうちの 1 本が等号になることである。基底解でこの $n$ 本はどれも等号である。$x'$ が同次の方程式 $a_i\cdot x'=0$($n+i\in N$)、$x'_j=0$($j\in N$、$j\le n$)を満たすとすると、$w'=(x',-Ax')$ は $Mw'=0$、$w'_N=0$ を満たすので、$M_Bw'_B=0$ から $w'=0$、すなわち $x'=0$ である。よってこの $n$ 本の係数ベクトルは 1 次独立で、$\beta\ge0$ より基底解は実行可能だから、多面体 の定理「頂点の特徴づけ」により頂点である。
3:同じ定理により、$v$ で等号になる不等式から、係数ベクトルが 1 次独立な $n$ 本を選べる。その番号の全体を $N$、残りを $B$ とする。$M_Bu=0$ なら、$u$ を $0$ で延長した $w'=(x',s')$ は $s'=-Ax'$、$w'_N=0$ を満たし、選んだ $n$ 本の同次の方程式から $x'=0$、よって $u=0$ である。したがって $M_B$ は正則で、$w=(v,b-Av)$ は $w_N=0$ を満たすので基底 $B$ の基底解であり、$\beta=w_B\ge0$ である。
4:基底解の $0$ でない成分の添字の全体は $B$ に一致する($m$ 個ある)。別の基底 $B'$ の基底解でもあれば、この集合は $B'$ に含まれるので $B'=B$ である。$\square$
退化した頂点には複数の基底が対応しうる。これが巡回の原因になる。
基底 $B$ の辞書から、$k\in N$ が入り $r\in B$ が出る 1 回の計算を ピボット という($\alpha_{rk}\ne0$)。
| 量 | 公式 | 使える条件 | 根拠 |
|---|---|---|---|
| 最適性の判定 | すべての $j\in N$ で $\gamma_j\le0$ なら基底解は最適、最適値 $\zeta$ | 辞書が実行可能 | prop-spx-criteria |
| 非有界性の判定 | $\gamma_k>0$ かつすべての $i\in B$ で $\alpha_{ik}\le0$ なら非有界 | 辞書が実行可能 | prop-spx-criteria |
| 入る変数 $k$ | $\gamma_k>0$ の $k\in N$ から選ぶ | 判定に当たらないとき | prop-spx-pivot |
| 出る変数 $r$(比の判定) | $\alpha_{ik}>0$ の $i$ のうち $\beta_i/\alpha_{ik}$ が最小のものから選ぶ | 同上 | prop-spx-pivot |
| 入った変数の行 | $\beta_k'=\dfrac{\beta_r}{\alpha_{rk}}$、$\alpha_{kj}'=\dfrac{\alpha_{rj}}{\alpha_{rk}}$、$\alpha_{kr}'=\dfrac1{\alpha_{rk}}$ | $j\in N\setminus\{k\}$、$\alpha_{rk}\ne0$ | prop-spx-pivot |
| ほかの行 | $\beta_i'=\beta_i-\alpha_{ik}\beta_k'$、$\alpha_{ij}'=\alpha_{ij}-\alpha_{ik}\alpha_{kj}'$、$\alpha_{ir}'=-\dfrac{\alpha_{ik}}{\alpha_{rk}}$ | $i\in B\setminus\{r\}$、同上 | prop-spx-pivot |
| 目的関数の行 | $\zeta'=\zeta+\gamma_k\beta_k'$、$\gamma_j'=\gamma_j-\gamma_k\alpha_{kj}'$、$\gamma_r'=-\dfrac{\gamma_k}{\alpha_{rk}}$ | 同上 | prop-spx-pivot |
| 双対問題の解 | $y_i=-\gamma_{n+i}$($n+i\in B$ なら $y_i=0$) | 最適性の判定に当たる辞書 | prop-spx-dual |
実行可能な辞書について次が成り立つ。
1:(P) の実行可能解では $w\ge0$ なので $z=\zeta+\sum_j\gamma_jw_j\le\zeta$ であり、基底解では $w_N=0$ なので $z=\zeta$ である。
2:$t\ge0$ について $w_k=t$、それ以外の非基底変数を $0$ とし、$w_i=\beta_i-\alpha_{ik}t$($i\in B$)とする。これは辞書の解で、$\beta_i\ge0$ と $-\alpha_{ik}\ge0$ より $w\ge0$ だから (P) の実行可能解を与え、$z=\zeta+\gamma_kt\to+\infty$($t\to\infty$)である。$\square$
実行可能な辞書で、$k\in N$ について $\gamma_k>0$ で、$\alpha_{ik}>0$ となる $i\in B$ があるとする。そのような $i$ のうち $\beta_i/\alpha_{ik}$ が最小のものの 1 つを $r$ とする。
第 $r$ 行から $w_k=\dfrac{\beta_r}{\alpha_{rk}}-\dfrac1{\alpha_{rk}}w_r-\sum_{j\in N\setminus\{k\}}\dfrac{\alpha_{rj}}{\alpha_{rk}}w_j$ である。これをほかの行と $z$ の式に代入すると公式の表の係数が出る。解いて代入する操作は逆にたどれる(新しい第 $k$ 行を $w_r$ について解いて代入すればもとに戻る)ので、解の全体は変わらず、新しい連立方程式は定義の意味で辞書である。
実行可能性を確かめる。$\beta_k'=\beta_r/\alpha_{rk}\ge0$ である。$i\in B\setminus\{r\}$ では $\beta_i'=\beta_i-\alpha_{ik}\beta_r/\alpha_{rk}$ であり、$\alpha_{ik}\le0$ なら $\beta_i'\ge\beta_i\ge0$ である。$\alpha_{ik}>0$ なら $r$ の選び方から $\beta_i/\alpha_{ik}\ge\beta_r/\alpha_{rk}$ なので、両辺に $\alpha_{ik}$ を掛けて $\beta_i'\ge0$ である。
2 は公式 $\zeta'=\zeta+\gamma_k\beta_r/\alpha_{rk}$ と $\gamma_k>0$、$\alpha_{rk}>0$ による。$\beta_r=0$ なら $\beta_k'=0$、$\beta_i'=\beta_i$ なので、新しい基底解は $w_k=0$、$w_r=0$ のもとの基底解に等しい。$\square$
幾何的には、$w_k$ を増やすと基底解は $P$ の辺に沿って動き、最初に $0$ になる基底変数のところで隣の頂点に着く。$\beta_r=0$ のときは同じ頂点のまま基底だけが変わる。
(P) の双対問題「最小化 $b\cdot y$、条件 $A^{\mathsf T}y\ge c$、$y\ge0$」を考える。prop-spx-criteria の 1 が当てはまる辞書について、$j\in B$ のとき $\gamma_j:=0$ とし、$y_i:=-\gamma_{n+i}$($i=1,\dots,m$)とおく。すると $y$ は双対問題の最適解で、$b\cdot y=\zeta$ である。
要点:辞書の $z$ の式は $x$ についての恒等式なので、係数を比べると $A^{\mathsf T}y\ge c$ と $b\cdot y=\zeta$ が出る。
辞書の定義より、すべての $x\in\mathbb{R}^n$ について、$s=b-Ax$ とおけば $$ c\cdot x=\zeta+\sum_{j\le n}\gamma_jx_j+\sum_{i\le m}\gamma_{n+i}(b_i-a_i\cdot x)=(\zeta-b\cdot y)+\sum_{j\le n}\bigl(\gamma_j+(A^{\mathsf T}y)_j\bigr)x_j $$ が成り立つ。$x$ についての恒等式なので、$b\cdot y=\zeta$、$c_j=\gamma_j+(A^{\mathsf T}y)_j$ である。$\gamma\le0$ より $A^{\mathsf T}y\ge c$、$y\ge0$ である。基底解の $x$ で $c\cdot x=\zeta=b\cdot y$ なので、線形計画法 の命題「弱双対性」により $y$ は最適である。$\square$
| 規則 | 入る変数 $k$ | 出る変数 $r$ | 有限回で止まるか |
|---|---|---|---|
| 最大係数の規則 | $\gamma_k$ が最大のもの | 比が最小の行のどれか | 保証されない(ex-spx-cycle)。止まるときも指数回かかることがある(thm-spx-klee-minty) |
| Bland の規則 | $\gamma_k>0$ のうち添字が最小 | 比が最小の行のうち添字が最小 | 保証される(thm-spx-bland) |
| 摂動 | $\gamma_k>0$ のどれか | 右辺に無限小の量を加えた問題の比で 1 つに決める | 保証される(rem-spx-perturbation) |
実行可能な辞書から始め、各ピボットで $\beta_r>0$ であるとする。このとき手順は高々 $\binom{n+m}{m}-1$ 回のピボットで、最適性か非有界性の判定に当たって止まる。
prop-spx-pivot の 2 により $\zeta$ は各ピボットで真に増えるので、同じ辞書は 2 度現れない。prop-spx-basis の 1 により辞書は基底で決まるから、同じ基底も 2 度現れない。基底は高々 $\binom{n+m}{m}$ 個なので有限回で止まり、手順が止まるのは 2 つの判定のどちらかに当たるときである。$\square$
問い:最大化 $4x_1+2x_2+5x_3$、条件 $x_1+x_2+2x_3\le8$、$2x_1+x_2+x_3\le10$、$x_1+3x_2+x_3\le12$、$x\ge0$。
使う公式:公式の表、prop-spx-criteria の 1、prop-spx-dual。規則は最大係数の規則。
答え:2 回のピボットで $z=26-x_2-2s_1-s_2$ となり、最適解 $x=(4,0,2)$、最適値 $26$、双対問題の最適解 $y=(2,1,0)$ である。
最初の辞書は $s_1=8-x_1-x_2-2x_3$、$s_2=10-2x_1-x_2-x_3$、$s_3=12-x_1-3x_2-x_3$、$z=4x_1+2x_2+5x_3$ である。
1 回目:係数が最大の $x_3$ が入る。比は $8/2=4$、$10/1$、$12/1$ で、$s_1$ が出る。$$\begin{aligned}x_3&=4-\tfrac12x_1-\tfrac12x_2-\tfrac12s_1,\\s_2&=6-\tfrac32x_1-\tfrac12x_2+\tfrac12s_1,\\s_3&=8-\tfrac12x_1-\tfrac52x_2+\tfrac12s_1,\\z&=20+\tfrac32x_1-\tfrac12x_2-\tfrac52s_1.\end{aligned}$$
2 回目:$x_1$ が入る。比は $4/\frac12=8$、$6/\frac32=4$、$8/\frac12=16$ で、$s_2$ が出る。$$\begin{aligned}x_1&=4-\tfrac13x_2+\tfrac13s_1-\tfrac23s_2,\\x_3&=2-\tfrac13x_2-\tfrac23s_1+\tfrac13s_2,\\s_3&=6-\tfrac73x_2+\tfrac13s_1+\tfrac13s_2,\\z&=26-x_2-2s_1-s_2.\end{aligned}$$
係数がすべて負なので止まる。$y=(2,1,0)$ は $A^{\mathsf T}y-c=(0,1,0)\ge0$、$b\cdot y=16+10=26$ を満たす。
$\beta_r=0$ のピボットでは $\zeta$ が増えない(prop-spx-pivot の 2)ので、thm-spx-nondegenerate の議論は使えない。実際、ピボットを続けて同じ基底に戻り、同じ列を永久に繰り返すことがある。これを 巡回(cycling)という。
問い:最大化 $10x_1-57x_2-9x_3-24x_4$、条件
$$
\tfrac12x_1-\tfrac{11}2x_2-\tfrac52x_3+9x_4\le0,\qquad\tfrac12x_1-\tfrac32x_2-\tfrac12x_3+x_4\le0,\qquad x_1\le1,\qquad x\ge0
$$
を、最大係数の規則で解く。比が最小の行が複数あるときは、添字が最小のものを出す(添字の順は $x_1,\dots,x_4,s_1,s_2,s_3$)。
答え:次の 6 回のピボットの後、最初の基底 $\{s_1,s_2,s_3\}$ に戻る。どのピボットでも $\beta_r=0$ で、基底解は $x=0$、$z=0$ のままである。
| 回 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 入る変数 | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $s_1$ | $s_2$ |
| 入る変数の係数 $\gamma_k$ | $10$ | $53$ | $\frac{29}2$ | $18$ | $\frac{21}2$ | $24$ |
| 出る変数 | $s_1$ | $s_2$ | $x_1$ | $x_2$ | $x_3$ | $x_4$ |
1 回目の後:$$\begin{aligned}x_1&=11x_2+5x_3-18x_4-2s_1,\\s_2&=-4x_2-2x_3+8x_4+s_1,\\s_3&=1-11x_2-5x_3+18x_4+2s_1,\\z&=53x_2+41x_3-204x_4-20s_1.\end{aligned}$$
2 回目の後:$$\begin{aligned}x_1&=-\tfrac12x_3+4x_4+\tfrac34s_1-\tfrac{11}4s_2,\\x_2&=-\tfrac12x_3+2x_4+\tfrac14s_1-\tfrac14s_2,\\s_3&=1+\tfrac12x_3-4x_4-\tfrac34s_1+\tfrac{11}4s_2,\\z&=\tfrac{29}2x_3-98x_4-\tfrac{27}4s_1-\tfrac{53}4s_2.\end{aligned}$$
3 回目の後:$$\begin{aligned}x_2&=x_1-2x_4-\tfrac12s_1+\tfrac52s_2,\\x_3&=-2x_1+8x_4+\tfrac32s_1-\tfrac{11}2s_2,\\s_3&=1-x_1,\\z&=-29x_1+18x_4+15s_1-93s_2.\end{aligned}$$
4 回目の後:$$\begin{aligned}x_3&=2x_1-4x_2-\tfrac12s_1+\tfrac92s_2,\\x_4&=\tfrac12x_1-\tfrac12x_2-\tfrac14s_1+\tfrac54s_2,\\s_3&=1-x_1,\\z&=-20x_1-9x_2+\tfrac{21}2s_1-\tfrac{141}2s_2.\end{aligned}$$
5 回目の後:$$\begin{aligned}x_4&=-\tfrac12x_1+\tfrac32x_2+\tfrac12x_3-s_2,\\s_1&=4x_1-8x_2-2x_3+9s_2,\\s_3&=1-x_1,\\z&=22x_1-93x_2-21x_3+24s_2.\end{aligned}$$
6 回目は $s_2$ が入り $x_4$ が出て、最初の辞書 $s_1=-\tfrac12x_1+\tfrac{11}2x_2+\tfrac52x_3-9x_4$、$s_2=-\tfrac12x_1+\tfrac32x_2+\tfrac12x_3-x_4$、$s_3=1-x_1$、$z=10x_1-57x_2-9x_3-24x_4$ に戻る。
同じ問題を Bland の規則(thm-spx-bland)で解くと、5 回目までは同じで、6 回目に係数の大きい $s_2$($24$)ではなく添字の小さい $x_1$($22$)が入って $x_4$ が出る。7 回目に $x_3$ が入り $s_3$ が出て($\beta_r>0$)、$z=1-30x_2-42x_4-18s_2-s_3$ となり、最適解 $x=(1,0,1,0)$、最適値 $1$ を得る。
巡回を防ぐには、選び方を添字で決めればよい。
添字に全順序を 1 つ固定する。実行可能な辞書から始め、次の規則でピボットする。
止まらないとして矛盾を導く。基底は有限個なので、ある基底が 2 度現れる。prop-spx-basis の 1 により辞書も同じなので、各 $D_{t+1}$ が $D_t$ のピボットであるような辞書の列 $D_0,D_1,\dots,D_p=D_0$ がある。prop-spx-pivot の 2 により $\zeta$ は減らず、一周して戻るので一定である。よってどのピボットでも $\beta_r=0$ であり、基底解は列全体で同じ点 $\bar w$ である。
列の中で基底に入る添字を 動く添字 といい(一周して戻るので基底から出もする)、その最大を $\ell$ とする。$\ell$ が基底から出るピボットの辞書を $D$ とし、その基底を $B$、係数を $\beta,\alpha,\gamma$、そのとき入る添字を $e$ とする。$e$ も動く添字で $e\ne\ell$ なので $e< \ell$ である。また $\ell$ が基底に入るピボットの辞書を $D^*$ とし、その基底を $B^*$、非基底を $N^*$、$z$ の式の係数を $\gamma^*$ とする。$j\in B^*$ については $\gamma_j^*:=0$ とすれば、$D^*$ の $z$ の式は
$$
z=\zeta+\sum_{j}\gamma_j^*w_j\qquad\text{(1)}
$$
である(和はすべての添字にわたる)。$D^*$ で入るのが $\ell$ なので、規則 1 より
$$
\gamma_\ell^*>0,\qquad\gamma_j^*\le0\quad(j< \ell)\qquad\text{(2)}
$$
である。
$D$ の式で、$t\in\mathbb{R}$ について $w_e=t$、$e$ 以外の非基底変数を $0$、$w_i=\beta_i-\alpha_{ie}t$($i\in B$)とすると、$z=\zeta+\gamma_et$ である。これは「$Mw=b$、$z=\tilde c\cdot w$」の解なので (1) も満たす:
$$
\zeta+\gamma_et=\zeta+\gamma_e^*t+\sum_{i\in B}\gamma_i^*(\beta_i-\alpha_{ie}t).
$$
すべての $t$ で成り立つので $t$ の係数を比べて
$$
\sum_{i\in B}\gamma_i^*\alpha_{ie}=\gamma_e^*-\gamma_e
$$
を得る。$D$ で $e$ が入るので $\gamma_e>0$ であり、$e< \ell$ と (2) より $\gamma_e^*\le0$ である。よって右辺は負で、$\gamma_i^*\alpha_{ie}< 0$ となる $i\in B$ がある。
この $i$ について $\gamma_i^*\ne0$ なので $i\in N^*$ である。$i\in B\cap N^*$ だから $i$ は動く添字で、$i\le\ell$ である。$i=\ell$ ではない:$\gamma_\ell^*>0$ で、$\ell$ は $D$ の比の判定で選ばれたので $\alpha_{\ell e}>0$ であり、積が正になるからである。したがって $i< \ell$ で、(2) から $\gamma_i^*< 0$、よって $\alpha_{ie}>0$ である。さらに $i\in N^*$ より $\bar w_i=0$ なので、$D$ で $\beta_i=0$ である。すると $D$ の比の判定で、行 $i$ の比は $0$ で、選ばれた行 $\ell$ の比 $\beta_\ell/\alpha_{\ell e}=0$ と等しい。$i< \ell$ なので、これは規則 2 に反する。$\square$
順序はどう決めてもよいが、途中で変えてはいけない。
右辺に無限小の量を加えて退化をなくす方法もある。等式標準形 $Ax=b$、$x\ge0$ の実行可能な基底 $B_0$ から、右辺を $b+A_{B_0}(\varepsilon,\varepsilon^2,\dots,\varepsilon^m)^{\mathsf T}$ に置き換え、$\varepsilon$ の多項式の順序で比の判定を行う。入る変数の選び方によらず止まることは、この記事では証明しない。証明は Lee21 §4.3 の Theorem 4.12(p. 36)にある。
$b$ に負の成分があると、$s=b-Ax$ は実行可能な辞書でない。そこで変数を 1 つ足した問題を先に解く(第 1 段)。その結果の辞書から (P) を解くのが第 2 段である。
$\mathbf 1$ を成分がすべて $1$ の $\mathbb{R}^m$ のベクトルとする。(P) の 補助問題 とは、変数 $x_0$ を足した
$$
\text{(P}_0\text{)}\qquad\text{最大化 } {-x_0}\quad\text{条件 } Ax-x_0\mathbf 1\le b,\ x\ge0,\ x_0\ge0
$$
のことである。これも (P) の形の問題で、余りの変数は $s_i=b_i-a_i\cdot x+x_0$ である。添字の順は $x_0$ を最小とし、続けて $x_1,\dots,x_n,s_1,\dots,s_m$ とする。
(P$_0$) の実行可能解 $(x,0)$ の $x$ は (P) の実行可能解で、逆も成り立つ。したがって、(P) が実行可能であることと (P$_0$) の最適値が $0$ であることは同じである。
$b$ の成分の最小値が負であるとし、$b_r$ を最小の成分の 1 つとする。
要点:1 は直接の計算である。$x_0$ を最小の添字にしたので、$x_0$ の定数項が $0$ になるピボットでは必ず $x_0$ が出る。したがって $x_0$ が基底に残れば $\beta_0>0$ で、最適値は負である。
1:最初の辞書は $s_i=b_i-a_i\cdot x+x_0$、$z_0=-x_0$ である。第 $r$ 行から $x_0=-b_r+s_r+a_r\cdot x$ で、ほかの行は $s_i=b_i-b_r+s_r+(a_r-a_i)\cdot x$ となる。定数項は $-b_r>0$ と $b_i-b_r\ge0$ である。
2:$z_0=-x_0\le0$ なので (P$_0$) は非有界でなく、prop-spx-criteria の 2 の判定には当たらない。よって thm-spx-bland により有限回で止まる。
4 の準備として、$x_0$ が基底にあるあいだ $\beta_0>0$ が保たれることを示す。$x_0$ が基底にある辞書で $\beta_0>0$ とし、$k$ が入り $r'\ne0$ が出るとする。比を $\theta:=\beta_{r'}/\alpha_{r'k}$ とすると、新しい定数項は $\beta_0'=\beta_0-\alpha_{0k}\theta$ である。$\alpha_{0k}\le0$ なら $\beta_0'\ge\beta_0>0$ である。$\alpha_{0k}>0$ なら、$\beta_0/\alpha_{0k}\ge\theta$ であり、等号なら行 $0$ も比が最小で添字が最小なので、規則により $x_0$ が出たはずである。よって $\beta_0/\alpha_{0k}>\theta$ で、$\beta_0'>0$ である。
4:$x_0$ が基底に残って判定に当たったとき、基底解で $x_0=\beta_0>0$ なので、最適値は $-\beta_0< 0$ である。よって $x_0=0$ の実行可能解はなく、(P) は実行不可能である。
3:$x_0$ が基底から出たとき、$x_0$ は非基底変数で、基底解で $x_0=0$ である。「$Ax-x_0\mathbf 1+s=b$」の解のうち $x_0=0$ のものは「$Ax+s=b$」の解である。辞書の行で $w_0=0$ とおいた式は、$w_{N\setminus\{0\}}$ を自由に動かしたときのこの解の全体を与える。$z=c\cdot x$ の中の基底変数を行の式で置き換えれば、$z$ も $w_{N\setminus\{0\}}$ の式になる。基底の大きさは $m$ で、定数項は $\beta\ge0$ のままなので、(P) の実行可能な辞書である。$\square$
別の規則で (P$_0$) を解いて $x_0$ が値 $0$ で基底に残ったときは、$x_0$ の行の $0$ でない係数の変数を入れて $x_0$ を出せばよい($\beta_0=0$ なので定数項は変わらない)。行の係数がすべて $0$ だと $x_0\equiv0$ となるが、$x_0$ は連立方程式の解で任意の値をとれるので、そうはならない。
どの (P) についても、2 段階法と Bland の規則は有限回のピボットで止まり、次のちょうど 1 つが分かる。
要点:thm-spx-two-phase、thm-spx-bland、prop-spx-dual を合わせる。
有限回で止まることは thm-spx-two-phase と thm-spx-bland による。$b\ge0$ なら第 1 段は要らない。第 2 段の結果が 2、3 であり、3 の $y$ は prop-spx-dual による。1 の場合は第 1 段の最後の辞書に prop-spx-dual を当てる((P$_0$) も (P) の形である)。(P$_0$) の双対問題の条件は $A^{\mathsf T}y\ge0$、$\mathbf 1\cdot y\le1$、$y\ge0$ で、$b\cdot y$ は負の最適値に等しい。3 つが同時に起きないことは定義から明らかである。$\square$
この系は、線形計画法 の定理「線形計画法の双対定理」の計算による別の証明になっている。(P) とその双対問題がどちらも実行可能なら、命題「弱双対性」より (P) は非有界でないので、3 が起きて最適値が一致する。
止まるとしても、回数が小さいとは限らない。Klee と Minty は、シンプレックス法が最悪の場合に指数時間かかりうることを示した(KP17 Appendix A §A.3、p. 341)。同じ現象を示す問題にはいくつかの形があり、ここでは次の形で、最大係数の規則に $2^n-1$ 回かかることを示す。
$n\ge1$ について、次の問題を $(\mathrm{KM}_n)$ と書く。
$$
\text{最大化 }\sum_{j=1}^n10^{n-j}x_j\quad\text{条件 } 2\sum_{j=1}^{i-1}10^{i-j}x_j+x_i\le100^{i-1}\ (i=1,\dots,n),\quad x\ge0
$$
$n=3$ なら、最大化 $100x_1+10x_2+x_3$、条件 $x_1\le1$、$20x_1+x_2\le100$、$200x_1+20x_2+x_3\le10000$、$x\ge0$ である。
$(\mathrm{KM}_n)$ の実行可能領域の頂点はちょうど $2^n$ 個である。$x=0$ から最大係数の規則で解くと、ちょうど $2^n-1$ 回のピボットですべての頂点を 1 回ずつ通り、$z$ はピボットごとに真に増えて、最適解 $x=(0,\dots,0,100^{n-1})$、最適値 $100^{n-1}$ に達する。
要点:各 $i$ で $x_i,s_i$ の一方を非基底にした $2^n$ 個の基底の辞書を書き下すと、$z$ の式の係数は $\pm10^{n-i}$ だけになる。入る変数はこの符号で決まり、出る変数は入る変数と対になる変数である。符号の列を 2 進数とみると、ピボットごとにその数がちょうど $1$ 増える。
準備:$Z_0:=0$、$Z_i:=\sum_{j\le i}10^{i-j}x_j$ とおくと、$Z_i=10Z_{i-1}+x_i$、$z=Z_n$ で、余りの変数は $$s_i=100^{i-1}-20Z_{i-1}-x_i\qquad\text{(3)}$$ である。$x_j,s_j\ge0$($j\le i$)ならば $0\le Z_i\le100^{i-1}$ である($\star$)。実際、$i$ についての帰納法で、$Z_i=10Z_{i-1}+x_i\ge0$ であり、$s_i\ge0$ より $x_i\le100^{i-1}-20Z_{i-1}$ なので $Z_i\le100^{i-1}-10Z_{i-1}\le100^{i-1}$ である。
辞書:$\varepsilon\in\{1,-1\}^n$ について、$\varepsilon_i=1$ なら $v_i:=x_i$、$u_i:=s_i$、$\varepsilon_i=-1$ なら $v_i:=s_i$、$u_i:=x_i$ とする。(3) は $x_i$ と $s_i$ について対称なので、どちらの場合も $$u_i=100^{i-1}-20Z_{i-1}-v_i\qquad\text{(4)}$$ である。(3) を $Z_i=10Z_{i-1}+x_i$ に代入すると、$c_i:=0$($\varepsilon_i=1$)、$c_i:=100^{i-1}$($\varepsilon_i=-1$)として $$Z_i=\varepsilon_i(10Z_{i-1}+v_i)+c_i\qquad\text{(5)}$$ である。(5) により $Z_i$ は $v_1,\dots,v_i$ の 1 次式(定数項つき)で、(4) により $u_i$ も $v_1,\dots,v_i$ の 1 次式である。これが基底 $\{u_1,\dots,u_n\}$ の辞書 $D(\varepsilon)$ を与える。$Z_n$ を (5) で展開すると、$\sigma_i:=\prod_{l\ge i}\varepsilon_l$ として $$z=(\text{定数})+\sum_{i=1}^n\sigma_i10^{n-i}v_i\qquad\text{(6)}$$ である。
実行可能性:どの $\varepsilon$ についても、$D(\varepsilon)$ の基底解で $u_i>0$($i=1,\dots,n$)である($\star\star$)。基底解では $v=0$ で、(4) より $u_i=100^{i-1}-20Z_{i-1}$ である。$i$ についての帰納法で、$u_1=1>0$ であり、$i\ge2$ で $j< i$ について $x_j,s_j\ge0$ なら、($\star$) より $Z_{i-1}\le100^{i-2}$ なので $u_i\ge80\cdot100^{i-2}>0$ である。
入る変数:$D(\varepsilon)$ で、(6) より $z$ の式の正の係数は $\sigma_i=1$ の $i$ の $10^{n-i}$ で、大きさはすべて異なる。よって入るのは、$\sigma_i=1$ となる最小の $i$ の $v_i$ である。そのような $i$ がなければ最適である。
出る変数:$v_i=t$、ほかの $v$ を $0$ とする。(4)、(5) より、$l< i$ の $u_l$ は $t$ によらず、$u_i=\beta_i-t$ である。行 $i$ の比は $\beta_i>0$ である(($\star\star$))。$l>i$ について、$u_l$ は $t$ の 1 次式で、$t=0$ で正である。$t=\beta_i$ の点では $u_i=0$ で、ほかの $v$ も $0$ なので、この点は $\varepsilon_i$ だけを反転した $\varepsilon'$ の $D(\varepsilon')$ の基底解である。よって ($\star\star$) より $t=\beta_i$ でも $u_l>0$ である。したがって $[0,\beta_i]$ で $u_l>0$ であり、行 $l$ の比は $\beta_i$ より大きい。比が最小の行は $i$ だけで、$u_i$ が出て $D(\varepsilon')$ になる。$z$ は真に増える(prop-spx-pivot の 2)。
回数:$\varepsilon_i$ を反転すると、$\sigma_j$ は $j\le i$ で符号が変わり、$j>i$ では変わらない。入る $i$ の選び方から $\sigma_1=\dots=\sigma_{i-1}=-1$、$\sigma_i=1$ なので、ピボットの後は $\sigma_1=\dots=\sigma_{i-1}=1$、$\sigma_i=-1$ である。そこで $K(\varepsilon):=\sum_{\sigma_i=-1}2^{i-1}$ とおくと、これは 2 進法の繰り上がりそのもので、ピボットごとに $K$ はちょうど $1$ 増える。出発点 $x=0$ はすべて $\varepsilon_i=1$ の辞書で $K=0$、止まるのはすべて $\sigma_i=-1$ のときで $K=2^n-1$ である。$\varepsilon\mapsto K(\varepsilon)$ は全単射なので、すべての $D(\varepsilon)$ を 1 回ずつ通る。
頂点:止まるところでは $\varepsilon_n=-1$、$\varepsilon_i=1$($i< n$)なので、$x_1=\dots=x_{n-1}=0$、$s_n=0$ で、$x_n=z=100^{n-1}$ である。($\star\star$) と prop-spx-basis の 2、4 により、$D(\varepsilon)$ の基底解は異なる $2^n$ 個の頂点である。ほかに頂点はない:実行可能領域の点では ($\star$) より $i\ge2$ なら $20Z_{i-1}\le20\cdot100^{i-2}< 100^{i-1}$($i=1$ でも $Z_0=0$)なので、(3) より $x_i+s_i>0$ である。頂点では少なくとも $n$ 個の $w_j$ が $0$ なので(多面体 の定理「頂点の特徴づけ」)、各 $i$ で $x_i,s_i$ のちょうど一方が $0$ であり、その頂点はある $D(\varepsilon)$ の基底解である。$\square$
$(\mathrm{KM}_n)$ を書くのに要る桁数は $n$ の多項式なので、$2^n-1$ 回は問題の大きさについて指数的である。同じ問題で最初に $x_n$ を入れると、$s_n$ が出て 1 回で最適解に着く。
thm-spx-klee-minty の経路は次のとおりである。
| 回 | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
|---|---|---|---|---|---|---|---|---|
| $x_1$ | $0$ | $1$ | $1$ | $0$ | $0$ | $1$ | $1$ | $0$ |
| $x_2$ | $0$ | $0$ | $80$ | $100$ | $100$ | $80$ | $0$ | $0$ |
| $x_3$ | $0$ | $0$ | $0$ | $0$ | $8000$ | $8200$ | $9800$ | $10000$ |
| $z$ | $0$ | $100$ | $900$ | $1000$ | $9000$ | $9100$ | $9900$ | $10000$ |
| 次に入る | $x_1$ | $x_2$ | $s_1$ | $x_3$ | $x_1$ | $s_2$ | $s_1$ | なし |
| 次に出る | $s_1$ | $s_2$ | $x_1$ | $s_3$ | $s_1$ | $x_2$ | $x_1$ | なし |
図: Klee–Minty の問題の実行可能領域。左は n=2 の領域を 4 つの頂点すべてを通って進む経路。右は n=3 の 8 頂点を立方体の形に描いた模式図で、z の値が 0 から 10000 まで増える経路
問い:最大化 $2x_1+x_2$、条件 $x_1+x_2\ge3$、$x_1+2x_2\le8$、$2x_1+x_2\le10$、$x\ge0$。
使う公式:thm-spx-two-phase、公式の表。第 1 の不等式は $-x_1-x_2\le-3$ と書く。
答え:第 1 段は 2 回のピボット、第 2 段は 1 回のピボットで、最適解 $x=(5,0)$、最適値 $10$、双対問題の最適解 $y=(0,0,1)$ である。
補助問題の最初の辞書は $s_1=-3+x_0+x_1+x_2$、$s_2=8+x_0-x_1-2x_2$、$s_3=10+x_0-2x_1-x_2$、$z_0=-x_0$ である。$b$ の最小の成分は第 1 行なので、$x_0$ を入れ $s_1$ を出す。$$\begin{aligned}x_0&=3-x_1-x_2+s_1,\\s_2&=11-2x_1-3x_2+s_1,\\s_3&=13-3x_1-2x_2+s_1,\\z_0&=-3+x_1+x_2-s_1.\end{aligned}$$
$x_1$ が入る。比は $3$、$\frac{11}2$、$\frac{13}3$ で、$x_0$ が出る。$x_0$ の項を除き、$z=2x_1+x_2$ に $x_1$ の行を代入すると、(P) の実行可能な辞書 $$\begin{aligned}x_1&=3-x_2+s_1,\\s_2&=5-x_2-s_1,\\s_3&=4+x_2-2s_1,\\z&=6-x_2+2s_1\end{aligned}$$ を得る。基底解は $(3,0)$ である。
第 2 段:$s_1$ が入る。比は $s_2$ の行が $5$、$s_3$ の行が $2$ で、$s_3$ が出る。$$\begin{aligned}x_1&=5-\tfrac12x_2-\tfrac12s_3,\\s_1&=2+\tfrac12x_2-\tfrac12s_3,\\s_2&=3-\tfrac32x_2+\tfrac12s_3,\\z&=10-s_3.\end{aligned}$$ $x_2$ の係数は $0$、$s_3$ の係数は $-1$ なので最適である。$y=(0,0,1)$ は $b\cdot y=10$ を満たす。
問い:最大化 $x_1+x_2$、条件 $x_1+x_2\le1$、$-x_1-x_2\le-2$、$x\ge0$。
使う公式:thm-spx-two-phase、cor-spx-fundamental の 1。
答え:補助問題の最適値は $-\frac12$ で、(P) は実行不可能である。証拠は $y=(\frac12,\frac12)$ で、2 つの不等式を $\frac12$ 倍して足すと $0\le-\frac12$ となる。
$b$ の最小の成分は第 2 行なので、$x_0$ を入れ $s_2$ を出す。$$\begin{aligned}x_0&=2-x_1-x_2+s_2,\\s_1&=3-2x_1-2x_2+s_2,\\z_0&=-2+x_1+x_2-s_2.\end{aligned}$$ $x_1$ が入る。比は $x_0$ の行が $2$、$s_1$ の行が $\frac32$ で、$s_1$ が出る。$$\begin{aligned}x_0&=\tfrac12+\tfrac12s_1+\tfrac12s_2,\\x_1&=\tfrac32-x_2-\tfrac12s_1+\tfrac12s_2,\\z_0&=-\tfrac12-\tfrac12s_1-\tfrac12s_2.\end{aligned}$$ 係数がすべて $0$ 以下で $x_0$ は基底に残っている。$s_1,s_2$ の係数から $y=(\frac12,\frac12)$ で、$A^{\mathsf T}y=0$、$b\cdot y=-\frac12$ である。
問い:最大化 $x_1+x_2$、条件 $x_1-x_2\le2$、$-2x_1+x_2\le2$、$x\ge0$。
使う公式:prop-spx-criteria の 2。
答え:1 回のピボットの後の辞書で判定に当たり、非有界である。$t\ge0$ について $x=(2+t,t)$ は実行可能で、$z=2+2t$ である($t=10$ で $z=22$)。
最初の辞書は $s_1=2-x_1+x_2$、$s_2=2+2x_1-x_2$、$z=x_1+x_2$ である。最大係数が等しいので添字の小さい $x_1$ を入れる。$\alpha>0$ は $s_1$ の行だけで、$s_1$ が出る。$$\begin{aligned}x_1&=2+x_2-s_1,\\s_2&=6+x_2-2s_1,\\z&=2+2x_2-s_1.\end{aligned}$$ $x_2$ の係数は正で、$x_2$ の列の $\alpha$ は $-1,-1$ である。$x_2=t$、$s_1=0$ とすると $x_1=2+t$、$s_2=6+t$ である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 出る行は比が最小(prop-spx-pivot) | 最大化 $x_1$、$x_1\le2$、$x_1\le3$ で、比が $3$ の行の $s_2$ を出す | 実行可能性($s_1=-1$ になる) |
| 入る変数は $\gamma_k>0$(prop-spx-pivot) | 最大化 $-x_1$、$x_1\le1$ で $x_1$ を入れる | $\zeta$ が減らない($0$ から $-1$ へ減る) |
| 辞書が実行可能(prop-spx-criteria) | 最大化 $-x_1$、$-x_1\le-1$ の最初の辞書 | 判定 1($\gamma\le0$ だが基底解 $x_1=0$ は実行可能でない) |
| 各ピボットで $\beta_r>0$(thm-spx-nondegenerate) | ex-spx-cycle | 有限回で止まること |
| 入る変数の規則(thm-spx-bland) | ex-spx-cycle:出る変数は添字最小のまま、入る変数を最大係数にする | 有限回で止まること |
| 出る変数の規則(thm-spx-bland) | ex-spx-cycle の問題で、添字の順を $x_2,s_2,x_1,x_4,x_3,s_1,s_3$ とし、入る変数は添字最小のまま、比が同じ行では添字最大を出す | 有限回で止まること(同じ 6 回で巡回する) |
判定 1 は最適であるための十分条件で、必要条件ではない。
最大化 $x_1$、条件 $x_1\le0$、$x\ge0$ の最初の辞書は $s_1=-x_1$、$z=x_1$ である。実行可能解は $x_1=0$ だけなので基底解は最適だが、$\gamma_1=1>0$ で判定 1 に当たらない。辞書は退化している。退化していない実行可能な辞書では、$\gamma_k>0$ なら $w_k$ を増やして値を上げられるので、基底解が最適なら判定 1 が成り立つ。この例では 1 回のピボットで $x_1=-s_1$、$z=-s_1$ となり、判定に当たる。
どの行も、左の条件だけを外している。
1 行目:最初の辞書は $s_1=2-x_1$、$s_2=3-x_1$ である。$\gamma_1>0$ で入る変数は正しく、$s_2$ を出すと $x_1=3-s_2$、$s_1=-1+s_2$ で、定数項が負になる。比が最小の $s_1$ を出せば $x_1=2$ である。
2 行目:最初の辞書は $s_1=1-x_1$、$z=-x_1$ で、$x_1$ の行の比の判定は正しい。ピボットすると $x_1=1-s_1$、$z=-1+s_1$ である。辞書は実行可能のままだが、値は下がる。
3 行目:最初の辞書は $s_1=-1+x_1$、$z=-x_1$ で定数項が負である。$\gamma_1< 0$ だが、最適値は $x_1=1$ の $-1$ で、$\zeta=0$ ではない。
4・5 行目:ex-spx-cycle の計算である。4 行目は thm-spx-nondegenerate の仮定だけが満たされない。5 行目は thm-spx-bland の規則 2 を満たし、規則 1 だけが満たされない。
6 行目:入る変数を順 $x_2,s_2,x_1,x_4,x_3,s_1,s_3$ で最小にとると、入る変数の列は ex-spx-cycle と同じ $x_1,x_2,x_3,x_4,s_1,s_2$ になる。比が同じ行で順の最大を出すと、出る変数の列も同じ $s_1,s_2,x_1,x_2,x_3,x_4$ になる。同じ順で比が同じ行の順の最小を出す(Bland の規則)と、1 回目に $x_1$ が入り $s_2$ が出て、2 回目に $x_3$ が入り $s_3$ が出て、最適値 $1$ で止まる。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 比の判定に $\alpha_{ik}\le0$ の行も入れる | $\alpha_{ik}>0$ の行だけで比をとる | $\alpha_{ik}\le0$ の行は $w_k$ を増やしても $0$ にならない(prop-spx-pivot の証明) |
| 最小化の問題のまま $\gamma_j>0$ を探す | $-c$ の最大化に直すか、符号を逆にして $\gamma_j< 0$ を探す | 判定は最大化の形についてのもの(prop-spx-criteria) |
| $\gamma\le0$ だけで最適とする | 辞書が実行可能($\beta\ge0$)であることも確かめる | 反例の表の 3 行目 |
| 値が増えなかったので最適とする | 判定に当たるまで続ける。$\beta_r=0$ のピボットでは値は増えない | prop-spx-pivot の 2、ex-spx-cycle(7 回目で値が増える) |
| 最大係数の規則で必ず止まるとする | 巡回がありうる。Bland の規則か摂動を使う | ex-spx-cycle、thm-spx-bland |
| 第 1 段の最初のピボットで比の判定をする | 最初のピボットだけは $b_r$ が最小の行を出す | $x_0$ の列はどの行も $\alpha=-1$ で、この行を選ぶと定数項が $0$ 以上になる(thm-spx-two-phase の証明) |
大きな問題では係数の表全体を更新せず、$M_B^{-1}$(の分解)だけを持って必要な列を prop-spx-basis の 1 の式で計算する(改訂シンプレックス法)。最小化の等式標準形「最小化 $c\cdot x$、$Ax=b$、$x\ge0$」では、実行可能な基底 $B$ の 被約費用 $\bar c_N=c_N-(A_B^{-1}A_N)^{\mathsf T}c_B$ が $-c$ の最大化の辞書の $-\gamma_N$ にあたり、すべて $0$ 以上なら最適である(Lee21 §4.1、Theorem 4.3、p. 28)。
Dantzig がシンプレックス法を開発したのは 1947 年である(KP17 Appendix A §A.3、p. 341)。最悪の場合は指数回でも、平均では多項式時間であることが示されている(Sma98 の Problem 9 の解説)。線形計画問題そのものは、1979 年の Khachiyan の方法で多項式時間で解けることが分かった(KP17 同所)。実数の算術演算の回数で測る多項式時間の方法があるかどうかは、Sma98 の Problem 9 に挙げられている(Smaleの問題)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する