第2章 对偶理论及灵敏度分析.ppt

《第2章 对偶理论及灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

第二章对偶理论及灵敏度分析2.1.1线性规划对偶问题2.1.2对偶问题的基本性质2.1.3影子价格2.1.4对偶单纯形法2.2.1灵敏度问题及其图解法2.2.2灵敏度分析 返回继续2.1.1线性规划的对偶问题一、对偶问题的提出二、原问题与对偶问题的数学模型三、原问题与对偶问题的对应关系 一、对偶问题的提出实例：某家电厂家利用现有资源生产两种产品，有关数据如下表：设备A设备B调试工序利润（元）0612521115时24时5时产品Ⅰ产品ⅡD 如何安排生产，使获利最多？厂家设Ⅰ产量–––––Ⅱ产量––––– 设：设备A——元／时设备B––––元／时调试工序––––元／时租赁付出的代价最小，且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。 设备A设备B调试工序利润（元）0612521115时24时5时ⅠⅡD厂家能接受的条件：租赁方的意愿：单位产品Ⅰ所需资源出租收入不低于2元单位产品Ⅱ所需资源出租收入不低于1元出让代价应不低于用同等数量的资源自己生产的利润。 厂家对偶问题原问题租赁厂家一对对偶问题 3个约束2个变量2个约束3个变量原问题对偶问题一般规律 特点：1．2．限定向量b价值向量C（资源向量）3．一个约束一个变量。4．的LP约束“”的LP是“”的约束。5．变量都是非负限制。其它形式的对偶? 二、原问题与对偶问题的数学模型1．对称形式的对偶当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。原问题对偶问题情形一： 原问题对偶问题化为标准对称型情形二：证明对偶 2、非对称形式的对偶若原问题的约束条件是等式，则原问题对偶问题 推导:原问题 根据对称形式的对偶模型,可直接写出上述问题的对偶问题: 令，得对偶问题为：证毕。 三、原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题） 例: 对偶问题为 返回结束线性规划的对偶问题 返回继续3.1.2对偶问题的基本性质引例对称性弱对偶性最优性对偶性（强对偶性）互补松弛性 对偶问题原问题租赁厂家引例 原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量原问题最终单纯形表： 原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表 （）原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量化为极小问题原问题最优解对偶问题最优解原问题化为极小问题，最终单纯形表： 两个问题作一比较:1.两者的最优值相同2.变量的解在两个单纯形表中互相包含原问题最优解（决策变量）对偶问题最优解（决策变量）对偶问题的松弛变量原问题的松弛变量 进一步来讨论它们之间的关系。从第1节得到检验数的表达式是CN−CBBN-1与−CBB-1由第1章已知：当检验数CN−CBBN-1≤0(2-9)−CBB-1≤0(2-10)时，表示线性规划问题已得到最优解。这也是最优解的判断条件。 现在讨论这两个条件。(1)由于(2-9)式，(2-10)式中都有乘子CBB-1，称它为单纯形乘子，用符号Y=CBB-1表示。由(2-10)式，得到Y≥0(2)对应基变量XB的检验数是0，CB−CBB-1B=0。包括基变量在内的所有检验数可用C−CBB-1A≤0表示。从此可得C−CBB-1A=C−YA≤0，移项后，得到YA≥C(3)Y由(2-10)式，得到−Y=−CBB-1(2-11)将(2-11)式两边右乘b，得到−Yb=−CBB-1b(2-12)Yb=CBB-1b=z，因Y的上界为无限大，所以只存在最小值。 (4)从这里可以得到另一个线性规划问题minw=YbYA≥CY≥0称它为原线性规划问题｛maxz=CX｜AX≤b，X≥0｝的对偶规划问题。 从引例中可见：原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅是第一个问题的另一种表达而已。理论证明：原问题与对偶问题解的关系 标准型原问题与对偶问题的关系 原问题（或对偶问题）对偶问题（或原问题） 对偶问题的基本性质一、对称定理：定理：对偶问题的对偶是原问题。设原问题（1）对偶问题（2） 证明：设原问题是maxz=CX;AX≤b；X≥0根据对偶问题的对称变换关系，可以找到它的对偶问题是minw=Yb;YA≥C；Y≥0若将上式两边取负号，又因minw=max(-ω)可得到max(−w)=−Yb;−YA≤−C；Y≥0根据对称变换关系，得到上式的对偶问题是min(−w′)=−CX；−AX≥−b;X≥0又因min(−w′)=maxw′，可得Maxw′=maxz=CX；AX≤b;X≥0这就是原问题。 对偶问题的基本性质二、弱对偶性定理：——若和分别是原问题（1）及对偶问题（2）的可行解，则有证明： 从弱对偶性可得到以下重要结论：（1）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。（2）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。（3）若原问题可行，但其目标函数值无界，则对偶问题无可行解。 （4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。（5）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。（6）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。原问题对偶问题 对偶问题的基本性质三、最优性定理：——若和分别是（1）和（2）的可行解，且有则分别是（1）和（2）的最优解。则为（1）的最优解，反过来可知：也是（2）的最优解。证明：因为（1）的任一可行解均满足 四、对偶定理（强对偶性）：——若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。对偶问题的基本性质 五、互补松弛性：——若分别是原问题（1）与对偶问题（2）的可行解，分别为（1）、（2）的松弛变量，则：为最优解 将原问题目标函数中的系数向量C用C=YA-YS代替得到z=(YA−YS)X=YAX−YSX(2-15)将对偶问题的目标函数中系数列向量b，用b=AX+XS代替后，得到w=Y(AX+XS)=YAX+YXS(2-16) 说明：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。 原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量 (7)原问题检验数与对偶问题解的关系设原问题是maxz=CX;AX+XS=b;X,XS≥0它的对偶问题是minw=Yb;YA−YS=C;Y,YS≥0则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系见表2-5。YS1是对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量。 证:设B是原问题的一个可行基，于是A=(B,N)；原问题可改写为maxz=CBXB+CNXNBXB+NXN+XS=bXB，XN，XS≥0相应地对偶问题可表示为minw=YbYB−YS1=CB(2-17)YN−YS2=CN(2-18)Y，YS1,YS2≥0这里YS=(YS1，YS2)。当求得原问题的一个解：XB=B-1b,其相应的检验数为CN−CBB-1N与−CBB-1现分析这些检验数与对偶问题的解之间的关系：令Y=CBB-1,将它代入(2-17)式，(2-18)式得YS1=0,−YS2=CN−CBB-1N证毕。 原问题（或对偶问题）对偶问题（或原问题） 原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表 例4已知线性规划问题maxz=x1+x2-x1+x2+x3≤2-2x1+x2-x3≤1x1,x2,x3≥0试用对偶理论证明上述线性规划问题无最优解。上述问题的对偶问题为minw=2y1+y2-y1-2y2≥1y1+y2≥1y1-y2≥0y1，y2≥0由第1约束条件，可知对偶问题无可行解；原问题虽然有可行解，但无最优解。 例5已知线性规划问题minw=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5≥42x1-x2+3x3+x4+x5≥3xj≥0，j=1，2，…，5已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解。maxz=4y1+3y2y1+2y2≤2①y1-y2≤3②2y1+3y2≤5③y1+y2≤2④3y1+y2≤3⑤y1，y2≥0将y1*=4/5,y2*=3/5的值代入约束条件，得②=1/5<3，③=17/5<5，④=7/5<2它们为严格不等式；由互补松弛性得x2*=x3*=x4*=0。因y1,y2>0；原问题的两个约束条件应取等式，故有x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原问题的最优解为X*=(1，0，0，0，1)T；w*=5 返回结束对偶问题的基本性质 返回继续2.1.3影子价格在单纯形法的每步迭代中，目标函数取值，和检验数中都有乘子，那么Y的经济意义是什么？ 当线性规划原问题求得最优解时，其对偶问题也得到最优解，且代入各自的目标函数后有：——是线性规划原问题约束条件的右端项，它代表第种资源的拥有量；（3） 影子价格的定义对偶变量的意义——代表在资源最优利用条件下对单位资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（shadowprice)。 原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量 影子价格的经济意义1．资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。市场价格影子价格市场企业 影子价格的经济意义2．影子价格是一种边际价格。，说明的值相当于在资源得到最优利用的生产条件下，每增加一个单位时目标函数的增量。 几何解释：引例图解法分析。（3，3）（15/4，5/4）,z=8.75（7/2，3/2），z=8.5 影子价格的经济意义3．资源的影子价格决定企业资源的买卖在纯市场经济条件下,当第2种资源的市场价格低于1/4时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这种资源。 4．在对偶问题的互补松弛性质中有这表明生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。影子价格也反映资源的稀缺程度,值越大越紧缺,可进行瓶颈分析. 5．从影子价格的含义上考察单纯形表的检验数的经济意义。（4）—生产第j中产品所消耗各项资源的影子价格的总和。（即隐含成本）可见，产品产值>隐含成本可生产该产品；否则，不安排生产。——检验数的经济意义松弛变量检验数—资源的边际价值非基决策变量检验数—产品的边际价值 互补松弛关系的经济解释以上性质同样于非对称形式。 原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量 影子价格的经济意义6．一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。影子价格本质是一种边际分析，根据实际情况解释经济学研究如何管理自己的稀缺资源 返回结束影子价格 2.1.4对偶单纯形法对偶单纯形法的基本思路对偶单纯形法的计算步骤返回继续 对偶单纯形法的基本思路单纯形法的基本思路：原问题基可行解最优解判断对偶问题的可行解对偶问题最优解判断对偶单纯形法基本思路 原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表 原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量 (7)原问题检验数与对偶问题解的关系设原问题是maxz=CX;AX+XS=b;X,XS≥0它的对偶问题是minw=Yb;YA−YS=C;Y,YS≥0则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系见表2-5。YS1是对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量。 对偶单纯形法的计算步骤线性规划问题不妨设为对偶问题的初始可行基，则。若，即表中原问题和对偶问题均为最优解，否则换基。 换基方法：确定换出基变量对应变量为换出基的变量确定换入基变量为主元素，为换入基变量 原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量 初始可行基例、用对偶单纯形法求解线性规划问题：对偶问题的初始可行基 例、用对偶单纯形法求解线性规划问题：使对偶问题基变量可行,换入换出换出 例、用对偶单纯形法求解线性规划问题： 最优解例、用对偶单纯形法求解线性规划问题： 对偶单纯性法的本质:在对偶问题的可行基解上迭代,找到原问题的可行解,从而得到原问题的最优解.AX=b,σ<=0,y=-σ>=0,X>=0 对偶单纯形法的优点：不需要人工变量；当变量多于约束时，用对偶单纯形法可减少迭代次数；在灵敏度分析中，有时需要用对偶单纯形法处理简化。对偶单纯形法缺点：在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。因此，对偶单纯形法一般不单独使用。 返回结束对偶单纯形法2.3(1)(2),2.4,2.5,2.7,2.8 2.2.1灵敏度问题及其图解法灵敏度问题灵敏度分析——图解法 灵敏度问题背景：线性规划问题中，都是常数，但这些系数是估计值和预测值。市场的变化值变化；工艺的变化值变化；资源的变化值变化。 问题：当这些系数中的一个或多个发生变化时，原最优解会怎样变化？当这些系数在什么范围内变化时，原最优解仍保持不变？若最优解发生变化，如何用最简单的方法找到现行的最优解？ 研究内容：研究线性规划中，的变化对最优解的影响。研究方法：图解法对偶理论分析仅适用于含2个变量的线性规划问题在单纯形表中进行分析 MaxZ=34x1+40x24x1+6x2482x1+2x2182x1+x216x1、x20线性规划模型灵敏度分析——图解法 x218—16—14—12—10—8—6—4—2—0|||||||||24681012141618x14x1+6x2482x1+2x2182x1+x216ABCDE(8,0)(0,6.8)最优解(3,6)4x1+6x2=482x1+2x2=18灵敏度分析——图解法 灵敏度分析—图解法18—16—14—12—10—8—6—4—2—0|||||||||24681012141618x14x1+6x2482x1+2x2182x1+x216ABCDE目标函数的系数34x1+40x2=Z40x2=-34x1+Zx2=-+34x1Z4040 灵敏度分析—图解法18—16—14—12—10—8—6—4—2—0|||||||||24681012141618x14x1+6x2482x1+2x2182x1+x216ABCDE目标函数的系数34x1+40x2=Z40x2=-34x1+Zx2=-+c1x1Zc2c2若c1增加（c2不变）新的最优解 灵敏度分析—图解法18—16—14—12—10—8—6—4—2—0|||||||||24681012141618x14x1+6x2482x1+2x2182x1+x216ABCDE目标函数的系数34x1+40x2=Z40x2=-34x1+Zx2=-+c1x1Zc2c2若c1减少新的最优解 18—16—14—12—10—8—6—4—2—0|||||||||24681012141618x14x1+6x2482x1+2x2182x1+x216ABCDE(斜率=-1)(斜率=-2/3)灵敏度分析—图解法最优解不变的范围（设c1固定c2可变） 2.2.1灵敏度问题及其图解法结束 2.2.2灵敏度分析一、分析的变化二、分析的变化三、增加一个变量的分析四、增加一个约束条件的分析五、分析的变化 研究内容：研究线性规划中，的变化对最优解的影响。常用公式： 实例：某家电厂家利用现有资源生产两种产品，有关数据如下表：设备A设备B调试工序利润（元）0612521115时24时5时ⅠⅡD 如何安排生产，使获利最多？厂家设Ⅰ产量–––––Ⅱ产量––––– 原问题最优解对偶问题最优解（相差负号）原问题的最终单纯形表： 一、分析的变化的变化仅影响的变化。设备A设备B调试工序利润（元）0612521115时24时5时ⅠⅡD1.52问题1：当该公司最优生产计划有何变化？ 最终单纯形表0×5/41.5×1/4+2×（-1/4）-1/80-（-1/8）= 最终单纯形表 换基后单纯形表为最优解 问题2：设产品II利润为，求原最优解不变时的范围。的变化仅影响的变化；在最后一张单纯形表中求出变化的；原最优解不变，即；由上述不等式可求出的范围。方法： 即产品II利润为时的最终单纯形表 二、分析的变化的变化仅影响，即原最优解的可行性可能会变化：可行性不变，则原最优解不变。可行性改变，则原最优解改变，用对偶单纯形法，找出最优解。 问题3：设备B的能力增加到32小时，原最优计划有何变化？ 代入单纯形表中可行性改变，用对偶单纯形法换基求解。主元 新的最优解换基迭代得： 问题4：设调试工序可用时间为小时，求，原最优解保持不变。原最优解保持不变，则 三、增加一个变量的分析增加一个变量相当于增加一种产品。分析步骤：1、计算2、计算3、若，原最优解不变；若，则按单纯形表继续迭代计算找出最优解。 问题5：设生产第三种产品，产量为件，对应的求最优生产计划。解： 代入最终原单纯形表中主元 换基后有： 四、增加一个约束条件的分析增加一个约束条件相当于增添一道工序。分析方法：将最优解代入新的约束中（1）若满足要求，则原最优解不变；（2）若不满足要求，则原最优解改变，将新增的约束条件添入最终的单纯形表中继续分析。 五、分析的变化若对应的变量为基变量，B将改变。需引入人工变量求出可行解，再用单纯形法求解。若对应的变量为非基变量，参见三的分析。 灵敏度分析的步骤归纳如下：（1）将参数的改变计算反映到最终单纯形表上；（2）检查原问题是否仍为可行解；（3）检查对偶问题是否仍为可行解；（4）按下表所列情况得出结论和决定继续计算的步骤。 原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代非可行解可行解用对偶单纯形法继续迭代非可行解非可行解编制新的单纯形表重新计算总之 清华大学出版社1201资源数量变化的分析资源数量变化是指资源中某系数br发生变化，即br′=br+Δbr。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为XB′=B-1(b+Δb)这里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB′为新的最优解。新的最优解的值可允许变化范围用以下方法确定。 清华大学出版社1211资源数量变化的分析新的最优解的值可允许变化范围用以下方法确定。 问题3：设备B的能力增加到32小时，原最优计划有何变化？ 原问题的最终单纯形表： 清华大学出版社1241资源数量变化的分析新的最优解的值可允许变化范围用以下方法确定。 代入单纯形表中可行性改变，用对偶单纯形法换基求解。主元 清华大学出版社1262价值系数cj的变化分析可以分别就cj是对应的非基变量和基变量两种情况来讨论。(1)若cj是非基变量xj的系数，这时它在计算表中所对应的检验数是σj=cj−CBB-1Pj或当cj变化Δcj后，要保证最终表中这个检验数仍小于或等于零，即σj’=cj−CBB-1Pj≤0那么cj+Δcj≤YPj，即Δcj的值必须小于或等于YPj−cj，才可以满足原最优解条件。这就可以确定Δcj的范围了。 清华大学出版社1272价值系数cj的变化分析(2)若cr是基变量xr的系数。因cr∈CB，当cr变化Δcr时，就引起CB的变化，这时(CB+ΔCB)B-1A=CBB-1A+(0，…，Δcr，…，0)B-1A=CBB-1A+Δcr(αr1,αr2,…，αrn)可见，当cr变化Δcr后，最终表中的检验数是σj′=cj−CBB-1A−Δcrrj，j=1,2,…，n若要求原最优解不变，即必须满足σj′≤0。于是得到 原问题的最终单纯形表： 清华大学出版社1292价值系数cj的变化分析Δcr可变化的范围是 清华大学出版社1302价值系数cj的变化分析例设基变量x2的系数c2变化Δc2，在原最优解不变条件下，确定Δc2的变化范围。解： 清华大学出版社1312价值系数cj的变化分析若保持原最优解，从检验数行可见应有由此可得Δc2≥−3和Δc2≤1。Δc2的变化范围为−3≤Δc2≤1即x2的价值系数c2可以在［0，4］之间变化，而不影响原最优解。 清华大学出版社1323技术系数αij的变化例分析原计划生产产品的工艺结构发生变化。仍以第1章例1为例，若原计划生产产品Ⅰ的工艺结构有了改进，这时有关它的技术系数向量变为P1′=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响?解：把改进工艺结构的产品Ⅰ看作产品Ⅰ′，设x1′为其产量。于是在原计算的最终表中以x1′代替x1，计算对应x1′的列向量。同时计算出x1′的检验数为c1′−CBB-1P1′=4−(1.5,0.125,0)(2,5,2)T=0.375将以上计算结果填入最终表x1′的列向量位置，得表。 清华大学出版社133 清华大学出版社1343技术系数αij的变化可见x1′为换入变量，x1为换出变量，经过迭代。得到 清华大学出版社1353技术系数αij的变化表中的结果已是最优解。即应当生产产品Ⅰ′，3.2单位；生产产品Ⅱ，0.8单位。可获利15.2元。注意：若碰到原问题和对偶问题均为非可行解时，就需要引进人工变量后重新求解。 清华大学出版社1363技术系数αij的变化例假设产品Ⅰ′的技术系数向量变为P1′=(4,5,2)T，而每件获利仍为4元。试问该厂应如何安排最优生产方案?解：方法与前例相同，以x1′代替x1，并计算列向量x1′的检验数为c1′−CBB-1P1′=4−（1.5,0.125,0)(4,5,2)T=−2.625。将这些数字填入最终表的x1列的位置，得到表。 清华大学出版社1373技术系数αij的变化将表2-16的x1′变换为基变量，替换x1，得表2-17。 清华大学出版社1383技术系数αij的变化从表2-17可见原问题和对偶问题都是非可行解。于是引入人工变量x6。因在表2-17中x2所在行，用方程表示时为0x1′+x2+0.5x3−0.4x4+0x5=−2.4引入人工变量x6后，便为−x2−0.5x3+0.4x4+x6=2.4将x6作为基变量代替x2，填入表2-17，得到表2-18。 清华大学出版社1393技术系数αij的变化这时可按单纯形法求解。x4为换入变量，x6为换出变量。经基变换运算后，得到表2-19的上表。在表2-19的上表中，确定x2为换入变量，x5为换出变量。经基变换运算后，得到表2-19的下表。此表的所有检验数都为非正，已得最优解。最优生产方案为生产产品Ⅰ′，0.667单位；产品Ⅱ，2.667单位，可得最大利润10.67元。 清华大学出版社1403技术系数αij的变化 原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代非可行解可行解用对偶单纯形法继续迭代非可行解非可行解编制新的单纯形表重新计算总之 3.2.2灵敏度分析结束2.9,2.10 参数线性规划