フーリエ・モツキンの消去法

フーリエ・モツキンの消去法

有限\(n\)個の変数\(x_{1},\cdots ,x_{n}\in \mathbb{R} \)に関する有限\(m\)本の1次不等式から構成される連立1次不等式\begin{equation}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\leq b_{m}\end{array}\right. \quad \cdots (1)
\end{equation}が与えられているものとします。ただし、\(a_{ij}\in \mathbb{R} \)は係数、\(b_{i}\in \mathbb{R} \)は定数項、\(x_{i}\in \mathbb{R} \)は変数です。

連立1次不等式\(\left( 1\right) \)に解\(\left( x_{1},\cdots ,x_{n}\right) \)が存在することを確認しようとしている状況を想定します。ある方法を通じて\(\left( 1\right) \)から特定の変数\(x_{n}\)を消去することにより、残りの変数\(x_{1},\cdots ,x_{n-1}\)に関する有限\(r\)本の1次不等式から構成される連立1次不等式\begin{equation}\left\{
\begin{array}{c}
a_{11}^{\prime }x_{1}+\cdots +a_{1n-1}^{\prime }x_{n-1}\leq b_{1}^{\prime }
\\
\vdots \\
a_{r1}^{\prime }x_{1}+\cdots +a_{rn}^{\prime }x_{n-1}\leq b_{r}^{\prime }\end{array}\right. \quad \cdots (2)
\end{equation}を得た際に、\(\left( 1\right) \)に解\(\left( x_{1},\cdots ,x_{n}\right) \)が存在することと、\(\left( 2\right) \)に解\(\left( x_{1},\cdots ,x_{n-1}\right) \)が存在することが必要十分になるように\(\left( 2\right) \)を生成できます。まずは具体例を提示し、後に議論を一般化します。

議論を一般化します。有限\(n\)個の変数\(x_{1},\cdots,x_{n}\in \mathbb{R} \)に関する有限\(m\)本の1次不等式から構成される連立1次不等式\begin{equation}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\leq b_{m}\end{array}\right. \quad \cdots (1)
\end{equation}が与えられているものとします。ただし、\(a_{ij}\in \mathbb{R} \)は係数、\(b_{i}\in \mathbb{R} \)は定数項、\(x_{i}\in \mathbb{R} \)は変数です。ここから変数\(x_{n}\)を消去することが目標です。

連立1次不等式\(\left( 1\right) \)を構成するそれぞれの1次不等式に含まれる変数\(x_{n}\)の係数\(a_{jn}\ \left( j=1,\cdots,m\right) \)に注目した上で、以下のルールにもとづいて新たな連立1次不等式を生成します。

1. \(\left( 1\right) \)において\(a_{jn}=0\)であるならば、\(\left( 1\right) \)を構成する\(j\)番目の1次不等式\begin{equation*}a_{j1}x_{1}+\cdots +a_{jn}x_{n}\leq b_{j}\end{equation*}をそのまま新たな連立1次不等式の構成要素とみなす。
2. \(\left( 1\right) \)において\(a_{jn}>0\)かつ\(a_{kn}<0\)を満たすそれぞれの\(j,k\in \left\{ 1,\cdots ,m\right\} \)に注目する。\(j\)番目の1次不等式の両辺に\(\frac{1}{a_{jn}}>0\)を掛けることにより得られる1次不等式\begin{equation*}\frac{a_{j1}}{a_{jn}}x_{1}+\cdots +\frac{a_{jn-1}}{a_{jn}}x_{n-1}+x_{n}\leq \frac{b_{j}}{a_{jn}}
   \end{equation*}を変形すると、\begin{equation*}
   x_{n}\leq \frac{b_{j}}{a_{jn}}-\left( \frac{a_{j1}}{a_{jn}}x_{1}+\cdots +\frac{a_{jn-1}}{a_{jn}}x_{n-1}\right)
   \end{equation*}となるため\(x_{n}\)の上界が得られる。\(k\)番目の1次不等式の両辺に\(\frac{1}{a_{kn}}<0\)を掛けることにより得られる1次不等式\begin{equation*}\frac{a_{k1}}{a_{kn}}x_{1}+\cdots +\frac{a_{kn-1}}{a_{kn}}x_{n-1}+x_{n}\geq
   \frac{b_{k}}{a_{kn}}
   \end{equation*}を変形すると、\begin{equation*}
   \frac{b_{k}}{a_{kn}}-\left( \frac{a_{k1}}{a_{kn}}x_{1}+\cdots +\frac{a_{kn-1}}{a_{kn}}x_{n-1}\right) \leq x_{n}
   \end{equation*}となるため\(x_{n}\)の下界が得られる。\(\left( 1\right) \)を満たす\(x_{n}\)が存在するためには上界が下界以上である必要があるため、\begin{equation*}\frac{b_{k}}{a_{kn}}-\left( \frac{a_{k1}}{a_{kn}}x_{1}+\cdots +\frac{a_{kn-1}}{a_{kn}}x_{n-1}\right) \leq \frac{b_{j}}{a_{jn}}-\left( \frac{a_{j1}}{a_{jn}}x_{1}+\cdots +\frac{a_{jn-1}}{a_{jn}}x_{n-1}\right)
   \end{equation*}すなわち、\begin{equation*}
   \left( \frac{a_{j1}}{a_{jn}}-\frac{a_{k1}}{a_{kn}}\right) x_{1}+\cdots
   +\left( \frac{a_{jn-1}}{a_{jn}}-\frac{a_{kn-1}}{a_{kn}}\right) x_{n-1}\leq
   \frac{b_{j}}{a_{jn}}-\frac{b_{k}}{a_{kn}}
   \end{equation*}を得る。これを新たな連立1次不等式の構成要素とみなす。
3. 新たな連立1次不等式の構成要素は以上だけである。

以上のアルゴリズムをフーリエ・モツキンの消去法（Fourier-Motzkin procedure）と呼びます。フーリエ・モツキンの消去法を適用すれば連立1次不等式から変数が1つ消去されますが、もとの連立1次不等式に解が存在することと、新たな連立1次不等式に解が存在することは必要十分であることが保証されます。

すべての係数の符号が一致する場合

連立1次不等式\begin{equation*}
\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\leq b_{m}\end{array}\right.
\end{equation*}において変数\(x_{n}\)のすべての係数\(a_{1n},\cdots ,a_{mn}\)が非ゼロであり、なおかつこれらの符号が一致する場合、フーリエ・モツキンの消去法を利用すると新たな連立1次不等式には1次不等式が付与されず、すべての1次不等式が消えてしまいます。これは何を意味するのでしょうか。

フーリエ・モツキンの消去法を繰り返し適用する

フーリエ・モツキンの消去法を繰り返し適用することにより変数を1つずつ消去できます。最終的には1つの変数に関する連立1次不等式が得られます。

連立1次不等式に解が存在しないことを示す

フーリエ・モツキンの消去法を適用すれば連立1次不等式から変数が消去されますが、もとの連立1次不等式に解が存在することと、新たな連立1次不等式に解が存在することは必要十分です。したがって、新たな連立1次不等式に解が存在しないことを示せば、それはもとの連立1次不等式に解が存在しないことを示したことになります。

演習問題