运筹学第二章线性规划的对偶理论与灵敏度分析ppt课件

1、运筹学教程第二章第二章 线性规划的对偶实际与灵敏度分析线性规划的对偶实际与灵敏度分析运筹学教程运筹学教程对偶实际是线性规划中最重要的实际之一，是深化了解线性规划问题构造的重要实际根底。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进展经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？运筹学教程线性规划的对偶实际线性规划的对偶实际引例引例俩家具制造商间的对话：俩家具制造商间的对话：唉唉!我想租您的木工和油漆工一我想租您的木工和油漆工一用。咋样？价钱嘛用。咋样？价钱嘛好说，好说，一定不会让您兄弟吃亏讪。一定不会让您兄弟吃亏讪。 王老板做家

2、具赚了王老板做家具赚了 大钱，惋惜我老李有大钱，惋惜我老李有 高科技产品，却苦于没有高科技产品，却苦于没有足够的木工和油漆工足够的木工和油漆工 咋办？只需租咯。咋办？只需租咯。Hi：王老板，听说：王老板，听说近来家具生意很好，近来家具生意很好，也帮帮兄弟我哦也帮帮兄弟我哦! 家具生意还真赚钱，但家具生意还真赚钱，但 是如今的手机生意这么好，是如今的手机生意这么好， 不如干脆把我的木工和油漆不如干脆把我的木工和油漆工租给他，又能工租给他，又能收租金又可做生意。收租金又可做生意。价钱嘛价钱嘛好商量，好商量， 好商量。只是好商量。只是. 家具家具-王王 总总李李 总总桌子椅子能力木工43120漆工2

3、150价格5030运筹学教程线性规划的对偶实际线性规划的对偶实际王老板的家具消费模型：王老板的家具消费模型：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

4、3y1+ y2 30 y1，y2 0对偶线性规划问题，记为对偶线性规划问题，记为D桌子椅子能力木工43120漆工2150价格5030运筹学教程线性规划的对偶实际线性规划的对偶实际 王老板按王老板按D的解的解 y1 、y2出租其拥有的木、漆工资出租其拥有的木、漆工资源，既保证了本人不吃亏出租资源的租金收入并不低于本人源，既保证了本人不吃亏出租资源的租金收入并不低于本人消费时的销售收入，又使得出租价钱对李老板有极大的吸引消费时的销售收入，又使得出租价钱对李老板有极大的吸引力李老板所付出的总租金力李老板所付出的总租金W最少。最少。运筹学教程对偶问题Min w=YbT=YTbs.t.ATY CTY 0

5、原始问题max z=CXs.t. AX bX 0maxbACCTATbTminmnmn运筹学教程 2、 换个角度审视消费方案问题例例 要求制定一个消费方案方案，在设备要求制定一个消费方案方案，在设备A,B和调试三种资源限制下，使得产品的总和调试三种资源限制下，使得产品的总利润最大利润最大 。 maxZ=2x1+x2 5x215 6x1+2x224 x1+x25 x1,x20st.运筹学教程转换思绪转换思绪: :投资人投资人: :假设某投资公司预备购买该工厂，它至少应付出多大假设某投资公司预备购买该工厂，它至少应付出多大的代价，才干使工厂本人放弃消费产品的代价，才干使工厂本人放弃消费产品、，而将

6、可利用，而将可利用的资源都出让。的资源都出让。被兼并人被兼并人: :该工厂的底线：最低可接受价钱，指按这种价钱转该工厂的底线：最低可接受价钱，指按这种价钱转让资源比本人消费产品让资源比本人消费产品、合算的价钱。合算的价钱。设设y1,y2， y3为代表单位时间这三种资源的出让价钱，为了为代表单位时间这三种资源的出让价钱，为了使工厂出让资源合算，显然应该使出让原来消费一件产品使工厂出让资源合算，显然应该使出让原来消费一件产品的资源所得收入不低于本人消费产品的资源所得收入不低于本人消费产品的利润，即的利润，即 0y1+6y2+1y3 2 对于产品对于产品，同样可以建立类似的约束条件，同样可以建立类似

7、的约束条件 5y1+2y2+1y31项目产品产品每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润(元)21y1y2y3运筹学教程 当原问题和对偶问题都获得最优解时，这一对线性规划对应的目的函数值是相等的： Zmax=Wmin显然在满足这两个约束的前提下，价钱越高，该显然在满足这两个约束的前提下，价钱越高，该工厂越合算，但价钱太高，投资人方面又不会情工厂越合算，但价钱太高，投资人方面又不会情愿购买。因此，我们需求确定的价钱是愿购买。因此，我们需求确定的价钱是 使工厂合算的最低价钱，故应建立目的函数：使工厂合算的最低价钱，故应建立目的函数： min w=15y1+24y

8、2+5y3 项目项目产品产品产品产品每天可用每天可用能力能力设备设备A(h)设备设备B(h)调试工序调试工序(h)06152115245利润利润(元元)21运筹学教程 调查原问题和对偶问题的解，给作决策的管理者另一个自在度； 怎样经过添加更多的资源来添加利润？怎样经过添加更多的资源来添加利润？ 怎样运用不同类型的资源来添加利润？怎样运用不同类型的资源来添加利润？ 对应第一个约束条件对应第一个约束条件 对应第二个约束条件对应第二个约束条件Pmax Z = 2X1 + X2 5X2 15 对应第一个对偶变量对应第一个对偶变量 y1 6X1 + 2X2 24 对应第二个对偶变量对应第二个对偶变量 y

9、2 X1 + X2 5 对应第三个对偶变量对应第三个对偶变量 y3 X1 ， X2 0 Dmin w = 15y1 + 24y2 + 5y3 6y2 + y3 2 5y1 + 2y2 + y3 1 y1， y2， y3 0运筹学教程1定义：假设原问题是定义：假设原问题是 0,.21221122222112112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMaxZ运筹学教程0,.21221122222112112211112211mnnmnnnnmmmmmyyycyayayacyayayacyayayatsybybybMinW 这两

10、个式子之间的变换关系称为这两个式子之间的变换关系称为“对称方式的对偶关系。对称方式的对偶关系。 运筹学教程0,. .21221122222112112211112211mnnmnnnnmmmmmyyycyayayacyayayacyayayatsybybybMinW0,. .21221122222112112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMaxZ运筹学教程2对称方式的对偶关系的矩阵描画对称方式的对偶关系的矩阵描画0.YCYAtsYbbYMinWTTTTD0. .XbAXtsCXMaxZL 3从原问题写出其对偶问题按照

11、定义； 记忆法那么： “上、下交换，换后矩阵转置。 不等式变号，“极大变“极小运筹学教程例例 写出下面线性规划的对偶问题：写出下面线性规划的对偶问题： 0,10251543. .221212121xxxxxxtsxxMaxZ0,124253. .101521212121yyyyyyt syyMinW运筹学教程3332213333323213122323222121223232221211131321211133332211321333323213123232221211313212111332211, 0, 0)()(.max, 0, 0.maxxxxxxxybxaxaxaybxaxaxayb

12、xaxaxaybxaxaxastxcxcxcxcZxxxbxaxaxabxaxaxabxaxaxastxcxcxcZ自由, 0, 0.min0, 0, 0, 0.min3213333223113233222211213312211113322113221333322322311333332232231132332222222112133122122111133222211yyycyayayacyayayacyayayastybybybWyyyycyayayayacyayayayacyayayayacyayayayastybybybybW自由y2=y2-y2y3=-y3运筹学教程2怎样写出非对称

13、方式的对偶问题？怎样写出非对称方式的对偶问题？把一个等式约束写成两个不等式约束，把一个等式约束写成两个不等式约束，再根据对称方式的对偶关系定义写出；再根据对称方式的对偶关系定义写出；按照原按照原-对偶表直接写出对偶表直接写出 ；3原原-对偶表对偶表运筹学教程项目项目原问题原问题（对偶问题）（对偶问题）对偶问题对偶问题（原问题）（原问题）目标函数类型目标函数类型maxmin目标函数系数与右边项目标函数系数与右边项的对应关系的对应关系目标函数各变量系数对应目标函数各变量系数对应约束条件右边项的系数约束条件右边项的系数右边项的系数对应目标函数右边项的系数对应目标函数系数系数变量个数与约束条件个变量个

14、数与约束条件个数的对应关系数的对应关系变量个数变量个数 n约束条件个数约束条件个数 m约束条件个数约束条件个数 n变量个数变量个数 m原问题变量类型与对偶原问题变量类型与对偶问题约束条件类型的对问题约束条件类型的对应关系应关系 0 (对称对称)变量类型变量类型 0 (非对称非对称) 自由自由 (对称对称)约束条件类型约束条件类型 (非对称非对称) =原问题约束条件类型与原问题约束条件类型与对偶问题变量类型的对对偶问题变量类型的对应关系应关系 (非对称非对称)约束条件类型约束条件类型 (对称对称) = (非对称非对称)变量类型变量类型 (对称对称) 自由自由运筹学教程例题：写出下面线性规划的对偶

15、规划：例题：写出下面线性规划的对偶规划：0, 01413121110987654. .32432121321321321xxxxxxxxxxxtsxxxMinZ符号不限运筹学教程0, 0,31062139541284. .1411732121321321321yyyyyyyyyyyt syyyMaxW符号不限0, 0,31062139541284. .1411732121321321321yyyyyyyyyyytsyyyMaxW符号不限原问题是极小化问题，因此应从原原问题是极小化问题，因此应从原-对偶表对偶表的右边往左边查！的右边往左边查！ 0,01413121110987654.324321

16、21321321321xxxxxxxxxxxtsxxxMinZ符号不限项目项目原问题原问题（对偶问（对偶问题）题）对偶问题对偶问题（原问题）（原问题）目标函数类型目标函数类型maxmin原问题变量类原问题变量类型与对偶问题型与对偶问题约束条件类型约束条件类型的对应关系的对应关系 0 (对称对称)变量类型变量类型 0 (非非对称对称) 自由自由 (对称对称)约束条件类型约束条件类型 (非对称非对称) =原问题约束条原问题约束条件类型与对偶件类型与对偶问题变量类型问题变量类型的对应关系的对应关系 (非对称非对称)约束条件类型约束条件类型 (对称对称) = (非对称非对称)变量类型变量类型 (对称对

17、称) 自由自由运筹学教程原问题对偶问题为对称方式的线性规划问题原问题对偶问题为对称方式的线性规划问题njxmibxat sxcMaxZjnjijijnjjj, 2 , 10, 2 , 1. .11miynjcyat sybMinWimijiijmiii, 2 , 10, 2 , 1. .11，运筹学教程运筹学教程0,0.0SSSXXbIXAXtsXCXMaxZ)(NBCCC)(NBXXX)(),.,(,21INBPPPPIAmnn运筹学教程bIXNXBXIXXXNBIXAXSNBSNBS)( 可得可得 用非基变量表示基变量的表达式：用非基变量表示基变量的表达式：SNSNBXBNXBbBIXNX

18、bBX1111)(运筹学教程项目非基变量基变量XB XNXS0 XS b B N ICj-ZjCB CN 0项目基变量非基变量XB XN XSCB XB B-1 b IB-1 N B-1 Cj-Zj 0CN -CB B-1 N -CB B-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

19、 N, B-1.约束系数矩阵的向量变化：约束系数矩阵的向量变化：PjT = B-1 PjCBCN0运筹学教程检验数：检验数：CN-CB B-1 N0 (1); CN-CB B-1 N0 (1); -CB B-1 0; -CB B-1 0; 令令:CB-CBI=0 (2):CB-CBI=0 (2)(1)+(2)(1)+(2)得到得到 CN-CB B-1 N +CB-CBI= CN-CB B-1 N +CB-CBB-1BCN-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+CN-CBB-1(B+N)=C

20、-CBB-1A 0 -CB B-1 0; -CB B-1 0;令令YT= CB B-1 YT= CB B-1 单纯形乘子单纯形乘子 ATY CT; ATY CT; Y0 Wmin= YTb= CBB-1b=Zmax Y0 Wmin= YTb= CBB-1b=ZmaxC-YTA 0C YTA C T (YTA)T检验数的相反数为其检验数的相反数为其对偶问题的一个可行对偶问题的一个可行解解运筹学教程052426155.0002max3521242113254321jxyxxxyxxxyxxstxxxxxZ012526.0052415min25321143154321iyxyyyyxyyystyyy

21、yyW例例 原问题、对偶问题之间的关系原问题、对偶问题之间的关系项目原问题变量原问题松弛变量 x1 x2x3 x4 x5X3 15/2X1 7/2X2 3/2 0 0 1 0 0 11 5/4 -15/20 -1/20 -1/4 3/2 -Cj+zj 0 00 1/2DUAL 剩余变量DUAL 变量 y4 y5y1 y2 y3项目dual变量dual剩余变量 y1 y2 y3y4 y5y2 1/4y3 1/2 -5/4 1 015/2 0 1-1 /4 -3/2Cj-zj 15/2 0 07/2 3/2原问题松弛变量原问题 变量 x3 x4 x5x1 x2运筹学教程y1 yi ym ym+1

22、ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjym+j=0 yixn+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0运筹学教程0.XbAXtsCXMaxZL 0.YCYAtsbYMinW和和 D 均有可行解，分别为均有可行解，分别为 和和 ，那么，那么C b。XXYY证明思绪：证明思绪：由由L bXA 左乘左乘 ，得，得 bYXAYY由由D CAY 右乘右乘 ，得，得 XXCXAYbYXC运筹学教程 推论推论:关于关于“界的结果；界的结果；极小化问题有下界极小化问题有下界推论推论1 原问题原问题 (极大化问题极大化问题) 的恣意一个可行解的恣意一个可行解所对应的目的函数值是其对偶问标题的函数值所对应的目的函数值是其对偶问标题的函数值的一个下界。的一个下界。运筹学教程运筹学教程运筹学教程XXXYYY运筹学教程CX=Y CX=Y b bCX*Y*b弱对偶弱对偶定定 理理已已 知知结论结论Y*bY b由 于由 于XY可 行可 行解解CX CX*设设X*,Y*分别为原问题和对偶问题的最优解分别为原问题和对偶问题的最优解;