第3章 对偶理论与灵敏度分析.ppt

《第3章 对偶理论与灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章对偶理论与灵敏度分析对偶线性规划对偶定理对偶最优解的经济解释——影子价格对偶单纯形法灵敏度分析对偶理论是线性规划的重要内容之一。随着线性规划问题研究的深入，人们发现对应于每个线性规划问题都伴生一个相应的线性规划问题。前者是由矩阵Ａ，右端向量ｂ和价值向量Ｃ定义的，称之为原问题；后者也是由相同的数据集合Ａ，ｂ和Ｃ构成的，称之为原问题的对偶问题。一对原问题和对偶问题是紧密关联的，它们不但有相同的数据集合，相同的最优目标函数值，而且在求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解。对偶理论深刻地指示了原问题和对偶问题的内在联系，由对偶问题引伸出来的对偶解还有着重要的经济意义

2、，是研究经济学的重要概念和工具之一。对偶问题的提出例1某工厂生产甲,乙两种产品，这两种产品需要在A、B、C三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划，即甲、乙两种产品各生产多少吨，可使该厂所获得利润达到最大。对偶线性规划设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）3230假设计划期内甲乙两种产品各生产吨，用图解法或单纯形法可求得最优解(元)即在计划期内甲产品生产吨，乙产品生产8吨，可以使总利润达到最大，为元。设备每吨产品的加工台时可供台

3、时数甲乙ABC359448364076利润（元/吨）3230现在从另一个角度来考虑该工厂的生产问题:假设该厂的决策者打算不再自己生产甲、乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。设分别为设备A、B、C每台时的租价，约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润目标函数：所获租金总额尽量少．由此可得两个对称的线性规划：矩阵形式：对偶线性规划考虑如下具有“≤”不等式约束的线性规划问题加入松弛变量XS=(xn+1,xn+2,…,xn+m)T以后可得标准型若B是系数矩阵（A,I）中的一个可行基，并假设（A,I）可

4、表示为（B,N），则线性规划问题可改写为可得基本可行解,目标函数值　　　　　　，若非基变量检验数　　　　　　　　　则　　　　　为最优解因为基变量检验数,最优解判别准则又可表述为　　　　　　　　　　　　。上述表达式又可写成即，其中称为单纯形乘子。所以当为最优解，且单纯形乘子用符号Ｙ示时，可以推得：①②③且由　　　　　　　　　　　　　，所以　　只存在最小值。由此可以得到另一个线性规划：称之为原线性规划问题的对偶问题，线性规划问题标准型的对偶问题考虑一个标准形式的线性规划问题由于任何一个等式约束都可以用两个不等式约束等价地表示，所以标准形线性规划问题可等价表示为：它的对偶规划为：若令线性规划标

5、准型的对偶规划为：对偶线性规划的求法从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解过程中，通常不通过求标准型，而是利用如下反映原始问题与对偶问题对应关系的原始─对偶表：目标函数变量系数约束条件右端项约束条件右端项目标函数变量系数约束条件个数：n个决策变量个数：n个对偶变量个数：m个约束条件个数：m个目标函数minW目标函数maxZ对偶问题（或原问题）原问题（或对偶问题）例2写出下列线性规划的对偶问题解：设对于原问题4个约束条件的对偶变量分别为由4个约束条件的类型，可知4个对偶变量分别为≤0，≥0，≥0和无约束；又因为原问题有3个决策变量，因此对偶规划有3个约束条件，由3个决

6、策变量的符号，可知对偶规划3个约束条件的类型分别为≥，≤，=。由此可得上述问题的对偶规划：本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。定理1对偶问题的对偶是原问题。证明：设原问题为　　　　　　　　对偶问题为改写对偶问题为　　　对偶问题的对偶为对偶定理定理2弱对偶定理若　　是原（极大化）问题的可行解，　　是对偶（极小化）问题的可行解，那么证明：因为　　是对偶问题的可行解，所以满足约束条且；又因为　　是原问题的可行解，可得　　　，,所以　　　　　　　　　。推论1原（极大化）问题的最优目标函数值以对偶问题任一可行解的目标函数值为上界。对偶（极小化）问题的

7、最优目标函数值以原问题任一可行解的目标函数值为下界。推论2如果原问题没有上界（即maxZ→+∞），则对偶问题不可行。如果对偶问题没有下界（即minW→-∞），则原问题不可行。定理3最优性定理若　　是原问题的可行解，　是对偶问题的可行解，而且两者的目标函数值相等，即　　　　，则　　和分别是原问题和对偶问题的最优解。证明：由弱对偶定理，对于原始问题的所有可行解　　，都有　　　　　　　因此　是原问题的最优解。同理，对于对偶问题的所有可行解