运筹学 | 基础向 | 线性规划の对偶理论

这篇博客是 b 站王老师运筹学应试向网课的随堂笔记，对应讲座 P5、P6、P34。
- 强烈安利王老师的网课 ✔️ 比课本好理解，节奏足够快，适合课余时间自学。
- 本人以前无运筹学基础，直接听应试向网课，感觉还可以。各位自学选手若感觉应试向太快，建议看王老师的教学向视频。
本博客
- 首先，介绍了对偶问题的概念、感性理解、写出对偶问题的方法。
- 然后，介绍了对偶问题的性质（相遇的最优解、互补松弛性、…）。
- 最后，简单介绍了对偶单纯形法，思想与单纯形法恰好相反：先保证最优性，然后迭代逼近可行性。
线性规划的对偶理论，真的很优美！❤️

1 对偶问题：是什么？
- 1.1 从例子开始：生产问题 & 资源收购问题
- 1.2 对偶问题的一般形式
2 对偶问题：性质、对偶理论
3 对偶单纯形法

1 对偶问题：是什么？

1.1 从例子开始：生产问题 & 资源收购问题

回顾：生产问题的定义

公司要生产 n 种产品，产品生产量用 \(X\)（n 维列向量）表示，第 i 种产品的产量记为 \(x_i\)。产品生产量是决策变量。要保证 \(X\ge0\)，即产品生产量非负。
公司一共有 m 种资源，资源限制用 \(b\)（m 维列向量）表示，第 j 种资源的限制为 \(b_j\)。
每生产一个产品 i、耗费资源 j 的数量记为 \(A_{ji}\)，可以将其写为一个 m 行 n 列的矩阵 \(A\)。
将资源限制表示为 \(AX\le b\) 的形式，每一行表示第 j 种资源的限制条件，每一列表示第 i 种产品耗费的各项资源。
每生产一个产品 i，可以获得 \(c_i\) 的收益，将其记做 \(C\)（n 维行向量）。公司希望最大化收益，即目标函数为 \(\max z=CX\)。

即：

\[\max z=CX \\
\left\{ \begin{array}&
AX\le b \\
X\ge0
\end{array}\right.
\tag{1}
\]

定义它的对偶问题：资源收购问题

假设我们要收购该公司的所有资源，用这些资源自己进行生产。
- 我们的目标：以最小代价收购所有资源。
- 对方愿意出让资源的条件：我们付的钱 ≥ 原有盈利。
决策变量：对一个第 j 种资源，我们愿意付出多少钱来买，这个钱数记为 \(Y_j\)，向量形式记为 \(Y\)（m 维列向量）。同样，有 \(Y\ge0\)，钱数 ≥ 0，（虽然月出感觉，对方倒赔钱把资源出手给我们，也不是不可能）。
目标函数：希望最小化收购总付出钱数。
- 我们要收购所有资源，第 j 种资源的总量为 \(b_j\)（生产问题的资源限制），我们为一个 j 资源的付钱为 \(Y_j\)，所以目标函数是 \(b\) 和 \(Y\) 两个列向量的内积，\(\min z=b^TY\)。
约束条件：我们付的钱 ≥ 原有盈利。
- 考虑公司自己生产第 i 种产品，那么对于每一个产品 i，它要付出 \(A_{ji}\) 个资源 j（ j = 1, 2, ..., m ），最后获得 \(c_i\) 的收益。现在，我们用 \(A_{ji}Y_j\) 的钱把 \(A_{ji}\) 个资源 j 买了（ j = 1, 2, ..., m ），公司希望我们给的这笔钱 ≥ 原来的收益 \(c_i\)，即 \(\sum_jA_{ji}Y_j\ge c_i\)。
- 对每一个产品，公司都有这样的要求（有点贪婪哈哈哈 ????），因此对 n 个产品列出 n 个不等式，矩阵形式为 \(A^TY\ge C^T\)（因为 \(C\) 是行向量）。

总结来说，

\[\min z=b^TY \\
\left\{ \begin{array}&
A^TY\ge C^T \\
Y\ge0
\end{array}\right.
\tag{2}
\]

资源收购问题，是生产问题的 对偶问题。

观察对偶问题的形式

可以观察到以下结论：

目标函数：原问题 max → 对偶问题 min。
约束条件：原问题 ≤ → 对偶问题 ≥。
目标函数系数（C）& 约束条件（b）：
- 原问题的目标函数系数（C）→ 对偶问题的约束条件。
- 原问题的约束条件（b）→ 对偶问题的目标函数系数。
决策变量个数 & 约束条件行数：
- 原问题的决策变量个数（n 种产品）→ 对偶问题的约束条件行数。
- 原问题的约束条件行数（m 种资源）→ 对偶问题的决策变量个数。
约束条件的系数矩阵：原问题 A → 对偶问题 A 的转置。

每个线性规划都对应着唯一的对偶问题，只不过，生产 & 资源收购这一对问题，它们物理意义比较明确。

想知道对偶问题的一般形式，接着读下去吧！

1.2 对偶问题的一般形式

线性规划的对称形式（注意与标准形式区分）

线性规划的对称形式，如前面的式 (1) 所示，搬运过来。

\[\max z=CX \\
\left\{ \begin{array}&
AX\le b \\
X\ge0
\end{array}\right.
\tag{1}
\]

满足以下条件：

目标函数：max 。
决策变量：全是 ≥。
约束条件：全是 ≤ 。

如果线性规划是对称形式，则可直接根据前面观察的规律，写出对偶问题。

并不是所有线性规划，都是对称形式。举个很不对称的例子：

这个例子里面，① 约束条件有 = 有 ≥，② 决策变量有 ≤ 有无约束。

（注意，这是自然的情况，决策变量全 ≥ 0 是标准形式。同样，资源限制 b 也没有要求是 ≥ 0 的形式。）
我们可以将其转化为对称形式，然后转对偶问题，再化简对偶问题，详见王老师应试向网课 P4 15:07 开始。
后面的对偶问题性质，都在对称形式下讨论，反正所有问题都能转化成对称形式。

对偶问题的一般形式

根据上面的例子，可以总结出一般规律：

（回顾：标准形式，具体请见前一篇博客）

\[\max z=CX \\
\left\{ \begin{array}&
AX = b \\
X\ge0
\end{array}\right.
\tag{1}
\]

满足：

目标函数 max：取相反数。
约束不等式 → 等式：加减非负变量（加松弛，减剩余）。
等式约束的右端项非负：取相反数。
决策变量非负：决策变量如果没有约束，将其转化为两个非负变量的差。

2 对偶问题：性质、对偶理论

方便起见，描述对偶问题性质时， ① 数学推导全部采用对称形式，② 采用生产问题 & 资源收购问题的直观解释。

2.1 对偶的对偶是原问题

证明：

首先写出
- 原问题：
- \[\max z=CX \\
  \left\{ \begin{array}&
  AX\le b \\
  X\ge0
  \end{array}\right.
  \tag{1}
  \]
- 对偶问题：
- \[\min z=b^TX \\
  \left\{ \begin{array}&
  A^TY\ge C^T \\
  Y\ge0
  \end{array}\right.
  \tag{2}
  \]
把对偶问题转为对称形式：
- min → max：目标函数取相反数。
- 约束条件 ≥ → ≤：约束条件取相反数。
- \[\max z=-b^TY \\
  \left\{ \begin{array}&
  (-A^T)Y\le -C^T \\
  Y\ge0
  \end{array}\right.
  \tag{2'}
  \]
然后，再转对偶问题：
- min → max，≤ → ≥，资源限制 / 收益位置互换。
- \[\min z=-(C^T)^TX \\
  \left\{ \begin{array}&
  (-A^T)^TX\ge(-b^T)^T \\
  X\ge0
  \end{array}\right.
  \tag{1'}
  \]
目标函数、约束条件取相反数后，可以发现，对偶的对偶是原问题。

2.2 弱对偶性：生产总收益 ≤ 直接躺平卖资源的收益

（不然干嘛要卖资源呢哈哈哈哈）

严格的写：

若 X 是原问题可行解，Y 是对偶问题可行解，则恒有 \(CX\le b^TY\)。

证明：

我们已知限制条件：\(AX\le b\)，\(A^TY\ge C^T\)。
把 \(AX\le b\) 带进要证明的 \(CX\le Y^Tb\) 里，发现 \(b^TY=Y^Tb\ge Y^TAX=(A^TY)^TX\ge CX\)，得证。

可以得到一些推论：

如果原问题有无界解（生产收益可以无穷大），则对偶问题无可行解（人家收益无穷大，干嘛用有限的钱把资源卖给你 ????）。
同样，对偶问题无界解 \(\Longrightarrow\) 原问题无可行解。
还有一种表述是，原问题有解对偶问题无界，则原问题有无界解。
但是反之不亦然，即，原问题无解推不出对偶问题无界解，对偶问题可能无解 / 无界解。

2.3 相遇的最优解：最大生产收益 = 最小买资源付出

（直观上也好理解，此时对公司来说，怎么选都无所谓）

严格的写：

若 X 是原问题可行解，Y 是对偶问题可行解，且 \(CX=b^TY\)，则 \(X\)、\(Y\) 分别是原问题、对偶问题最优解。

证明：

很好理解！设 \(X^*\)、\(Y^*\) 是原问题、对偶问题最优解，则 \(CX^*\) 是 max，\(b^TY^*\) 是 min，所以有 \(b^TY^*\le b^TY=CX\le CX^*\)，可以推出 \(b^TY^*\le CX^*\)。
然而，根据 2.2 弱对偶性，生产收益 ≤ 卖资源收益，有 \(b^TY^*\ge CX^*\)。
所以，\(b^TY^*=CX^*\)，即 \(b^TY^*=b^TY=CX=CX^*\)，所以 X Y 是最优解。

2.4 强对偶性 / 对偶定理：原问题有最优解 \(\Longrightarrow\) 对偶有最优解，且最优解相遇

严格的写：

若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。

证明：

要用到单纯形法的矩阵描述，月出讲不清楚 ????，建议看 P4 24:37 - 32:02。
结论：在原问题的最终单纯形表，能找到对偶问题的解。

2.5 互补松弛性：双最优解时，约束条件能否严格取等

严格的写：

（双最优解情况下）原问题中某一约束条件对应的【对偶变量】≠ 0 \(\Longrightarrow\) 该约束条件取严格等式；
若约束条件取严格不等式，则其对应的对偶变量一定 = 0。
对偶变量：生产 & 资源收购问题中，生产问题的约束条件代表一类资源的限制，它的对偶变量是资源收购问题中买该资源的价格。

简单的说：

约束条件的对偶变量和松弛变量，总有一个要 = 0。（两个都 = 0 也可以）

证明：

双最优解时，有 \(CX=b^TY\)，写成 \(CX=Y^Tb\) 的形式，然后有 \(Y^Tb=Y^TAX=CX\)，所以有 \(Y^T(AX-b)=0,~X^T(A^TY-C^T)=0\)。
\(Y^T(AX-b)=0\)（内积 = 0）说明：① AX-b（松弛变量）每一个元素与 ② Y（对偶变量）每一个元素，总有一个 = 0，得证。
同理，\(X^T(A^TY-C^T)=0\) 说明，对偶问题约束条件的 ① 松弛变量与 ② 在原问题对应的决策变量，总有一个 = 0。（合理，因为对偶的对偶是原问题）。

非常重要的应用：

得知原问题的解；
把解带入原问题的约束条件，得知哪几个 ≤ 约束条件取 <（而非 = ）；
【互补松弛性】这些约束条件在对偶问题中的对偶变量强制 = 0；
这些对偶变量不是基变量，其余（可能）是基变量；
如果能得知基变量，即可直接 \(A_{Base}x_{Base}=b\) 求解。

2.6 影子价格：对偶问题的最优解 = 资源的边际价格

起因：

比如，我们要做饺子馅 ???? 肉菜配比 1:1，一斤饺子馅能卖 10 元。现在有一万斤菜、一斤肉，那么我们不愿意花钱买任何菜，却愿意为一斤肉花 10 元（刚好不赚不赔）。
哪些资源紧俏（比如肉），哪些资源的“边际价格”就高。
资源的边际价格，可以理解为该资源（在最优生产方案里）做出贡献的估价；也就是说，该资源增加一单位，能给我们带来多少收益，或者，我们愿意为资源增加付多少钱。

定义 & 计算：

在双最优解的情况下，有原问题的目标函数 \(z=CX=Y^Tb\)，其中 b 是资源限制。
对 z 求 b 的左偏导，得 \(\frac{\partial z}{\partial b}=Y\)，这说明，Y 的各个元素代表了相应资源每增加一个单位所能带来的生产收益，也就是边际价格。

影子价格的性质：

根据互补松弛性，如果生产问题第 j 个 ≤ 约束条件取＜而非 =，即第 j 种资源没有充分利用，可以推出对偶变量 i = 0，资源 j 的影子价格 / 边际价格 = 0。
- 这是合理的，对于没有充分利用的资源，我们并不想花钱买更多。
反之，资源 j 充分利用 \(\nRightarrow\) 资源 j 的对偶变量（影子价格）> 0，此时，资源 j 只是恰好耗尽而已，而非稀缺。
- 这种情况叫做“退化的最优解”，直观理解，就是在线性规划的图解法中，目标函数的线与约束条件的线重合了。
- 下图以饺子馅问题为例，说明了对偶问题退化时，可能出现资源 j 充分利用，且对偶变量 j = 0。
从影子价格角度，讨论单纯形表的检验数：
- \(σ_i=c_i-\sum a_{ji}y_{j}\)，（是用单纯形法矩阵描述推出来的），代表着，第 i 种产品的检验数（牺牲其他产品的生产，来多生产一个单位的第 i 种产品，能增加多少收益）= 第 i 种产品的单位收益 - 生产一单位产品 i 所消耗的各项资源的影子价格之和。
- 可以将影子价格，理解为产品的隐含成本 / 机会成本。只有收益＞机会成本时，生产第 i 种产品才是有利的。

3 对偶单纯形法

3.1 思想：对原问题使用“对偶”的单纯形法，实质为求解对偶问题

复习：单纯形法的基本思路：

先找到初始基可行解，判断所有检验数 σ 是否 ≤ 0。
若是，查看基变量中是否有人工变量（大 M 法中，用来凑单位矩阵的人工变量），如果没有人工变量 ≠ 0，则找到了最优解。
若否，转换到 σ 最大的相邻基可行解，继续判断是否所有 σ 都 ≤ 0，直到找出最优解。

对偶单纯形法的基本思路：（跟单纯形法反着来 ???? ）

首先，对于原问题，我们要找满足 ① 可行性 ② 最优性的解。然而，原问题解的 ① 可行性 ② 最优性，恰好对应对偶问题 ① 最优性 ② 可行性。
单纯形法的思路：先满足可行性，然后逐渐逼近最优性；对偶单纯形法：先满足最优性，然后逐渐逼近可行性。
- 即，先找到对偶问题的可行解，再寻找符合原问题可行性（对偶问题最优性）的解。
- 最优性：检验数 σ 是否全 ≤ 0；可行性：右端项 b 是否全 ≥ 0。

3.2 基本步骤与具体做法

确定初始基解

设法找到一个解，满足所有 σ ≤ 0，但是对 b 值不做要求（可以＜0）。
如果发现 b 全都 ≥ 0，则我们一开始就找到了 可行的 最优解。
如果有些 b＜0，进行换基操作，换到一个目标函数值较小的相邻基解，直到找到 可行的 最优解。
- 换基细节：
- 在单纯形法中，先确定 σ 最大的作为入基变量，然后在可行性约束（b ≥ 0）下确定出基变量。
- 在对偶单纯形法中，先确定 b 最小的作为出基变量，然后在最优性约束（σ ≤ 0）下确定入基变量。

确定出基变量

如果不是可行解，那么存在 \(b_j\le0\)，选取最小的 \(b_j\) 对应的 x 为出基变量。

确定入基变量

刚刚决定换掉第 j 行原来的基，所以要再找一列，把它变换成 \((0,\cdots,1,\cdots,0)^T\)（只有第 j 行为 1）的形式。
入基变量的列（记为第 i 列），需要满足系数矩阵第 i 列第 j 行的 \(a_{ji}\lt0\)。
- 这是因为，我们换掉第 j 行的原因，是 \(b_j\) 为绝对值很大的负数；所以现在，希望通过换基，让 \(b_j\) 改邪归正，变成 ≥ 0 ，即逐步接近可行性。\(a_{ji}\rightarrow1,~b_j\rightarrow\frac{b_j}{a_{ji}}\)，即可实现 \(b_j\) 变成正数。
如果有多列满足 \(a_{ji}\lt0\)，则选取 \(\theta_i=\sigma_i/a_{ji}\) 最小的一列，作为入基变量。

换基操作 & 最优性判断

换基操作：和原来一样，通过 \((A,b)\) 矩阵的行变换，得到新的单位矩阵。
最优性判断：
- 如果所有 b 都 ≥ 0，则原问题、对偶问题均取到最优解。
- 如果发现有一行，① b＜0、② 所有该行的系数 a＞0，则对于 ≥ 0 的 x 们，不可能在 ≥ 0 的 a 的加持下，凑出＜0 的 b，原问题无解，对偶问题有无界解。
- 其余情况，继续迭代。

最后，贴一个具体例题，王老师应试向网课 P5 15:54 开始。

在对偶单纯形法中，最难的一步是最开始找 σ ≤ 0 的基解，因此，对偶单纯形法只在能找到基解的情况下使用，比如灵敏度分析。求解线性规划问题，主流的方法还是单纯形法。

3.3 灵敏度分析

对应王老师网课 P34（在最后），这部分的笔记可能比较潦草 ????

灵敏度分析，就是在部分参数（单位收益 c、资源限制 b、资源用量 a）发生变化时，判断问题的最优解有什么变化。

单位收益 c 变化：直接在单纯形表终表中，把 c 的值改掉，看检验数 σ 怎么变（会影响最优性）。
资源限制 b 变化：直接在单纯形表终表中，b += \(B^{-1}\Delta b\)。
- 不会影响检验数 σ，即不会影响最优性。因为，检验数代表我们选择牺牲其他产品、生产第 i 种产品可否获利更多，纯属思想实验（空想），和资源限制没关系。
- 然而，有可能影响可行性，b += \(B^{-1}\Delta b\) 之后出现负数，此时使用对偶单纯形法。
资源约束系数 a 变化：
- 如果系数矩阵 A 中，最终基变量的那些列没有变化：直接改单纯形表终表，b 不变，系数矩阵 += \(B^{-1}[\Delta A]\)，会改变检验数 σ（影响最优性）。
- 如果系数矩阵 A 中，最终基变量的那些列有变化：\(B^{-1}\) 有变化，可能同时影响可行性 / 最优性。如果仅影响可行性，可以使用对偶单纯形法。如果不最优、不可行，需要引入人工变量重新计算。

其他变式：

新增一个变量（出现一种新产品，是否去生产）。
- 假设该变量原来就存在，只不过单位收益 c = 0，耗费资源 a = 0。
- 然后，采用 c 变化 + 非基变量 a 变化的思路，直接改单纯形表。
新增一个约束条件（出现一种新资源，并且还有限制）。
- 单纯形表新增了一行（一行不等式）一列（不等式的松弛变量）。
- 松弛变量那一列系数矩阵是 \((0,\cdots,1)^T\) 的形式，正好可以与原先的基向量（单位矩阵）拼在一起，成为新的基向量，得到了新的单纯形表。
- 此时，解的可行性 / 最优性都可能受到影响，分情况继续迭代：可行性 → 对偶单纯形法；最优性 → 普通单纯形法；可行性+最优性 → 重新算吧 ????。