《对偶理论第三章线性规划优秀课件.ppt》由会员分享，可在线阅读，更多相关《对偶理论第三章线性规划优秀课件.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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页原问题（对偶问题）原问题（对偶问题）约束条件约束条件对偶问题（原问题）对偶问题（原问题）决策变量决策变量max约束为
4、正向正向约束为反向反向约束为双向双向变量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初始单纯形表初始单纯形表最优单纯形表最优单纯形表原问题原问题5 4 0 0 0054第
8、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对偶问题最优单纯形表：对偶问题最优单纯形表：综上所述，一对对偶问题的解必然是下列三种情况之一：综上所述，一对对偶问题的解必然是下列三种情况之一：1.原问题和对偶问
9、题都有最优解，且最优目标函数值相等。原问题和对偶问题都有最优解，且最优目标函数值相等。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-42maxf=5X1+8X2+6X
10、3X1+X2+2X36X1+2X2+2X310X1，X2,X20第23页，本讲稿共47页例例3 已知线性规划问题已知线性规划问题试用对偶理论证明上述问题无最优解。试用对偶理论证明上述问题无最优解。第24页，本讲稿共47页三、对偶解的经济涵义三、对偶解的经济涵义影子价格影子价格通过求解：原问题和对偶问题的最优解分别为通过求解：原问题和对偶问题的最优解分别为 第25页，本讲稿共47页1.影子价格的定义影子价格的定义 对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的种资源的影子价格影子价格（Shadow Price）。）。影子价格
11、影子价格是指在最优解的基础上，当第是指在最优解的基础上，当第 i 个约束条件的右个约束条件的右端项端项 bi 增加一个单位时，目标函数的变化量。增加一个单位时，目标函数的变化量。由对偶定理可知由对偶定理可知，当达到最优解时，原问题与对偶问题的目当达到最优解时，原问题与对偶问题的目标函数值相等，即有标函数值相等，即有f*=CX*=Y*b=y1*b1+y2*b2+ym*bm 现考虑在最优解处，右端项现考虑在最优解处，右端项bi的微小变动对目标函数值的微小变动对目标函数值的影响，由上式，将的影响，由上式，将f*对对bi求偏导数：求偏导数：该式表明了，若原问题的某一个约束条件的右端项该式表明了，若原问
12、题的某一个约束条件的右端项bi每增加每增加一个单位，则由此引起的最优目标函数值的增加量，就等于一个单位，则由此引起的最优目标函数值的增加量，就等于与该约束条件相对应的对偶变量的最优解的值。与该约束条件相对应的对偶变量的最优解的值。第26页，本讲稿共47页2.影子价格的求法影子价格的求法例例4 某工厂生产三种产品，三种产品对于原材料、劳动力、某工厂生产三种产品，三种产品对于原材料、劳动力、电力的单位消耗系数，资源限量和单位产品价格如下表电力的单位消耗系数，资源限量和单位产品价格如下表所示：所示：ABC资源限量资源限量原材料原材料（kg）劳动力（人）劳动力（人）电力（度）电力（度）2652.515
13、4810320640750单位价格（元）单位价格（元）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 2 0 -0.8 2 0 0 6 1 -3.2
14、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。对偶单纯形法对偶单纯形法：找基：找基B B，满足，满足C-CBB-1 A 0
17、，但但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 0 1 0 -1/4 3/215/27/23/2-f0 0
18、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+x3=5 2x2+x3 5 4x2+6x3 9x1 ,x2,x3
19、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-102 1 0 0 0 0200 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.标准化标准化找初始基变量找初始基变量第39页，本讲稿共47页xj x
20、1 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 1 -2/3 0 1 2/3 0 -1/3 0 0 -4/3
21、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页，本讲稿共47页xi x1 x2 x3 x4 x5 B-1bx4x5-1
22、-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该问题无可行解。该问题无可行解。第44页，本讲稿共47页对偶单纯形法基本步骤
23、对偶单纯形法基本步骤 （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页