线性规划问题

我们要优化一个目标函数 \[ F(x_1,x_2,...x_p)=c_1x_1 + c_2x_2+...+c_px_p \] 也就是求它的最大值或者最小值。同时还有很多约束条件 \[ a_{i1}x_1+...+a_{ip}x_p \le b_i \\ a_{i1}x_1+...+a_{ip}x_p \ge b_i \\ a_{i1}x_1+...+a_{ip}x_p = b_i \] 以及非负的限制条件 \[ x_j \ge 0 \]

解集的定义

  • \(\textbf{x}=(x_1,x_2,...,x_p)\)​​​ 满足线性约束条件的是一个解
  • 如果 \(\textbf{x}\)​​ 还满足非负限制条件，那么是一个可行解
  • \[x^{*}\] 是最优解
  • \[X^*\] 是所有最优解的集合

转化问题

每个线性规划问题可以转化成最大值的线性规划问题：

最大化目标函数 \[ F(x_1,x_2,...x_p)=c_1x_1 + c_2x_2+...+c_px_p \] 约束条件： \[ \sum_{j=1}^{p} a_{ij} x_j \le b_i \\ x_j \ge 0 \] 解释：

  1. 如果是大于等于，可以两边同时乘一个 \(-1\)​
  2. 如果是求最小值，可以求 \(-F(\textbf{x})\) 的最大值
  3. 如果是相等，可以拆成一个大于等于一个小于等于

线性规划问题的范式

对于每一个小于等于的约束条件，我们可以给他加上一个变量，使得它变成一个相等的约束条件。 \[ \sum_{j=1}^{p} a_{ij} x_j + x_{p+i} = b_i \] 这里的 \(x_{p+i}\) 是对于的偏移变量

所以我们就得到了范式 Normalform

最大化目标函数： \[ F(x_1,x_2,...x_p)=c_1x_1 + c_2x_2+...+c_px_p \] 约束条件 \[ \sum_{j=1}^{p} a_{ij} x_j = b_i \\ x_j \ge 0 \] 我们也可以表示成我矩阵的写法

最大化目标函数 \[ F(\textbf{x})=\textbf{c}^T\textbf{x} \] 约束条件 \[ A\textbf{x}=\textbf{b} \\ \textbf{x} \ge 0 \]

kanonische Form

  • 在标准式的前提下，所有约束条件右边都是正数
  • 每行都有一个Basisvariable(当前行的系数是1，在所有其他行的系数是0)

解决线性规划Simplex算法

比如这个线性规划 \[ max:8x_1+12x_2 \\ 6x_1+8x_2\le 72 \\ 10x_1+20x_2 \le 140 \\ x_i \ge 0 \] 首先转换为范式，添加偏移变量 \[ 6x_1+8x_2+x_3 = 72 \\ 10x_1+20x_2+x_4=140 \] 然后设 \(z=8x_1+12x_2\) 变形一下 \[ z-8x_1-12x_2 = 0 \\ 6x_1+8x_2+x_3 = 72 \\ 10x_1+20x_2+x_4=140 \] 发现它已经是kanonischer Form

首先找到一个解Basislösung

\(z\) \(x_1\) \(x_2\) \(x_3\) \(x_4\) Res
\(z\) \(1\) \(-8\) \(-12\) \(0\)
\(x_3\) \(6\) \(8\) \(1\) \(72\)
\(x_4\) \(10\) \(20\) \(1\) \(140\)

然后在第1行找到一个负数最小的 \(x\)​ ，此时是 \(x_2\)

然后计算对于的 \(Res/系数\) 这里是 \[ x_3: 72/8=9 \\ x_4: 140/20=7 \] 找到结果最小的且是正数与之交换,这里是 \(x_2 \leftrightarrow x_4\)

\(z\) \(x_1\) \(x_2\) \(x_3\) \(x_4\) Res
\(z\) \(1\) \(-8\) \(-12\) \(0\)
\(x_3\) \(6\) \(8\) \(1\) \(72\)
\(x_2\)​ \(10\) \(20\) \(1\) \(140\)

然后通过行操作转换成 kanonischer Form

\(z\) \(x_1\) \(x_2\) \(x_3\) \(x_4\) Res
\(z\) \(1\) \(-2\) \(3/5\) \(84\)
\(x_3\) \(2\) \(1\) \(-2/5\) \(16\)
\(x_2\)​ \(1/2\) \(1\) \(1/20\) \(7\)

然后重复操作，这里交换 \(x_1 \leftrightarrow x_3\) \[ x_3: 16/2=8 \\ x_4: 7/0.5=14 \]

\(z\) \(x_1\) \(x_2\) \(x_3\) \(x_4\) Res
\(z\) \(1\) \(1\) \(1/5\) \(100\)
\(x_1\) \(1\) \(1/2\) \(-1/5\) \(8\)
\(x_2\)​ \(1\) \(-1/4\) \(3/20\) \(3\)

到这里就结束了

最优解是 \(\textbf{x}=(8,3),z=100\)

大M法找初始解

如线性规划问题 \[ max:2x_1-x_2 \\ -x_1+x_2 \ge 2 \\ x_1 + x_2 \le 4 \] 首先变成标准式子 \[ max:z=2x_1-x_2 \\ -x_1+x_2-x_3 = 2 \\ x_1+x_2 +x_4 = 4 \] 此时第2行的式子没有Basisvariable，然后我们再所有没有Basisvariable的行添加一个变量, 转换成下面的问题, 这里假设\(M\) 是一个很大的正数 \[ max: z=2x_1 -x_2 - Mw_1 \\ -x_1+x_2-x_3+w_1 = 2 \\ x_1 + x_2 +x_4 = 4 \] 此时有

\(x_1\) \(x_2\) \(x_3\) \(x_4\) \(w_1\) Res
\(z\) \(-2\) \(1\) \(M\) \(0\)
\(w_1\) \(-1\) \(1\) \(-1\) \(1\) \(2\)
\(x_4\)​ \(1\) \(1\) \(1\) \(4\)

但此时还不是kanonische Form, 还需要转换

\(x_1\) \(x_2\) \(x_3\) \(x_4\) \(w_1\) Res
\(z\) \(M-2\) \(1-M\) \(M\) \(-2M\)
\(w_1\) \(-1\) \(1\) \(-1\) \(1\) \(2\)
\(x_4\)​ \(1\) \(1\) \(1\) \(4\)

这样就是kanonische Form了，然后正常计算

交换 \(x_2 \leftrightarrow w_1\)

\(x_1\) \(x_2\) \(x_3\) \(x_4\) \(w_1\) Res
\(z\) \(-1\) \(1\) \(-1+M\) \(-2\)
\(x_2\) \(-1\) \(1\) \(-1\) \(1\) \(2\)
\(x_4\)​ \(2\) \(1\) \(1\) \(-1\) \(2\)

交换 \(x_1 \leftrightarrow x_4\)

\(x_1\) \(x_2\) \(x_3\) \(x_4\) \(w_1\) Res
\(z\) \(3/2\) \(1/2\) \(-3/2+M\) \(-1\)
\(x_2\) \(1\) \(-1/2\) \(1/2\) \(1/2\) \(3\)
\(x_1\)​ \(1\) \(1/2\) \(1/2\) \(-1/2\) \(1\)

于是就能解出来了 \(\textbf{x}=(1,3),z=-1\)

对偶性

逻辑

NOT

\[ Z_{\neg A}=1-A \]

OR

\[ \begin{array}{r} Z_{A \vee B} \geq A \\ Z_{A \vee B} \geq B \\ Z_{A \vee B} \leq A+B \end{array} \]

AND

\[ \begin{array}{r} Z_{A \wedge B} \leq A \\ Z_{A \wedge B} \leq B \\ Z_{A \wedge B} \geq A+B-1 \end{array} \]

推出

\[ \begin{array}{r} Z_{A \Rightarrow B} \geq 1-A \\ Z_{A \Rightarrow B} \geq B \\ Z_{A \Rightarrow B} \leq 1+2 B-A \end{array} \]