运筹学模型与软件实践课件

运筹学模型与软件实践中国科学院研究生院

ModelsandSoftwarePracticeoftheOperationsResearch运筹学模型与软件实践中国科学院研究生院Modelsand第三章对偶规划、灵敏度分析与实验对偶理论简介对偶线性规划应用单纯形方法的灵敏度分析LINDO软件求解与灵敏度分析投资的收益和风险组合问题WinQSB软件的应用

DUAL第三章对偶规划、灵敏度分析与实验对偶理论简介DUAL引入对偶问题(1)说法：一般,我们把下面的两个现象称为对偶现象,例如“在周长一定的四边形中,以正方形的面积为最大”,或者“在面积为一定的四边形中,以正方形的周长为最小”,这实际上是一个现象的两种提法。引入对偶问题(1)说法：引入对偶问题(2)实际的例子（汽车生产）：某汽车工厂生产大轿车和载重汽车两种型号的汽车，已知生产每辆汽车所用的钢材都是2吨／辆，该工厂每年供应的钢材是1600吨；工厂的生产能力是每2.5小时可生产一辆载重汽车，每5小时可生产一辆大轿车，工厂全年的有效工时为2500小时；已知供应给该厂大轿车用的座椅每年可装配400辆。出售一辆大轿车可获利4千元，出售一辆载重汽车可获利3千元。问工厂如何安排生产才能获利最大引入对偶问题(2)实际的例子（汽车生产）：引入对偶问题引入对偶问题现在提一个新的问题：

如果工厂不再打算生产汽车，而是把钢材和座椅以比买价高的价格卖出，把工厂的生产能力以更高的工时费来接受外协加工，那么材料和工时的定价应该是多少才划算？现在提一个新的问题：在考虑定价时，肯定要和生产汽车时的情况进行比较，起码应当使两种情况下的总利润相等。在考虑定价时，肯定要和生产汽车时的情况进行比较设y1表示出售单位钢材的利润，y2表示外协加工的工时利润，y3表示出售每套大轿车座椅的利润，那么，用于生产一辆载重汽车的材料销售利润和工时利润之和不应该低于出售一辆载重汽车所得的利润，即

2y1+2.5y2>=3用于生产一辆大轿车的材料销售利润、工时利润和座椅利润之和不低于出售一辆大轿车所得的利润

W>=1600y1+2500y2+400y3为了使材料的价格和工时费在市场上有竞争力，对工厂来说最佳的决策是，在满足上述的约束条件的基础上，售价越低越好，这就是总利润最小值。设y1表示出售单位钢材的利润，y2表示外协加工显然工厂决策者认为当minW=maxZ时，这两种方案具有相同的结果，都是最优解显然工厂决策者认为当minW=maxZ时，这两种方案具有相同一、对偶的定义原始问题minz=CTXs.t. AX≥b X≥0对偶问题（旋转90°）maxy=bTWs.t.ATW≤C W≥0≥minbACTCATbT≤maxmnmn一、对偶的定义原始问题对偶问题（旋转90°）≥minbACT对偶规划的要点从min变成max价值系数与右端向量互换系数矩阵转置按规则添上不等式对偶规划的要点从min变成max二、对偶问题的性质对偶的对偶就是原始问题maxz’=-CTXs.t.-AX≤-b X≥0miny=-bTWs.t.-ATW≥-C W≥0minz=CTXs.t.AX≥b X≥0对偶的定义对偶的定义maxy=bTWs.t.ATW≤C W≥0二、对偶问题的性质对偶的对偶就是原始问题maxz’=-CT三、原始对偶关系1、可行解的目标函数值之间的关系

设XF、WF分别是原始问题和对偶问题的可行解

z=CTXF≥WTAXF≥WTb=y2、最优解的目标函数值之间的关系

设Xo、Wo分别是原始问题和对偶问题的最优解

z=CTXo=WoTAXo=WoTb=y三、原始对偶关系1、可行解的目标函数值之间的关系3、原始问题和对偶问题最优解之间的互补松弛关系minz=CTXs.t.AX≥bX≥0对偶引进松弛变量引进松弛变量XTWS=0WTXS=0互补松弛关系X，XsW，Wsminz=CTXs.t.AX-XS=bX,XS≥0maxy=bTWs.t.ATW≤CW≥0maxy=bTWs.t.ATW+WS=CW,WS≥03、原始问题和对偶问题最优解之间的互补松弛关系minz=Cminz=CTXs.t. AX-XS=b X,XS≥0maxy=bTWs.t.ATW+WS=C W,WS

≥0XTWS=0WTXS=0mn=WWSATICn=AXS-IbnmmX原始问题和对偶问题变量、松弛变量的维数minz=CTXmaxy=bTWXTWS=0mn=WWSw1wiwmwm+1wm+jwn+m

x1xjxnxn+1xn+ixn+m

对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjwm+j=0 wixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0w1wiwmwm+1Kuhn-Tucher条件3、原始问题和对偶问题最优解的充分必要条件(1)原始可行条件（PFC）

AX-XS=b X,XS≥0 (2)对偶可行条件（DFC）

ATW+WS=C W,WS≥0 (3)互补松弛条件（CSC）

XTWS=0 WTXS=0Kuhn-Tucher条件3、原始问题和对偶问题最优解的充任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？任何线性规划问题都有其对偶问题假设有商人要向厂方购买设A、B资源的出售价格分别为y1

和

y2显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少目标函数ming(y)=25y1+15y2设A、B资源的出售价格分别为y1和y2目标函数mi四、对偶的经济解释1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）四、对偶的经济解释1、原始问题是利润最大化的生产计划问题单位2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、...、wm称为m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润maxz=miny2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于03、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺w1w2wm4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源w14、产品的机会成本机会成本增加单位资源可以增加的利润减少机会成本利润差额成本5、产品的差额成本（ReducedCost）差额成本=机会成本-利润机会成本利润差额成本5、产品的差额成本（ReducedCo在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产5、互补松弛关系的经济解释在利润最大化的生产计划中5、互补松弛关系的经济解释理论部分介绍到这里理论部分介绍到这里运筹学模型与软件实践课件五、对偶线性规划的应用五、对偶线性规划的应用五、对偶线性规划的应用五、对偶线性规划的应用运筹学模型与软件实践课件运筹学模型与软件实践课件运筹学模型与软件实践课件运筹学模型与软件实践课件Lindo的求解过程及结果Lindo的求解过程及结果Lingo求解模型的例子－－灵敏度分析应用

一奶制品加工厂用牛奶生产A1,A2两种奶制品，1桶牛奶可以在甲车间用12小时加工成3公斤A1，或者在乙车间用8小时加工成4公斤A2。根据市场需求，生产的A1,A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间480小时，并且甲车间每天至多能加工100公斤A1，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大？假设：x1为甲车间消耗的牛奶桶数，x2为乙车间消耗的牛奶桶数Lingo求解模型的例子－－灵敏度分析应用一进一步讨论以下3个附加问题：1）若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？Lingo求解模型的例子－－灵敏度分析应用

Lingo求解模型的例子－－灵敏度分析应用！目标描述；max=72*x1+64*x2;！约束条件描述；x1+x2<=50; ！牛奶的能力限制，不能超过50桶牛奶 12*x1+8*x2<=480;！劳动时间的限制，不能超过480小时3*x1<=100; ！甲车间的生产能力限制，每天最多加工100公斤！目标描述；SlackorSurplus给出这3种资源在最优解下是否有剩余DualPrice给出这3种资源在最优解下“资源”增加1个单位时“效益”的增量.经济学上称为影子价格，即1桶牛奶的影子价格为48元，1小时劳动的影子价格为2元，车间甲的影子价格为零。SlackorSurplus给出这3种资源在最优解下是否

“ReducedCost”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时,目标函数的变化率。其中基变量的reducedcost值应为0，对于非基变量Xj,相应的reducedcost值表示当某个变量Xj增加一个单位时目标函数减少的量(max型问题)。“ReducedCost”列出最优单纯形表中判别数所在行回答附加问题1：用35元可以买到1桶牛奶，低于1桶牛奶的影子价格48，当然应该作这项投资。回答附加问题2：聘用临时工人以增加劳动时间，付给的工资低于劳动时间的影子价格才可以增加利润，所以工资最多是每小时2元。回答附加问题1：用35元可以买到1桶牛奶，低于1桶牛奶的影子进行灵敏度分析：进行灵敏度分析：进行灵敏度分析：目标函数的系数发生变化时（假定约束条件不变），可以给出最优基不变条件下目标函数系数的允许变化范围：x1的系数为（72-8，72+24）=（64，96）；x2的系数为（64-16，64+8）=（48，72）。（注意：x1系数的允许范围需要x2系数64不变，反之亦然）由于目标函数的费用系数变化并不影响约束条件，因此此时最优基不变可以保证最优解也不变，但最优值变化。用这个结果很容易回答附加问题3）：若每公斤A1的获利增加到30元，则x1系数变为30×3=90，在允许范围内，所以不应改变生产计划，但最优值变为90×20+64×30=3720。进行灵敏度分析：目标函数的系数发生变化时（假定约束条件不变）影子价格的作用（即在最优解下“资源”增加1个单位时“效益”的增量）是有限制的。影子价格在有意义条件下约束右端的限制范围：milk）原料最多增加10（桶牛奶），time）劳动时间最多增加53（小时）。现在可以回答附加问题1）的第2问：虽然应该批准用