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

《对偶理论与灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、运筹学OPERATIONALRESEARCH燕山大学经济管理学院运筹学课程教学课题组编制2第二章线性规划的对偶理论与灵敏度分析3第一节LP的对偶理论一、对偶问题的提出ⅠⅡ每天可用能力设备A0515设备B6224调试工序115利润21①两种家电各生产多少,可获最大利润?4解:设两种家电产量分别为变量x1，x25x2156x1+2x224x1+x25x1，x20maxZ=2x1+x25②另一家公司至少应付出多少代价才能使美佳公司愿意出让自己的资源而不组织两种产品的生产？解：设y1,y2,y3分别为A,B设

2、备和调试工序工时出让的单价。minW=15y1+24y2+5y36y2+y325y1+2y2+y31y1…y306二、对偶问题与原问题的关系1.“对称型”(P)MaxZ=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXnb1a21X1+a22X2+…+a2nXnb2………am1X1+am2X2+…+amnXnbmXj0(j=1,…,n)7MinW=b1Y1+b2Y2+…+bnYna11Y1+a21Y2+…+am1Ymc1a12Y1+a22Y2+…+am2Ymc2………a1

3、nY1+a2nY2+…+amnYmcnYi0(i=1,…,m)(D)8例1：写出下面问题的对偶规划maxZ=5X1+6X23X1-2X274X1+X29X1,X20minW=7y1+9y23y1+4y25-2y1+y26y1,y209例1：写出下面问题的对偶规划maxZ=5X1+6X23X1-2X2=74X1+X29X1,X202.“非对称型”(P)10对偶问题minW=7y1+9y23y1+4y25-2y1+y26y1自由,y2011例2：写对偶规划minZ=4X1+2X2-3X3

4、-X1+2X262X1+3X39X1+5X2-2X3=4X2,X3012maxW=6y1+9y2+4y3-y1+2y2+y3=42y1+5y323y2-2y3-3y10,y20,y3自由13minZ=4X1+2X2-3X3X1-2X2-62X1+3X39X1+5X2-2X3=4X2,X30或将原问题变形为14观察结论:①一对对偶问题都有最优解，且目标函数值相等。②最优表中有两个问题的最优解。15第二节对偶问题的基本性质一、单纯形法计算的矩阵描述maxZ=CXAX≤bX0(P)maxZ=C

5、XAX+IXS=bX,XS016（初始单纯形表）非基变量基变量XBXNXS0XSbBNIσCBCN017（迭代中的单纯形表）基变量非基变量XBXNXS0XBB-1bIB-1NB-1σ0CN-CBB-1N-CBB-118二、对偶问题的基本性质1.对称性：对偶问题的对偶问题是原问题2.定理1(弱对偶定理)若,分别是原问题和对偶问题的可行解，则存在推论：1.原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。19推论：2.若原问题有可行解且目标

6、函数值无界，则其对偶问题无可行解；反之，对偶问题有无界解，原问题无可行解。（但逆向不成立）推论：3.若原问题有可行解，对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解，而原问题无可行解，则对偶问题的目标函数值无界。203.定理2yX,分别为(P),(D)的可行解，且XyC=b,则它们是(P),(D)的最优解。4.定理3（对偶定理）若原问题有最优解，对偶问题也有最优解，且目标函数值相等。或若原问题与对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。5.互补松弛性：，分别是原

7、问题和对偶问题的可行解，则当且仅当为最优解。21例：min=2x1+3x2+5x3+2x4+3x5其对偶解y1﹡=4/5y2﹡=3/5Z﹡=5用对偶理论求(P)的最优解x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53xi0(i=1…5)(P)在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，该约束条件取严格等式。反之，若约束条件取严格不等式，则其所对应的对偶变量一定为0。22第四节对偶单纯形法minZ=2X1+3X2+4X3X1+2X2+X332X1-X2+3X3

8、4X1,X2,X3023初始单纯形表为CBXBbx1x2x3x4x5-2-3-4000x4-3-1-2-1100x5-4-21-301σ-2-3-40024思路：(max型)单纯形法：找基B，满足B-1b0，即先找到基可行解，当C-CBB-1A不全0，（即检验数）。迭代保持B-1b0，使C-CBB-1A0，即CBB-1AC，（保持原问题的为基可行解，寻找对偶问题的可行解）25一、对偶单纯