参考书目：

[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:

求解线性方程组

{x1+x2+x3+x4=1 (L1)x1+x2−x3−x4=2 (L2)x1−x2+x3−x4=1 (L3)x1−x2−x3+x4=1 (L4)\begin{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) \end{cases}

解法一：

L1+L2L_1+L_2 ,L3+L4L_3+L_4 得:

{2x1+2x2=3 (L1)2x1−2x2=2 (L2)\begin{cases} 2x _1 + 2x _2 = 3 \ (L_1)\\ 2x _1 - 2x _2 = 2 \ (L_2) \end{cases}

再次L1+L2L_1+L_2 得4x1=54 x _ 1=5 , 可解的x1=54,x2=14x _ 1 = \frac {5} {4},x_2=\frac {1} {4}

同理,L1−L2L_1-L_2 ,L3−L4L_3-L_4 得:

{2x3+2x4=−1 (L1)2x3−2x4=0 (L2)\begin{cases} 2x _3 + 2x _4 = -1 \ (L_1)\\ 2x _3 - 2x _4 = 0 \ (L_2) \end{cases}

可解的x3=x4=−14x _ 3 = x _ 4 = - \frac {1} {4}

综上,x1=54,x2=14,x3=x4=−14x _ 1 = \frac {5} {4},x_2=\frac {1} {4},x _ 3 = x _ 4 = - \frac {1} {4}

解法二：

系数增广矩阵:

A‾={1111111−1−121−11−111−1−111}\overline{A}= \begin{Bmatrix} 1&1&1&1&1\\ 1&1&-1&-1&2\\ 1&-1&1&-1&1\\ 1&-1&-1&1&1 \end{Bmatrix}

矩阵变换化为行阶梯形矩阵, 得：

{100−13/20−20−2000−2−210004−1}\begin{Bmatrix} 1&0&0&-1&3/2\\ 0&-2&0&-2&0\\ 0&0&-2&-2&1\\ 0&0&0&4&-1 \end{Bmatrix}

then:

{4x4=−1−2x3−2x4=1−2x2−2x3=0x1−x4=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}

由上到下求解方程,x4=x3=−14,x2=14,x1=54x _ 4 = x _ 3 = - \frac {1} {4},x_2=\frac {1} {4},x _ 1 = \frac {5} {4}

Gauss and Ceres

Gauss 在使用最小二乘法计算小行星帕拉斯 (Pallas) 的轨道时, 遇到了求解线性方程组的问题;

👉故事阅读

👉概述：

Fourier–Motzkin Elimination

  • 求解简单线性不等式约束下的最优化目标
  • 不等式可用来确认等式, 例如x≤1,x≥1⇒x=1x \leq 1,x \geq 1 \Rightarrow 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,

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 \},

当且仅当任意i,ji,j 满足1≤i≤r,1≤j≤s1\leq i \leq r,1 \leq j \leq s, 有 $\alpha _ i \leq \beta_j $；

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 \} 成立,

则对于任意1≤i≤r,1≤j≤s1\leq i \leq r,1 \leq j \leq 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

Then:

  • 对于同一不等式, 不等式左侧实值应小于等于右侧实值, 在此基础上不等式成立, 且可进一步求解；

    当a≤x,x≤ba \leq x , x \leq b, 当且仅当a≤ba \leq b 时成立；

eg 1:

max x+ys.t. x+2y≤32x+y≤3x≥0y≥0\text{max} \ x+y\\ \text{s.t.} \ x+2y\leq3\\ 2x+y \leq 3\\ x \geq 0\\ y \geq0

解：

令x+y=zx+y=z, 则x=z−yx=z-y
带入原规划问题,

max zs.t. z+y≤32z−y≤3z−y≥0y≥0\text{max} \ z\\ \text{s.t.}\ z+y \leq 3\\ 2z-y \leq 3\\ z-y \geq 0\\ y \geq 0

将yy 视作不等式组的未知数:

{y≤3−z2z−3≤yy≤z0≤y\begin{cases} y\leq3-z\\ 2z-3 \leq y\\ y \leq z\\ 0\leq y \end{cases}

then: 不等式左侧数值需要小于右侧数值,max {0,2z−3}≤min {3−z,z}\text{max}\ \{0,2z-3\} \leq \text{min}\ \{3-z,z\}

{0≤3−z2z−3≤3−z2z−3≤z0≤z\begin{cases} 0\leq3-z\\ 2z-3 \leq 3-z\\ 2z-3 \leq z\\ 0\leq z \end{cases}

解的：0≤z≤20\leq z \leq 2, 则max z=2\text{max}\ z=2

eg 2:

max x+ys.t. 8x+3y≤245x+7y≤35−x+y≤4y≥2\text{max} \ x+y\\ \text{s.t.} \ 8x+3y\leq 24\\ 5x+7y \leq 35\\ -x+y \leq 4\\ y \geq 2

  • 求max x+y\text{max} \ x+y

    令x+y=zx+y=z, 则x=z−yx=z-y
    带入原规划问题

    max zs.t. 8z−5y≤245z+2y≤35−z+y≤4y≥−2\text{max} \ z\\ \text{s.t.} \ 8z-5y \leq 24\\ 5z+2y \leq 35\\ -z+y \leq 4\\ y \geq -2

    将yy 视作不等式组的未知数:

    {8/5z−24/5≤yy≤35/2−5/2zy≤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}

    then:max {−2,8/5z−24/5}≤min {35/2−5/2z,2+z/2}\text{max}\ \{-2,8/5z-24/5 \} \leq \text{min}\ \{35/2-5/2z,2+z/2\}

    {−2≤35/2−5/2z8/5z−24/5≤35/2−5/2z8/5z−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}

    解的z≤22341z \leq \frac{223}{41}, 则max z=22341\text{max} \ z = \frac{223}{41}

  • 第三个约束条件改为−x+y≤−7-x+y \leq -7 , 是否有解

{8/5z−24/5≤yy≤35/2−5/2zy≤−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}

​ then:max {−2,8/5z−24/5}≤min {35/2−5/2z,−7/2+z/2}\text{max}\ \{-2,8/5z-24/5 \} \leq \text{min}\ \{35/2-5/2z,-7/2+z/2\}

{−2≤35/2−5/2z8/5z−24/5≤35/2−5/2z8/5z−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}

​ 得：3≤z,z≤13/113 \leq z,z\leq 13/11, 无解

推导及证明有误之处欢迎批评指正~