运筹学课件 第2章：线性规划的对偶理论.ppt

《运筹学课件 第2章：线性规划的对偶理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第二章线性规划的对偶理论(DualityTheory)线性规划的对偶问题对偶问题的基本性质对偶问题的经济解释----影子价格对偶单纯形法灵敏度分析WinQSB软件应用第一节线性规划的对偶问题一、问题的提出【例2-1】第一章例1-1中讨论了某企业利用三种资源生产甲乙两种产品的生产计划问题，得到其线性规划问题为：下面从另一个角度来讨论这个问题：假定该企业决定自己不生产产品，而将现有的资源转让或出租给其他企业，那么该如何确定资源的转让价格？分析问题：1、定价不能太高，否则买方无法接受，并且对买方来说，其目的是越低越好；2、定价不能太低，否则企业不

2、愿意放弃生产、出让资源合理的价格应是对方用最少的资金购买该企业的全部资源，而该企业所获得的利润又不低于自己组织生产时所获得的利润。设分别用y1、y2和y3代表单位时间(h)设备、每公斤材料A、材料B的出让代价，则有：（LP2）对偶问题从以下方面比较(LP1)与(LP2)：系数矩阵目标函数价格系数向量约束条件右端项目标函数约束条件决策变量原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数Maxz=CXMinw=Y’b约束条件AX≤bA’Y≥C’决策

3、变量X≥0Y≥0（LP2）二、对称形式下对偶问题的一般形式满足下列条件的线性规划问题称为具有对称形式:(1)变量均满足非负约束；(2)约束条件当目标函数求极大时取“≤”号，目标函数求极小时取“≥”号注：对称形式与线性规划标准型是两种不同的形式，对称形式中约束条件的符号由目标函数决定原问题对偶问题若原问题为求极小形式的对称形式线性规划问题，对偶问题应该具有什么形式？若一个线性规划问题是另一个线性规划问题的对偶问题，则它们互为对偶问题对偶问题的对偶问题是原问题【例2-2】写出下述线性规划问题的对偶问题例中目标函数为max，若为对称形式，则约束条

4、件应为“≤”号，所有变量均应≥0。——非对称形式三、非对称形式的原——对偶问题关系2．变量均有非负约束令则1．目标函数为求极大，故约束条件应均为“≤”号约束b两边乘-1：约束c写成两个不等式约束：令，则原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数Maxz=CX目标函数Minw=Y’b约束条件m个≤≥=m个≥0≤0无约束变量变量n个≥0≤0无约束n个≥≤=约束条件【例2-3】写出下列线性规划问题的对偶问题【练习】写出下列线性规划问题的对偶问题

5、第二节对偶问题的基本性质一、单纯形法计算的矩阵描述(LP)(LD)对称形式线性规划问题的矩阵表达式加上松弛变量后为：其中，Xs=(xn+1,xn+2,…，xn+m)为松弛变量，I为m×m单位矩阵。设B是一个可行基，也称基矩阵。若将系数矩阵A分为(B,N)两块(这里N是非基变量的系数矩阵),对应于基B的变量为XB，其它非基变量用XN表示。则:同时也将C分为两块(CB,CN)，CB是目标函数中基变量XB的系数行向量，CN是目标函数中非基变量XN的系数行向量。于是0CNCBCj-zjINBbXs0XsXNXB基变量非基变量初始单纯形表-CBB-1

6、CN-CBB-1N0Cj-zjB-1B-1NIB-1bXBCBXsXNXB非基变量基变量最终单纯形表此时，若B-1b为最优解，则1.初始表中单位阵在迭代后单纯形表中对应的位置就是B-12.对于原问题的最优解，各松弛变量检验数的相反数恰好是其对偶问题的一个可行解，且两者具有相同的目标函数值。根据下面介绍的对偶问题的基本性质还将看到，若原问题取得最优解，则对偶问题的解也为最优解。二、对偶问题的基本性质1、对称性：对偶问题的对偶问题是原问题2、弱对偶性：设和分别是问题（LP）和（LD）的可行解，则恒有:____¢£bYXC证明：注：LP求极大，L

7、D求极小推论1：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。试估计它们目标函数的界，并验证弱对偶性原理。例1LP：LD：解：由观察可知：=（1,1,1,1），=（1,1），分别是（LP）和（LD）的可行解。Z=10，W=40，故有弱对偶定理成立。由推论⑴可知，W的最小值不能小于10，Z的最大值不能超过40。推论2：如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解注：本点性质的逆不成立，当对

8、偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然推论3：若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解而其原问题无可行解，则对偶问