对偶理论(第三章线性规划3).ppt

1、对偶理论,一、原问题与对偶问题 例1、某厂在计划期内要安排生产A、B两种产品，这两种产品分别需要在甲、乙丙三种不同的设备上加工，有关数据如表3-14所示。问应如何安排生产计划才能使利润最大？,该问题的数学模型,如果设A、B两种产品生产的件数分别为 ,则这个问题可以归结为求解下列线性规划问题：,其对偶问题的数学模型,设 分别表示设备甲、乙、丙每台时的价格（或租金）,则,例2、每头牲畜每日对各种维生素的需求量及饲料商提供的营养饲料M和N中各种维生素含量及定价如下表所示，牧场主在保证牲畜维生素需求条件下，每日为每头牲畜购M、N各多少可使总费用最少？,设每日每头牲畜需营养饲料M、N分别为 ，则该问题的

2、线性规划模型为：,已知条件同上例，某药品商想提供畜用维生素A、B、C、D四种营养药品，在满足牲畜营养要求且可与饲料商竞争条件下，四种药品如何定价可使总收入最大？,对称的对偶问题,原问题,对偶问题,对称的对偶问题,原问题,对偶问题,非对称的对偶问题,原问题,对偶问题,混合形式的对偶问题,原问题和对偶问题的关系,原问题和对偶问题的关系,二、对偶问题的基本性质,1.弱对偶性：若X和Y分别是原问题和对偶问题的任一可行解，则必有,该性质告诉我们，最大化问题的任一可行解的目标函数值都是其对偶最小化问题目标函数的下界；而最小化问题的任一可行解的目标函数值都是其对偶最大化问题目标函数的上界。,2.强对偶性：若

3、 分别为原问题和对偶问题的可行解，且可行解对应的原问题和对偶问题的目标函数值相等，即 ，则 分别为原问题和对偶问题的最优解。（最优性准则）（对偶可行性）,二、对偶问题的基本性质 （续）,6. 若原问题的最优解为,3.无界性 若原问题（对偶问题）的目标函数无界，则其对偶 问题（原问题）必无可行解。,该性质说明，原问题和对偶问题之一无最优解，则另一个也 无最优解。,4.对偶定理 若原问题和对偶问题之一有最优解，则另一个也 也有最优解，且两者的最优目标函数值相等。,5. 若原问题和对偶问题同时有可行解，则他们必都有最优解。,7.根据原问题最优单纯形表中的检验数可以读出对偶问题的 最优解。,例1、 原

4、问题,对偶问题,原问题,标准型,初始单纯形表,最优单纯形表,原问题,5 4 0 0 0,0 5 4,常用单纯形表的矩阵形式,CB,CN,0,0,CB,对偶问题,对偶问题最优单纯形表：,综上所述，一对对偶问题的解必然是下列三种情况之一：,1.原问题和对偶问题都有最优解，且最优目标函数值相等。,3.原问题和对偶问题都无可行解。,2.一个问题具有无界解，则另一个问题无可行解。,maxf=5X1+8X2+6X3,X1+ X2 +2X36 X1+2X2 +2X310 X1，X2 ,X20,例3 已知线性规划问题,试用对偶理论证明上述问题无最优解。,三、对偶解的经济涵义影子价格,通过求解：原问题和对偶问题

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

6、件相对应的对偶变量的最优解的值。,2.影子价格的求法例4,某工厂生产三种产品，三种产品对于原材料、劳动力、电力的单位消耗系数，资源限量和单位产品价格如下表所示：,资源,产品,1.求最佳生产方案使总产值最大。,2.求各资源的影子价格，并解释其经济意义。,3.影子价格的作用,影子价格可以告诉管理人员，增加哪一种资源对增加经济效益最有益。,影子价格可以告诉管理人员，花多大的代价增加资源才是合算的。,影子价格在新产品开发决策中的应用。,影子价格在资源购销决策中的应用。,利用影子价格分析工艺改变后对资源节约的收益。,如在上例中，当工艺改进后，使原材料节约10%，则带来的经济效益为：2320 10%=64

7、（元）,在利润最大化的生产计划中 （1）边际利润大于0的资源没有剩余 （2）有剩余的资源边际利润等于0,关于影子价格的几点说明：,影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0 影子价格为0，资源并不一定有剩余,影子价格是资源最优配置下资源的理想价格，资源的影子价格与资源的紧缺度有关,思路：(max型),单纯形法：找基B，满足B-1b0，但检验数 C - CBB-1 A不全 0。,对偶单纯形法：找基B，满足C - CBB-1 A 0，但B-1b不全0。,四、对偶单纯形法,举例,原问题,对偶问题,例1,

8、2 1 0 0 0 0,2 0 0,2 0 1,例2.,0,2/3,1,2/3,0,1/3,1,2/3,0,-1/3,0,4/3,0,4/3,0,1/3,1,-1/3,0,-7/3,0,-1/3,0,4/3,例3(课本）,练习,例3,1,-1,-1,1,0,1,2,-3,0,-2,-1,1,该问题无可行解。,对偶单纯形法基本步骤 （ max型）,1、标准化（化标准型）；,2、寻找第一个正则解，建立初始单纯形表；,3、判别可行性： （1）若所有bi 0,则得到最优解， （2）若对于bk 0，有akj 0(均）， 则无可行解，停止计算。 否则，换基迭代。 4、选择bl=minbi/ bi 0= bl,i=1.m,确定基变量