3.2

Fourier–Motzkin の消去法

59と書き換え，さらに，符号制約のない変数x を，符号制約のある新しい変数 y  0,室田一雄，杉原正顯:
線形代数II，z  0 の差として x = y − z と表現する．このとき，東京大学工学教程，丸善出版，
⎤⎡
⎤⎡
2013.
yyAx  b ⇐⇒A−AI⎥⎢⎢ z ⎥ = b,⎦⎣s⎢⎥⎢ z ⎥0⎣⎦sが成り立つが，上式の ⇐⇒ の右側は式 (3.9) の形である．この式の “⇐⇒” の意味を正確に述べると，右側の条件を満たす (y, z, s) に対して x = y − z が左側の条件を満たし，逆に，左側の条件を満たす x に対して右側の条件と x = y − z の関係を満たす (y, z, s) が存在するということである．

3.2

Fourier–Motzkin の消去法連立方程式を解くときに，二つの方程式を組み合わせることによって変数を消去するという考え方 (消去法) は，理論上も数値計算上もきわめて重要である．とくに線形方程式系に対する消去法は，Gauss の消去法として確立され，実用に供されている．不等式系に対しても，同様に，不等式を組み合わせることによって変数を消すという発想はきわめて自然であるが，これを系統的な手順として与えたものが Fourier–Motzkin (フーリエ–モツキン) の消去法である．なお，Fourier–Motzkin の消去法は不等式系に対する消去法の基本原理を与えるという意味で重要であるが，数値計算のアルゴリズムとしては効率が悪く，これを実際の数値計算に用いることはほとんどない．実際の数値計算には，線形計画法 (3.5 節) における単体法の系統のアルゴリズムが利用される．
与えられた不等式系がAx  bの形であるとする．ここで，行列 A は m × n 型行列，ベクトル b は m 次元ベクトルとする．上の不等式系を成分ごとに書けばnaij xj  bi(i = 1, . . . , m)

(3.10)

j=1である．
第 1 変数 x1 を消去するために，x1 の係数 ai1 の符号によって不等式を分類する．記号が煩雑になるのを避けるため，最初の m1 個が正 (a11 , . . . , am1 1 > 0)，603線形不等式系

次の m2 個が負 (am1 +1,1 , . . . , am1 +m2 ,1 < 0)，残りの m0 = m − m1 − m2 個が0 (am1 +m2 +1,1 , . . . , am1 = 0) とする．さらに，不等式は正の数で割って規格化できるので，正の係数は 1，負の係数は −1 であるとする．このとき，不等式系(3.10) は
x1 + ai2 x2 + · · · + ain xn  bi

(i = 1, . . . , m1 ),−x1 + ak2 x2 + · · · + akn xn  bk
al2 x2 + · · · + aln xn  bl(3.11)(k = m1 + 1, . . . , m1 + m2 ), (3.12)(l = m1 + m2 + 1, . . . , m)

(3.13)となる．
式 (3.11) の m1 本の不等式は

x1 min (bi − (ai2 x2 + · · · + ain xn ))1im1と同値であり，式 (3.12) の m2 本の不等式は

max

m1 +1km1 +m2(ak2 x2 + · · · + akn xn − bk )  x1と同値であるから，両方を合わせて⎛⎞

max

m1 +1km1 +m2⎝nakj xj − bk ⎠  x1 j=2が得られる．これよりmax⎛

m1 +1km1 +m2⎛n⎝min ⎝bi −1im1⎞
akj xj − bk ⎠ j=2n⎞
aij xj ⎠(3.14)

j=2⎛
min ⎝bi −1im1n⎞
aij xj ⎠j=2が導かれるが，この条件は，任意の i = 1, . . . , m1 と任意の k = m1 +1, . . . , m1 +m2
に対して

nn

akj xj − bk  bi −j=2

aij xj(3.15)

j=2が成り立つことと等価である．移項して整理すると
n(aij +akj )xj  bi +bk
j=2(i = 1, . . . , m1 ; k = m1 +1, . . . , m1 +m2 ) (3.16)

3.2

Fourier–Motzkin の消去法

61となる．これは，式 (3.11) の i 番目の不等式と式 (3.12) の k 番目の不等式を加え合わせて新たな不等式を生成することを，すべての (i, k) に対して行った結果に一致している．
以上の変形により，(x1 , x2 , . . . , xn ) に関する不等式系 (3.11), (3.12), (3.13) は，(x2 , . . . , xn ) に関する不等式系 (3.16), (3.13) と x1 に関する不等式 (3.14) に分解されたことになる．この分解は必要十分条件を与えており，不等式条件 (3.16), (3.13)を満たす (x2 , . . . , xn ) に対して条件 (3.14) を満たす x1 を定めれば，与えられた不等式条件 (3.11), (3.12), (3.13) を満たす (x1 , x2 , . . . , xn ) が得られる．
次に，(x2 , . . . , xn ) に関する不等式系 (3.16), (3.13) に対して，同様にして，変数 x2 を消去して (x3 , . . . , xn ) に関する不等式系を得ることができる．このような変数消去を繰り返していくと，最後には一つだけの変数 xn に関する不等式系が得られるが，これを満たす xn を求める (あるいは，そのような xn が存在しないことを判定する) ことは容易である．これが Fourier–Motzkin の消去法の考え方である．
注意 3.1 変数の消去に伴う不等式の本数の変化を見ておこう．式 (3.11) の m1 本の不等式と式 (3.12) の m2 本の不等式から，式 (3.16) の m1 m2 本の不等式が生成されている．したがって，不等式の本数は m = m1 + m2 + m0 本から m1 m2 + m0本になる．これは一つの変数を消去したときの変化であり，変数消去を繰り返すと，通常は不等式の本数が急速に増加する．Fourier–Motzkin の消去法では，不等式の本数が (大幅に) 増大する可能性があることには注意が必要である．



変数の消去は，幾何学的には射影に対応する．与えられた不等式条件 (3.11),(3.12), (3.13) を満たす (x1 , x2 , . . . , xn ) の成す領域を S ( Rn ) とするとき，x1軸に沿った S の射影

Ŝ = {(x2 , . . . , xn ) | ある x1 に対して (x1 , x2 , . . . , xn ) ∈ S}
を記述する不等式系が，式 (3.16), (3.13) である．
例 3.1 変数 (x1 , x2 ) に関する不等式系

623線形不等式系

図 3.1

Fourier–Motzkin の消去法の例題

1x2  2,
3x1 + x2  5,

(3.18)−x1 − x2  −2,(3.19)−x1 + 2x2  4,(3.20)− x2  −1(3.21)

x1 −(3.17)に Fourier–Motzkin の消去法を適用する．この不等式系で記述される領域 S は
図 3.1 のような多角形領域であり，この図を見れば上の不等式系に解 (x1 , x2 ) が存在することがわかるが，Fourier–Motzkin の消去法によってこのことを導こう．
不等式は全部で 5 本あり，そのうち x1 の係数が正のものが 2 本，負のものが 2本である (m = 5, m1 = m2 = 2)．式 (3.14) は
1max (2 − x2 , −4 + 2x2 )  x1  min 2 + x2 , 5 − x23となり，x1 を消去した不等式系 (3.16) は
1− − 1 x2  (2 − 2),
3(1 − 1) x2  (5 − 2),

(3.22)
1− + 2 x2  (2 + 4),
3(1 + 2) x2  (5 + 4),

すなわちx2  0,x2 18,5無条件,x2  3(3.23)

3.3となる (図 3.1 の線形不等式系の解の存在63◦ 印の点の x2 座標に対応している)．式 (3.23) と式 (3.21) より
1 = max (1, 0)  x2  min

18,35

=3(3.24)が得られる．したがって，S の射影は Ŝ = {x2 | 1  x2  3} となる．式 (3.24) を満たす x2 が存在することから，与えられた不等式系の解 (x1 , x2 ) が存在することがわかる．たとえば，x2 = 2 とすると，式 (3.22) は
880 = max(0, 0)  x1  min,3 =33となり，たとえば x1 = 1 とすることができる．これにより，(x1 , x2 ) = (1, 2) が不等式条件 (3.17)〜(3.21) を満たすことが結論できる．

3.3

線形不等式系の解の存在

本節では，線形不等式系 Ax  b が解 x をもつための条件を考える．行列 A はm × n 型行列，ベクトル b は m 次元ベクトルとする．
比較のために，方程式系 (線形等式系) の場合の定理を思い出しておく[15] ．
定理 3.1 行列 A とベクトル b に関して，次の 2 条件 (a), (b) は同値である．

(a) Ax = b を満たすベクトル x が存在する．
(b) 任意の実数ベクトル y について，y  A = 0 ならば y  b = 0 である．
当然のこととして，方程式系と不等式系では具体的な条件は異なるが，不等式系に関する諸定理においても定理 3.1 のパターンは踏襲される．なお，上の条件(a) は，幾何学的には(c) b は A の列ベクトルの張る部分空間 Im(A) に属すると言い換えることができる．

3.3.1

Farkas の 補 題

ここでは，線形不等式系が解をもつための条件を与える定理として，Farkas の補題とそれに関連する定理について述べる．Farkas の補題は，線形不等式論にお