对偶理论第三章线性规划优秀PPT.ppt

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

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

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

3、料商竞争条件下，营养药品，在满足牲畜营养要求且可与饲料商竞争条件下，四种药品如何定价可使总收入最大四种药品如何定价可使总收入最大？你现在浏览的是第六页，共47页你现在浏览的是第七页，共47页你现在浏览的是第八页，共47页对称的对偶问题原问题原问题对偶问题对偶问题你现在浏览的是第九页，共47页对称的对偶问题原问题原问题对偶问题对偶问题你现在浏览的是第十页，共47页非对称的对偶问题原问题原问题对偶问题对偶问题你现在浏览的是第十一页，共47页混合形式的对偶问题混合形式的对偶问题你现在浏览的是第十二页，共47页 原问题和对偶问题的关系原问题和对偶问题的关系你现在浏览的是第十三页，共47页原问题（对偶问

4、题）原问题（对偶问题）约束条件约束条件对偶问题（原问题）对偶问题（原问题）决策变量决策变量max约束为正向正向约束为反向反向约束为双向双向变量0为正向正向变量0为反向反向变量无约束为双向双向min约束为正向正向约束为反向反向约束为双向双向原问题和对偶问题的关系原问题和对偶问题的关系你现在浏览的是第十四页，共47页二、对偶问题的基本性质二、对偶问题的基本性质1.1.弱对偶性：弱对偶性：若若X X和和Y Y分别是原问题和对偶问题的任一可行解，则必有分别是原问题和对偶问题的任一可行解，则必有该性质告诉我们，最大化问题的任一可行解的目标函数值都是其对偶最小化问题目标函数的该性质告诉我们，最大化问题的任

5、一可行解的目标函数值都是其对偶最小化问题目标函数的下界；而最小化问题的任一可行解的目标函数值都是其对偶最大化问题目标函数的上界。下界；而最小化问题的任一可行解的目标函数值都是其对偶最大化问题目标函数的上界。2 2.强对偶性：强对偶性：若若 分别为原问题和对偶问题的可行解，且可行解分别为原问题和对偶问题的可行解，且可行解对应的原问题和对偶问题的目标函数值相等，即对应的原问题和对偶问题的目标函数值相等，即 ，则，则 分别为原问题和对偶问题的最优解。分别为原问题和对偶问题的最优解。（最优性准则）（对偶可行性）（最优性准则）（对偶可行性）你现在浏览的是第十五页，共47页二、对偶问题的基本性质二、对偶问

6、题的基本性质（续）（续）6.6.若原问题的最优解为若原问题的最优解为 3.3.无界性无界性 若原问题（对偶问题）的目标函数无界，则其对偶若原问题（对偶问题）的目标函数无界，则其对偶 问题（原问题）必无可行解。问题（原问题）必无可行解。该性质说明，原问题和对偶问题之一无最优解，则另一个也该性质说明，原问题和对偶问题之一无最优解，则另一个也无最优解。无最优解。4.4.对偶定理对偶定理 若原问题和对偶问题之一有最优解，则另一个也若原问题和对偶问题之一有最优解，则另一个也 也有最优解，且两者的最优目标函数值相等。也有最优解，且两者的最优目标函数值相等。5.5.若原问题和对偶问题同时有可行解，则他们必都

7、有最优解。若原问题和对偶问题同时有可行解，则他们必都有最优解。你现在浏览的是第十六页，共47页7.7.根据原问题最优单纯形表中的检验数可以读出对偶问题的根据原问题最优单纯形表中的检验数可以读出对偶问题的 最优解。最优解。例例1、原问题原问题对偶问题对偶问题你现在浏览的是第十七页，共47页 原问题原问题标准型标准型你现在浏览的是第十八页，共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

8、 1 1 0 0 1908045-f5 4 0 0 00初始单纯形表初始单纯形表最优单纯形表最优单纯形表原问题原问题54000054你现在浏览的是第十九页，共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你现在浏览的是第二十页，共47页对偶问题对偶问题你现在浏览的是第二十一页，共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.一个问题具有无界解，则另一个问题无可行解。一个问题具有无界解，则另一个问题无可行解。你现在浏览的是第二十二页，共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

10、 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-42maxf=5X1+8X2+6X3X1+X2+2X36X1+2X2+2X310X1，X2,X20你现在浏览的是第二十三页，共47页例例3 已知线性规划问题已知线性规划问题试用对偶理论证明上述问题无最优解。试用对偶理论证明上述问题无最优解。你现在浏览的是第二十四页，共47页三、对偶解的经济涵义三、对偶解的经济涵义影子价格影子价格通过求解：原问题和对偶问题的最优解分别为通过求解：原问题和对偶问题的最优解分别为 你现在浏览的是第二十五页，共47页1.影子价格的定义

11、影子价格的定义 对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的种资源的影子价格影子价格（Shadow Price）。）。影子价格影子价格是指在最优解的基础上，当第是指在最优解的基础上，当第 i 个约束条件的右端项个约束条件的右端项 bi 增加一个单位时，目标函数的变化量。增加一个单位时，目标函数的变化量。由对偶定理可知由对偶定理可知，当达到最优解时，原问题与对偶问题的目标函当达到最优解时，原问题与对偶问题的目标函数值相等，即有数值相等，即有f*=CX*=Y*b=y1*b1+y2*b2+ym*bm 现考虑在最优解处，右端项现

12、考虑在最优解处，右端项bi的微小变动对目标函数值的的微小变动对目标函数值的影响，由上式，将影响，由上式，将f*对对bi求偏导数：求偏导数：该式表明了，若原问题的某一个约束条件的右端项该式表明了，若原问题的某一个约束条件的右端项bi每增加一个每增加一个单位，则由此引起的最优目标函数值的增加量，就等于与该约束条件单位，则由此引起的最优目标函数值的增加量，就等于与该约束条件相对应的对偶变量的最优解的值。相对应的对偶变量的最优解的值。你现在浏览的是第二十六页，共47页2.影子价格的求法影子价格的求法例例4 某工厂生产三种产品，三种产品对于原材料、劳动力、电力某工厂生产三种产品，三种产品对于原材料、劳动

13、力、电力的单位消耗系数，资源限量和单位产品价格如下表所示：的单位消耗系数，资源限量和单位产品价格如下表所示：ABC资源限量资源限量原材料原材料（kg）劳动力（人）劳动力（人）电力（度）电力（度）2652.5154810320640750单位价格（元）单位价格（元）4610资源资源产品产品1.求最佳生产方案使总产值最大。求最佳生产方案使总产值最大。2.求各资源的影子价格，并解释其经济意义。求各资源的影子价格，并解释其经济意义。你现在浏览的是第二十七页，共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

14、-1 0 0.54016055-f-1 0 0 -2 0 -0.2-790你现在浏览的是第二十八页，共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你现在浏览的是第二十九页，共47页3.影子价格的作用影子价格的作用影子价格可以告诉管理人员，增加哪一种资源对增加经济效益最有益。影子价格可以告诉管理人员，增加哪一种资源对增加经济效益最有益。影子价格可以告诉管理人员，花多大的代价增加资源才是合算的。影子价格可以告诉管理人员，花多大

15、的代价增加资源才是合算的。影子价格在新产品开发决策中的应用。影子价格在新产品开发决策中的应用。影子价格在资源购销决策中的应用。影子价格在资源购销决策中的应用。利用影子价格分析工艺改变后对资源节约的收益。利用影子价格分析工艺改变后对资源节约的收益。如在上例中，当工艺改进后，使原材料节约如在上例中，当工艺改进后，使原材料节约10%，则带来的经济效益为：，则带来的经济效益为：2 320 10%=64（元）（元）你现在浏览的是第三十页，共47页在利润最大化的生产计划中在利润最大化的生产计划中（1）边际利润大于）边际利润大于0的资源没有剩余的资源没有剩余（2）有剩余的资源边际利润等于）有剩余的资源边际利

16、润等于0关于影子价格的几点说明：关于影子价格的几点说明：你现在浏览的是第三十一页，共47页影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于格一定等于0影子价格为影子价格为0，资源并不一定有剩余，资源并不一定有剩余影子价格是资源最优配置下资源的理想价格，资源的影子价格是资源最优配置下资源的理想价格，资源的影子价格与资源的紧缺度有关影子价格与资源的紧缺度有关你现在浏览的是第三十二页，共47页

17、思路：思路：(max型型)单纯形法单纯形法：找基：找基B B，满足，满足B-1b 0，但检验数但检验数C-CBB-1 A不全不全 0。迭代迭代保持保持B-1b 0，使使C-CBB-1 A 0。对偶单纯形法对偶单纯形法：找基：找基B B，满足，满足C-CBB-1 A 0，但但B-1b不全不全 0。迭代迭代保持保持C-CBB-1 A 0，使使B-1b 0。四、对偶单纯形法四、对偶单纯形法你现在浏览的是第三十三页，共47页举例原问题对偶问题你现在浏览的是第三十四页，共47页xj x1 x2 x3 x4 x5 B-1bx3x4x50 5 1 0 0 6 2 0 1 0 1 1 0 0 115245-f

18、2 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 0 1 0 -1/4 3/215/27/23/2-f0 0 0 -1/4 -1/2-17/2你现在浏览的是第三十五页，共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 -

19、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你现在浏览的是第三十六页，共47页例例1 1max f=2x1+x2x1+x2+x3=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你现在浏览的是第三十七页，共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

20、 -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你现在浏览的是第三十八页，共47页例例2.标准化标准化找初始基变量找初始基变量你现在浏览的是第三十九页，共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

21、/31-1/30-7/30-1/3 04/3你现在浏览的是第四十页，共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 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(课本）课本）

22、你现在浏览的是第四十一页，共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你现在浏览的是第四十二页，共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

23、1 0 7/5 -1/5 -2/52/512/5-f0 0 -9/5 -8/5 -1/5 28/5你现在浏览的是第四十三页，共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该问题无可行解。该问题无可行解。你现在浏览的是第四十四页，共47页对偶单纯形法基本步骤对偶单纯形法基本步骤 （max型）型）1、标准化（化标准型）；标准化（化标准型）；2、寻找第一个正则解，建立初始单纯形表；寻找第一个正则解，建立初始单纯形表；3、判别可行性：判别可行性：（1 1）若所有）若所有b bi i

24、0,0,则得到最优解，则得到最优解，（2 2）若对于若对于bk 0，有，有akj 0(均），均），则无可行解，停止计算。则无可行解，停止计算。否则，换基迭代。否则，换基迭代。4、选择、选择bl=minbi/bi 0=bl,i=1.m,确定基变量确定基变量xl出基；出基；5、你现在浏览的是第四十五页，共47页6 6、以、以alk 为中心进行单纯形迭代，得一新单纯为中心进行单纯形迭代，得一新单纯形表，同时得到一新的正则解；形表，同时得到一新的正则解；7 7、返回第、返回第3 3步，直到获得可行解，即得到最优解。步，直到获得可行解，即得到最优解。你现在浏览的是第四十六页，共47页课堂练习：1、用单纯形方法求解2、写出上述问题的对偶规划，并求出对偶问题的最优解3、用对偶单纯形方法求解你现在浏览的是第四十七页，共47页