参考书目：
[1] 数学规划与组合优化. 浙江大学出版社, 2001. [Online]. Available: https://books.google.com.sg/books?id=ZmSSAAAACAAJ
[2] 组合优化与博弈论. 浙江大学出版社, 2015. [Online]. Available: https://books.google.com.sg/books?id=6w44swEACAAJ
[3] Lauritzen, Niels. Undergraduate Convexity: From Fourier And Motzkin To Kuhn And Tucker. Singapore: World Scientific Publishing Company, 2013. 👉 Download
Fourier–Motzkin Elimination , also known as FME method for eliminating variables from a system of liner inequalities.
Gauss Elimination
通常使用高斯消元法求解线性方程组 , 在有限个未知数的线性方程组中, 消去部分未知数后求解；
在线性代数中即是, 把矩阵转化为行阶梯形矩阵, 后求解未知数；
eg:
求解线性方程组
{ x 1 + x 2 + x 3 + x 4 = 1 ( L 1 ) x 1 + x 2 − x 3 − x 4 = 2 ( L 2 ) x 1 − x 2 + x 3 − x 4 = 1 ( L 3 ) x 1 − x 2 − x 3 + x 4 = 1 ( L 4 ) \begin{cases}
x _1 + x _2 + x _3 + x _4 = 1 \quad (L_1)\\
x _1 + x _2 - x _3 - x _4 = 2 \quad (L_2)\\
x _1 - x _2 + x _3 - x _4 = 1 \quad (L_3)\\
x _1 - x _2 - x _3 + x _4 = 1 \quad (L_4)
\end{cases}
⎩ ⎨ ⎧ x 1 + x 2 + x 3 + x 4 = 1 ( L 1 ) x 1 + x 2 − x 3 − x 4 = 2 ( L 2 ) x 1 − x 2 + x 3 − x 4 = 1 ( L 3 ) x 1 − x 2 − x 3 + x 4 = 1 ( L 4 )
解法一：
L 1 + L 2 L_1+L_2 L 1 + L 2 L 3 + L 4 L_3+L_4 L 3 + L 4
{ 2 x 1 + 2 x 2 = 3 ( L 1 ) 2 x 1 − 2 x 2 = 2 ( L 2 ) \begin{cases}
2x _1 + 2x _2 = 3 \quad (L_1)\\
2x _1 - 2x _2 = 2 \quad (L_2)
\end{cases}
{ 2 x 1 + 2 x 2 = 3 ( L 1 ) 2 x 1 − 2 x 2 = 2 ( L 2 )
再次 L 1 + L 2 L_1+L_2 L 1 + L 2 4 x 1 = 5 4 x _ 1=5 4 x 1 = 5 x 1 = 5 4 , x 2 = 1 4 x _ 1 = \frac {5} {4},x_2=\frac {1} {4} x 1 = 4 5 , x 2 = 4 1
同理, L 1 − L 2 L_1-L_2 L 1 − L 2 L 3 − L 4 L_3-L_4 L 3 − L 4
{ 2 x 3 + 2 x 4 = − 1 ( L 1 ) 2 x 3 − 2 x 4 = 0 ( L 2 ) \begin{cases}
2x _3 + 2x _4 = -1 \quad (L_1)\\
2x _3 - 2x _4 = 0 \quad (L_2)
\end{cases}
{ 2 x 3 + 2 x 4 = − 1 ( L 1 ) 2 x 3 − 2 x 4 = 0 ( L 2 )
可解的 x 3 = x 4 = − 1 4 x _ 3 = x _ 4 = - \frac {1} {4} x 3 = x 4 = − 4 1
综上, x 1 = 5 4 , x 2 = 1 4 , x 3 = x 4 = − 1 4 x _ 1 = \frac {5} {4},x_2=\frac {1} {4},x _ 3 = x _ 4 = - \frac {1} {4} x 1 = 4 5 , x 2 = 4 1 , x 3 = x 4 = − 4 1
解法二：
系数增广矩阵:
A ‾ = ( 1 1 1 1 1 1 1 − 1 − 1 2 1 − 1 1 − 1 1 1 − 1 − 1 1 1 ) \overline{A}=
\begin{pmatrix}
1&1&1&1&1\\
1&1&-1&-1&2\\
1&-1&1&-1&1\\
1&-1&-1&1&1
\end{pmatrix}
A = 1 1 1 1 1 1 − 1 − 1 1 − 1 1 − 1 1 − 1 − 1 1 1 2 1 1
矩阵变换化为行阶梯形矩阵, 得：
( 1 0 0 − 1 3 / 2 0 − 2 0 − 2 0 0 0 − 2 − 2 1 0 0 0 4 − 1 ) \begin{pmatrix}
1&0&0&-1&3/2\\
0&-2&0&-2&0\\
0&0&-2&-2&1\\
0&0&0&4&-1
\end{pmatrix}
1 0 0 0 0 − 2 0 0 0 0 − 2 0 − 1 − 2 − 2 4 3/2 0 1 − 1
then:
{ 4 x 4 = − 1 − 2 x 3 − 2 x 4 = 1 − 2 x 2 − 2 x 3 = 0 x 1 − x 4 = 3 / 2 \begin{cases}
4x_4=-1\\
-2x_3-2x_4=1\\
-2x_2-2x_3=0\\
x_1-x_4=3/2
\end{cases}
⎩ ⎨ ⎧ 4 x 4 = − 1 − 2 x 3 − 2 x 4 = 1 − 2 x 2 − 2 x 3 = 0 x 1 − x 4 = 3/2
由上到下求解方程, x 4 = x 3 = − 1 4 , x 2 = 1 4 , x 1 = 5 4 x _ 4 = x _ 3 = - \frac {1} {4},x_2=\frac {1} {4},x _ 1 = \frac {5} {4} x 4 = x 3 = − 4 1 , x 2 = 4 1 , x 1 = 4 5
Gauss and Ceres
Gauss在使用最小二乘法计算小行星帕拉斯(Pallas)的轨道时, 遇到了求解线性方程组的问题;
👉故事阅读
👉概述 ：
Fourier–Motzkin Elimination
求解简单线性不等式约束下的最优化目标
不等式可用来确认等式, 例如 x ≤ 1 , x ≥ 1 ⇒ x = 1 x \leq 1,x \geq 1 \Rightarrow x=1 x ≤ 1 , x ≥ 1 ⇒ x = 1
更高效的求解线性不等式的方式
Proposition 1：
α 1 , α 2 , α 3 , . . . , α r , β 1 , β 2 , β 3 , . . . , β s ∈ R \alpha_1,\alpha_2,\alpha_3,...,\alpha_r ,\ \ \beta_1,\beta_2,\beta_3,...,\beta_s \in \R α 1 , α 2 , α 3 , ... , α r , β 1 , β 2 , β 3 , ... , β s ∈ R
max { α 1 , α 2 , α 3 , . . . , α r } ≤ min { β 1 , β 2 , β 3 , . . . , β s } \text{max} \{\alpha_1,\alpha_2,\alpha_3,...,\alpha_r \} \leq \text{min} \{\beta_1,\beta_2,\beta_3,...,\beta _ s \} max { α 1 , α 2 , α 3 , ... , α r } ≤ min { β 1 , β 2 , β 3 , ... , β s }
当且仅当任意 i , j i,j i , j 1 ≤ i ≤ r , 1 ≤ j ≤ s 1\leq i \leq r,1 \leq j \leq s 1 ≤ i ≤ r , 1 ≤ j ≤ s
Proof :
如果max { α 1 , α 2 , α 3 , . . . , α r } ≤ min { β 1 , β 2 , β 3 , . . . , β s } \text{max} \{\alpha_1,\alpha_2,\alpha_3,...,\alpha_r \} \leq \text{min} \{\beta_1,\beta_2,\beta_3,...,\beta _ s \} max { α 1 , α 2 , α 3 , ... , α r } ≤ min { β 1 , β 2 , β 3 , ... , β s }
则对于任意1 ≤ i ≤ r , 1 ≤ j ≤ s 1\leq i \leq r,1 \leq j \leq s 1 ≤ i ≤ r , 1 ≤ j ≤ s
α i ≤ max { α 1 , α 2 , α 3 , . . . , α r } ≤ min { β 1 , β 2 , β 3 , . . . , β s } ≤ β j \alpha_i \leq \text{max} \{\alpha_1,\alpha_2,\alpha_3,...,\alpha_r \} \leq \text{min} \{\beta_1,\beta_2,\beta_3,...,\beta _ s \} \leq \beta_j
α i ≤ max { α 1 , α 2 , α 3 , ... , α r } ≤ min { β 1 , β 2 , β 3 , ... , β s } ≤ β j
Then:
对于同一不等式, 不等式左侧实值应小于等于右侧实值, 在此基础上不等式成立, 且可进一步求解；
当a ≤ x , x ≤ b a \leq x , x \leq b a ≤ x , x ≤ b a ≤ b a \leq b a ≤ b
eg 1:
max x + y s.t. x + 2 y ≤ 3 2 x + y ≤ 3 x ≥ 0 y ≥ 0 \begin{align}
\text{max} \quad & x+y\\
\text{s.t.} \quad & x+2y\leq3\\
& 2x+y \leq 3\\
& x \geq 0\\
& y \geq0
\end{align}
max s.t. x + y x + 2 y ≤ 3 2 x + y ≤ 3 x ≥ 0 y ≥ 0
解：
令x + y = z x+y=z x + y = z x = z − y x=z-y x = z − y
max z s.t. z + y ≤ 3 2 z − y ≤ 3 z − y ≥ 0 y ≥ 0 \begin{align}
\text{max} \quad & z\\
\text{s.t.} \quad & z+y \leq 3\\
& 2z-y \leq 3\\
& z-y \geq 0\\
& y \geq 0
\end{align}
max s.t. z z + y ≤ 3 2 z − y ≤ 3 z − y ≥ 0 y ≥ 0
将 y y y
{ y ≤ 3 − z 2 z − 3 ≤ y y ≤ z 0 ≤ y \begin{cases}
y\leq3-z\\
2z-3 \leq y\\
y \leq z\\
0\leq y
\end{cases}
⎩ ⎨ ⎧ y ≤ 3 − z 2 z − 3 ≤ y y ≤ z 0 ≤ y
then: 不等式左侧数值需要小于右侧数值, max { 0 , 2 z − 3 } ≤ min { 3 − z , z } \text{max}\ \{0,2z-3\} \leq \text{min}\ \{3-z,z\} max { 0 , 2 z − 3 } ≤ min { 3 − z , z }
{ 0 ≤ 3 − z 2 z − 3 ≤ 3 − z 2 z − 3 ≤ z 0 ≤ z \begin{cases}
0\leq3-z\\
2z-3 \leq 3-z\\
2z-3 \leq z\\
0\leq z
\end{cases}
⎩ ⎨ ⎧ 0 ≤ 3 − z 2 z − 3 ≤ 3 − z 2 z − 3 ≤ z 0 ≤ z
解的：0 ≤ z ≤ 2 0\leq z \leq 2 0 ≤ z ≤ 2 max z = 2 \text{max}\ z=2 max z = 2
eg 2:
max x + y s.t. 8 x + 3 y ≤ 24 5 x + 7 y ≤ 35 − x + y ≤ 4 y ≥ 2 \begin{align}
\text{max} \quad & x+y\\
\text{s.t.} \quad & 8x+3y\leq 24\\
& 5x+7y \leq 35\\
& -x+y \leq 4\\
& y \geq 2
\end{align}
max s.t. x + y 8 x + 3 y ≤ 24 5 x + 7 y ≤ 35 − x + y ≤ 4 y ≥ 2
求 max x + y \text{max} \ x+y max x + y
令x + y = z x+y=z x + y = z x = z − y x=z-y x = z − y
max z s.t. 8 z − 5 y ≤ 24 5 z + 2 y ≤ 35 − z + y ≤ 4 y ≥ − 2 \begin{align}
\text{max} \quad & z\\
\text{s.t.} \quad & 8z-5y \leq 24\\
& 5z+2y \leq 35\\
& -z+y \leq 4\\
& y \geq -2
\end{align}
max s.t. z 8 z − 5 y ≤ 24 5 z + 2 y ≤ 35 − z + y ≤ 4 y ≥ − 2
将y y y
{ 8 / 5 z − 24 / 5 ≤ y y ≤ 35 / 2 − 5 / 2 z y ≤ 2 + z / 2 − 2 ≤ y \begin{cases}
8/5z-24/5 \leq y\\
y \leq 35/2-5/2z\\
y \leq 2+z/2\\
-2\leq y
\end{cases}
⎩ ⎨ ⎧ 8/5 z − 24/5 ≤ y y ≤ 35/2 − 5/2 z y ≤ 2 + z /2 − 2 ≤ y
then: max { − 2 , 8 / 5 z − 24 / 5 } ≤ min { 35 / 2 − 5 / 2 z , 2 + z / 2 } \text{max}\ \{-2,8/5z-24/5 \} \leq \text{min}\ \{35/2-5/2z,2+z/2\} max { − 2 , 8/5 z − 24/5 } ≤ min { 35/2 − 5/2 z , 2 + z /2 }
{ − 2 ≤ 35 / 2 − 5 / 2 z 8 / 5 z − 24 / 5 ≤ 35 / 2 − 5 / 2 z 8 / 5 z − 24 / 5 ≤ 2 + z / 2 − 2 ≤ 2 + z / 2 \begin{cases}
-2 \leq 35/2-5/2z\\
8/5z-24/5 \leq 35/2-5/2z\\
8/5z-24/5 \leq 2+z/2\\
-2 \leq 2+z/2
\end{cases}
⎩ ⎨ ⎧ − 2 ≤ 35/2 − 5/2 z 8/5 z − 24/5 ≤ 35/2 − 5/2 z 8/5 z − 24/5 ≤ 2 + z /2 − 2 ≤ 2 + z /2
解的z ≤ 223 41 z \leq \frac{223}{41} z ≤ 41 223 max z = 223 41 \text{max} \ z = \frac{223}{41} max z = 41 223
第三个约束条件改为 − x + y ≤ − 7 -x+y \leq -7 − x + y ≤ − 7
{ 8 / 5 z − 24 / 5 ≤ y y ≤ 35 / 2 − 5 / 2 z y ≤ − 7 / 2 + z / 2 − 2 ≤ y \begin{cases}
8/5z-24/5 \leq y\\
y \leq 35/2-5/2z\\
y \leq -7/2+z/2\\
-2\leq y
\end{cases}
⎩ ⎨ ⎧ 8/5 z − 24/5 ≤ y y ≤ 35/2 − 5/2 z y ≤ − 7/2 + z /2 − 2 ≤ y
then: max { − 2 , 8 / 5 z − 24 / 5 } ≤ min { 35 / 2 − 5 / 2 z , − 7 / 2 + z / 2 } \text{max}\ \{-2,8/5z-24/5 \} \leq \text{min}\ \{35/2-5/2z,-7/2+z/2\} max { − 2 , 8/5 z − 24/5 } ≤ min { 35/2 − 5/2 z , − 7/2 + z /2 }
{ − 2 ≤ 35 / 2 − 5 / 2 z 8 / 5 z − 24 / 5 ≤ 35 / 2 − 5 / 2 z 8 / 5 z − 24 / 5 ≤ − 7 / 2 + z / 2 − 2 ≤ − 7 / 2 + z / 2 \begin{cases}
-2 \leq 35/2-5/2z\\
8/5z-24/5 \leq 35/2-5/2z\\
8/5z-24/5 \leq -7/2+z/2\\
-2 \leq -7/2+z/2
\end{cases}
⎩ ⎨ ⎧ − 2 ≤ 35/2 − 5/2 z 8/5 z − 24/5 ≤ 35/2 − 5/2 z 8/5 z − 24/5 ≤ − 7/2 + z /2 − 2 ≤ − 7/2 + z /2
得：3 ≤ z , z ≤ 13 / 11 3 \leq z,z\leq 13/11 3 ≤ z , z ≤ 13/11
推导及证明有误之处欢迎批评指正~
