1、运筹学模型与软件运筹学模型与软件实践实践中国科学院研究生院中国科学院研究生院 Models and Software Practice of the Operations Research第三章对偶规划、灵敏度分析与实验第三章对偶规划、灵敏度分析与实验 对偶理论简介对偶理论简介 对偶线性规划应用对偶线性规划应用 单纯形方法的灵敏度分析单纯形方法的灵敏度分析 LINDO软件求解与灵敏度软件求解与灵敏度分析分析 投资的收益和风险组合问投资的收益和风险组合问题题 WinQSB软件的应用软件的应用 DUAL引入对偶问题引入对偶问题 (1)说法：说法：一般一般,我们把下面的两个现象称为对偶现象我们把下面
2、的两个现象称为对偶现象,例如例如“在在周长一定周长一定的四边形中的四边形中,以正方形的面积为以正方形的面积为最大最大”,或者或者“在在面积为一定面积为一定的四边形中的四边形中,以正方形的周长为以正方形的周长为最小最小”,这实际上是一个现象的两种提法。这实际上是一个现象的两种提法。引入对偶问题引入对偶问题 (2)实际的例子（汽车生产）：实际的例子（汽车生产）：某汽车工厂生产某汽车工厂生产大轿车大轿车和和载重汽车载重汽车两种型号的汽车两种型号的汽车，已知生产每辆汽车所用的钢材都是，已知生产每辆汽车所用的钢材都是2吨辆，该工厂每吨辆，该工厂每年供应的钢材是年供应的钢材是1600吨；工厂的生产能力是每
3、吨；工厂的生产能力是每2.5小时可小时可生产一辆载重汽车，每生产一辆载重汽车，每5小时可生产一辆大轿车，工厂全小时可生产一辆大轿车，工厂全年的有效工时为年的有效工时为2500小时；已知供应给该厂大轿车用的小时；已知供应给该厂大轿车用的座椅每年可装配座椅每年可装配400辆。出售一辆大轿车可获利辆。出售一辆大轿车可获利4千元，千元，出售一辆载重汽车可获利出售一辆载重汽车可获利3千元。问工厂如何安排生产才千元。问工厂如何安排生产才能获利最大能获利最大引入对偶问题引入对偶问题 现在提一个新的问题：现在提一个新的问题：如果工厂不再打算生产汽车，而是把如果工厂不再打算生产汽车，而是把钢材钢材和和座椅座椅以
4、以比买价高的价格比买价高的价格卖出，把工厂的卖出，把工厂的生产能力生产能力以以更高的工时更高的工时费费来接受外协加工，那么材料和工时的定价应该是多少来接受外协加工，那么材料和工时的定价应该是多少才划算？才划算？在考虑定价时，肯定要和生产汽车时在考虑定价时，肯定要和生产汽车时的情况进行比较，的情况进行比较，起码起码应当使两种情况应当使两种情况下的下的总利润相等总利润相等。设设y1表示表示出售单位钢材出售单位钢材的的利润利润，y2表示表示外协加工外协加工的工时的工时利润利润，y3表示出售每套表示出售每套大轿车座椅大轿车座椅的的利润利润，那，那么，用于生产一辆么，用于生产一辆载重汽车载重汽车的材料销
5、售利润和工时利的材料销售利润和工时利润之和润之和不应该低于不应该低于出售一辆载重汽车所得的利润，即出售一辆载重汽车所得的利润，即2y1+2.5y2=3 用于生产一辆用于生产一辆大轿车大轿车的材料销售利润、工时利润的材料销售利润、工时利润和座椅利润之和和座椅利润之和不低于不低于出售一辆大轿车所得的利润出售一辆大轿车所得的利润W=1600y1+2500y2+400y3 为了使材料的价格和工时费在市场上有竞争力，为了使材料的价格和工时费在市场上有竞争力，对工厂来说最佳的决策是，在满足上述的约束条件的对工厂来说最佳的决策是，在满足上述的约束条件的基础上，基础上，售价越低越好售价越低越好，这就是总利润，
6、这就是总利润最小值最小值。显然工厂决策者认为当显然工厂决策者认为当minW=maxZ时，这两种方案时，这两种方案具有相同的结果，都是最优解具有相同的结果，都是最优解一、对偶的定义一、对偶的定义原始问题原始问题min z=CTXs.t.AXbX 0对偶问题（旋转对偶问题（旋转90）max y=bTWs.t.ATWCW 0minbACTCATbTmaxmnmn对偶规划的要点对偶规划的要点 从从min变成变成max 价值系数与右端向量互换价值系数与右端向量互换 系数矩阵转置系数矩阵转置 按规则添上不等式按规则添上不等式二、对偶问题的性质二、对偶问题的性质对偶的对偶就是原始问题对偶的对偶就是原始问题m
7、ax z=-CTXs.t.-AX-bX 0min y=-bTWs.t.-ATW-CW 0min z=CTXs.t.AXb X 0对偶的定义对偶的定义对偶的定义对偶的定义max y=bTWs.t.ATWCW 0三、原始对偶关系三、原始对偶关系1、可行解的目标函数值之间的关系、可行解的目标函数值之间的关系 设设XF、WF分别是原始问题和对偶问题的可行解分别是原始问题和对偶问题的可行解z=CTXF WTAXF WTb=y2、最优解的目标函数值之间的关系最优解的目标函数值之间的关系 设设Xo、Wo分别是原始问题和对偶问题的最优解分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=y
8、3、原始问题和对偶问题最优解之间的互补松弛关系、原始问题和对偶问题最优解之间的互补松弛关系min z=CTXs.t.AXb X 0对偶对偶引进松弛变量引进松弛变量引进松弛变量引进松弛变量XTWS=0 WTXS=0互补松弛关系互补松弛关系X，XsW，Wsmin z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATWC W0max y=bTWs.t.ATW+WS=C W,WS0min z=CTXs.t.AX-XS=bX,XS 0max y=bTWs.t.ATW+WS=CW,WS 0XTWS=0WTXS=0mn=WWSATICn=AXS-IbnmmX原始问题和对偶问题变量、松弛
9、变量的维数原始问题和对偶问题变量、松弛变量的维数w1 wi wm wm+1 wm+j wn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjwm+j=0wixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0Kuhn-Tucher 条条件件3、原始问题和对偶问题最优解的充分必要条件、原始问题和对偶问题最优解的充分必要条件 (1)原始可行条件（原始可行条件（PFC）AX-XS
10、=bX,XS 0(2)对偶可行条件（对偶可行条件（DFC）ATW+WS=CW,WS 0(3)互补松弛条件（互补松弛条件（CSC）XTWS=0WTXS=0 任何线性规划问题都有其对偶问题任何线性规划问题都有其对偶问题 对偶问题有其明显的对偶问题有其明显的经济含义经济含义 假设有商人要向厂方购买资源假设有商人要向厂方购买资源A和和B，问他们谈判原料，问他们谈判原料价格的模型是怎样的？价格的模型是怎样的？0,B 15232A 25322.432)(max4321432143214321xxxxxxxxxxxxtsxxxxxf资源资源设设A、B资源的出售价格分别为资源的出售价格分别为 y1 和和 y2
11、显然商人希望总的收购价越小越好显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少工厂希望出售资源后所得不应比生产产品所得少0,4 423 3 332 2 22 1 12.2121212121yyyyyyyyyyts的所得的所得产品产品的所得的所得产品产品的所得的所得产品产品的所得的所得产品产品目标函数目标函数 min g(y)=25y1+15y20,B 15232A 25322.432)(max4321432143214321xxxxxxxxxxxxtsxxxxxf资源资源四、对偶的经济解释四、对偶的经济解释1、原始问题是利润最大化的生产计划问题原始问题是利润最大化的生产
12、计划问题0 xxxxxxbxxaxaxabxxaxaxabxxaxaxa.t.sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111222211单位产品的利润（单位产品的利润（元元/件）件）产品产量（件）产品产量（件）总利润（元）总利润（元）资源限量（吨）资源限量（吨）单位产品消耗的资源（吨单位产品消耗的资源（吨/件）件）剩余的资源（剩余的资源（吨）吨）消耗的资源（吨）消耗的资源（吨）2、对偶问题对偶问题0wwwwwwcwwawawacwwawawacwwawawa.t.swbwbwbyminnm2m1mm21nnmmmn2n21n12
13、2mm2m22211211mm1m221111mm2211资源限量（吨）资源限量（吨）资源价格（元资源价格（元/吨）吨）总利润（元）总利润（元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为称为m种资源的种资源的影子价格（影子价格（Shadow Price）原始和对偶问题都取得最优解时，原始和对偶问题都取得最优解时，最大利润最大利润 max z=min y3、资源影子价格的性质资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不
14、紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于0种资源的边际利润第种资源的增量第最大利润的增量iibzwiooimmii2211wbwbwbwbyzmmiii2211wbw)bb(wbwbzziiwbzw1w2wm4、产品的机会成本、产品的机会成本机会成本机会成本表示减少一件产品所节省的资源可以增加的利润表示减少一件产品所节省的资源可以增加的利润mmjiijjjwawawawa2211增加单位资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源减少一件产品可以节省的资源0 xxxxbxaxaxaxa
15、bxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211机会成本机会成本利润利润差额成本差额成本0wwwwwwcwwawawacwwawawacwwawawa.t.swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm22115、产品的差额成本（、产品的差额成本（Reduced Cost）差额成本差额成本=机会成本机会成本-利润利润jjTjmjmj22j11jmcaWc)awawaw(w0 x0w0w0 x0wx0w0
16、x0 x0w0 xwjjmjmjjmjiininiini在利润最大化的生产计划中在利润最大化的生产计划中（1）边际利润大于）边际利润大于0的资源没有剩余的资源没有剩余（2）有剩余的资源边际利润等于）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产）机会成本大于利润的产品不安排生产5、互补松弛关系的经济解释、互补松弛关系的经济解释理论部分介绍到这里理论部分介绍到这里五、对偶线性规划的应用五、对偶线性规划的应用五、对偶线性规划的应用五、对偶线性规划的应用 Lindo的求解过程及结果的求解过程及结果 Lingo求解模
17、型的例子灵敏度分析应用求解模型的例子灵敏度分析应用 一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产A1,A2两种奶制品，两种奶制品，1桶桶牛奶可以在甲车间用牛奶可以在甲车间用12小时加工成小时加工成3公斤公斤A1，或者在乙，或者在乙车间用车间用8小时加工成小时加工成4公斤公斤A2。根据市场需求，生产的。根据市场需求，生产的A1,A2全部能售出，且每公斤全部能售出，且每公斤A1获利获利24元，每公斤元，每公斤A2获获利利16元。现在加工厂每天能得到元。现在加工厂每天能得到50桶牛奶的供应，每天桶牛奶的供应，每天正式工人总的劳动时间正式工人总的劳动时间480小时，并且甲车间每天至多能小时，并且甲
18、车间每天至多能加工加工100公斤公斤A1，乙车间的加工能力没有限制。试为该，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大？厂制订一个生产计划，使每天获利最大？假设假设：x1x1为甲车间消耗的牛奶桶数，为甲车间消耗的牛奶桶数，x2x2为乙车间消耗的为乙车间消耗的牛奶桶数牛奶桶数进一步讨论以下进一步讨论以下3个附加问题个附加问题：1）若用若用35元可以买到元可以买到1桶牛奶，应否作这项投资？若投桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？资，每天最多购买多少桶牛奶？2）若可以聘用临时工人以增加劳动时间，付给临时工若可以聘用临时工人以增加劳动时间，付给临时工人的工资
19、最多是每小时几元？人的工资最多是每小时几元？3）由于市场需求变化，每公斤由于市场需求变化，每公斤A1的获利增加到的获利增加到30元，元，应否改变生产计划？应否改变生产计划？Lingo求解模型的例子灵敏度分析应用求解模型的例子灵敏度分析应用！目标描述目标描述；max=72*x1+64*x2;！约束条件描述约束条件描述；x1+x2=50;！牛奶的能力限制，不能超过！牛奶的能力限制，不能超过50桶牛奶桶牛奶12*x1+8*x2=480;！劳动时间的限制，不能超过！劳动时间的限制，不能超过480小小时时3*x1=100;！甲车间的生产能力限制，每天最多加工！甲车间的生产能力限制，每天最多加工100公斤
20、公斤Slack or Surplus给出这给出这3种资源在最优解下种资源在最优解下是否有剩余是否有剩余Dual Price 给出这给出这3种资源在最优解下种资源在最优解下“资源资源”增加增加1个个单位时单位时“效益效益”的增量的增量.经济学上称为影子价格，即经济学上称为影子价格，即1桶桶牛奶的影子价格为牛奶的影子价格为48元，元，1小时劳动的影子价格为小时劳动的影子价格为2元，元，车间甲的影子价格为零。车间甲的影子价格为零。“Reduced Cost”列出最优单纯形表中判列出最优单纯形表中判别数别数所在行所在行的变量的系数，的变量的系数，表示当变量有微表示当变量有微小变动时小变动时,目标函数的
21、变化率目标函数的变化率。其中基变量。其中基变量的的reduced cost值应为值应为0，对于非基变量对于非基变量 Xj,相应的相应的 reduced cost值表示当某个变量值表示当某个变量Xj 增加一个单位时目标函数减少的量增加一个单位时目标函数减少的量(max型问题型问题)。回答附加问题回答附加问题1：用：用35元可以买到元可以买到1桶牛奶，低于桶牛奶，低于1桶桶牛奶的影子价格牛奶的影子价格48，当然应该作这项投资。，当然应该作这项投资。回答附加问题回答附加问题2：聘用临时工人以增加劳动时间，付：聘用临时工人以增加劳动时间，付给的工资低于劳动时间的影子价格才可以增加利润给的工资低于劳动时
22、间的影子价格才可以增加利润，所以工资最多是每小时，所以工资最多是每小时2元。元。进行灵敏度分析：进行灵敏度分析：目标函数的系数发生变化时（假定约束条件进行灵敏度分析：目标函数的系数发生变化时（假定约束条件不变），可以给出最优基不变条件下目标函数系数的允许变化不变），可以给出最优基不变条件下目标函数系数的允许变化范围：范围：x1的系数为（的系数为（72-8，72+24）=（64，96）；）；x2的系数为的系数为（64-16，64+8）=（48，72）。）。（注意：（注意：x1系数的允许范围需要系数的允许范围需要x2系数系数64不变，反之亦然）不变，反之亦然）由于目标函数的费用系数变化并不影响约束
23、条件，因此此时最由于目标函数的费用系数变化并不影响约束条件，因此此时最优基不变可以保证最优解也不变，但最优值变化。优基不变可以保证最优解也不变，但最优值变化。用这个结果很容易回答附加问题用这个结果很容易回答附加问题3）：若每公斤）：若每公斤A1的获利增加的获利增加到到30元，则元，则x1系数变为系数变为303=90，在允许范围内，所以不应，在允许范围内，所以不应改变生产计划，但最优值变为改变生产计划，但最优值变为9020+6430=3720。影子价格的作用（即在最优解下影子价格的作用（即在最优解下“资源资源”增加增加1个单位时个单位时“效益效益”的增量）是的增量）是有限制的有限制的。影子价格在
24、影子价格在有意义条件下有意义条件下约束右端的限制范围：约束右端的限制范围：milk）原料最）原料最多增加多增加10（桶牛奶），（桶牛奶），time）劳动时间最多增加）劳动时间最多增加53（小时）。（小时）。现在可以回答附加问题现在可以回答附加问题1）的第）的第2问：虽然应该批准用问：虽然应该批准用35元买元买1桶桶牛奶的投资，但每天最多购买牛奶的投资，但每天最多购买10桶牛奶。此外，可以用低于每桶牛奶。此外，可以用低于每小时小时2元的工资聘用临时工人以增加劳动时间，但最多增加元的工资聘用临时工人以增加劳动时间，但最多增加53.3333小时。小时。灵敏性分析给出的只是最优基保持不变的充分条件，而
25、不一定灵敏性分析给出的只是最优基保持不变的充分条件，而不一定是必要条件。是必要条件。所以要使影子价格有意义，利润的增加要大于牛奶的投资。所以要使影子价格有意义，利润的增加要大于牛奶的投资。六、投资的收益和风险组合问题六、投资的收益和风险组合问题问题描述（问题描述（1）问题描述（问题描述（2）一、一、建模及求解过程建模及求解过程 模型的建立模型的建立 模型的简化和分析模型的简化和分析 使用偏好系数使用偏好系数 来分析模型来分析模型cWinQSB软件的应用软件的应用 例题求解例题求解第一步第一步 例题求解例题求解第二步第二步 例题求解例题求解第三步第三步 例题求解例题求解第四步第四步 例题求解例题求解第五步第五步 例题求解例题求解第六步第六步 使用使用Excel电子表格进行灵敏度分析电子表格进行灵敏度分析最优解无变化最优解无变化 使用使用Excel电子表格进行灵敏度分析电子表格进行灵敏度分析在选项中务必选择采用线性模型在选项中务必选择采用线性模型
