2.3　Fourier-Motzkin消去法

本节将要介绍的Fourier-Motzkin消去法 ^[62] 是一种用来求解线性规划问题的常用方法，它是由Joseph Fourier和Theodore Motzkin分别于1827年和1936年独立发明的。William等人将Fourier-Motzkin消去法扩展到了整数规划领域 ^[76] 。我们在这里先介绍该消去法的原因是后面整数集合和仿射函数的操作会用到该消去法进行消元。

Fourier-Motzkin消去法的基本思想与求解线性方程组的高斯消去法类似。对于矩阵形式描述的不等式组

A _{m × n} x ≤ b （2-32）

其中， x 和 b 分别为 n 维和 m 维向量， A _{m × n} 的 m 个 n 维行向量分别记为 a ₁ , a ₂ ,…, a _m 。为了方便描述，可以将上述不等式组改写成等价形式

对于式（2-33）所示的不等式组和一系列非负系数 λ ₁ ,λ ₂ ,…,λ _m ，有

总成立。因此，可以通过选择合适的非负数 λ ₁ ,λ ₂ ,…,λ _m ，让式（2-34）中某个自变量 x _i （1≤ i ≤ n ）的系数为零，从而达到消去 x _i 的目的。需要注意的是，由于我们假设 λ _i ≥0，因此要想将 x _i 彻底消去的前提是不等式组（2-34）中所有 x _i 的系数的符号不完全相同。

我们以式（2-35）所示的一个简单的不等式组为例来展示它的基本方法。假设有

对于上述的不等式组，只需要令 λ ₁ = λ ₂ =1，即可将 x ₂ 消去，从而得到一个只包含 x ₁ 的不等式

5 x ₁ ≤13　　（2-36）

同理，只需要令 λ ₁ =6, λ ₂ =1，即可得到

6（ −x ₁ +2 x ₂ ）+（6 x ₁ − 2 x ₂ ）≤6（ − 4）+17　　（2-37）

从而得到 − 2 x ₂ ≤1。

在具体操作过程中，令 S 为不等式组（2-33）的所有约束的集合， C _i 为不等式组（2-33）中所有涉及 x _i 的约束的集合。集合 C _i 中的约束可以进一步分为两个子类：

（1）下界约束集合 L _i ：形如 l _j ≤ c ₁ x _i 的约束集合；

（2）上界约束集合 U _i ：形如 c ₂ x _i ≤ u _k 的约束集合。

因此有 C _i = U _i ∪L _i 。

Fourier-Motzkin消去法每次从 U _i 和 L _i 中分别选择以下约束 l∈L _i 和 u∈U _i ：

记 c ₁ 和 c ₂ 的最小公倍数为 v ，构造以下不等式：

其中， U _i 中元素个数记为| U _i |, L _i 中元素个数记为| L _i |，那么上述步骤至多会构造出| U _i |×| L _i |个新的不等式。记新构造的不包含 x _i 的约束集合为 C ^/ _i ，那么消去 x _i 后得到的不等式的集合为

式中虽然不包含变量 x _m ，但是却隐含了与 x _m 相关的所有约束。因此，如果式（2-40）是无解的，或者 S ^/ 是无解的，那么 S 一定也是无解的。

对于复杂的不等式组，可以借助一些现成的工具来求解。Racket ^[41] 和Matlab ^[32] 都提供了Fourier-Motzkin消去的工具包。此外，第3章将要介绍的Omega测试 ^[63] 也实现了一种改进的Fourier-Motzkin消去法。

从解析几何的角度来看，消去不等式组中某个变量 x _m （1≤ m ≤ n ）的过程，相当于计算多面体

在 n 维空间中的平面

上的投影 P _m （ S ）。我们以三维空间（ x,y,z ）上的多面体为例，消去变量 z ，相当于将整个三维多面体沿着 z 轴方向投影到由 x 轴和 y 轴构成的二维平面上。或者说，将三维多面体投影到 z =0所对应的二维平面上。

结合多面体的基本性质，即多面体上任意两点的连线一定位于多面体内部。 P _m （ S ）仍然是一个多面体，而且 P _m （ S ）的每个面都对应 S 的一个面，而 P _m （ S ）的每个顶点都是 S 的某些顶点在投影平面 S _m 的投影。如果 S 有 m 个面，那么 P _m （ S ）至多有 个面。

P _m （ S ）描述的是 x _m 在取满足 S 约束的任意合法值的前提下， n− 1的变量之间的约束。因此， P _m （ S ）存在可行解的充分必要条件是 S 至少存在一个可行解。从而可以推出，如果 P _m （ S ）不是多面体，那么 S 也一定不是多面体。

经过Fourier-Motzkin消去法处理过的不等式组中可能存在冗余的不等式，因为他们的约束不是最紧致的，将这些冗余的不等式组消去后得到的 仍然是一个合法的不等式组，或者说 还是一个多面体。

可以利用Fourier-Motzkin消去法计算 N 重循环的循环变量[ x ₁ ,x ₂ ,…,x _N ]的循环上界和循环下界，其过程如图2.4所示。