线性规划与对偶理论

线性不等式：

$$Ax\le B$$

标准形式：

最大化 $c^Tx$，满足 $Ax\le b，x\ge 0$

满足条件的是可行解，我们要找最优解

例子：

AB产品，有利润

3个约束：时间、材料、运输能力

建模为线性规划：

方法：单纯形法

1. 引入 $x_3,x_4,x_5$，把不等式变成等式

   

   因为等式比较好处理

2. 给所有变量选定一个初始值

   此时 $z$ 不是最大值，而我们的目的是尽可能让 $z$ 变大

   观察 $z=3x_1+5x_2$

   所以我们尽可能让 $x_2$ 增大，同时让 $x_1$ 保持不变

   由我们的约束可以得到 $x_2\le 5$

   我们让 $x_2=5$，那样子我们可以得到对应的 $x_1,x_3,x_4,x_5,z$

3. 分析当前 $z=25$ 是不是最大值

   发现目前 $x_1=x_3=0$，我们可以把原来利润写成关于二者的函数：

   最大化：$z=25+\dfrac{1}{2}x_1-\dfrac 5 2 x_3$

   所以我们又要去找 $x_1$ 最大（同时固定 $x_3=0$ 不变）

   这个时候可以得到 $x_1\le 2$

   我们令 $x_1=2$，那么 $z=26$

4. 我们继续上面的过程

   发现 $x_3=x_4=0$，因此我们用 $x_3,x_4$ 来表示 $z$，就得到：$z=26-x_3-x_4$

   又 $x_3,x_4\ge 0$，说明我们目前已经取到了最大值，不可能再大了

背后本质：

约束条件给出的是一个凸多边形，所以我们的最大值一定在顶点处取到

单纯形法就是在找各个顶点

对偶理论

比如：

强对偶定理：

如果原始问题存在最优解，那么其对偶问题也存在最优解，并且其最优值相等

即：

$$\max\{c^Tx:Ax\le b,x\ge 0\}=\min\{b^Ty:A^Ty\ge c,y\ge 0\}$$

一个例子（博弈论）：

我们这个博弈的受益可以拿一个矩阵来描述

玩家A的混合策略是一个概率向量

这里的 $x_i$ 是概率分布，就以随机的概率来选择策略（$x_i$ 是代表选第 $i$ 种策略的概率）

同样玩家B

玩家一要最大化自己的最小收益，即寻找最小：

$$\max_{x\in \Delta _m}\min_{y\in \Delta _n} x^TAy$$

用 $\Delta k$ 表示 $k$ 维概率分布集合

类似玩家二有最小化自己的最大损失，即：

$$\min_{y\in \Delta _n}\max_{x\in \Delta _m} x^TAy$$

这里引入Minimax定理：

推论：双人零和博弈，混合策略纳什均衡总是存在

我们发现两者恰好互为对偶的线性规划问题，由对偶定理即得证