数据挖掘--对偶理论与灵敏度分析

1、燕山大学经济管理学院燕山大学经济管理学院运筹学课程教学课题组编制运筹学课程教学课题组编制2第二章第二章 线性规划的对偶理论线性规划的对偶理论与灵敏度分析与灵敏度分析3第一节第一节 LP 的对偶理论的对偶理论一、对偶问题的提出一、对偶问题的提出 每天可用能力每天可用能力 设备设备A 0 5 15 设备设备B 6 2 24 调试工序调试工序 1 1 5 利润利润 2 1两种家电各生产多少两种家电各生产多少, , 可获最大利润可获最大利润?4解解: :设两种家电设两种家电产量分别为变量产量分别为变量x1 ， x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1，x2 0 max Z

2、= 2x1 +x25另一家公司至少应付出多少代价才能使美佳公另一家公司至少应付出多少代价才能使美佳公司愿意出让自己的资源而不组织两种产品的生产？司愿意出让自己的资源而不组织两种产品的生产？解：设解：设 y1 , y2 , y3 分别为分别为A, B设备和调试工序工设备和调试工序工时出让的单价。时出让的单价。minW=15y1+24y2 +5y3 6y2 +y3 25y1 +2y2 +y3 1y1 y3 06二、对偶问题与原问题的关系二、对偶问题与原问题的关系1. “对称型对称型” (P)MaxZ=C1X1+ C2X2+CnXna11X1+ a12X2+ a1nXn b b1 1a21X1+ a

3、22X2+ a2nXn b b2 2 am1X1+ am2X2+ amnXn b bm mXj j 0(0(j=1,n) )7MinW=b1Y1+ b2Y2+bnYna11Y1+ a21Y2+ am1Ym c c1 1a12Y1+ a22Y2+ am2Ym c c2 2 a1nY1+ a2nY2+ amnYm c cn nYi 0(0(i=1,m) )(D)8例例1 1：写出下面问题的对偶规划写出下面问题的对偶规划maxZ= 5X1 +6X2 3X1 -2X2 74X1 +X2 9X1 , X2 0minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1, y2 09例例1 1：

4、写出下面问题的对偶规划写出下面问题的对偶规划maxZ= 5X1 +6X2 3X1 -2X2 =74X1 +X2 9X1 , X2 02. “非非对称型对称型” (P)10对偶问题对偶问题minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1自由自由 , y2 011例例2 2：写对偶规划：写对偶规划minZ= 4X1 +2X2 -3X3 -X1+2X2 62X1 +3X3 9 X1 +5X2 -2X3 = = 4X2 , X3 012maxW= 6y1 +9y2 +4y3 -y1+2y2 + y3 = = 42y1 +5y3 2 3y2 -2y3 -3y1 0 , y2 0 ,

5、 y3自由自由13minZ= 4X1 +2X2 -3X3 X1 -2X2 - 62X1 +3X3 9 X1 +5X2 -2X3 = = 4X2 , X3 0或将原问题变形为或将原问题变形为14观察结论观察结论: 一对对偶问题都有最优解，且目标函数一对对偶问题都有最优解，且目标函数值相等。值相等。 最优表中有两个问题的最优解。最优表中有两个问题的最优解。15第二节第二节 对偶问题的基本性质对偶问题的基本性质一一、单纯形法计算的矩阵描述单纯形法计算的矩阵描述maxZ=CX AX b X 0(P)maxZ=CX AX+I+IXS = =b X, XS 016（初始单纯形表）（初始单纯形表）非基变量非

6、基变量基变量基变量XBXNXS0XSbBNICBCN017（迭代中的单纯形表）（迭代中的单纯形表）基变量基变量非基变量非基变量XBXNXS0XBB-1 bIB-1 NB-10CN- CB B-1 N- CB B-118二、对偶问题的基本性质二、对偶问题的基本性质1.1.对称性：对偶问题的对偶问题是原问题对称性：对偶问题的对偶问题是原问题2.2.定理定理1 (1 (弱对偶定理弱对偶定理) )若若 , , 分别是分别是原问题和对偶问题的可行解，则存在原问题和对偶问题的可行解，则存在 推论：推论：1.1.原问题任一可行解的目标函数原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之，值是其

7、对偶问题目标函数值的下界，反之，对偶问题任一可行解的目标函数值是其原对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。问题目标函数值的上界。 XYbYXC19 推论：推论：2.2.若原问题有可行解且目标函数若原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之，值无界，则其对偶问题无可行解；反之，对偶问题有无界解，原问题无可行解。对偶问题有无界解，原问题无可行解。（但逆向不成立）（但逆向不成立） 推论：推论：3.3.若原问题有可行解，对偶问题若原问题有可行解，对偶问题无可行解，则原问题目标函数值无界；反无可行解，则原问题目标函数值无界；反之，对偶问题有可行解，而原问题无可行之，对

8、偶问题有可行解，而原问题无可行解，则对偶问题的目标函数值无界。解，则对偶问题的目标函数值无界。203.3.定理定理2 2 yX,分别为分别为(P), (D)(P), (D)的可行解，且的可行解，且X yC=b , 则它们是则它们是(P), (D)(P), (D) 的最优解。的最优解。4.4.定理定理3 3（对偶定理）若原问题有最优解，对偶（对偶定理）若原问题有最优解，对偶问题也有最优解，且目标函数值相等。或问题也有最优解，且目标函数值相等。或若原问若原问题与对偶问题均具有可行解，则两者均具有最优题与对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。解，且它们最优解的目标函

9、数值相等。5.5.互补松弛性：互补松弛性： ， 分别是原问题和对偶分别是原问题和对偶问题的可行解，则问题的可行解，则 当且当且仅当仅当 为最优解。为最优解。XY0,0SSXYXYXY21例例： min = 2x1+3x2+5x3+2x4+3x5 其对偶解其对偶解 y1 =4/5 y2 =3/5 Z =5 用对偶理论求用对偶理论求(P)的最优解的最优解x1+x2+2x3+x4+3x5 42x1 -x2+3x3+x4+x5 3 xi 0 ( i =1 5 )(P)在线性规划问题的最优解中，若对应某一约束条在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，该约束条件取严格等式。件的对偶

10、变量值为非零，该约束条件取严格等式。反之，若约束条件取严格不等式，则其所对应的反之，若约束条件取严格不等式，则其所对应的对偶变量一定为对偶变量一定为0。22 第四节第四节 对偶单纯形法对偶单纯形法minZ=2X1 +3X2 +4X3 X1+2X2 + X3 32X1 - X2 +3X3 4X1 , X2 , X3 023初始单纯形表为初始单纯形表为CBXBbx1x2x3x4x5-2-3-4000 x4-3-1-2-1100 x5-4-21-301-2-3-40024思路：思路：( (maxmax型型) )单纯形法：找基单纯形法：找基B B，满足满足B-1b 0，即先找到基可即先找到基可行解，当

11、行解，当 C - CBB-1 A不全不全 0 0，（，（即检验数）即检验数）。迭代迭代保持保持B-1b 0，使使C -CBB-1 A 0，即即CBB-1 A C，（保持原问题保持原问题的为基可行解，寻找对偶问的为基可行解，寻找对偶问题的可行解题的可行解）25一、对偶单纯形法的基本思路：一、对偶单纯形法的基本思路： 找基找基B，满足，满足C - CBB-1 A 0（检验数）（检验数），即找到对偶问题的可行解。即找到对偶问题的可行解。 如果如果B-1b不全不全 0 0，即原问题的基解为非即原问题的基解为非可行解，则可行解，则迭代迭代保持保持C -CBB-1 A 0，使使B-1b 0。即保持对偶问题

12、的解为可行即保持对偶问题的解为可行解，使原问题的基解逐渐转解，使原问题的基解逐渐转换为基可行解。换为基可行解。26二、对偶单纯形法基本步骤二、对偶单纯形法基本步骤 maxmax型型( (minmin型型) )(1) 作初始表，要求全部作初始表，要求全部j 0 ( 0)(2) 判定判定： B-1 b全全 0，停停。否则，取否则，取max B-1 b =(B-1 b)l B-1 b0令第令第 l 行的行的Xj l为换出变量为换出变量. .27(3)确定换入变量确定换入变量 若若Xi l行的行的alj 全全 0 ，停停，原问题无可行解原问题无可行解。 若若Xi l行的行的alj 有有alj 0 ,则求则求j k =min =aljalkalj 12,原最优