交通运筹学教学课件作者张文会第2章节线性规划的对偶理论和灵敏度分析课件

《交通运筹学教学课件作者张文会第2章节线性规划的对偶理论和灵敏度分析课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的对偶理论和灵敏度分析1主要内容第一节对偶问题的数学模型第二节对偶问题的性质第三节影子价格第四节对偶单纯形法第五节灵敏度分析2第一节对偶问题的数学模型2.1对偶问题的数学模型（1）目标函数求极大值时，所有约束条件为号，变量非负；（2）目标函数求极小值时，所有约束条件为号，变量非负。数学模型可表示为：34【例2.1】写出下列线性规划的对偶问题。52.1.3、非对称型对偶问题将原问题与对偶问题的对应关系列于表2-1。6因此，写线性规划的对偶问题时的要点归纳如下：（1）两个问题，一个求极大化，一个求极小化；（2）两个问题的约束数和变量数互换；（3）两个问题的价值系

2、数和资源限量互换；（4）两个问题的约束系数矩阵有互为转置的关系；（5）一个问题等式约束与另一个问题变量无约束相互对应；（6）一个问题约束（变量）的不等式符号与它的规范形式符号相反时，另一个问题变量（约束）的不等式符号与它的规范形式符号相反；（7）规范形式的线性规划的对偶仍然是规范形式。7【例2.2】写出下列线性规划的对偶问题。8第二节对偶问题的性质【性质2.1】对称性对偶问题的对偶是原问题。【性质2.2】弱对偶性若X*、Y*分别为（LP）和（DP）的可行解，则存在：【性质2.3】最优性设X*、Y*分别为（LP）和（DP）的可行解，则X*、Y*是最优解，当且仅当。【性质2

3、.4】对偶定理若（LP）有最优解，则（DP）也有最优解（反之亦然），且其最优值相等。【性质2.5】互补松弛性设X*、Y*分别为（LP）和（DP）的可行解，Xs和Ys是它的松弛变量的可行解，则X*、Y*是最优解当且仅当和。9【例2.4】已知线性规划的最优解为，试求对偶问题的最优解。1011第三节影子价格因为原问题和对偶问题的最优值相等，即，由此可得：即是第i种资源的变化率。的意义是在其它条件不变的情况下，单位资源变化所引起的目标函数最优值的变化。它的值代表对第i种资源的估价，称之为“影子价格”。12第四节对偶单纯形法（1）初始表中对偶问题可行，即极大化问题时，极小化问题时。（2）

4、原问题不可行，即某个资源限量。由对偶单纯形法的条件可知，并不是所有的线性规划都适合用这种方法求解。从运算次数和速度看，该方法最适合于下列线性规划：13对偶单纯形法的计算步骤：（1）将线性规划的约束化为等式，列出初始单纯形表。（2）确定出基变量。（3）确定进基变量。（4）求新的基本解。14【例2.6】求解线性规划【例2.7】用单纯形法求解线性规划15第五节灵敏度分析前面讨论的线性规划问题都是假定cj，bi，aij是常数，但在实际生产过程中，它们是不断变化的。例如市场条件的改变往往使cj改变，工艺条件的改变通常使得aij改变，而bi也受资源投入后的经济效果影响。因此，这些线性规划问

5、题的解带有一定程度的不准确性，企业决策者必须随时掌握市场动态及数据资料的变化情况，及时调整决策方案。线性规划的灵敏度分析（SensitivityAnalysis）也称敏感性分析，它是研究和分析参数的波动对最优解的影响程度，主要研究以下内容：（1）参数在什么范围内变化，原最优解或最优基不变；（2）模型发生变化（参数变化，增减约束、变量）时，最优解或最优基如何变化。162.5.1资源限量的灵敏度分析1718【例2.8】已知线性规划分别求，，的变化范围，使最优基不变。192.5.2价值系数的灵敏度分析2021222.5.3工艺系数的灵敏度分析工艺系数的灵敏度分析主要分析工艺系数的变化

6、对最优解的影响，是对改变工艺系数的大小或增加约束、变量以及减少约束、变量等情况的分析，下面举例说明。23（1）增加一个变量【例2.10】已知线性规划24（2）改变的值25（3）增加一个新的约束【例2.12】对于例如下线性规划，增加一个约束，求新的最优解。262.5.4参数分析参数分析是研究线性规划的资源限量与价值系数中附加了一个参数，分析该参数在不同取值区间内最优解的变化情况，是研究最优解对于参数波动的一种灵敏度分析方法。2728