线性规划对偶理论与灵敏度分析.ppt

《线性规划对偶理论与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《线性规划对偶理论与灵敏度分析.ppt（102页珍藏版）》请在三一办公上搜索。

1、第 二 章 线性规划对偶理论与灵敏度分析,教学时数：6学时教学目的与要求：理解线性规划对偶问题理论与影子 价格概念,掌握对偶单纯形法及灵敏度分析技巧教学内容：1.线性规划对偶问题及相关理论2.影子价格3.对偶单纯形法4.灵敏度分析及参数规划教学重点：影子价格及灵敏度分析教学难点：对偶理论,第二章 讲授内容和知识,第 一 节线性规划的对偶问题,解：利用第一章的知识，设三种产品的生产量分别为x1，x2和 x3，可以建立线性规划模型如下:,一、对偶问题的提出,3000,假如企业不进行生产，而是把全部可利用的资源转让给其他企业。此时，企业必须考虑一个合适的资源价格，使得：1.有企业愿意接受转让；2.企

2、业自身没有经济损失。,设四种资源的价格确定为 y1,y2,y3,y4。,y1,y2,y3,y4,而企业自身没有经济损失的要求可做如下思考：生产一件产品，比如A，需要四种资源的量分别为3，2，1，1个单位。由于要把生产A 产品的这些资源卖出去，所以，单件总卖值不应比企业自己生产时的收益（2000）低，即，3 y1+2 y2+y3+y4 2000 对产品B：4 y1+y2+3 y3+2 y4 4000 对产品C：2 y1+2 y2+3 y3+4 y4 3000,则有企业愿意接受转让的条件是极小化资源总价，即 w=600 y1+400 y2+300 y3+200 y4,原问题,对偶问题,两个线性规划

3、问题的比较中，可以初步发现：原问题的目标函数求极大，对偶问题的目标函数求极小；原问题目标函数中的系数 在对偶问题中变为约束条件的右端常数项；约束条件的不等式方向改变了；约束方程的系数矩阵发生了转置；原问题约束数目与对偶问题的变量数相等。,对称形式的条件：（1）变量全部具有非负约束；（2）目标函数求极大值时，约束不等式符号全部为；目标函数为求极小值时，约束不等式的符号全部为。,对偶问题的一般形式为：,二、对称形式的原始-对偶关系,Y=(y1,y2,ym),说明：表 2的变量行与参数行相乘组成原始问题的约束条件和目标函数；表2 的变量列与参数列相乘组成对偶问题的约束条件和目标函数。,600,400

4、,300,200,2000,4000,3000,0,非对称形式是指一般情况下的线性规划问题，是目标函数求极小或求极大；约束条件、=、；变量0、0或者无限制的随意组合。,建立非对称形式线性规划问题的对偶模型可采取以下步骤：（1）通过变换，把线性规划问题化为具有对称形式的原问题。（2）根据原问题，写出对偶问题。（此时的对偶并非是原线性规划问题的对偶）（3）通过变量代换等，把参数还原为最初的形式（必须做）。,三、非对称形式的原始-对偶问题,解：（1）把原线性规划问题化为对称形式要求的形状目标函数求极大；约束条件全部为“”符号；变量全部非负。,第一个约束条件的符号符合要求，保留不变。第二个约束条件分解

5、为：x1 x2+x3 1 和 x1 x2+x3 1第一个分解式乘以-1 变为-x1+x2 x3-1 第三个约束条件乘以-1 得：-2x1 x2 x3-2,（2）写出上述对称形式线性规划问题的对偶。,（3）还原为原来的参数符号,令 u1=y1,u2=-y2+y3,u3=-y4,u1,u2,u3,四、原始-对偶关系一览表,解：根据表3，得出对偶线性规划问题如下：,max w=2 y1+y2+4 y3,st.,2 y1+3 y2+y3 1 3 y1 y2+y3 4 y1+y3=3 y1 0,y2 0,y3自由变量.,课堂练习,第 二 节对偶问题的基本性质,本节以对称形式的原始-对偶问题为讨论的基础，

6、除非特别需要，一般不再专门说明。,一、单纯形法计算的矩阵描述,原问题通过加入松弛变量 Xs 可以化为标准形式：,其中，I 是对应于松弛变量的单位方阵。,单纯形法计算时，总是选择 I 为初始可行基，松弛变量作为初 始基变量的。由于松弛变量作为基变量意味着资源没有被利用，所以，单纯形法迭代若干步后，松弛变量会被置换出基变量集合。,项 目,0 Xs b,非基变量,基变量,XB XN,Xs,B N,I,检验数,CB CN,0,设新的基变量组合为XB，在初始单纯形表中的系数矩阵为B，价值系数为CB。A去掉B 的若干列后，剩余的列向量组成子矩阵N，对应的变量组合记为XN，价值系数记为CN。,CB XB b

7、1,基变量,非基变量,XB,XN Xs,I,检验数,N1 S1,0,N S,Xs,XB,XN,x1x2,B,I,N,I,N1,S1,N S,CB CN,根据上述划分，约束方程可改写为：,B XB+N XN+I Xs=b,XB=B 1 b B 1 N XN B 1 Xs,代入目标函数中，得,z=max z=CX+0Xs=CB XB+CN XN+0 Xs=CB(B 1 b B 1 N XN B 1 Xs)+CN XN+0 Xs=CB B 1 b CB B 1 N XN CB B 1 Xs+CN XN+0 Xs=z0+(CN CB B 1 N)XN+(0 CB B 1)Xs,其中带白色字体的就是非基

8、变量的检验数，z0 对应于当前的目标函数值,AX+IXs=b,(CN CB B 1 N),(0 CB B 1),B 1 b,B 1 N,B 1,(CN CB B 1 N),CB B 1,XB=（x1，x3）T,XS=（x4，x5）T,XN=x2,B-1N=,B-1=,(CN CB B 1 N),CB B 1,如果表中的检验数满足最优性条件，即 CN CB B 1 N0 CB B 1=CS CB B 1 I0,由于基变量的检验数可以写为 CB CB B1 B=0,所以，上述3个式子可以重写为 C CB B 1 A0,令 Y=CB B 1 单纯形乘子,Y A C Y 0,当原问题达到最优时，Y=C

9、B B 1对应于对偶问题的一个可行解。将该解代入对偶问题的目标函数，可知w=Y b=CB B1 b=z。对偶理论将进一步说明，对偶与原始问题具有相同的最优目标函数值。,XB=B 1 b,Y=CB B 1,Max z=CX=CB B 1 b,w=Yb=CB B 1 b,原问题的对偶变量 y1 y2,对偶问题的对偶变量（原问题）x1 x2 x3,14 4,9 4,994,14 0 4,性质1.弱对偶性。如果X 0，Y 0分别是原始问题和对偶问题的可行解，则 CX 0 Y 0 b,证明：因为X 0，Y 0是可行解,它们满足约束条件和非负性限制,二、对偶问题的基本性质,A X 0 b X 0 0 Y

10、0 A C Y 0 0 用Y 0左乘第一个不等式，X 0右乘第二个不等式，得 Y 0 A X 0 Y 0 b Y 0 A X 0 C X 0 比较上面两个不等式可知，弱对偶性成立。,推论：（1）原问题任一可行解的目标函数值是对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是原问题目标函数值的上界。（2）如果原问题有可行解且目标函数值无界（无界解），则对偶问题无可行解；反之，对偶问题有可行解且目标函数值无界，则原问题无可行解。注意：本性质的逆不成立。因为当对偶不可行时，要么原问题无界，要么原问题无可行解。（3）如果原问题有可行解，对偶问题无可行解，则原问题目标函数值无界；反之，对偶

11、问题有可行解，原问题无可行解，则对偶问题的目标函数值无界。,maxZ,原问题可行解,minW,对偶可行解,用途：判断线性规划问题有无最优解。因为原始和对偶问题可行解的目标函数值分别是对偶、原始的下、上界，所以，只要找到原始、对偶的可行解，就可断定原始、对偶问题有无最优解。,二、对偶问题的基本性质,可以看出，原问题有可行解，比如X=（1，1，1，1）T，对偶问题有可行解Y=（1，1），所以，原线性规划问题有最优解。,性质2.最优性。如果X 0，Y 0分别是原始问题和对偶问题的可行解，且有 CX 0=Y 0 b，则X 0，Y 0分别是原始问题和对偶问题的最优解。,证明：设X，Y分别是原始问题和对偶

12、问题的最优解。根据最优解的定义知：CX 0 C X,Y 0 b Yb。又根据弱对偶性，C X Yb，所以，C X Y 0 b=CX 0，X 0是原问题的最优解。同理，C X Yb，Y 0 b=CX 0 Yb，所以，Y 0是对偶问题的最优解。,性质3 强对偶性（或对偶定理）如果原始问题和对偶问题都有可行解，则两者都有最优解，并且目标函数值相同。,证明：由于两者都有可行解，根据弱对偶性的推论知：原问题目标函数值有上界，对偶问题目标函数值有下界，因此，两者都有有限的最优目标函数值。其次，用单纯形法求原问题最优解时，最优性判断条件是：检验数0，即 C CB B 1 A 0 CB B 10 令Y=CB

13、B 1，则，Y A C，Y 0。即，Y=CB B 1是对偶问题的可行解。由于该可行解的 目标函数值与原问题的目标函数值相同，由最优性可知，两者都是最优解。,根据上述的对偶性质（理论），不难看出原问题和对偶问题的解存在有如下关系。,性质4.互补松弛性（或松紧定理）。在线性规划问题的最优解中，如果对应于某一约束条件的对偶变量值不为零，则该约束条件取严格的等式符号；反之，如果约束条件取严格不等式符号，则其对应的对偶变量一定取零值。,或：如果X 0，Y 0分别是原始问题和对偶问题的可行解，Xs、Ys分别是原问题和对偶问题的松弛变量和剩余变量，则X 0，Y 0为最优解的条件是 Ys X 0+Xs Y 0

14、=0进一步地，Ys X 0=0，Y 0 Xs=0,证明：把可行解X 0，Y 0，松弛变量Xs、Ys代入原问题和对偶问题的约束中，得 A X 0+Xs=b Y 0 A Ys=C,前式左乘Y 0，后式右乘X 0，得 Y 0 A X 0+Y 0 Xs=Y 0 b Y 0 A X 0 Ys X 0=C X 0,Y 0 Xs+Ys X 0=Y 0 b C X 0,显然，如果X 0，Y 0 是最优解，右端为零，互补松弛性成立；由于式中的每一个向量都是非负的，所以，它们的点积（内积）非负。而如果两个非负项相加等于零，那么，每一个非负项必须等于零。即 Ys X 0=0，Y 0 Xs=0,经济意义：如果某种资源

15、有剩余（约束为严格不等式），则它的价值为零。,其对偶问题的最优解为 y1=4/5，y2=3/5。试确定原问题的最优解。,将对偶问题最优解代入对偶约束中可知，第2、3、4约束为严格不等式，x2=x3=x4=0。,对偶问题的解大于零，所以，原问题的约束条件在最优时取等号，即 x1+3 x5=4 2x1+x5=3,X=（1，0，0，0，1）T。,求解后得，x1=1，x5=1。,第 三 节影 子 价 格,二、影子价格的特点和应用,一、影子价格的概念、定义,一、影子价格的概念、定义,从对偶问题的基本性质可以看出，当线性规划原问题求得最优解时，其对偶问题也得到了最优解，且目标函数值相同，即 Z=CB XB

16、=CB B 1 b=Y b=w,由于 b是线性规划原问题约束条件的右端常数项，表示企业对资源的拥有量，如果 Z是企业所创造的总收益的话，Y就是资源在生产中作用和贡献的有效性估价。为区别于资源的市场价格，称 Y为影子价格。,影子价格也叫经济价格，它有广泛的含义。一般认为，凡用各种方法计算出来的非自然形成的价格，以及由国际市场引进的价格，只要不在现实生活中发生作用，都可以称为影子价格。,（1）资源的市场价格是已知数，相对比较稳定。而影子价格则有赖于资源的利用情况，是未知数。企业人、财、物、技术、管理的变化，都会直接引起影子价格的变动。,（2）影子价格是一种边际价格。,目标函数对对偶变量的偏导数表明

17、，影子价格是在其它条件都不变化的情况下，单位资源变化所引起的目标函数最优值的变化量。,二、影子价格的特点和应用,在图解法中，我们曾解决过如下问题：,max z=3x1+x2,x1x21x1+x22,x1,x2 0,x1-x2=1,x1+x2=2,可行域,Z=3x1+x2,A(3/2,1/2);Z=5,x1+x2=1,B(1,0);Z=3,（3）影子价格是一种机会成本。在纯市场经济条件下，如果第二种资源的市场价低于2，可以买进这种资源；相反，当市场价格高于影子价格2时，应该卖出库存的该种资源，因为经过企业加工后，资源不但没有升值，反而贬值了。随着资源的买进卖出，它的影子价格也在变化，一直到影子价

18、格与市场价格相同时，才会处于平衡状态（没有投机的机会）。,（4）影子价格反映了资源利用的状况。根据互补松弛性质，当某种资源未得到充分利用时，该资源的影子价格等于零；当资源的影子价格不等于零时，该资源在生产中已耗费完毕。,（5）影子价格有助于给新产品定价和确定新产品是否值得生产。各种产品在使用相同资源的情况下，新产品的定价一定要高于它的成本，反映到单纯形表里，就是要求检验数大于零：,检验数的第一项是产品的价格（产值），第二项是所耗费资源的隐含成本。检验数大于零说明新产品可以投产，能为企业带来附加收益。,（6）影子价格能确定资源的相对重要性，有助于决策。影子价格大小指明了资源的相对重要性次序。一般

19、来说，企业的资金是有限的，按照影子价格的大小，决策者可以方便地决定资源采购的先后顺序。,（7）一般来说，对线性规划问题的求解解决的是最优分配方案；而对对偶问题的求解则主要集中于资源的估价或资源是否得到合理利用问题上。,（8）上述分析是基于最优可行基不变的前提下展开的，如果最优可行基发生变化，则需要修正所得到的结论。,第 四 节对偶单纯形法,一、对偶单纯形法的思路,二、对偶单纯形法的计算步骤,对偶单纯形法不是解对偶问题的，而是在单纯形表上进行对偶运算的方法。为了了解对偶单纯形法的实质，我们回顾一下单纯形法。,单纯形法开始于初始基可行解。如果不满足最优性条件，则要转到能使目标函数值得到改善的邻近顶

20、点上。在这个转换过程中，存在两个原则:一是保持原问题的解仍是可行的，另一个是要求目标函数值有改善。,一、对偶单纯形法的思路,当目标函数值无法改善时（因退化出现循环的情况除外），所有的检验数都0（求极大时0，求极小时，检验数0）。“检验数 0”意味着在获得原问题最优解的同时，也获得了对偶问题的一个可行解。因为原问题与对偶问题的解都可行，并且目标函数值相同，根据对偶理论，这个对偶可行解就是对偶问题的最优解。,因此，单纯形法迭代过程的实质是：在保持原问题可行性的前提下，驱使对偶问题从不可行（起始点、中间点）转变为可行的（最优点）发展历程。,把上述思想移植到对偶问题上。如果保持对偶问题的可行性（只要检

21、验数0即可），通过改变对偶问题的可行基，使原问题由不可行变为可行，根据对偶理论，这两个可行解就是原始和对偶问题的最优解。,使用对偶单纯形法必须满足两个条件：（1）单纯形表中的所有检验数必须符合最优性要求,即对偶可行.（2）右端常数项列向量必须有负分量（如果原问题可行，则直接用单纯形法）,（1）把线性规划问题化为标准形式，找出对偶问题的初始可行基，列出单纯形表。表的格式与第一章的单纯形表完全相同。,（2）确定换出基的变量。这一点与单纯形法正好相反，那里是先确定换入变量。因为常数项有负分量，所以令br=minbi,第 i 行对应的基变量 xr 作为换出变量。,二、对偶单纯形法的计算步骤,（3）确定

22、换入基的变量。这里要注意：单纯形法确定换出变量时用的是换入变量列向量与常数项列的最小比值；对偶单纯形法确定换入变量时则用检验数行与换出变量所在行的最小比值。,.如果所有的arj0，则原问题没有可行解。停止计算。如果存在arj 0，则计算最小比值。,(4)选择 ar s 为主元素，把该列向量变为单位列向量。这里的旋转运算和单纯形法一样，主元素处变为1，其余变为0即可。,（5）重复步骤（2）（4），直至原问题变为可行解为止。,在标准形式里，目标函数系数满足使用对偶单纯形法的一个条件，但是，约束条件的右端常数项非负，且没有单位矩阵。为此，把约束方程两边都乘以-1，得,根据对偶单纯形法，首先选择换出变

23、量：显然常数项列最小的元素是-2，所以第一行的基变量 x4 作为换出变量。,换入变量的确定:第一行与检验数行对应分量比值的最小值为：最小比值=，-24/-6，-5/-1=4-6是主元素，x2是换入变量。,负元素是-1/3，第二行基变量 x5 作为换出变量。,换入变量的确定:最小比值=-15/-5，-1/（-2/3），-4/（-1/3）=3/2-2/3是主元素，x3是换入变量。,-2/3,由于原始，对偶都已经可行，对应的解是最优解。,注意：具有本例题形式的线性规划问题在求最优解时，可以不使用人工变量，对偶单纯形法能使求解过程更简便。,第 五 节灵敏度分析,一、线性规划的基本假设,灵敏度分析的概念

24、：是指对系统或事物因周围环境条件发生变化所表现出来的敏感程度的分析。,二、灵敏度分析及其步骤,(2)检查原问题是否仍可行：基变量的取值是否仍全部0；,（3）检查对偶问题是否仍可行：检验数行是否仍满足最优性条件,（4）按下表所列情况得出结论，即决定继续计算的步骤。,按与变量的对应关系划分，价值系数可分为基变量价值系数和非基变量价值系数两种。由于价值系数的变化直接影响到检验数，所以，价值系数变化的结果只有两个：原始，对偶问题均可行，最优解不变；原始问题可行，但对偶问题不可行，需要用单纯形法继续求解。,三、价值系数cj的变化分析,XN XS,CN CS,CN,XB,CB,CB,CB,1非基变量 xj

25、的价值系数cj 发生变化。设价值系数的增量为 cj，要保证最优基不变，必须使最终表中的检验数仍0，即,或者,（2）基变量xr的价值系数cr 发生变化。,所以，非基变量在最终表的检验数变为,如果要求原最优基不变，非基变量的检验数必须满足0的条件,于是，基变量价值系数 cr 的变化范围是,上式仅适用于一个基变量价值系数发生变化的情况。,注意：在进行灵敏度分析时，可以用上面的公式确定参数的变化范围，也可以把价值系数当作未知数在表上进行直接计算。,（1）当产品1的价值系数由 2变为 3，产品2的价值系数从3变为2 时，最优解会如何变化？产品2的价值系数的变化范围是什么？,四、资源量bi的变化分析,b,

26、b,设第r 种资源发生变化，资源量从 br变为br+br。其它系数维持不变。这样，在最终表中的基解相应地改变为,只要XB0，最终表中的检验数不变，则最优基不变（注意，最优解的值已经改变）。为保持最优基不变，资源增量的变化范围如下：,这是可行基矩阵B的逆矩阵B1的第 r 列,这样，最终表里保持最优基不变的b列元素满足,企业又购进资源A 4个单位用于生产。求此时的最优方案。,B1b=,=,附加资源带来了获利水平的提高，最优的目标函数值为17,资源B在何范围变动时,最优基不变。,B1b=,=,-8 b2 16,五、增加一个新变量 xk 的分析,XP,P,CP,XP,B-1P,CP CBB-1P,增加

27、新变量在实践中对应于增加一种新产品。分析步骤是：,（1）利用新产品的数据计算检验数，(cpzp)=cpY Pp。（2）计算新产品在单纯形表中的系数列向量 Pp=B1 Pp。（3）如果检验数0，最优基不变，只要把上面计算的结果放在单纯形表的最后一列即可。如果检验数大于零，则要用单纯形法继续迭代，求出最优解。,例:在上述模型中，企业打算生产一种新产品，每件产品消耗 3种资源的量分别为2、6和3个单位，单件可获利5元。问可否投产？,解：（1）新产品能否投产关键看能否为企业带来利润。设新产品的生产量为x6，它的检验数为,因为检验数大于零，所以，新产品可以生产。,（2）计算新产品在单纯形表中的系数列向量

28、 P6=B1 P6。,B1 P6=,0 1/4 0-2 1/2 1 1/2-1/8 0,263,5 x6,5/4,3/2 21/4,参数 aij变化使得系数矩阵A也随之发生变化。如果变量 xj 在最终单纯形表里是非基变量，可以按照增加一个变量的方法处理。如果 xj 是基变量，则参数aij的变化有可能同时影响可行性和最优性。,六、分析参数aij 的变化,例2.5.4 由于产品工艺结构改变，产品1的技术系数向量变为 P1=（4，5，2）T。每件产品的利润为4元（原来为2元）。问：该企业应如何安排生产计划？,解：先将改变工艺结构后的产品x1作为新产品看待。,4 x1 5/4-7/211/8-21/8

29、,由于x1是基变量，所以，要把 x1的系数列向量变成与 x1相同的单位列向量（主元素为5/4）。然后，把的x1系数列向量划去，仅保留的x1系数列向量。,x1+1/5 x4=16/5,-2 x3+6/5 x4+x5=76/5,x2+1/2 x3-2/5x4=-12/5,x2+1/2 x3-2/5x4=-12/5,x2 1/2 x3+2/5x4=12/5,+x6,x1,x5,-M x6 0 0 1 0,x4作为换入变量，2/5作为主元素，经过迭代获得最优解，如表示。,2/5,1.减少一个约束条件：通常，减少约束条件可以使变量的取值空间变大，自由度增加。如果要删除的约束与基变量无关，可以很方便地去掉

30、，因为此约束是多余约束；如果要删除的约束与基变量有关，删除此约束会影响到最优解。这时，可以在约束方程中同时加上和减去一个非负的松弛变量，经过迭代之后，约束会自动失去作用。,七、增加或减少一个约束条件的分析,2.增加一个约束条件：增加约束条件一般意味着活动空间的缩小，灵活性的降低。此时，通常有两种情况发生，一是基变量没有改变，二是基变量不适应新增加的约束条件。(1)第一种情况，因为增加约束可以使可行域减小或保持不变，只要基变量仍然可行，最优解肯定没变化。（方法：把基变量的值代入约束条件中，如果满足新的约束条件，就可断定最优解没有变化。(2)第二种情况，必须另找新的最优解。此时，只要在原来的单纯形表（注意：是最终单纯形表）里增加一行，用对偶单纯形法求解.,1 3 0 0 0,0 x6 0 0 0 1 0,对于例2.5.1的原问题，如果增加一道生产工序，要求产品满足约束条件 x1+3 x2 9，试问应如何安排生产，可以使利润最大？,0 x6 9,x1+3 x2 9,+x6=,第 六 节参数线性规划,（暂略）,