线性规划

线性规划问题

我们要优化一个目标函数

$$F(x_1,x_2,...x_p)=c_1{x}_1+c_2{x}_2+...+c_p{x}_p$$

也就是求它的最大值或者最小值。同时还有很多约束条件

$$\begin{gathered} 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 \end{gathered}$$

以及非负的限制条件

$$x_j\ge 0$$

解集的定义

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

转化问题

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

最大化目标函数

$$F(x_1,x_2,...x_p)=c_1{x}_1+c_2{x}_2+...+c_p{x}_p$$

约束条件：

$$\begin{gathered} \sum _{j=1}^p{a}_{ij}{x}_j\le b_i \\ {x}_j\ge 0 \end{gathered}$$

解释：

1. 如果是大于等于，可以两边同时乘一个 $-1$​
2. 如果是求最小值，可以求 $-F(\mathbf{\text{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_1{x}_1+c_2{x}_2+...+c_p{x}_p$$

约束条件

$$\begin{gathered} \sum _{j=1}^p{a}_{ij}{x}_j=b_i \\ {x}_j\ge 0 \end{gathered}$$

我们也可以表示成我矩阵的写法

最大化目标函数

$$F(\mathbf{\text{x}})={\mathbf{\text{c}}}^T\mathbf{\text{x}}$$

约束条件

$$\begin{gathered} A\mathbf{\text{x}}=\mathbf{\text{b}} \\ \mathbf{\text{x}}\ge 0 \end{gathered}$$

kanonische Form

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

解决线性规划Simplex算法

比如这个线性规划

$$\begin{gathered} max:8x_1+12x_2 \\ 6x_1+8x_2\le 72 \\ 10x_1+20x_2\le 140 \\ {x}_i\ge 0 \end{gathered}$$

首先转换为范式，添加偏移变量

$$\begin{gathered} 6x_1+8x_2+x_3=72 \\ 10x_1+20x_2+x_4=140 \end{gathered}$$

然后设 $z=8x_1+12x_2$ 变形一下

$$\begin{gathered} z-8x_1-12x_2=0 \\ 6x_1+8x_2+x_3=72 \\ 10x_1+20x_2+x_4=140 \end{gathered}$$

发现它已经是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/\mathrm{系}\mathrm{数}$ 这里是

$$\begin{gathered} x_3:72/8=9 \\ {x}_4:140/20=7 \end{gathered}$$

找到结果最小的且是正数与之交换,这里是 $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$

$$\begin{gathered} x_3:16/2=8 \\ {x}_4:7/0.5=14 \end{gathered}$$

	$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$

到这里就结束了

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

大M法找初始解

如线性规划问题

$$\begin{gathered} max:2x_1-x_2 \\ -x_1+x_2\ge 2 \\ {x}_1+x_2\le 4 \end{gathered}$$

首先变成标准式子

$$\begin{gathered} max:z=2x_1-x_2 \\ -x_1+x_2-x_3=2 \\ {x}_1+x_2+x_4=4 \end{gathered}$$

此时第2行的式子没有Basisvariable，然后我们再所有没有Basisvariable的行添加一个变量, 转换成下面的问题, 这里假设$M$ 是一个很大的正数

$$\begin{gathered} max:z=2x_1-x_2-M{w}_1 \\ -x_1+x_2-x_3+w_1=2 \\ {x}_1+x_2+x_4=4 \end{gathered}$$

此时有

	$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$

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

对偶性

逻辑

NOT

$$Z_{\mathrm{\neg }A}=1-A$$

OR

$$\begin{array}{r}{Z}_{A\vee B}\ge A\\ Z_{A\vee B}\ge B\\ Z_{A\vee B}\le A+B\end{array}$$

AND

$$\begin{array}{r}{Z}_{A\wedge B}\le A\\ Z_{A\wedge B}\le B\\ Z_{A\wedge B}\ge A+B-1\end{array}$$

推出

$$\begin{array}{r}{Z}_{A\Rightarrow B}\ge 1-A\\ Z_{A\Rightarrow B}\ge B\\ Z_{A\Rightarrow B}\le 1+2B-A\end{array}$$