Chapter3.1_3.2线性规划的对偶和灵敏度分析.ppt

Chapter 3 线性规划的对偶和灵敏度分析;3.1 对偶问题的提出; 对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？;两个黄鹂鸣翠柳，一行白鹭上青天。 窗含西岭千秋雪，门泊东吴万里船。 杜甫《绝句》 ;俩家具制造商间的对话：;王老板家具厂木器车间生产木门与木窗两种产品。加工木门收入为56元/扇，加工木窗收入为30元/扇。生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总工时为120小时，油漆工总工时为50小时。 该车间应如何安排生产才能使每日收入最大？;;设用y1,y2分别表示付给木工和油漆工的价格。王老板在做定价决策时,作如下比较：若用4个小时木工和2个小时油漆工可以生产一扇木门,可获利56元,那么付给加工木门的木工和油漆工的价格应不低于加工一扇木门的利润,这就有;王老板的家具生产模型： x1 、 x2是木门、木窗生产量。 Z是家具销售总收入。 max Z = 56x1 + 30x2 s.t. 4x1+3x2 ≤ 120（木工） 2x1+ x2 ≤ 50 （油漆工） x1，x2 ≥ 0 原始线性规划问题，记为（P）; 王老板按（D）的解 y1 、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。 ;Max Z= 1500x1 +2500x2;根据原则2 ，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：;2.4 线性规划的对偶理论;;对偶问题的形式;对称型问题的对偶规则;原始问题 Max Z=CX s.t. AX≤b X ≥0;当原问题为求极小值时，对偶问题为求极大值。 原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。 原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。 原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。 原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。 ;求线性规划问题的对偶规划;求线性规划问题的对偶规划;求线性规划问题的对偶规划;上式已为对称型对偶问题，故可写出它的对偶规划;对偶问题的非对称形式;原问题（或对偶问题）;例2、写出下述线性规划问题的对偶问题;【例2.5】写出下列线性规划的对偶问题 ;性质1 对称性定理：对偶问题的对偶是原问题;;性质2 弱对偶原理(弱对偶性)：设 和 分别是问题(P)和(D)的可行解，则必有;推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。;推论2: 在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。;利用对偶性质判断下面问题有无最优解;课堂练习 利用对偶性质判断下面问题有无最优解;性质3 最优性定理：如果 是原问题的可行解， 是其对偶问题的可行解，则:;性质4 强对偶性：若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。;性质6 互补松弛性：设X*和Y*分别是P问题 和 D问题 的可行解，则它们分别是最优解的充要条件是：;证: (必要性）;Max Z=CX s.t. AX+XS=b X, XS ≥0;;性质5的应用： 该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y＊求X＊或已知X＊求Y＊; 已知线性规划 ;设原问题最优解为X＊＝(x1，x2 ，x3)T ,由互补松弛性定理知，X＊和 Y＊满足： ;试用对偶原理求解线性规划问题;;代入对偶规划的约束条件得;XB;证明：设B是原始问题的一个可行基，于是A=(B,N)；原问题及其对偶问题可改写为;分析XN和Xs的检验数CN-CBB-1N和-CBB-1与对偶问题的解之间的关系。; Max Z=40x1+ 50x2 ;Max W′= -30y1- 60y2 - 24y3 +0(y4 + y5 )-M (y6 + y7 ) ;cj;cj;;原问题与其对偶问题的变