线性规划及其对偶问题(单纯形法｜人工变量｜对偶理论）
线性规划及其对偶问题(单纯形法｜人工变量｜对偶理论）
线性规划是运筹学中的一个重要分支，主要用于解决资源分配、生产计划等问题。本文将详细介绍线性规划的基本概念、解法以及对偶问题的理论和应用。
（一）线性规划
1.化标准型
线性规划的标准型包括以下要素：
- 目标函数最大：c为价值系数
- 约束条件等式：a为工艺或技术系数
- 决策变量非负：x为某个方案
- 资源限量非负：b为资源限制
对于不等式约束，可以通过添加松弛变量或剩余变量将其转化为等式约束。松弛变量表示未被充分利用的资源，剩余变量表示超出的资源数。在目标函数中，这些变量的系数均为零。
2.图解法
线性规划的解可以分为以下几种情况：
- 唯一最优解
- 无穷多最优解
- 无界解
- 无可行解
如果线性规划的可行域存在，则可行域一定是凸集。最优解（之一）一定是可行域凸集的某个顶点。
3.单纯形法原理
3.1最优判断(检验数)
- 最优解：全部检验数<=0
- 唯一最优解：全部检验数<0
- 无穷多最优解：全部检验数<=0，存在某个非基变量检验数=0
- 无界解：有一个非基变量检验数>0，所有系数都>=0
3.2单纯形法步骤
- 求初始可行基，列出初始单纯形表
- 最优性检验
- 基变换
- 换入基：某个非基变量变为基变量X(in)
- 换出基：某个基变量变为非基变量，最小比值，对Pk列计算得到变量X(out)为换出变量
- 迭代变量：用换入基代替换出基，得到一个新的基和一张新的单纯形表Pk列只有X(out),X(in)对应的系数=1，其余均为0
4.单纯形法的进一步讨论
4.1 大M法
人工变量在目标函数中的系数为-M，M为任意大的正数。因此只要人工变量>0，目标函数不可能实现最优，人工变量只能为0。求解结果中所有检验数非正，如果基变量中有非0的人工变量，则无可行解，否则有最优解。
4.2 两阶段法
- 加入人工变量后，构造仅含人工变量的目标函数，要求实现最小化
- 将一阶段得到的最终表去除人工变量，将目标函数行的系数换成原问题的目标函数系数，作为二阶段的初始表
当一阶段的最优解中基变量不包含人工变量时，得到的原始线性规划问题的一个基可行解，第二阶段以此为基础对原目标函数求解最优解；当一阶段的最优解不等于0，说明基变量中有不为0的人工变量，则原问题无可行解
4.3 退化解
退化解的主要特征是，在基本可行解中，至少有一个基变量对应的值为零。这会导致问题的目标函数在这个解上不发生改变，因为对应于零值的基本变量的系数在目标函数中的贡献为零。因此，算法无法通过调整这个基本变量的值来改进目标函数值，从而陷入了循环或停滞。
为了解决退化解问题，通常使用一些策略，例如Bland’s Rule（布兰德规则）来选择要进入或离开基变量的变量，以确保算法可以继续寻找最优解而不陷入循环。
5.对偶单纯形法
5.1 对偶单纯形法步骤
- 化成标准型
- 判断是否最优解
- 换基计算
- 迭代运算
5.2 对偶单纯形法的特点
优点：
- 不需要人工变量
- 变量多于约束时，用对偶单纯形法可减少迭代次数
- 灵敏度分析中，有时需要用对偶单纯形法处理简化
缺点：
- 在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。因此，对偶单纯形法一般不单独使用
6.灵敏度分析
灵敏度分析用于研究线性规划问题中参数变化对最优解的影响。通过分析目标函数系数、约束条件系数和资源限量的变化，可以判断最优解是否发生变化，以及如何变化。
（二）对偶问题
1.线性规划的对偶问题
对偶问题的概念是线性规划中的一个重要理论。通过将原问题转化为对偶问题，可以更方便地求解某些优化问题。对偶问题的变量和约束与原问题相对应，可以通过表格形式直观地表示出来。
2.单纯形法矩阵描述
见（一）线性规划 3.1，下面是由原问题推出对偶问题
3.线性规划对偶理论
3.1 对称性
对偶问题的对偶是原问题
3.2 弱对偶性
弱对偶性可以用来提供bound，比如有原始问题的任意可行解目标值为a，则得到对偶问题的目标值的一个下界为a，反之也可以得到原始问题目标值的一个上界。
- 极大化问题(原问题)的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界
- 极小化问题(对偶问题)的任一可行解所对应的目标函数值是原问题最优目标函数值的上界
- 若原问题可行，但是目标函数无界，则对偶问题无可行解
- 若对偶问题可行，但其目标函数无界，则原问题无可行解
- 若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界
- 若原问题无可行解，则对偶问题无可行解或无界解
3.3 最优性定理
3.4 对偶定理(强对偶性)
- 一个有有限最优解，另一个也有有限最优解
- 一个有无界解，另一个无可行解
- 两个均无可行解
3.5 互补松弛性
4.影子价格
在对偶问题中，Yb是目标函数，其中b是原问题的约束条件的右端项，代表资源拥有量。影子价格的定义(对偶变量y的意义)：代表在资源最优利用条件下对单位第i中资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格(shadow price)
生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。
以Dakota problem为例说明，公司生产desk，table和chair，每个产品都需要三类资源:lumber，finishing，capentry，每个产品的售价和所需资源以及资源容量如下表，要求最大化利润
容易写出原始问题和对偶问题，现在从经济的角度解释对偶问题
假设一家企业想要购买Dakota的所有资源，这家企业必须决定购买单价，假设lumber，finishing和capentry价格分为y 1 y_1y1 ，y 2 y_2y2 ，y 3 y_3y3 ，购买所有的资源需要花费48 y 1 + 20 y 2 + 8 y 3 48y_1+20y_2+8y_348y1 +20y2 +8y3 ，因此优化目标肯定是最小化成本。资源单价必须设置的足够高能让Dakota公司出售，比如有8个lumber，4小时finishing，2小时capentry，Dakota公司就可以生产一个desk卖出60，因此企业购买这些资源的出价至少要为60，也就是8 y 1 + 4 y 2 + 2 y 3 > = 60 8y_1+4y_2+2y_3>=608y1 +4y2 +2y3 >=60，同理可得table和chair对偶约束。Dakota problem的对偶模型可以得到每类资源的价格，称为资源影子价格resource shadow prices.
本文原文来自CSDN