对偶理论第三章线性规划精选PPT.ppt

《对偶理论第三章线性规划精选PPT.ppt》由会员分享，可在线阅读，更多相关《对偶理论第三章线性规划精选PPT.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、对偶理论第三章线性规划第1页，此课件共47页哦该问题的数学模型如如果果设设A、B两两种种产产品品生生产产的的件件数数分分别别为为 ,则则这这个个问问题题可可以以归结为求解下列线性规划问题：归结为求解下列线性规划问题：第2页，此课件共47页哦其对偶问题的数学模型设设 分别表示设备甲、乙、丙每台时的价格（或租金）分别表示设备甲、乙、丙每台时的价格（或租金）,则则第3页，此课件共47页哦例例2、每头牲畜每日对各种维生素的需求量及饲料商提供的营养饲料每头牲畜每日对各种维生素的需求量及饲料商提供的营养饲料M和和N中各种维生素含量及定价如下表所示，牧场主在保证牲畜维生素中各种维生素含量及定价如下表所示，牧

2、场主在保证牲畜维生素需求条件下，每日为每头牲畜购需求条件下，每日为每头牲畜购M、N各多少可使总费用最少？各多少可使总费用最少？MN日需要量日需要量ABCD0.100.10.200.10.20.10.40.62.01.7定价定价104维生素维生素营养饲料营养饲料第4页，此课件共47页哦设每日每头牲畜需营养饲料设每日每头牲畜需营养饲料M、N分别为分别为 ，则该问题的线，则该问题的线性规划模型为：性规划模型为：第5页，此课件共47页哦已知条件同上例，某药品商想提供畜用维生素已知条件同上例，某药品商想提供畜用维生素A、B、C、D四种四种营养药品，在满足牲畜营养要求且可与饲料商竞争条件下，四营养药品，在

3、满足牲畜营养要求且可与饲料商竞争条件下，四种药品如何定价可使总收入最大种药品如何定价可使总收入最大？第6页，此课件共47页哦第7页，此课件共47页哦第8页，此课件共47页哦对称的对偶问题原问题原问题对偶问题对偶问题第9页，此课件共47页哦对称的对偶问题原问题原问题对偶问题对偶问题第10页，此课件共47页哦非对称的对偶问题原问题原问题对偶问题对偶问题第11页，此课件共47页哦混合形式的对偶问题混合形式的对偶问题第12页，此课件共47页哦 原问题和对偶问题的关系原问题和对偶问题的关系第13页，此课件共47页哦原问题（对偶问题）原问题（对偶问题）约束条件约束条件对偶问题（原问题）对偶问题（原问题）决

4、策变量决策变量max约束为正向正向约束为反向反向约束为双向双向变量0为正向正向变量0为反向反向变量无约束为双向双向min约束为正向正向约束为反向反向约束为双向双向原问题和对偶问题的关系原问题和对偶问题的关系第14页，此课件共47页哦二、对偶问题的基本性质二、对偶问题的基本性质1.1.弱对偶性：弱对偶性：若若X X和和Y Y分别是原问题和对偶问题的任一可行解，则必有分别是原问题和对偶问题的任一可行解，则必有该性质告诉我们，最大化问题的任一可行解的目标函数值都是其对偶最小化问题该性质告诉我们，最大化问题的任一可行解的目标函数值都是其对偶最小化问题目标函数的下界；而最小化问题的任一可行解的目标函数值

5、都是其对偶最大化问目标函数的下界；而最小化问题的任一可行解的目标函数值都是其对偶最大化问题目标函数的上界。题目标函数的上界。2 2.强对偶性：强对偶性：若若 分别为原问题和对偶问题的可行解，且可行解对应的原问分别为原问题和对偶问题的可行解，且可行解对应的原问题和对偶问题的目标函数值相等，即题和对偶问题的目标函数值相等，即 ，则，则 分别为原问题和对偶问分别为原问题和对偶问题的最优解。题的最优解。（最优性准则）（对偶可行性）（最优性准则）（对偶可行性）第15页，此课件共47页哦二、对偶问题的基本性质二、对偶问题的基本性质（续）（续）6.6.若原问题的最优解为若原问题的最优解为 3.3.无界性无界

6、性 若原问题（对偶问题）的目标函数无界，则其对偶若原问题（对偶问题）的目标函数无界，则其对偶 问题（原问题）必无可行解。问题（原问题）必无可行解。该性质说明，原问题和对偶问题之一无最优解，则另一个也该性质说明，原问题和对偶问题之一无最优解，则另一个也无最优解。无最优解。4.4.对偶定理对偶定理 若原问题和对偶问题之一有最优解，则另一个也若原问题和对偶问题之一有最优解，则另一个也 也有最优解，且两者的最优目标函数值相等。也有最优解，且两者的最优目标函数值相等。5.5.若原问题和对偶问题同时有可行解，则他们必都有最优解。若原问题和对偶问题同时有可行解，则他们必都有最优解。第16页，此课件共47页哦

7、7.7.根据原问题最优单纯形表中的检验数可以读出对偶问题的根据原问题最优单纯形表中的检验数可以读出对偶问题的 最优解。最优解。例例1、原问题原问题对偶问题对偶问题第17页，此课件共47页哦 原问题原问题标准型标准型第18页，此课件共47页哦xj x1 x2 x3 x4 x5 B-1bx3x1x20 0 1 2 -5 1 0 0 1 -1 0 1 0 -1 2253510-f0 0 0 -1 -3-215xj x1 x2 x3 x4 x5 bx3x4x51 2 1 0 0 2 1 0 1 0 1 1 0 0 1908045-f5 4 0 0 00初始单纯形表初始单纯形表最优单纯形表最优单纯形表原

8、问题原问题54000054第19页，此课件共47页哦常用单纯形表的矩阵形式常用单纯形表的矩阵形式 XB XN XSbXS B N Ib-f CB CN 00CBCN 0 0XB I B-1N B-1B-1b-f 0 CN-CBB-1N -CBB-1 -CBB-1bCB第20页，此课件共47页哦对偶问题对偶问题第21页，此课件共47页哦 y1 y2 y3 y4 y5B-1by2y3-2 1 0 -1 1 5 0 1 1 -2 13-g-25 0 0 -35 -10215对偶问题最优单纯形表：对偶问题最优单纯形表：综上所述，一对对偶问题的解必然是下列三种情况之一：综上所述，一对对偶问题的解必然是下

9、列三种情况之一：1.原问题和对偶问题都有最优解，且最优目标函数值相等。原问题和对偶问题都有最优解，且最优目标函数值相等。3.原问题和对偶问题都无可行解。原问题和对偶问题都无可行解。2.一个问题具有无界解，则另一个问题无可行解。一个问题具有无界解，则另一个问题无可行解。第22页，此课件共47页哦C Cj j5 58 86 60 00 0C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5B B-1-1b b5 58 8X X1 1X X2 21 10 00 01 12 20 02 2-1-1-1-11 12 24 4j j0 00 0-4-4-2-2-3-3-42

10、-42maxf=5X1+8X2+6X3X1+X2+2X36X1+2X2+2X310X1，X2,X20第23页，此课件共47页哦例例3 已知线性规划问题已知线性规划问题试用对偶理论证明上述问题无最优解。试用对偶理论证明上述问题无最优解。第24页，此课件共47页哦三、对偶解的经济涵义三、对偶解的经济涵义影子价格影子价格通过求解：原问题和对偶问题的最优解分别为通过求解：原问题和对偶问题的最优解分别为 第25页，此课件共47页哦1.影子价格的定义影子价格的定义 对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的种资源的影子价格影子价格

11、（Shadow Price）。）。影子价格影子价格是指在最优解的基础上，当第是指在最优解的基础上，当第 i 个约束条件的右端项个约束条件的右端项 bi 增加一个单位时，目标函数的变化量。增加一个单位时，目标函数的变化量。由对偶定理可知由对偶定理可知，当达到最优解时，原问题与对偶问题的目标函数值当达到最优解时，原问题与对偶问题的目标函数值相等，即有相等，即有f*=CX*=Y*b=y1*b1+y2*b2+ym*bm 现考虑在最优解处，右端项现考虑在最优解处，右端项bi的微小变动对目标函数值的影的微小变动对目标函数值的影响，由上式，将响，由上式，将f*对对bi求偏导数：求偏导数：该式表明了，若原问题

12、的某一个约束条件的右端项该式表明了，若原问题的某一个约束条件的右端项bi每增加一个每增加一个单位，则由此引起的最优目标函数值的增加量，就等于与该约单位，则由此引起的最优目标函数值的增加量，就等于与该约束条件相对应的对偶变量的最优解的值。束条件相对应的对偶变量的最优解的值。第26页，此课件共47页哦2.影子价格的求法影子价格的求法例例4 某工厂生产三种产品，三种产品对于原材料、劳动力、电力的单某工厂生产三种产品，三种产品对于原材料、劳动力、电力的单位消耗系数，资源限量和单位产品价格如下表所示：位消耗系数，资源限量和单位产品价格如下表所示：ABC资源限量资源限量原材料原材料（kg）劳动力（人）劳动

13、力（人）电力（度）电力（度）2652.5154810320640750单位价格（元）单位价格（元）4610资源资源产品产品1.求最佳生产方案使总产值最大。求最佳生产方案使总产值最大。2.求各资源的影子价格，并解释其经济意义。求各资源的影子价格，并解释其经济意义。第27页，此课件共47页哦xj x1 x2 x3 x4 x5 x6 B-1bx2x5x30 1 0 2 0 -0.8 2 0 0 6 1 -3.2 1/2 0 1 -1 0 0.54016055-f-1 0 0 -2 0 -0.2-790第28页，此课件共47页哦xj x1 x2 x3 x4 x5 x6 B-1bx2x5x30 1 0

14、2 0 -0.8 2 0 0 6 1 -3.2 1/2 0 1 -1 0 0.54016055-f-1 0 0 -2 0 -0.2-790第29页，此课件共47页哦3.影子价格的作用影子价格的作用影子价格可以告诉管理人员，增加哪一种资源对增加经济效益最有益。影子价格可以告诉管理人员，增加哪一种资源对增加经济效益最有益。影子价格可以告诉管理人员，花多大的代价增加资源才是合算的。影子价格可以告诉管理人员，花多大的代价增加资源才是合算的。影子价格在新产品开发决策中的应用。影子价格在新产品开发决策中的应用。影子价格在资源购销决策中的应用。影子价格在资源购销决策中的应用。利用影子价格分析工艺改变后对资源

15、节约的收益。利用影子价格分析工艺改变后对资源节约的收益。如在上例中，当工艺改进后，使原材料节约如在上例中，当工艺改进后，使原材料节约10%，则带来的经济效益为：，则带来的经济效益为：2 320 10%=64（元）（元）第30页，此课件共47页哦在利润最大化的生产计划中在利润最大化的生产计划中（1）边际利润大于）边际利润大于0的资源没有剩余的资源没有剩余（2）有剩余的资源边际利润等于）有剩余的资源边际利润等于0关于影子价格的几点说明：关于影子价格的几点说明：第31页，此课件共47页哦影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影

16、子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于于0影子价格为影子价格为0，资源并不一定有剩余，资源并不一定有剩余影子价格是资源最优配置下资源的理想价格，资源的影子影子价格是资源最优配置下资源的理想价格，资源的影子价格与资源的紧缺度有关价格与资源的紧缺度有关第32页，此课件共47页哦思路：思路：(max型型)单纯形法单纯形法：找基：找基B B，满足，满足B-1b 0，但检验数但检验数C-CBB-1 A不全不全 0。迭代迭代保持保持B-1b 0，使使C-CBB-1 A 0。对偶单纯形法对偶单纯

17、形法：找基：找基B B，满足，满足C-CBB-1 A 0，但但B-1b不全不全 0。迭代迭代保持保持C-CBB-1 A 0，使使B-1b 0。四、对偶单纯形法四、对偶单纯形法第33页，此课件共47页哦举例原问题对偶问题第34页，此课件共47页哦xj x1 x2 x3 x4 x5 B-1bx3x4x50 5 1 0 0 6 2 0 1 0 1 1 0 0 115245-f2 1 0 0 00 x3x1x50 5 1 0 0 1 1/3 0 1/6 0 0 2/3 0 -1/6 11541-f0 1/3 0 -1/3 0-8x3x1x20 0 1 5/4 -15/2 1 0 0 1/4 -1/2

18、0 1 0 -1/4 3/215/27/23/2-f0 0 0 -1/4 -1/2-17/2第35页，此课件共47页哦yi y1 y2 y3 y4 y5 B-1by4y50 -6 -1 1 0 -5 -2 -1 0 1-2-1-f-15 -24 -5 0 0 0y2y50 1 1/6 -1/6 0 -5 0 -2/3 -1/3 11/3-1/3-f-15 0 -1 -4 0 -8y2y3-5/4 1 0 -1/4 1/4 15/2 0 1 1/2 -3/21/41/2-f-15/2 0 0 -7/2 -3/2 -17/2第36页，此课件共47页哦例例1 1max f=2x1+x2x1+x2+x

19、3=5 2x2+x3 5 4x2+6x3 9x1 ,x2,x3 0max f=2x1+x2x1+x2+x3 =5 2x2+x3+x4 =5 -4x2 6x3 +x5=-9x1 x5 0第37页，此课件共47页哦xj x1 x2 x3 x4 x5 B-1bx1x4x51 1 1 0 0 0 2 1 1 0 0 -4 -6 0 155-9-f0 -1 -2 0 0-10210000200 x1x4x21 0 -1/2 0 1/4 0 0 -2 1 -1/2 0 1 3/2 0 -1/411/41/29/4-f0 0 -1/2 0 -1/4-31/4201第38页，此课件共47页哦例例2.标准化标准

20、化找初始基变量找初始基变量第39页，此课件共47页哦xj x1 x2 x3 x4 x5 bix3x4x5 2 2 1 0 0 -3 -2 0 1 0 1 2 0 0 13-41-f -1 -3 0 0 00 xj x1 x2 x3 x4 x5 B-1bx3x1x5 -f02/312/301/312/30-1/304/304/301/31-1/30-7/30-1/3 04/3第40页，此课件共47页哦Xj x1 x2 x3 x4 x5 B-1bx3x4x5 -2 -1 1 0 0 -3 -2 0 1 0 -1 -2 0 0 1-3-4-1-f -1 -3 0 0 00 x3x1x5 0 1/3

21、1 -2/3 0 1 2/3 0 -1/3 0 0 -4/3 0 -1/3 1-1/34/31/3-f 0 -7/3 0 -1/3 04/3x4x1x5 0 -1/2 -3/2 1 0 1 1/2 -1/2 0 0 0 -3/2 -1/2 0 11/23/21/2-f 0 -5/2 -1/2 0 03/2例例3(课本）课本）第41页，此课件共47页哦练习练习min f=2x1+3x2+4x3 x1+2x2+x3 32x1-x2+3x3 4x1 ,x2,x3 0min f=2x1+3x2+4x3-x1 2x2-x3+x4 =-3-2x1+x2 3x3 +x5=-4x1 x5 0第42页，此课件共

22、47页哦xi x1 x2 x3 x4 x5 B-1bx4x5-1 -2 -1 1 0 -2 1 -3 0 1-3-4-f-2 -3 -4 0 0 0 x4x10 -5/2 1/2 1 -1/2 1 -1/2 3/2 0 -1/2-12-f0 -4 -1 0 -1 4x2x10 1 -1/5 -2/5 1/5 1 0 7/5 -1/5 -2/52/512/5-f0 0 -9/5 -8/5 -1/5 28/5第43页，此课件共47页哦例例3xj x1 x2 x3 x4bix3x4 -1 1 1 0 2 -1 0 1 -1-1-f -1 -1 0 0 01-1-11012-30-2-11x1该问题无

23、可行解。该问题无可行解。第44页，此课件共47页哦对偶单纯形法基本步骤对偶单纯形法基本步骤 （max型）型）1、标准化（化标准型）；标准化（化标准型）；2、寻找第一个正则解，建立初始单纯形表；寻找第一个正则解，建立初始单纯形表；3、判别可行性：判别可行性：（1 1）若所有）若所有b bi i 0,0,则得到最优解，则得到最优解，（2 2）若对于若对于bk 0，有，有akj 0(均），均），则无可行解，停止计算。则无可行解，停止计算。否则，换基迭代。否则，换基迭代。4、选择、选择bl=minbi/bi 0=bl,i=1.m,确定基变量确定基变量xl出出基；基；5、第45页，此课件共47页哦6 6、以、以alk 为中心进行单纯形迭代，得一新单纯形为中心进行单纯形迭代，得一新单纯形表，同时得到一新的正则解；表，同时得到一新的正则解；7 7、返回第、返回第3 3步，直到获得可行解，即得到最优解。步，直到获得可行解，即得到最优解。第46页，此课件共47页哦课堂练习：1、用单纯形方法求解2、写出上述问题的对偶规划，并求出对偶问题的最优解3、用对偶单纯形方法求解第47页，此课件共47页哦