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

《运筹学课件第二章线性规划的对偶理论与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《运筹学课件第二章线性规划的对偶理论与灵敏度分析.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学教程第二章第二章 线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析运筹学教程一、对偶问题的提出一、对偶问题的提出1、对偶思想举例对偶思想举例周周长长一一定定的的矩矩形形中中，以以正正方方形形面面积积最最大大；面面积积一一定定的的矩矩形形中中，以以正正方方形形周长最小；周长最小；第一节第一节 LP的的对偶问题对偶问题运筹学教程对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？3运筹学教程线性

2、规划的对偶理论线性规划的对偶理论引例引例俩家具制造商间的对话：俩家具制造商间的对话：唉唉!我想租您的木工和油漆工一我想租您的木工和油漆工一用。咋样？价格嘛用。咋样？价格嘛好说，好说，肯定不会让您兄弟吃亏讪。肯定不会让您兄弟吃亏讪。王老板做家具赚了王老板做家具赚了大钱，可惜我老李有大钱，可惜我老李有高科技产品，却苦于没有高科技产品，却苦于没有足够的木工和油漆工足够的木工和油漆工咋办？只有租咯。咋办？只有租咯。Hi：王老板，听说王老板，听说近来家具生意很好，近来家具生意很好，也帮帮兄弟我哦也帮帮兄弟我哦!家具生意还真赚钱，但家具生意还真赚钱，但是现在的手机生意这么好，是现在的手机生意这么好，不如干

3、脆把我的木工和油漆不如干脆把我的木工和油漆工租给他，又能工租给他，又能收租金又可做生意。收租金又可做生意。价格嘛价格嘛好商量，好商量，好商量。只是好商量。只是.家具家具-王王总总李李总总桌子 椅子 能力木工 43120漆工 2150价格 5030运筹学教程线性规划的对偶理论线性规划的对偶理论王老板的王老板的家具生产模型家具生产模型：x1、x2是桌、椅生产量。是桌、椅生产量。Z是家具销售总收入（总利润）。是家具销售总收入（总利润）。max Z=50 x1+30 x2s.t.4x1+3x2 120（木工）木工）2x1+x2 50（油漆工）油漆工）x1，x2 0原始线性规划问题，记为（原始线性规划问

4、题，记为（P）王老板的王老板的资源出租模型资源出租模型：y1、y2单位木、漆工出租价格。单位木、漆工出租价格。W是资源出租租金总收入。是资源出租租金总收入。min W=120y1+50y2s.t.4y1+2y2 50 3y1+y2 30 y1，y2 0对偶线性规划问题，记为（对偶线性规划问题，记为（D）桌子椅子能力木工43120漆工2150价格5030运筹学教程线性规划的对偶理论线性规划的对偶理论 王老板按（王老板按（D）的解的解 y1、y2出租其拥有的木、漆工资源，既保证了自出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使己不吃亏（出租资源

5、的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。最少）。按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着运筹学教程对偶问题Min w=YbT=YTbs.t.ATY CTY 0原始问题max z=CXs.t.AX bX 0maxbACCTATbTminmnmn运筹学教程 2、换个角度审视生产计划问题换个角度审视生产计划问题例例 要求制定一个生产计划方案，在设备要求制定一个生产计划方案，在设备A,B和调试

6、三种资源限制下，使得产品的总和调试三种资源限制下，使得产品的总利润最大利润最大。maxZmaxZ=2=2x1+x25x2156x1+2x224x1+x25x1,x20st.运筹学教程转换思路转换思路:投资人投资人:如果某投资公司准备购买该工厂，它至少应付出多大如果某投资公司准备购买该工厂，它至少应付出多大的代价，才能使工厂自己放弃生产产品的代价，才能使工厂自己放弃生产产品、，而将可利用，而将可利用的资源都出让。的资源都出让。被兼并人被兼并人:该工厂的底线：最低可接受价格，指按这种价格转该工厂的底线：最低可接受价格，指按这种价格转让资源比自己生产产品让资源比自己生产产品、合算的价格。合算的价格。

7、设设y1,y2，y3为代表单位时间这三种资源的出让价格，为了为代表单位时间这三种资源的出让价格，为了使工厂出让资源合算，显然应该使出让原来生产一件产品使工厂出让资源合算，显然应该使出让原来生产一件产品的资源所得收入不低于自己生产产品的资源所得收入不低于自己生产产品的利润，即的利润，即 0y1+6y2+1y3 2 对于产品对于产品，同样可以建立类似的约束条件，同样可以建立类似的约束条件 5y1+2y2+1y31项目产品产品每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润(元)21y1y2y3运筹学教程 当原问题和对偶问题都取得最优解时，这一对线当原问题和对偶问题都取得

8、最优解时，这一对线性规划对应的目标函数值是相等的：性规划对应的目标函数值是相等的：Zmax=Wmin显然在满足这两个约束的前提下，价格越高，该显然在满足这两个约束的前提下，价格越高，该工厂越合算，但价格太高，投资人方面又不会愿工厂越合算，但价格太高，投资人方面又不会愿意购买。因此，我们需要确定的价格是意购买。因此，我们需要确定的价格是 使工厂合算的最低价格，故应建立目标函数：使工厂合算的最低价格，故应建立目标函数：min w=15y1+24y2+5y3 项目项目产品产品产品产品每天可用每天可用能力能力设备设备A(h)设备设备B(h)调试工序调试工序(h)06152115245利润利润(元元)2

9、1运筹学教程 考察原问题和对偶问题的解，给作决考察原问题和对偶问题的解，给作决策的管理者另一个自由度；策的管理者另一个自由度；怎样通过增加更多的资源来增加利润？怎样通过增加更多的资源来增加利润？怎样使用不同类型的资源来增加利润？怎样使用不同类型的资源来增加利润？对应第一个约束条件对应第一个约束条件 对应第二个约束条件对应第二个约束条件（P）max Z=2X1+X2 5X2 15 对应第一个对偶变量对应第一个对偶变量 y1 6X1+2X2 24 对应第二个对偶变量对应第二个对偶变量 y2 X1+X2 5 对应第三个对偶变量对应第三个对偶变量 y3 X1，X2 0 （D）min w=15y1+24

10、y2+5y3 6y2+y3 2 5y1+2y2+y3 1 y1，y2，y3 0运筹学教程二、原问题和对偶问题的关系二、原问题和对偶问题的关系1、对称形式的对偶关系、对称形式的对偶关系（1）定义：若原问题是）定义：若原问题是 运筹学教程则定义其对偶问题为则定义其对偶问题为这两个式子之间的变换关系称为这两个式子之间的变换关系称为“对称形式的对偶关系对称形式的对偶关系”。运筹学教程运筹学教程（2）对称形式的对偶关系的矩阵描述）对称形式的对偶关系的矩阵描述（D）（L）（3）从原问题写出其对偶问题）从原问题写出其对偶问题按照定义；按照定义；记忆法则：记忆法则：“上、下上、下”交换，换后矩阵转置。交换，换

11、后矩阵转置。不等式变号，不等式变号，“极大极大”变变“极小极小”运筹学教程例例 写出下面线性规划的对偶问题：写出下面线性规划的对偶问题：运筹学教程y2=y2-y2y3=-y32、非对称形式的对偶关系：、非对称形式的对偶关系：（1）原问题原问题对偶问题对偶问题运筹学教程（2）怎怎样样写写出出非非对对称称形形式式的的对对偶偶问问题题？把把一一个个等等式式约约束束写写成成两两个个不不等等式式约约束束，再根据对称形式的对偶关系定义写出；再根据对称形式的对偶关系定义写出；按照原按照原-对偶表直接写出对偶表直接写出；（3）原）原-对偶表对偶表运筹学教程项目项目原问题原问题（对偶问题）（对偶问题）对偶问题对

12、偶问题（原问题）（原问题）目标函数类型目标函数类型maxmin目标函数系数与右边项目标函数系数与右边项的对应关系的对应关系目标函数各变量系数对应目标函数各变量系数对应约束条件右边项的系数约束条件右边项的系数右边项的系数对应目标函数右边项的系数对应目标函数系数系数变量个数与约束条件个变量个数与约束条件个数的对应关系数的对应关系变量个数变量个数 n约束条件个数约束条件个数 m约束条件个数约束条件个数 n变量个数变量个数 m原问题变量类型与对偶原问题变量类型与对偶问题约束条件类型的对问题约束条件类型的对应关系应关系 0(对称对称)变量类型变量类型 0(非对称非对称)自由自由 (对称对称)约束条件类型

13、约束条件类型 (非对称非对称)=原问题约束条件类型与原问题约束条件类型与对偶问题变量类型的对对偶问题变量类型的对应关系应关系 (非对称非对称)约束条件类型约束条件类型 (对称对称)=(非对称非对称)变量类型变量类型 (对称对称)自由自由运筹学教程例题：写出下面线性规划的对偶规划：例题：写出下面线性规划的对偶规划：运筹学教程（原原问问题题是是极极小小化化问问题题，因因此此应应从从原原-对对偶偶表表的的右边右边往往左边左边查！查！）项目项目原问题原问题（对偶问（对偶问题）题）对偶问题对偶问题（原问题）（原问题）目标函数类型目标函数类型maxmin原问题变量类原问题变量类型与对偶问题型与对偶问题约束

14、条件类型约束条件类型的对应关系的对应关系 0(对称对称)变量类型变量类型 0(非对称非对称)自由自由 (对称对称)约束条件类型约束条件类型 (非对称非对称)=原问题约束条原问题约束条件类型与对偶件类型与对偶问题变量类型问题变量类型的对应关系的对应关系 (非对称非对称)约束条件类型约束条件类型 (对称对称)=(非对称非对称)变量类型变量类型 (对对称称)自由自由运筹学教程第二节第二节对偶问题的基本性质对偶问题的基本性质原问题对偶问题为对称形式的线性规划问题原问题对偶问题为对称形式的线性规划问题运筹学教程 一、一、单纯形法的矩阵描述单纯形法的矩阵描述进一步讨论修正单纯形法进一步讨论修正单纯形法便于

15、理论推导（如对偶定理的证明）便于理论推导（如对偶定理的证明）二、矩阵描述二、矩阵描述关键关键写出两个基本的表达式。写出两个基本的表达式。2.1单纯形法的矩阵描述单纯形法的矩阵描述运筹学教程1、准备工作：、准备工作：（1）标准型的矩阵形式）标准型的矩阵形式（2）将式中矩阵写成分块矩阵形式）将式中矩阵写成分块矩阵形式 运筹学教程2 2、将将将将分分分分块块块块形形形形式式式式代代代代入入入入矩矩矩矩阵阵阵阵形形形形式式式式标标标标准准准准型型型型，得得得得出出出出两两两两个个个个基基基基本本本本表达式：表达式：表达式：表达式：（1）由约束条件）由约束条件 可得可得用非基变量表示基变量的表达式：用非

16、基变量表示基变量的表达式：运筹学教程项目非基变量基变量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 N,B-

17、1.约束系数矩阵的向量变化：约束系数矩阵的向量变化：PjT =B-1 PjCBCN0运筹学教程检验数：检验数：CN-CB B-1 N0 (1);-CB B-1 0;令令:CB-CBI=0 (2)(1)+(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 -C -CB B B B-1-1 0;0;令令Y YT T=C CB B B B-1-1 单纯形乘子单纯形乘子 A AT TY CY CT;T;Y0 Y0 WminWmin=Y YT Tb b=C CB BB B-1-1b=b=Z

18、maxZmaxC-YTA 0C YTA C T(YTA)T检验数的相反数为其对检验数的相反数为其对偶问题的一个可行解偶问题的一个可行解运筹学教程例例 原问题、对偶问题之间的关系原问题、对偶问题之间的关系项目原问题变量原问题松弛变量 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/2

19、Cj-zj 15/2 0 07/2 3/2原问题松弛变量原问题 变量 x3 x4 x5x1 x2运筹学教程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运筹学教程二、对偶问题的基本性质二、对偶问题的基本性质 对偶基本性质揭示对偶基本性质揭示原问题的解与对偶问题的解之间关系原问题的解与对偶问题的解之间关系 补充补充:对称性定理对称性定理 对偶问题的对偶是原问题对偶问题

20、的对偶是原问题。定定理理1 弱弱对对偶偶定定理理若若一一对对对对称称形形式的对偶线性规划式的对偶线性规划（L）和和 （D）均有可行解，分别为均有可行解，分别为 和和 ，则，则C b。证证明明思思路路：由由（L）左乘左乘 ，得，得 由由（D）右乘右乘 ，得，得 运筹学教程该结论对非对称形式的对偶问题同样成立该结论对非对称形式的对偶问题同样成立。推推论:关于关于“界界”的结果；的结果；极小化问题有下界极小化问题有下界推推论论1 原原问问题题(极极极极大大大大化化化化问问问问题题题题)的的任任意意一一个个可可行行解解所所对对应应的的目目标标函函数数值值是是其其对对偶偶问问题题目目标标函函数数值值的的

21、一个下界。一个下界。运筹学教程极大化问题有上界极大化问题有上界推论推论1 对偶问题对偶问题(极小化问题极小化问题极小化问题极小化问题)的任意一个可的任意一个可行解所对应的目标函数值是其原问题目标行解所对应的目标函数值是其原问题目标函数值的一个上界。函数值的一个上界。关于最优解无界情况与对偶问题的关系；关于最优解无界情况与对偶问题的关系；推论推论2 若原问题可行，则其目标函数无界若原问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。的充要条件是对偶问题没有可行解。运筹学教程推论推论3原原问问题题可可行行，且且目目标标函函数数值值无无界界=对偶问题不可行对偶问题不可行对对偶偶问问题题可可行

22、行，且且目目标标函函数数值值无无界界=原问题不可行原问题不可行若对偶问题不可行，其原问题若对偶问题不可行，其原问题或或或或没有可没有可行解行解或或或或无界解。无界解。原问题有可行解而其对偶问题没有原问题有可行解而其对偶问题没有可行解，可行解，则原问题的目标函数无界；则原问题的目标函数无界；对偶问题有可行解而其原问题没有可行解，对偶问题有可行解而其原问题没有可行解，则对偶问题的目标函数无界；则对偶问题的目标函数无界；运筹学教程定理定理 2 最优性定理最优性定理 若若、分别分别为对称形式对偶线性规划的可行解，为对称形式对偶线性规划的可行解，且两者目标函数的相应值相等，即且两者目标函数的相应值相等，

23、即C =b ，则则 ，分别为原问题和分别为原问题和对偶问题的最优解。对偶问题的最优解。运筹学教程CX=Y CX=Y b bCX*Y*b弱对偶弱对偶定定理理已已知知结论结论Y*bYY b因因为为XY可可行行解解CXCX*证明思路证明思路 设设X*,Y*分别为原问题和对偶问题的最优解分别为原问题和对偶问题的最优解;X,Y分别为原问分别为原问题和对偶问题的可行解题和对偶问题的可行解CXCX*Y*bY b=CXCX=CX*=Y*b=Y b运筹学教程3 3 3 3、强对偶性强对偶性强对偶性强对偶性 若原问题和对偶问题两者若原问题和对偶问题两者若原问题和对偶问题两者若原问题和对偶问题两者均具有可行解，则两

24、者均有最优解，且此时均具有可行解，则两者均有最优解，且此时均具有可行解，则两者均有最优解，且此时均具有可行解，则两者均有最优解，且此时目标函数值相同。目标函数值相同。目标函数值相同。目标函数值相同。都有可行解都有可行解各自有上下界各自有上下界都有最优解都有最优解目标函数值相等目标函数值相等证明要点：证明要点：运筹学教程定理定理定理定理4 4 互补松弛性互补松弛性 在线性规划问题的最优解在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其

25、对应的对偶变量一定为零。取严格不等式，则其对应的对偶变量一定为零。证明证明弱对偶性弱对偶性最优性最优性此定理适用于此定理适用于非对称形式非对称形式(1)式应取式应取=运筹学教程例:已知线性规划其最优解为x=(6,2,0)T,求对偶问题的最优解26+22+0=16;y206+22+0=10;y10运筹学教程x1=60;约束条件为=x2=20;约束条件为=x3=0;约束条件为求解结果为Y=(1,1)TMin W=26运筹学教程n思考题n如何理解对偶问题的基本性质？如何理解对偶问题的基本性质？n讨论题讨论题n用例子说明互补松弛性的实际应用。用例子说明互补松弛性的实际应用。运筹学教程n小结n对偶问题的基本性质。n对偶定理。n作业:n 2.1(1),2.3,2.7