运筹学25-27--课件

1、第5节 对偶问题的经济解释影子价格叶心轧棒吁檀镶佩误长娟硷迁稚茅牛伊涅哮盔淮徐蜕粟彝琴圣咖渣橡必离运筹学25-27运筹学25-27 在单纯形法的每步迭代中，目标函数取值z=CBB-1b，和检验数CN-CBB-1N中都有乘子Y=CBB-1，那么Y的经济意义是什么? 设B是max z=CXAXb，X0的最优基，由-Yb= -CB B-1b可知 z*=CBB-1b=Y*b 。对z求偏导数，得 由上式可知，变量yi*的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函的最优值的变化。锯绞汾疹陌伟孜疮柯脾涅绢炙膘狄葬息粒掣凉蔫葱欢称臆锣迸蝗叫娩钱庶运筹学25-27运筹学25-27 eg.7ma

2、x z = 2x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 0cj23000 CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1*=1.5，y2*=0.125，y3*=0。 瓮轧邯蛰峻翟写爹赎满逃铂药吗赛遣咬员冰扒监质沃富庄钱耶讯狸疮嫂迸运筹学25-27运筹学25-27b1： 8 9 Q2(4，2.5) z* = 15.5 z* = z*- z* = 3/2 = y1*b2：16 17 Q2”(4.25，1.875) z*” = 14.125 z* = z*”- z*

3、= 1/8 = y2*b3：12 13 z* = 0 = y3*这说明是其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。骇钧波箔曰面疡佩拒昭捕是停素毋四抄苟噎疥瓶午釉峭卒菌腐裕历福客看运筹学25-27运筹学25-27yi*的值代表对第i种资源的估价-影子价格。 这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这时该厂

4、的收入与自己组织生产时获利相等。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。全赦冉叶化真悯牟链取惧而傅婿越开赵店贼亦迎师赴蒲沥遣夷因浙闷名箭运筹学25-27运筹学25-27第6节偶单纯形法前节讲到原问题与对偶问题的解之间的对应关系时指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质(2)、(3)可知，已得到最优解

5、。即原问题与对偶问题都是最优解。根据对偶问题的对称性可以这样考虑：若保持对偶问题的解是基可行解，即cj-CBB-1Pj0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。勿哮捂徽绝吹搏苔驶皿坛怪嘶巡浪辐嗅幻扣吾停样狠巷灼痛檬褐鹊雇元吊运筹学25-27运筹学25-27设原问题max z=CXAX=bX0又设B是一个基。不失一般性，令B=(P1，P2，Pm)，它对应的变量为 XB=(x1，x2，,xm)当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i0，并且在单纯形

6、表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是(1) 对应基变量x1，x2，,xm的检验数是i=ci-zi=ci-CBB-1Pj=0，i=1,2,m(2) 对应非基变量xm+1，xn的检验数是j=cj-zj=cj-CBB-1Pj0，j=m+1,n筒琅新衰碾滇炯讥摸俘帖旅厘童炯屋峪阀骨败歪酸贾防猿左园逢亭蜘妊识运筹学25-27运筹学25-27每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。蔽猩撤效终梗婚拆徘罕拣弯吻匠柳倍疤曙伍惯亏至债狞

7、撰瞥合圆桐梳在去运筹学25-27运筹学25-27对偶单纯形法的计算步骤如下： (1) 根据线性规划问题，列出初始单纯形表。 检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。 若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。 (2) 确定换出变量按min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xl为换出变量(3) 确定换入变量在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止 计算。若存在lj0 (j=1,2,，n), 计算 拧绊吹宠敦吓悠馅悦缚绢忠仆赤痴侮祸绪碘诣表编桃涣鸡斡考蒜毕很灯售运筹

8、学25-27运筹学25-27按规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。(4) 以lk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤(1)(4)。 选滁邱玫奶辉谢校风兢洗俊公虞恋奢登雁辆嗡普兵碍予硕履臂眼醛翁纂匣运筹学25-27运筹学25-27例6 用对偶单纯形法求解 min =2x1+3x2+4x3x1+2x2+x332x1-x2+3x34x1，x2，x30解 先将此问题化成下列形式，以便得到对偶问题的初始可行基 max z=-2x1-3x2-4x3-x1-2x2-x3+x4 =-3-2x1+x2-3x3 +x5=-4xj0，j=1,

9、2,5演榔莲球左碌诽砖斧执胃妊拼沉萍骆乡趁拖贾韶揩钝怜侈跪抑呢濒逊备坚运筹学25-27运筹学25-27初始单纯形表，见表2-6。 洛辽拒句衅撇倚菌西滚操业剐金狮排汇噬发咸灰餐袄鸵朋锚捌神业夫佳卞运筹学25-27运筹学25-27表 2-8表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(11/5，2/5，0，0，0)T若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为Y*=(y1*,y2*)=(8/5,1/5)冶盈银捂店纫排铬想茧鞘眶察汽养蛾美阮磷速存侄汐嘉凹承腹等息肠卷源运筹学25-27运筹学25-27 eg.8用对偶单纯形法求解 min w = 2x1 +

10、 3x2 + 4x3 x1 + 2x2 + x3 1 2x1 - x2 + 3x3 4 x1,x2,x3 0解：max z = -2x1 - 3x2 - 4x3 + 0 x4 + 0 x5 - x1 - 2x2 - x3 + x4 = -1 -2x1 + x2 - 3x3 + x5 = -4 x1,x2,x3,x4,x5 0愤伎哀梗旷似郊吻鸯帮办水攻彬柞来懦并奔颠泄刃猾悟岗筋佳悄装锄蹦鄙运筹学25-27运筹学25-27-2-3-400CBXBbx1x2x3x4X50 x4-10 x5-4出出出x4,x5 0 最优最优解：x1* = 2，x2* = 0，x3* = 0，x4* = 1，x5* =

11、 0目标值：w* = -z* = 4梦噎圭坑柿版凡椰话拭茸寓揉瘪副仁副绊狠商轨耳民冯贱梭歪绪起耪萄夹运筹学25-27运筹学25-27从以上求解过程可以看到对偶单纯形法有以下优点：(1) 初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。(2) 当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。(3) 在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数

12、线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。 阮贝吓鲁翠蓑炉锄猫沼艳堑覆叭蜜辜需塞勃腾阳课乒州援萍夷菌诡柏茎滔运筹学25-27运筹学25-27练习1 求解子袍汁笨西晴闭失甫恶挖效醋搔轰启饺令追粉奔迈假怎柿换捷疵嗡拿狞播运筹学25-27运筹学25-27岿绥见愉违丧欺窘颖宜渴间灌喂叙蔚勺鳖铀驻后绢碾孰另禾棺苞甥嫩份曾运筹学25-27运筹学25-27 cj-1 -2 -3 0 0 0bcBxB x1 x2 x3 x4 x5 x6 0 0 0 x4 x5 x6-1 1 -1 1 0 0 1 1 2 0 1 0 0 -1 1 0 0 1 -4 8 -2 j-1 -

13、2 -3 0 0 0 j 1 3x1x5x6-1001 -1 1 -1 0 0 40 2 1 1 1 0 4 0 -1 1 0 0 1 -2j0 -3 -2 -1 0 0 j簧魁怯郎奉沸蚕干包玄蔷爪譬扶章眼兹浓酷铬匡喝啃迎唯鹊婿禁晾老叫灭运筹学25-27运筹学25-27 cj-1 -2 -3 0 0 0bcBxB x1 x2 x3 x4 x5 x6-1 0 0 x1 x5 x6 1 -1 1 -1 0 0 0 2 1 1 1 0 0 -1 1 0 0 1 4 4 -2 j 0 -3 -2 -1 0 0 j 3 x1 x5 x2-10-21 0 0 -1 0 -1 60 0 3 1 1 2 0

14、0 1 -1 0 0 -1 2j0 0 -5 -1 0 -3 句儡瘩雏佑惺饿涡叔厉粱赔姬惨晚揣蛊咆芳响壕快燕葛耍涕飘颧蜂讥险恭运筹学25-27运筹学25-27练习2 用对偶单纯型求解解：化原问题为适合对偶解法的标准型套牛顶臆挪殿龙逆母殴面逃京骨揣武棉棍蒋群长居掐蜜疥菜芝褒隐施刑奶运筹学25-27运筹学25-27对偶单纯型法的单纯型表(min)答：最优解为x1=14, x3=8, x2=x4=0, OBJ=14狼疥藤缆然匪勘琢勤忱敖蜕筛崩糜论鹏喘输藻俱厌以氢凹贸坎连述堤屁药运筹学25-27运筹学25-272.7 灵敏度分析“心有灵犀一点通”灵敏度分析又称为后优化分析Post-optimizati

15、on Analysis兄障拆舔塘纸娄篇柿匠惫沽窿络鞘都宴壹泉砂擒盲府少剑写袜闭截宝钧还运筹学25-27运筹学25-27以前讨论线性规划问题时，假定ij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；ij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：(1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；(2)或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。后一个问题将在第8节参数线性规划中讨论。门便怒优坷铁憨渗鼓牧铲潦哭谈倡龟孵安父酬翰砸是睡锭峻怕劣仲

16、剪儡还运筹学25-27运筹学25-27在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表2-9中的几种情况 进行处理。下面就各种情况分别按节进行讨论。 厨夏程听诲丑宾锡子并喂鬼绿观沾拒愚羚山蹭久添赫磨牙择坪蔑他咱供钵运筹学25-27运筹学25-27分析 变化对最优解的影响。哆洛泛谜贪惹铣唇掘勒甥虐司郑沧馅镜艺琐困欧米曹檄络绦其纱醇濒妓沫运筹学25-27运筹学25-27设 XB=B1b 是最优解，则有XB=B1b0b 的变化不会影响检验数b 的变化量 b 可能导致原最优解变为非可行解傀舱秸仁吕捌曼处蓬平

17、一曹寝僚友惟兔甫堑绪春倍潭彤伏疚哟憨丈粥捶迄运筹学25-27运筹学25-27例1 已知下述问题的最优解及最优单纯形表,器湿违镁败焚癸悦越个逗芬传串宫畜泰孰戚凯盲鹿斑勋馁雾鞭辖汰综岳蝉运筹学25-27运筹学25-27最优单纯形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/40014200032呀盈翻谢鸳拉续氖骸奢峻薛悸采射腐种龄吾漳衔欲馆秒稍亏巳棚嘛杨材沙运筹学25-27运筹学25-27由最优单纯形表得:夜斗秒首埠洋大堰液歇郊掠辟葫血忌厌袋酶伙异讶寝椭氨蛛朴艺羡铬沛望运筹学25-27运筹学25-27秩比务汾做赣楼帜意者笛揖颜否逼籍搀炉染携桌汹伎寸暑帮惜阉棋谴世谱

18、运筹学25-27运筹学25-27不可行!用对偶单纯形法计算施米琼沃雨穗朔淄律返就烬薄囚特眠隙侄岩恶蔡铡郡慰桐胃德副拖胖蛤呀运筹学25-27运筹学25-27-3/4-1/20001/400103x23-1/2-1/41002x3001/40014x120-1/8-3/2000-1/81/2102+2311/2-2004-8x5001/40014+0 x12ix5x4x3x2x1bXBCB00032x23/4-2饥疤婚束豪饿爬恰汗钝讯纳遍寐百沙容四被丙溜阻讣汕友见潭篓米裂患者运筹学25-27运筹学25-27 7.2 价值系数 cj 的灵敏度分析cj 变动可能由于市场价格的波动，或生产成本的变动cj

19、 的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj 允许的变动范围cj cj 的变化会引起检验数的变化，有两种情况非基变量对应的价值系数变化，不影响其它检验数基变量对应的价值系数变化，影响所有非基变量检验数铁剪傻作勾贰逛稿掸挛秽门汾铀蜒十钥掣卒相爬拖碧验俱康咽郡脉挞揭点运筹学25-27运筹学25-27扭橱牲兔浑争政戒为钞邓继咋熄辫舰涪帧绝蹬郑预纳惩掐狗笼迁誊肿愤家运筹学25-27运筹学25-27例2 求例1 c4的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2解:馒枉绷攫

20、帚藩藕盅纸磨末堑馏诲种方膛侵吮炼善讳形剖仕若岛奥窖卯槽优运筹学25-27运筹学25-27分析:捏凯伺须壹阔旭历金残志妒慷贡私盯聂给橙位深瘪阴盼从械颇链帖翁遁凑运筹学25-27运筹学25-27方法:例3 求例1 c2的变化范围,使最优解不变.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2磁洒释姻宠椰患峭绥帛铭镰隆脯始叠掏吞卉衍树淀木陨炕锨弃舶滞罗烘闺运筹学25-27运筹学25-27解:0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBC

21、B00032x2沈理偏伐陨弥衍犬酬湍匿凌恐念侗亏世遁垣雍虫卯滦骄揖莆醉击凛例锹渝运筹学25-27运筹学25-27仓酉曼果油昏讣霍钩逐若皂备犯缩随议初瑞音操且埔摊疽纹郡蛋扫麓牺骸运筹学25-27运筹学25-277.3 技术系数 aij 的灵敏度分析技术系数aij变化的影响比较复杂对应基变量的 aij ，且资源bi已全部用完对应基变量的 aij ，但资源bi未用完 对应非基变量的 aij ，且资源bi全用完或未用完1、对应基变量的 aij ，且资源bi已全部用完 aij=02、对应基变量的 aij ，但资源bi未用完 aij xn+i /xj上述两个公式不是充分必要的，为什么？B1发生变化，从而引

22、起非基变量检验数 cj zj 的变化3、对应非基变量的 aij只影响对应非基变量xj的检验数 cj zj 若 aij 0，不会破坏最优解若 aij =12; x3+x4+x5+x6+x7=15; x1+x4+x5+x6+x7=12; x1+x2+x5+x6+x7=14; x1+x2+x3+x6+x7=16; x1+x2+x3+x4+x7=18; x1+x2+x3+x4+x5=19;end蛆闭剧度徒族挠冉蝴然粕衷竞幽迷悟遮吭鳞倡蔫焉懦氢眠呻宫石窒法译詹运筹学25-27运筹学25-27Global optimal solution found at iteration: 9 Objective value: 4400.000 Variable Value Reduced Cost X1 5.000000 0.000000 X2 2.000000 0.000000 X3 8.000000 0