运筹学笔记 对偶理论与灵敏度分析

运筹学笔记 对偶理论与灵敏度分析

本章内容要点

  1. 单纯形法的矩阵描述及改进单纯形法的介绍;
  2. 线性规划的对偶问题的概念、理论及经济意义;
  3. 线性规划的对偶单纯形法;
  4. 线性规划的灵敏度分析。

文章目录

改进单纯形法的介绍

用前单纯形表方法求解线性规划问题时,在每步迭代过程中,都要把整个单纯形表计算一遍。
实际上不必要地计算了许多与下一步迭代无关的数字,影响了计算效率。若用计算机求解时,就需要占用许多的存储单元。特别当求解规模很大的线性规划问题时,计算效率就低了。

在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述

线性规划的对偶问题

在这里插入图片描述


在这里插入图片描述

对偶问题的基本性质

对称性: 对偶问题的对偶是原问题。

在这里插入图片描述


弱对称性

在这里插入图片描述


无界性: 若原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解。

在这里插入图片描述

可行解是最优解时的性质:

在这里插入图片描述

对偶定理: 若原问题有最优解,那么对偶问题也有最优解;且目标函数值相等。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述


松弛互补性:

在这里插入图片描述


在这里插入图片描述


在这里插入图片描述

线性规划的对偶单纯形法

1 . 对偶单纯形法的基本思想
从原规划的一个基本解出发,此基本解不一定可行,但它对应着一个对偶可行解(检验数非正),所以也可以说是从一个对偶可行解出发;然后检验原规划的基本解是否可行,即是否有负的分量,如果有小于零的分量,则进行迭代,求另一个基本解,此基本解对应着另一个对偶可行解(检验数非正)。如果得到的基本解的分量皆非负,则该基本解为最优解。

对偶单纯形法和单纯形法一样,都是求解原线性规划问题的一种方法 。

在这里插入图片描述

2 . 对偶单纯形法的计算步骤

在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


3. 对偶单纯形法的适用范围
对偶单纯形法适合于解如下形式的线性规划问题

在这里插入图片描述

在引入剩余变量化为标准型之后,约束等式两侧同乘-1,能够立即得到检验数全部非正的原规划基本解,可以直接建立初始对偶单纯形表进行求解,非常方便。

总结
对于有些线性规划模型,如果在开始求解时,不能很快使所有检验数非正,最好还是采用单纯形法求解。因为这样可以免去是检验数全部非正而做的许多工作。从此意义上看,可以说对偶单纯形法只是单纯形法的一个补充。除此之外,在后面对线性规划进行灵敏度分析中有时也要用到对偶单纯形法,可以简化计算。

线性规划的灵敏度分析

研究最优解受数据变化的影响情况主要考虑2个方面:
1 . 解的最优性,即检验数是否仍<0
2 . 解的可行性,即基本解的各个分量是否>0。
灵敏度分析采用的方法:
从已得到的最优解出发,通过对变化数据进行分析,将个别参数的变化直接在计算得到最优解的单纯形表上反映出来(即把发生变化的个别系数,经过一定计算后直接填入最终计算表中,并进行检查和分析) ,判断是否仍满足最优解的条件,如果不满足的话,再从这个表开始进行迭代计算,求得最优解。
灵敏度分析——又称优化后分析

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述