运筹学课件第二章线性规划的对偶理论与灵敏度分析.ppt
第二章 线性规划的对偶理论与灵敏度分析,一、对偶问题的提出1、对偶思想举例 周长一定的矩形中，以正方形面积最大；面积一定的矩形中，以正方形周长最小；,第一节 LP的对偶问题,3,对偶问题？.,对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？,线性规划的对偶理论引例俩家具制造商间的对话：,唉!我想租您的木工和油漆工一用。咋样？价格嘛好说，肯定不会让您兄弟吃亏讪。,王老板做家具赚了 大钱，可惜我老李有 高科技产品，却苦于没有足够的木工和油漆工 咋办？只有租咯。,Hi：王老板，听说近来家具生意很好，也帮帮兄弟我哦!,家具生意还真赚钱，但 是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。,价格嘛好商量，好商量。只是.,家具-王 总,李 总,线性规划的对偶理论,王老板的家具生产模型：x1、x2是桌、椅生产量。Z是家具销售总收入（总利润）。max Z=50 x1+30 x2s.t.4x1+3x2 120（木工）2x1+x2 50（油漆工）x1，x2 0原始线性规划问题，记为（P）,王老板的资源出租模型：y1、y2单位木、漆工出租价格。W是资源出租租金总收入。min W=120y1+50y2s.t.4y1+2y2 50 3y1+y2 30 y1，y2 0对偶线性规划问题，记为（D）,线性规划的对偶理论 王老板按（D）的解 y1、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。,按时下最流行的一个词，叫什么来着,对偶问题Min w=YbT=YTbs.t.ATY CTY 0,原始问题max z=CXs.t.AX bX 0,max,b,A,C,CT,AT,bT,min,m,n,m,n,2、换个角度审视生产计划问题,例 要求制定一个生产计划方案，在设备A,B和调试三种资源限制下，使得产品的总利润最大。,maxZ=2x1+x2 5x215 6x1+2x224 x1+x25 x1,x20,st.,转换思路:投资人:如果某投资公司准备购买该工厂，它至少应付出多大的代价，才能使工厂自己放弃生产产品、，而将可利用的资源都出让。被兼并人:该工厂的底线：最低可接受价格，指按这种价格转让资源比自己生产产品、合算的价格。,设y1,y2，y3为代表单位时间这三种资源的出让价格，为了使工厂出让资源合算，显然应该使出让原来生产一件产品的资源所得收入不低于自己生产产品的利润，即 0y1+6y2+1y3 2 对于产品，同样可以建立类似的约束条件 5y1+2y2+1y31,y1,y2,y3,当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：Zmax=Wmin,显然在满足这两个约束的前提下，价格越高，该工厂越合算，但价格太高，投资人方面又不会愿意购买。因此，我们需要确定的价格是 使工厂合算的最低价格，故应建立目标函数：min w=15y1+24y2+5y3,考察原问题和对偶问题的解，给作决策的管理者另一个自由度；,怎样通过增加更多的资源来增加利润？怎样使用不同类型的资源来增加利润？,对应第一个约束条件 对应第二个约束条件（P）max Z=2X1+X2 5X2 15 对应第一个对偶变量 y1 6X1+2X2 24 对应第二个对偶变量 y2 X1+X2 5 对应第三个对偶变量 y3 X1，X2 0,（D）min w=15y1+24y2+5y3 6y2+y3 2 5y1+2y2+y3 1 y1，y2，y3 0,二、原问题和对偶问题的关系1、对称形式的对偶关系,（1）定义：若原问题是,则定义其对偶问题为,这两个式子之间的变换关系称为“对称形式的对偶关系”。,（2）对称形式的对偶关系的矩阵描述,（D）,（L）,（3）从原问题写出其对偶问题按照定义；记忆法则：“上、下”交换，换后矩阵转置。不等式变号，“极大”变“极小”,例 写出下面线性规划的对偶问题：,y2=y2-y2y3=-y3,2、非对称形式的对偶关系：,（1）原问题 对偶问题,（2）怎样写出非对称形式的对偶问题？把一个等式约束写成两个不等式约束，再根据对称形式的对偶关系定义写出；按照原-对偶表直接写出；（3）原-对偶表,例题：写出下面线性规划的对偶规划：,（原问题是极小化问题，因此应从原-对偶表的右边往左边查！）,第二节 对偶问题的基本性质,原问题对偶问题为对称形式的线性规划问题,一、单纯形法的矩阵描述 进一步讨论修正单纯形法 便于理论推导（如对偶定理的证明）二、矩阵描述 关键写出两个基本的表达式。,2.1单纯形法的矩阵描述,1、准备工作：（1）标准型的矩阵形式,（2）将式中矩阵写成分块矩阵形式,2、将分块形式代入矩阵形式标准型，得出两个基本表达式：（1）由约束条件,可得 用非基变量表示基变量的表达式：,迭代后的单纯形表,初始单纯形表,对应初始单纯形表中的单位阵 I，迭代后为B-1,基变量的变换：初始 XS=b；迭代后XB=B-1b,约束系数矩阵的变化：A,I=B,N,I；B-1 A,B-1 I=B-1 B,B-1 N,B-1 I=I,B-1 N,B-1.,约束系数矩阵的向量变化：PjT=B-1 Pj,CB,CN,0,检验数：CN-CB B-1 N0(1);-CB B-1 0;令:CB-CBI=0(2)(1)+(2)得到 CN-CB B-1 N+CB-CBI=CN-CB B-1 N+CB-CBB-1B=CB+CN-CBB-1(B+N)=C-CBB-1A 0-CB B-1 0;令YT=CB B-1 单纯形乘子 ATY CT;Y0 Wmin=YTb=CBB-1b=Zmax,C-YTA 0C YTA C T(YTA)T,检验数的相反数为其对偶问题的一个可行解,例 原问题、对偶问题之间的关系,y1 yi ym ym+1 ym+j yn+m,x1 xj xn xn+1 xn+i xn+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0,二、对偶问题的基本性质 对偶基本性质揭示原问题的解与对偶问题的解之间关系,补充:对称性定理 对偶问题的对偶是原问题。,定理1 弱对偶定理若一对对称形式的对偶线性规划,均有可行解，分别为 和，则C b。,证明思路：,该结论对非对称形式的对偶问题同样成立。,推论:关于“界”的结果；,极小化问题有下界推论1 原问题(极大化问题)的任意一个可行解所对应的目标函数值是其对偶问题目标函数值的一个下界。,极大化问题有上界推论1 对偶问题(极小化问题)的任意一个可行解所对应的目标函数值是其原问题目标函数值的一个上界。,关于最优解无界情况与对偶问题的关系；,推论2 若原问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。,推论3,原问题可行，且目标函数值无界=对偶问题不可行对偶问题可行，且目标函数值无界=原问题不可行若对偶问题不可行，其原问题或没有可行解或无界解。,原问题有可行解而其对偶问题没有可行解，则原问题的目标函数无界；对偶问题有可行解而其原问题没有可行解，则对偶问题的目标函数无界；,定理 2 最优性定理 若、分别为对称形式对偶线性规划的可行解，且两者目标函数的相应值相等，即C=b，则，分别为原问题和对偶问题的最优解。,CX=Y b,CX*Y*b,弱对偶定 理,已 知,结论,Y*bY b,因为XY可行解,CX CX*,证明思路,设X*,Y*分别为原问题和对偶问题的最优解;X,Y分别为原问题和对偶问题的可行解,CX CX*Y*bY b=CX,CX=CX*=Y*b=Y b,3、强对偶性 若原问题和对偶问题两者均具有可行解，则两者均有最优解，且此时目标函数值相同。,都有可行解,各自有上下界,都有最优解,目标函数值相等,证明要点：,定理4 互补松弛性 在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零。,证明,弱对偶性,最优性,此定理适用于非对称形式,(1)式应取=,例:已知线性规划,其最优解为x=(6,2,0)T,求对偶问题的最优解,26+22+0=16;y20,6+22+0=10;y10,x1=60;约束条件为=,x2=20;约束条件为=,x3=0;约束条件为,求解结果为Y=(1,1)TMin W=26,思考题如何理解对偶问题的基本性质？讨论题用例子说明互补松弛性的实际应用。,小结对偶问题的基本性质。对偶定理。作业:2.1(1),2.3,2.7,
