[其它]第2章对偶理论.ppt

《[其它]第2章对偶理论.ppt》由会员分享，可在线阅读，更多相关《[其它]第2章对偶理论.ppt（146页珍藏版）》请在三一文库上搜索。

1、第2章 对 偶 理 论 (Duality Theory),对偶问题的提出,线性规划的对偶理论,对偶问题的经济解释-影子价格,对 偶 单 纯 形 法,灵 敏 度 分 析,对偶问题的提出 定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题。,应用: 在某些情况下，解对偶问题比解原问题更加容易 对偶变量有重要的经济解释(影子价格) 作为灵敏度分析的工具 对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解) 避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量),例1、某工厂用A、B、C、D四种原料生产甲乙

2、两种产品，生产甲乙所需各种原料的数量、在一个计划期内各种原料的现有数量及单件产品的利润见下表，问应如何安排生产才能获得最大利润?,线性规划模型,分析问题：现从另一角度讨论该问题 假如某人要租赁该厂的四种原料生产这两种产品，此时需考虑：这四种原料的加价应如何确定才便于厂方和租赁者达成协议。,对于工厂：希望定价尽可能地高，但太高了人家不会租赁，所以只能期望，尽管我不生产，但收益不能低于自己生产所得，否则，不如自己生产而不租赁出去。,对于租赁者，当然希望定价尽可能地低，至少不应超过原来实际生产所得的利润,为了便于达成协议，就必须在保证原工厂利益不降低的情况下，总的价格尽可能地低。,即出售生产两种产品

3、的原料的价格不应低于自己生产所得的利润，同时为了不亏本，各种原料加价不能为负，即：,可得线性规划模型：,线性规划问题的对偶问题,线性规划问题的原问题,两个数学模型间的关系：,(1)原问题为求最大值，而对偶问题是求最小值；,(2)原问题的约束条件为“”，而对偶问题的约束条件为“”；,(3)原问题的目标函数系数为对偶问题的约束条件右端的常数项，而原问题的约束右端常数项为对偶问题的目标函数系数；,(4)原问题的约束条件中xi 的系数为对偶问题第i个约束条件的系数,例2 合理配料问题,某饲养场用n种饲料B1,B2, Bn配置成含有m种营养成分A1,A2, Am的混合饲料，其余资料如表所示。问应如何配料

4、，才能既满足需要，又使混合饲料的总成本最低？,假设工厂想把这m 种营养成分分别制成一种营养丸销售，问如何定价，以保证总收入为最多？,解： 显然为了保证销路，价格不能太高，设含一个单位的第i种营养成分的营养丸定价为yi(i=1,2,m).因为原来的饲料中，第j种饲料每单位的价格为cj(j=1,n),而它所含第i种营养成分的量为aij,即现在要用aij个单位的第i种营养丸才能代替它，因此，为了使饲养场愿意用营养丸来代替原来的饲料，必须使营养丸的价格满足,由于每一份饲料中必须含有bi个单位的第i种营养成分，因此这样一份代替饲料的总收入为,对于工厂来说，问题是如何确定每种营养丸的售价yi(i=1,m)

5、使在满足上述约束条件下工厂的总收入达到最大，则问题可归结为,对偶问题,原问题,两个数学模型间的关系：,(1)原问题为求最小值，而对偶问题是求最大值；,(2)原问题的约束条件为“”而对偶问题的约束条件为 “” ；,(3)原问题的目标函数系数为对偶问题的约束条件右端的常数项，而原问题的约束右端常数项为对偶问题的目标函数系数；,(4)原问题的约束条件xi 的系数为对偶问题第i个约束条件的系数,对称型对偶问题,二、线性规划的对偶理论,(一)对偶问题的形式,变量均具有非负约束，其约束条件当目标函数求极大时均取“”号，当目标函数求极小时均取“”号。,P,D,矩阵形式,例1、写出线性规划问题的对偶问题,解：

6、首先将原式变形,例2、原问题,解：原问题化为,例3、求下列问题的对偶问题,原问题可化为：,对偶问题为：,综上所述，其变换形式归纳如下：,例4、线性规划问题如下：,对偶问题是,练习：,1、对称性定理：对偶问题的对偶是原问题。,（二）、对偶问题的性质,2、弱对偶原理（弱对偶性）：设 和 分别是问题（P）和（D）的可行解，则必有,推论.若 和 分别是问题（P）和（D）的可行解，则 是（D）的目标函数最小值的一个下界； 是（P）的目标函数最大值的一个上界。,因,是原问题的可行解，所以满足约束条件，即,原问题的对偶问题是 min w=Yb; YA C;Y 0,推论.在一对对偶问题（P）和（D）中，若其中

7、一个问题可行但目标函数无界，则另一个问题不可行。,例1、,试估计它们目标函数的界，并验证弱对偶性原理。,（P）,解,例2、已知,试用对偶理论证明原问题无界。,例3、已知,显然，这两个问题都无可行解。,3、最优性判别定理：,例如,在例1中,可找到X*=(0,0,4,4),Y*=（1.2,0.2）,则Z=28,W=28.故X* ,Y*分别是 P和D 的最优解。,4、对偶定理（强对偶性）： 若原问题有最优解，则对偶问题也有最优解，且目标函数的最优值相等。,综上所述，一对对偶问题的关系，只能有下面三种情况之一出现： .都有最优解，分别设为X* 和 Y*，则必有CX* =Y*b； . 一个问题无界，则另

8、一个问题无可行解； .两个都无可行解。,5、互补松弛定理： 设X*和Y*分别是问题P 和 D 的可行解，则它们分别是最优解的充要条件是,同时成立,设原问题和对偶问题的标准型是,证 由于 z=(YA-YS)X =YAX-YSX ，w=Y(AX+XS)=YAX+YXS,若Y*XS=0,YSX*=0,则Y*b=CX*,由性质3知X*,Y*是最优解。,若X*,Y*是原问题和对偶问题的最优解，根据性质4,知，CX*=Y*AX*=Y*b,必有Y*XS=0,YSX*=0.,例4、已知,试通过求对偶问题的最优解来求解原问题的最优解。,解：对偶问题为,此方程组有无穷多组解,例5、已知原问题的最优解为X* =（0

9、,0,4），Z=12 试求对偶问题的最优解。,解：,（1）,（2）,（3）,将X* =（0 , 0 ,4）代入原问题中，有下式：,所以，根据互补松弛条件，必有y*1= y*2=0，代入对偶问题 （3）式， y3 =3。因此，对偶问题的最优解为 Y*=（0 ,0 ,3），W=12。,6、对偶问题的解,引入xs ，构建初始基变量，然后用单纯形法求解。当所有非基变量的检验数满足j0 ，则求得最优解。此时， xs对应的s 为- Y* ，故求对偶问题的最优解Y* ，只要将最优单纯形表上xs 对应的检验数反号即可。,(1),例1、,初 始 表,最终表,由上表可知： X*=（50/7 , 200/7），Z=

10、4100/7 对偶问题的最优解： Y*=（0 ,32/7 , 6/7），W=4100/7 也就是外加工时的收费标准。,此时，矩阵A中没有现成的单位矩阵I作为可行基，必须通过加入人工变量来凑一个单位矩阵，再用大M法或两阶段法求解。,CB,XB,b,CB,XB,B-1b,CB,XB,CN,XN,CI,XI,I,B-1N,B-1,-z,-CBB-1b,0,CN-CBB-1N,CI-CBB-1,例2、,所以， X*=（4 ,1 ,9），Z = 2, y*1= (0 4 )=1/3 y*2=(M 6 )= M(1/3M)=1/3 y*3 =(M 7 )= M(2/3 M)=2/3 Y*=（1/3 ,1/

11、3 , 2/3） W = 2,初始基变量的检验数4 =1/3，6 =1/3M, 7 =2/3M,三、对偶问题的经济解释影子价格,目标函数最优值变为：,也可以写成：,其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi 就是第 i 个约束条件的影子价格。,也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。,例1、某工厂用A、B、C三种原料生产甲乙两种产品，生产甲乙所需各种原料的数量、在一个计划期内各种原料的现有数量及单件产品的利润见下表，问应如何安排生产才能获得最大利润?,其对偶问题,原问题的最优解为 X*=（50/7 ,

12、 200/7），Z*=4100/7 对偶问题的最优解： Y*=（0 ,32/7 , 6/7），W*=4100/7,即原问题中第1种资源(钢材)的影子价格y1*=0,第2种资源(煤炭)的影子价格为y2*=32/7,第3种资源(设备台时)的影子价格为y3*=6/7,即在现有资源的基础上，若再增加1吨煤，可使总利润增加32/7万元，若再增加一个台时，可使总利润增加6/7万元，但若增加1吨钢材，将不会使总利润增加。,之所以出现上述几种不同情况，由互补松弛条件可知，,这说明按最优生产计划进行生产，现有资源中的煤炭和设备台时已经全部用完而没有剩余，因此，若再增加这两种资源，肯定会给工厂带来新的收益。,若再

13、增加这种资源，只能造成积压，而不会使工厂增加收益。,bi 代表第i种资源的拥有量；yi*代表在资源最优利用条件下对第i种资源的单位估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价。,一、影子价格的概念,设 xj 表示第 j 种产品每天的产量,设 yj 表示第 j 种原料的收费单价,由对偶定理知当P问题求得最优解X*时，D问题也得到最优解Y*，且有,影子价格,一、影子价格的概念,由 得,说明 的值相当于在资源得到最优 利用的生产条件下， 每增加一个 单位时目标函数z的增量,边际价格,说明若某资源 未被充分利用，则该种资源的影子价格为0；,若某资源的影子价格不为0，则说明

14、已有资源已消耗完毕。,二、在经营管理中的应用,y1* = 2 y2* = 1 y3* = 0,Y*T= CBB-1,CBB-1,二、在经营管理中的应用,y1* = 2 y2* = 1 y3* = 0,若原料A增加1单位，该厂按最优计划安排生产可多获利200元； 若原料B增加1单位，可多获利100元; 原料C本已剩余，再增加不会带来收益。,1、指示企业内部挖潜的方向,影子价格能说明增加哪种资源对增加经济效益最有利,二、在经营管理中的应用,y1* = 2 y2* = 1 y3* = 0,2、在企业经营决策中的作用,当某种资源的影子价 格高于市场价格时： 当某种资源的影子价 格低于市场价格时：,企业

15、经营决策者可通过把本企业资源的影子价格与当时的市场价格进行比较，决定资源的买卖，以获取较大利润。,买进,卖出,特别是影子价格为零时,二、在经营管理中的应用,y1* = 2 y2* = 1 y3* = 0,3、在新产品开发决策中的应用,利用影子价格，通过分析新产品使用资源的经济效果，以决定新产品是否应该投产。,假设该企业计划生产一类新产品，单件消耗三种原料的数量为（2,3,2），则新产品的单位利润必须大于 22 + 13 + 02 = 7（百元） 才能增加公司的收益，否则生产是不合算的。,二、在经营管理中的应用,y1* = 2 y2* = 1 y3* = 0,4、分析现有产品价格变动对资源紧缺情

16、况的影响,若甲产品提价，单位利润增至4，则影子价格改变，由,Y*T= CBB-1,说明如果甲产品提价的话，资源A将变得更紧俏.,二、在经营管理中的应用,y1* = 2 y2* = 1 y3* = 0,5、分析工艺改变后对资源节约的收益,若企业革新技术，改进工艺过程后使资源A能节约2%，则带来的经济收益每天将是 262% = 0.24（百元）,二、在经营管理中的应用,y1* = 2 y2* = 1 y3* = 0,注意:,1、以上分析都是在最优基不变的条件下进行的,2、应对影子价格有更为广义的理解,若增加产量约束 x1+ x2 40：产量不超过市场需求量,若y4*较大，则说明扩大销路能比增加资源

17、带来更大的经济效益,Y*T= CBB-1,6单纯形表中各个检验数的经济意义,当产品产值大于隐含成本时，表明生产该项产品有利，可在计划中安排，否则这些资源来生产别的产品更为有利，就不在计划中安排。这就是单纯形表中各个检验数的经济意义。,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,x2,x1,(4 2),0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,x2,x1,(4 2),对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。,由对偶理论可以知道，对于一个线性规划问题，我

18、们能够通过求解它的对偶问题来找到它的最优解。,四、对 偶 单 纯 形 法,考虑一般的标准形线性规划问题及其对偶问题,原始单纯形法的基本思路是：从满足初始可行性条件,单纯形法：在整个迭代过程中，始终保持原问题的可行性，即常数列b0，而检验数C-CBB-1A（即C-YA）由有正分量逐步变为全部0(即满足YA C,Y为对偶问题的可行解)即同时得到原问题和对偶问题的最优解。,对偶单纯形法：在整个迭代过程中，始终保持对偶问题的可行性，即全部检验数0，而常数列由有负分量逐步变为全部0(即变为满足原问题的可行性)，即同时得到原问题和对偶问题的最优解。,单纯形法与对偶单纯形法的迭代过程之比较,对偶单纯形法所使

19、用的表格与原单纯形法一样，所不同的是对偶单纯性表保证j 0,而不保证右端常数非负。,对偶单纯形法的迭代方式与原单纯形法基本一致，所不同的是：先选出基变量，再选进基变量，决定主元并作换基运算得到一个新的对偶可行解。,对偶单纯形法具体步骤：,(1)据线性规划问题，列初始单纯形表，设检验数全都小于或等于0,检查b列数字，若全为非负数，则已得到最优解，停止计算，否则，转下一步,(2)确定换出变量，若min(B-1b)i|(B-1b)i0=(B-1b)l则xl出基,(3)确定换入变量，检查xl 所在行的各系数alj(j=1,n)若所有alj0则无可行解，计算结束，若存在alj0,则,xk进基.,(4)以

20、alk为主元素，按单纯形法在表中的换基运算，得到新的单纯形表；,重复以上各步，直至计算结束,例1、用对偶单纯形法求解：,解：将模型转化为,x5,x4,1 1/2 0 1 0 -1/4,3/2,-2 -3 -8 0 1 -1/2,-1,0 -24,36,-4 -8 -32 0 0 -6,x1,x4,1/2,1 3/2 4 0 -1/2 1/4,1,0 -1 -4 1 1/2 -1/2,-28 -24,38,0 -2 -16 0 -2 -5,-z,-z,练习：,初始正则解的求法,考虑标准形线性规划问题,列单纯形表,市场行情的变化会引起价值系数Cj的变化; 工艺条件的改变会引起消耗系数aij的变化；

21、 资源投入量的改变会引起右端常数bi的变化； 增加新产品会引起决策变量的增加； 增加新的资源限制会引起约束条件的增加。,五、灵敏度分析,当这些数据中有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化，或者这些数据在什么范围内变化时，已求得的线性规划问题的最优解或最优基不变。这正是灵敏度分析所要讨论的问题。,灵敏度分析又称为优化后分析，因为它是在已求得线性规划最优解的基础上，来讨论这些数据变化对最优解的影响。,灵敏度分析的任务是研究这些数据的变化对最优解的影响，灵敏度分析又称为优化后分析，它是在已求得最优解的基础上进行分析。,灵敏度分析研究的问题： (1)为了保持现有的最优解或最优

22、基不变，找出这些数据的变化范围；(2)当这些数据的变化超出了(1)的范围时，如何在原有最优基(解)的基础上，作微小的调整，尽快求新的最优基(解),给定线性规划问题的标准型,单纯形表的矩阵描述,由上表可见，某些数据只与表中的某些块有关，当这些数据发生变化时，只需,对表中的某些块进行修改，便可得新问题的单纯形表，继续迭代即可求得最优解。,一、目标函数系数cj的灵敏度分析,若要保持最优解不变，则必须使,例1 已知线性规划问题,最优单纯形表,要使最优解不变，则必须满足,解：,二、 右端常数的灵敏度分析,解(1),则由,(2),x2的检验数,解：,四、增加新变量的灵敏度分析,否则可继续用单纯形法迭代求解

23、。,解：,五、增加新约束条件的灵敏度分析,若在原线性规划问题中，再增加一个新的约束条件,则首先将已得到的最优解代入上述约束中，若满足，则新问题的最优解即为原问题的最优解。否则，在原最优表中增加一行（约束）一列(单位列向量)，用矩阵的初等行变换将原单位矩阵列恢复，再继续迭代。,综合实例,例1 已知线性规划问题,最优单纯形表为,试 分别就下列情况进行灵敏度分析，并求新的最优解： (1)第2个约束条件的右端常数变为b2=95; (2)第1个约束条件的右端常数变为b1=45; (3)目标函数中x3的系数变为c3=8; (4)目标函数中x2的系数变为c2=6; (5)变量x1的系数变为(c1, a11,

24、a21)T=(-2,0,5)T; (6)变量x2的系数变为(c2,a12,a22)T=(6,2,5)T; (7)增加一个新变量x6,其系数变为(c6,a16,a26)T=(10,3,5)T; (8)增加一个新约束条件2x1+3x2+5x350; (9)第2个约束条件变为10x1+4x2+12x3100,解 (1),列单纯形表,(2),(3),(4),列最优单纯形表,(5),当j=1时，,或直接计算,(6),列最优单纯形表,(8),不满足约束。,列单纯形表,(7),(9),故最优性仍保持,例2：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划,最优单纯形表如下,(1)确定x2的系数

25、c2的变化范围，使原最优解保持最优; (2)若c2=6，求新的最优解;,(3)b3在什么范围内变化，原最优基不变; (4)若b3=55，求出新的最优解;,(5)设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示,P6= (3/2,1,1/2)T 。问它的价值系数c6符合什么条件才必须安排它的生产？设c6=3，新的最优生产计划是什么？,(6)假设还要考虑一个新的资源约束：4x1+2x2150,(7)假定c2由4上升为6，b3增加到55，试问最优解将会发生什么变化？,(8)第一种产品的消耗系数改变为 P1=(3/2,1/2,1/2)T，价值系数不变，求新的最优解。,最优解X*=（35，1

26、0，25，0，0）保持不变。,(1),即当b340，50 时，最优基B 不变,(3),x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=495/2,（2）,（4）当 b3= 55 时,=,6=c6CBB1P6 =c6（0，5，4） = c65/2,(5),4x1+2x2+x6=150,X*=（35，10，25，0，0）T,(6),4x1+2x2+x6=150,(7)假定c2由4上升为6，b3增加到55，试问最优解将会发生什么变化？,B1=,B1 = =,代替最优表的b列，并把c2改为6,原问题与对偶问题均非可行解，表中第一方程是 x3+2x45x5=25， 两边

27、乘以（-1），得： x32x4+5x5=25， 再引入人工变量x6： x32x4+5x5+x6=25 以x6为基变量，增添第6列，应用大M法继续求解。,新的最优计划产量为x1*=30，x2*=20，z*=270。,x32x4+5x5+x6=25,(8)第一种产品的消耗系数改变为 ，价值系数不变，求新的最优解。,B1=,参数线性规划,参数线性规划概念,当参数 或 沿某一方向连续变动时，目标函数值z将随 或 的变动而呈线性变动，z是这个变动参数的线性函数，因而称为参数线性规划。,模型,目标函数的系数含有参数的线性规划模型,约束条件右端的常数项含有参数的LP模型,参数线性规划问题的分析步骤：,（1）

28、令 求解得最终单纯形表； （2）将 或 项反映到最终单纯形表中去； （3）随 值的增大或减小，观察原问题或对偶问题。 （4）重复第（3）步，一直到 值继续增大或减小 时，表中的解（基）不再出现变化时为止。,确定现有解（基）允许的 的变动范围；,当 的变动超出这个范围时，用单纯 形法或对偶单纯形法求新的解。,举例分析目标函数的系数 含有参数的线性规划问题,分析 值变化时，下述参数线性规划 问题最优解的变化。,先令 求得最优 解，然后 将 反映在最终单纯形表中，见下表：,最优解保持不变的条件,当 时,当 时，换基得：,当 时，由原最终单纯形表,当 时，最终单纯形表,当 时，原最终单纯形表,当 时，最终单纯形表,目标函数值 随 值变化的情况,举例分析约束条件右端的常数项含 有参数的线性规划问题,分析 值变化时，下述参数线性规划 问题最优解的变化。,先令 求得最优 解，然后 将 反映在最终单纯形表中，见下表：,最优基不变条件是 最优值为,当 时,先令 求得最优 解，然后 将 反映在最终单纯形表中，见下表：,最优基不变条件是 最优值为,当 时,当 时 最优值为,当 时,当 时 最优值 当 时， 所在元素均为正， 故原问题无可行解,