参考书目：

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

解法一：

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 \quad (L_1)\\ 2x _1 - 2x _2 = 2 \quad (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 \quad (L_1)\\ 2x _3 - 2x _4 = 0 \quad (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{pmatrix} 1&1&1&1&1\\ 1&1&-1&-1&2\\ 1&-1&1&-1&1\\ 1&-1&-1&1&1 \end{pmatrix}

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

(100−13/20−20−2000−2−210004−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}

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:

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

解：

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

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

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

\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 x+y\text{max} \ x+y

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

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

    将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, 无解

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