运筹学模型与软件实践.ppt

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