《线性规划对偶理论及其应用》由会员分享，可在线阅读，更多相关《线性规划对偶理论及其应用（127页珍藏版）》请在金锄头文库上搜索。
1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外 线性规划对偶理论线性规划对偶理论运筹学君子曰：学不可以已。君子曰：学不可以已。青，取之于蓝而青于蓝；冰，水为之而寒于水。青，取之于蓝而青于蓝；冰，水为之而寒于水。故不登高山，不知天之高也；故不登高山，不知天之高也；不临深溪，不知地之厚也；不临深溪，不知地之厚也； 荀子劝学荀子劝学置焰嚎淮毛耶泻诊营潜惋瞒览帽扼蚂晋哗痰贮翔诅攀泵效扇协森峪进熏壁线性规划对偶理论及其应用线性规划对偶理论及其应用掌握掌握线性规划对偶理论及其基本经济学意义；教学要求：教学要求：了解了解运用对偶理论对线性规划最优解进行分析的基本方法；会会运用对偶理论对
2、一些基本的管理问题进行经济学分析。第三章线性规划对偶理论第三章线性规划对偶理论稀际筛宅场烯绳悟萎官魄逢促抚墨好呜撅耕貌橇伞桅炒募疥早衙杏剑斌三线性规划对偶理论及其应用线性规划对偶理论及其应用p线性规划的对偶问题线性规划的对偶问题p对偶规划的基本性质对偶规划的基本性质p对偶单纯形法对偶单纯形法p影子价格和灵敏度分析影子价格和灵敏度分析重点：对偶转换、对偶单纯形法重点：对偶转换、对偶单纯形法难点：对偶性质、灵敏度分析难点：对偶性质、灵敏度分析第三章线性规划对偶理论第三章线性规划对偶理论碴团它测阂吹茸炽宏赠谜浚闪肄届叠汕哆叭淡束屋懂猾焕酬芭菩夸卫辞咎线性规划对偶理论及其应用线性规划对偶理论及其应用某
3、家具厂木器车间生产木门和木窗两种产品，加工木门收入为某家具厂木器车间生产木门和木窗两种产品，加工木门收入为56元元/扇、加工木窗收入为扇、加工木窗收入为30元元/扇，生产扇，生产 一扇木门需要木工一扇木门需要木工4小时，油漆工小时，油漆工2小时；生产一扇木窗需要木工小时；生产一扇木窗需要木工3小时，油漆工小时，油漆工1小小时，该车间可用本工总工时为时，该车间可用本工总工时为120小时，油漆工总工时为小时，油漆工总工时为50小小时问该车间应如何安排生产才能使每日收入最大？时问该车间应如何安排生产才能使每日收入最大？令该车间每日安排生产木门令该车间每日安排生产木门x1,木窗木窗x2扇，则其数学模型
4、为：扇，则其数学模型为：max z=56x1+30x2s.t 4x1+3x2120 2x1+x2 50 x1,x20即每日安排生产木门即每日安排生产木门15扇，木窗扇，木窗20扇时，收入最大为扇时，收入最大为1440元元一、一、对偶问题的提出最优解为：最优解为：X=(15,20)，最优值为最优值为1440元元第一节线性规划的对偶问题第一节线性规划的对偶问题烦憋径圣锌凯爸镶玛正翼酱蓑磐归拜巡茶悲始晦显混雷阁摇摘陈翌滴瞬啸线性规划对偶理论及其应用线性规划对偶理论及其应用 假若有一个个体经营者，手中有一批木器家具生产订单，但无人手加工，因此想利用该木器车间的木工与油漆工来加工完成他的订单，它需要考虑
5、付给该车间每个工时的价格 那他应如何定价才能使木器车间觉得有利可图从而愿意替他加工这批订单，同时又使自己所付的工时费用总数最少？设w1,w2分别为付给木工、油漆工每个工时的价格，则该个体经营者的目标函数为：min f=120w1+50w2第一节线性规划的对偶问题第一节线性规划的对偶问题界活蘑示窜舜彪怎蔓毫轧替炽哟氨泉焰赣淖巢冈咏荔建苑板酝道痹屉词基线性规划对偶理论及其应用线性规划对偶理论及其应用另外，该个体经营者所付的价格不能太低，至少不能低于该另外，该个体经营者所付的价格不能太低，至少不能低于该车间生产木门和木窗所得到的收入，否则该车间觉得无利可车间生产木门和木窗所得到的收入，否则该车间觉得
6、无利可图就不会替他加工这批订单，因此，图就不会替他加工这批订单，因此，w1,w2 应满足应满足 4w1+2w2 56上式可理解：生产一扇木门的木工工时上式可理解：生产一扇木门的木工工时*木工工时价木工工时价+生产生产一扇木门的油漆工时一扇木门的油漆工时*油漆工工时价油漆工工时价生产一扇木门的收入生产一扇木门的收入 3w1+w2 30上式可理解：生产一扇木窗的木工工时上式可理解：生产一扇木窗的木工工时*木工工时价木工工时价+生产生产一扇木窗的油漆工时一扇木窗的油漆工时*油漆工工时价油漆工工时价生产一扇木窗的收入生产一扇木窗的收入第一节线性规划的对偶问题第一节线性规划的对偶问题柏净颇矿莹盗辞降绢缄
7、扼访若名一查胡活磨囊旬佯诫管感兰笛袭馈酸由百线性规划对偶理论及其应用线性规划对偶理论及其应用该个体经营者的数学模型为min f=120w1+50w24w1+2w2 563w1+w2 30W1,w2 0解得解得w1=2,w2=24,f=1440第一节线性规划的对偶问题第一节线性规划的对偶问题奥朝敌炭奸铡绷表黍吐诣慑懂老绢扇蹈旋栓勉溪茁顷处最雹诉透兔座车窒线性规划对偶理论及其应用线性规划对偶理论及其应用第一节线性规划的对偶问题第一节线性规划的对偶问题一、一、对偶问题的提出原问题原问题某工厂甲生产A、B、C三种产品。这三种产品的单位利润分别是60、30、20。生产这三种单位产品所占用M、N、P三种机
8、器的时间如表所示，机器M、N、P每天可供使用的时间分别是48、20、8小时。这三种产品每天生产多少才能使工厂获得最大效益。产品机器ABC资源限制M86148N421.520P210.58利润603020该问题的数学模型为：该问题的数学模型为：M机器机器N机器机器P机器机器争樟膛僧匡杠煤掸批藩挽尾槐拜牛描漓醋券愿铃丘辕阮帅诫撰庐风灿傀让线性规划对偶理论及其应用线性规划对偶理论及其应用 现在甲厂拟出租机器给乙厂，即甲厂出租机器现在甲厂拟出租机器给乙厂，即甲厂出租机器M、N和和P给乙厂，请问甲厂应如何给这三种机器定价？给乙厂，请问甲厂应如何给这三种机器定价？考虑：1、定价不能太低太低？2、定价不能太
9、高太高？既要保证甲厂利润又必须使乙厂的租金越少越好咋办？第一节线性规划的对偶问题第一节线性规划的对偶问题楷尊若柯筑山唐壳隆哟植牙毋临泼虚脑电牢势逾稼畸暴甩例疼虏哼歹陵腺线性规划对偶理论及其应用线性规划对偶理论及其应用产品机器ABC资源限制M86148y1N421.520y2P210.58y3利润 60 3020设M、N、P机器的单位出售价格分别为 y1 、 y2和y3，针对乙厂，建立其相应的数学模型：目标：目标：min w=48y1+20y2+8y3对于A产品而言，甲厂生产一件产品可获利60元，如果8y1+4y2+2y30 0 ，则有，则有y y0 0p pj j=c=cj j2. 2. 如果
10、如果y y0 0p pj jccj j, ,则有则有x x0 0=0=03. 3. 如果如果y y0 0i i00，则有，则有A Ai ix xi i0 0 =b=bi i4.4.如果如果A Ai ix xi i0 0 b,0，由松驰性质得到原问题约束条件应取等号即，由松驰性质得到原问题约束条件应取等号即w10 2x3+3x4=20w2 0 3x3+2x4=20， 解方程组，得解方程组，得x3=x4=4故原问题的最优解为故原问题的最优解为(0,0,4,4)第二节对偶规划的基本性质第二节对偶规划的基本性质 w1+2w212w1+w222w1+3w2=33w1+2w2=4x1=0x2=0皿蜂陶椽差
11、锹拈饵叮身剪搓阻蛋字棋鼠转稿习惶逸傀谋兵啪徐胸纹迢聋此线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.3已知线性规划问题已知线性规划问题Max z=2x1+x2+5x3+6x4s.T 2x1 + x3+ x4 8 2x1+2x2+x3+2x412 x1 ,x2 ,x3 , x4 , 0其对偶问题的最优解为其对偶问题的最优解为w=(4,1)T，试根据对偶理论求出原问题的最优解，试根据对偶理论求出原问题的最优解解，该原问题的对偶问题为：解，该原问题的对偶问题为：min Y=8w1+12w2s.t 2w1+2w2 2 (1) 2w1+2w22 x1=0 2w2 1 (2) 2w21 x2=0
12、 w1+ w2 5 (3) w1+w2=5 w1+2w2 6 (4) w1+2w2=6 w1,w2 0将对偶问题的最优解代入，得到将对偶问题的最优解代入，得到(1),(2)为严格不等式，故由互补松驰性质得到为严格不等式，故由互补松驰性质得到X1=x2=0又又w1,w20，由松驰性质得到原问题约束条件应取等号即，由松驰性质得到原问题约束条件应取等号即W10 x3+x4=8W20 x3+2x4=12，解方程组，得，解方程组，得x3=x4=4故问题的最优解为（故问题的最优解为（0,0，4,4）第二节对偶规划的基本性质第二节对偶规划的基本性质 趟峪沧揪尤朱严撬云纯励蓑就沂剿南啡淹付阎赎赤环庐缎钻喊臻希
13、亲跳兹线性规划对偶理论及其应用线性规划对偶理论及其应用第三节对偶单纯形法第三节对偶单纯形法 一、对偶单纯形法原理一、对偶单纯形法原理 对偶单纯形法是利用对偶原理求解原问题的一对偶单纯形法是利用对偶原理求解原问题的一种方法（而不是求解对偶问题的方法）种方法（而不是求解对偶问题的方法） 对偶单纯形法基本思想是：首先从原问题的一对偶单纯形法基本思想是：首先从原问题的一个对偶可行的基本解个对偶可行的基本解(它不是原线性规划问题的可它不是原线性规划问题的可行解行解)出发，求改进的对偶可行的基本解，向原问出发，求改进的对偶可行的基本解，向原问题的题的 可行域逼近，当求到对偶可行的基本解是原可行域逼近，当求
14、到对偶可行的基本解是原问题的可行解时，就得到了最优解。问题的可行解时，就得到了最优解。剿贯墩疗冰省个涵票仗蒜位禁莉撑沂炊耐曾虱萨桅滤展螟撞碑受塌匠蹲驾线性规划对偶理论及其应用线性规划对偶理论及其应用p原单纯型迭代要求每步都是基础可行解p达到最优解时，检验数 cjzj 0 (max) 或 cjzj 0 (min)p但对于(min, )型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决p大M法和二阶段法较繁p能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件， cjzj 0 (max) 或 cjzj 0 (min)n每步迭代保持检验数满足最优条件，但减少非可行度n
15、如何判断达到最优解n如何保证初始基础解满足最优条件b=B1b0劈涂献迹呢厉论斋仰歹伯戌翁纤罩赖盂衡码酬螟蹈支注批藤俞涨洱评像锄线性规划对偶理论及其应用线性规划对偶理论及其应用考虑对偶线性规划问题 min z=cxs.t Ax=b x0其中A=(p1,p2,pn)B=(b1,b2,.bn)Bi可以是任意数第三节对偶单纯形法第三节对偶单纯形法 募六乞太挪酵庚羹橙钩垄劝猴距福兹谜苟遏侍记蹋辩酉劲迹怠挛驶输茫友线性规划对偶理论及其应用线性规划对偶理论及其应用二、对偶单纯形法的计算步骤：二、对偶单纯形法的计算步骤：1、给定一个初始对偶可行的基本解，设相应的基为B；2若 ，则停止计算，现行对偶可行的基本解
16、为最优解。否则令 ，则该行所对应的变量xr 为换出基的变量； 3若对所有j， ，则停止计算，原问题无可行解。否则，令则 为换入基的变量；4以 为主元进行主元消去，返回2。第三节对偶单纯形法第三节对偶单纯形法 拉堑狼笋砷恢乡酉辫劲塘锥艳航薯备墙梗屁梭煞捣楚剔压涣崩挺盗捐的奉线性规划对偶理论及其应用线性规划对偶理论及其应用标准化乘以(-1)3100Bx1x2x3x40x3-1-1-1100x4-2-2-3013100初始对偶单纯形表：初始对偶单纯形表：出基出基进基进基主元主元 直到直到B0，停止，停止第三节对偶单纯形法第三节对偶单纯形法 为了得了初始基本解，为了得了初始基本解，可用大可用大M法和两
17、阶段法法和两阶段法例例亭淄鸟整蚕就哥叼舟缕裴阜撇哟眺秃簿忙俺谍骄河趾遗秆幸躁沪焰站皱巩线性规划对偶理论及其应用线性规划对偶理论及其应用3100cbxbBx1x2x3x40x3-1/3-1/301-1/30x22/32/310-1/37/3001/3 3100cbxbBx1x2x3x40x4110-311x2111-102010因为因为B0，且所有检验数，且所有检验数 cj-zj0,运算结束，得到最优解为运算结束，得到最优解为x1=0,x2=1 最优目标值为最优目标值为 fmin=1表二表二表三表三第三节对偶单纯形法第三节对偶单纯形法 毕全锨费痴续丙尊赛揪梧老羽款宣踢挽连秒裹跌楞粕辗沙昨雾辛倡郭
18、奥谁线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.4用对偶单纯形法求解线性规划用对偶单纯形法求解线性规划解：在第解：在第2 2个约束方程的两边同乘以个约束方程的两边同乘以-1-1，然后引入变量，然后引入变量x x4 4,x,x5 5得：得： 第三节对偶单纯形法第三节对偶单纯形法 柱屠未曰墙钡缚豌佃骂滓呈砸抹蜘就庆脐俩印效譬乙受盏扒丰掌医炼损叫线性规划对偶理论及其应用线性规划对偶理论及其应用13200CbXbbx1x2x3x4x50x4863-4100x5-2-3-1301Cj-zj01320013200CbXbbx1x2x3x4x50x44012121x12/311/3-10-1/3
19、Cj-zj-2/308/3301/3 表一表一表二表二用对偶单纯形法求解得最优解用对偶单纯形法求解得最优解 ：最优目标函数值最优目标函数值 ：fmin=2/3第三节对偶单纯形法第三节对偶单纯形法 廊恰延傅寥央裳键斑胳邯缺达丁粱甄糟撞力跑祈梨鼓挎栈蜡阉附衅浴敬席线性规划对偶理论及其应用线性规划对偶理论及其应用例3.5 某工厂有生产A、B两种化工产品 的能力，生产一千克A产品需要2小时，花费成本为2元，而生产一千克B产品则需要1小时，成本为3元，下个月的总生产时间是600小时，公司决定A，B的总产量至少为350千克，此外公司的一个主要客户订购了125千克A产品的要求必须满足，在满足客户要求的前提下
20、，公司应怎样安排生产计划，才能尽量降低成本？解 设A产品的产量为x1千克，B产品的产量为x2千克，则建立相应模型Min z=2x1+3x2s.t x1 125 x1+x2 350 2x1+x2600 x1,x2 0第三节对偶单纯形法第三节对偶单纯形法 注滞募奉抠央衙烙耙蓬媳蓟狈亦洛鲜嫉旅叁更掐文垃恶叹相握屿题凉老巨线性规划对偶理论及其应用线性规划对偶理论及其应用在第一、二两个约束条件两边同乘以-1，然后引入变量x3,x4,x5，化为如下形式Minz=2x1+3x2s.T -x1 +x3 =-125 -x1-x2 +x4 =-135 2x1+x2 +x5=600 x1,x2,x3,x4,x50表
21、一23000cbxbBx1x2x3x4x50x3-125-101000x4-350-1-10100x56002100123000 第三节对偶单纯形法第三节对偶单纯形法 信蜜预裕颊弘励吟常之斋绥歼树弃脓色疲捎锗块敬吉块行菲诺蹄替环尽侣线性规划对偶理论及其应用线性规划对偶理论及其应用表二23000cbxbBx1x2x3x4x50x3225011-102x1350110-100x5-1000-102101020表三23000cbxbBx1x2x3x4x50x3125001112x1250100113x2100010-2-100041此时所有此时所有b且所有检验数大于等于且所有检验数大于等于0，所得得
22、到最优解为，所得得到最优解为x1=250,x2=100,x3=125 最优值为最优值为800 第三节对偶单纯形法第三节对偶单纯形法 氨督攫辉郴伟屯炼货厂袭徘筐紧光寂肌番炸例杠焦抡侄户滞耘邱设匝那寄线性规划对偶理论及其应用线性规划对偶理论及其应用三、单纯形算法和对偶单纯形算法之差别三、单纯形算法和对偶单纯形算法之差别 第三节对偶单纯形法第三节对偶单纯形法 照汕晰害宜镑座悄音垫雏霍爷债蔬键艇都臃引助奇剩莉胎倦特利荤欺爆坎线性规划对偶理论及其应用线性规划对偶理论及其应用四、原问题检验数与对偶问题的解的总结四、原问题检验数与对偶问题的解的总结在主对偶定理的证明中我们有：对偶在主对偶定理的证明中我们有：
23、对偶(min型型)变量的最变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值量检验数的绝对值不管原问题是否标准，在不管原问题是否标准，在最优解的单纯型表中，都有原问最优解的单纯型表中，都有原问题题虚变量虚变量(松弛或剩余松弛或剩余) 的检验数对应其对偶问题的检验数对应其对偶问题实变量实变量 (对对偶变量偶变量)的最优解的最优解，原问题原问题实变量实变量(决策变量决策变量) 的检验数对应的检验数对应其对偶问题其对偶问题虚变量虚变量 (松弛或剩余变量松弛或剩余变量)的最优解。的最优解。第三节对偶单纯形法第三节对偶单纯形法
24、 询贩尿李湍讽汇仗辕粉猪曾砖泵苹珠购仪光涕媳杜取材堕瘪锭叮垢荷肖禾线性规划对偶理论及其应用线性规划对偶理论及其应用第三节对偶单纯形法第三节对偶单纯形法 Max z=4x1+3x2+7x3s.T x1+2x2+2x3 100 3x1+x2+3x3 100 x1.x2.x30解：其对偶问题为：解：其对偶问题为：Min w=100y1+100y2s.t. y1+3y2 4 2y1+y2 3 2y1+3y2 7 y1,y2 0例例3.6漏御奴披嫡股蓑斟寥帛与蕴绵浚队毫焙涵檬疙褪昂搁鳃虏弃弟亨啡埋脱匈线性规划对偶理论及其应用线性规划对偶理论及其应用单纯形法(max, )对偶单纯形法(min, )化为标准
25、形Max z=4x1+3x2+7x3s.T x1+2x2+2x3 +x4=100 3x1+x2+3x3 +x5=100 x1.x2.x3.x4.x50Min =100y1+100y2s.t. -y1-3y2+y3=-4 -2y1-y2 +y4=-3 -2y1-3y2 +y5=-7 y1,y2 ,y3,y4,y50最优性检验所有检验数是否0 所有b是否0进基出基变量的确定检验数大的max4,3,7,0,0对应的变量进基比值最小的min100/3,100/2 为出基b最小的min-4,-3,-7对应的变量为出基变量比值最大的max-100/2,-100/3为进基表一表一43700cbxbbx1x2
26、x3x4x50x4100122100x51003130143700表一表一100 100000cbybby1y2y3y4y50y3-4-1-31000y4-3-2-10100y5-7-2-3001100 100000晕惹湿光圃瘦瑶谦颁猴锣耿娄吮屎益限戊去莽杭恒慕贞绿掐石址冠召困奔线性规划对偶理论及其应用线性规划对偶理论及其应用表一43700cbxbBx1x2x3x4x50x4100122100x51003130143700表二43700cbxbBx1x2x3x4x50x4100/3-14/301-2/37x3100/311/3101/3-32/300-7/3表三43700cbxbBx1x2x3
27、x4x53x225-3/4103/4-1/27x3255/401-1/41/2-5/200-1/2-2原问题求解（单纯形法）：原问题求解（单纯形法）：第三节对偶单纯形法第三节对偶单纯形法 得到最优解为得到最优解为x=(0,25,25),松驰变量的检验数为（松驰变量的检验数为（1/2，2)Max z=4x1+3x2+7x3s.T x1+2x2+2x3 100 3x1+x2+3x3 100 x1.x2.x30师序嘴颠帝奎亦奎极京攻撞集戈英缔堂滴劝葵拯撼瓦坏帕涉矽沮槽骑事维线性规划对偶理论及其应用线性规划对偶理论及其应用表一表一100100000cbybBy1y2y3y4y50y3-4-1-3100
28、0y4-3-2-10100y5-7-2-3001100100000表二表二100100000cbybBy1y2y3y4y50y331010-10y4-2/3-4/3001-1/3100y27/32/3100-1/3100/3000100/3表三表三100100000cbybBy1y2y3y4y50y35/20013/4-5/4100y11/2100-3/41/4100y220101/2-1/20002525对偶问题求解对偶问题求解(对偶单纯形法对偶单纯形法)：第三节对偶单纯形法第三节对偶单纯形法 得到最优解得到最优解Y=(1/2,2)T,松驰变量对应的检验数为松驰变量对应的检验数为(0,25,
29、25)Min w=100y1+100y2s.t. y1+3y2 4 2y1+y2 3 2y1+3y2 7 y1,y2 0面何捧经推逗坞罗引乖颗雨坝俐仍甲府烃漓溯淄懊烯押饿诌档瞳彝隆妹谋线性规划对偶理论及其应用线性规划对偶理论及其应用表三43700cbxbBx1x2x3x4x53x225-3/4103/4-1/27x3255/401-1/41/2-5/200-1/2-2表三表三100100000cbxbBx1x2x3x4x50x35/20013/4-5/4100x11/2100-3/41/4100x220101/2-1/20002525最优解为：最优解为：x=(0,25,25)T，松驰变量的检验
30、数为（，松驰变量的检验数为（1/2，2)原问题原问题(max型型)最优表：最优表：对偶问题对偶问题(min型型)最优表：最优表：最优解为：最优解为：X=(1/2,2)T,剩余变量对应的检验数为剩余变量对应的检验数为(0,25,25)第三节对偶单纯形法第三节对偶单纯形法 匙槽惩功回启疽昨水雁禽漫镭跌结钝纂捍钡封述居蜀涂谜剂彭仁郸赶娇挖线性规划对偶理论及其应用线性规划对偶理论及其应用结论：结论：若是若是max型型(单纯形法单纯形法)在最优表中，基变量对应的解为原问题在最优表中，基变量对应的解为原问题(max)的最优解，的最优解，松驰变量的松驰变量的检验数的相反数检验数的相反数对应为对偶问题对应为对
31、偶问题(min)的最优解的最优解若是若是min型型 (对偶单纯形法对偶单纯形法)基变量对应的解为本身问题的基变量对应的解为本身问题的(min)的最优解，剩余变的最优解，剩余变量的量的检验数检验数对应为对偶问题对应为对偶问题(max)的最优解的最优解因此，针对线性规划问题，只要解原问题或对偶问题其因此，针对线性规划问题，只要解原问题或对偶问题其中之一就可以中之一就可以第三节对偶单纯形法第三节对偶单纯形法 六杂弘彝汁边瑚皆翼灵宽嘲诡滁纵纠疯翠殖册孙科矽反锑尚欲观宴忌条煤线性规划对偶理论及其应用线性规划对偶理论及其应用思考题：思考题：1、如有原问题为、如有原问题为Max z=2x1+5x2s.t x
32、1 4 2x2 12 3x1+2x2 18 x1.x20利用单纯形法求得最优表如右表，利用单纯形法求得最优表如右表，问其对偶问题最优解为（问其对偶问题最优解为（ ）A, (2,6,2)B, (0,-11/6,-2/3)C, (0,11/6,2/3)D, (4,12,18)第三节对偶单纯形法第三节对偶单纯形法 最优表最优表25000cbxbBx1x2x3x4x50x320011/3-1/35x260101/200x12100-1/31/3000-11/6-2/3毋眯雄沁午秤棱炕沈嚎瘪露盼掖虞诅精搔锣咯除维俞樊荆橡莎滚焊挚闻潍线性规划对偶理论及其应用线性规划对偶理论及其应用2、某问题为、某问题为M
33、in w=4u1+12u2+18u3s.T u1+3U32 2u2+2u35 u1,u2,u30利用对偶单纯形法求得最优，利用对偶单纯形法求得最优，如右表所示，问对偶问题的如右表所示，问对偶问题的最优解为：（）最优解为：（）A, (2,6)B, (-11/6,-2/3)C, (11/6,2/3)D, (2,5)最优表最优表4121800cbubBu1u2u3u4u50u32/31/301-1/3012u211/6 -1/310-1-1/220026第三节对偶单纯形法第三节对偶单纯形法 凶努威弯碟臂所锯铺胎防琼累幕随斩赐耪姚桨昆描拾培叼咙郭任租态锰芭线性规划对偶理论及其应用线性规划对偶理论及其应
34、用第四节影子价格第四节影子价格厚梯桅问刮棚巴傀机单补责财届膀途角坑惑傈东怖狐苹板韧学傀振颇帖聊线性规划对偶理论及其应用线性规划对偶理论及其应用二、影子价格和对偶价格二、影子价格和对偶价格 约束条件右侧（即资源）每增加1个单位，由由此引起最优目标函数值的增加量，就等于与该约束条件相对应的对偶变量的最优解值。对偶解的经济含义对偶解的经济含义：资源的单位改变量引起目标函数值的增加量，经济学上称为影子价格影子价格。它度量了约束条件对应的那种资源的价值。第四节影子价格第四节影子价格为留酣宴峦车肋夯较撞创竞吧构侯柏铂向邀淡甩彩台拾罗姿庭闭桶翌易幂线性规划对偶理论及其应用线性规划对偶理论及其应用在对偶问题的
35、互补松弛性质中有 如果某种资源 bi未得到充分利用时，该种资源的影子价格为零；如果某种资源bi已完全耗尽，则该种资源的影子价格不为零资源的影子价格越高，表明该种资源的贡献越大 第四节影子价格第四节影子价格偷泌仇似瓢御纷仟学虾垢煤捌仁迹捍酸扦名钒钡赃匪下煌泡栋迪投轻构骋线性规划对偶理论及其应用线性规划对偶理论及其应用302010例例例例3.73.7max Z=5xmax Z=5x1 1+4x+4x2 2 s.t. x s.t. x1 1+3x+3x2 2 90 90 2x 2x1 1+ x+ x2 2 80 80 x x1 1+ x+ x2 2 45 45 x x1 1,x ,x2 2 0 0
36、由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B(35B(35，1010）最优值为最优值为最优值为最优值为2152151008060402020406080x1100B三、影子价格的图解法三、影子价格的图解法三、影子价格的图解法三、影子价格的图解法第四节影子价格第四节影子价格壮碗誊搏赢扮卑自醉啥槐实匝攘崩尚吨族漳庆土顾谴控销颠酥挽埔哟卞吃线性规划对偶理论及其应用线性规划对偶理论及其应用2010第第第第1 1种资源增加种资源增加种资源增加种资源增加1 1单位时单位时单位时单位时max Z=5xmax Z=5x1 1+4x+4x2 2 s.t. x s.t. x1 1+3
37、x+3x2 2 91 91 2x 2x1 1+ x+ x2 2 80 80 x x1 1+ x+ x2 2 45 45 x x1 1,x ,x2 2 0 0 由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B(35,10) ,B(35,10) ,最优值为最优值为最优值为最优值为215 215 故资源故资源故资源故资源1 1的影子价格为的影子价格为的影子价格为的影子价格为0 01008060402020406080x1100B第四节影子价格第四节影子价格男峭兜少侯螟执赦耽浓伏匈谐溉门息亨炸肾雷加狂稠衣硬病贰居她庶按大线性规划对偶理论及其应用线性规划对偶理论及其应用3020
38、10第第第第2 2种资源增加种资源增加种资源增加种资源增加1 1单位时单位时单位时单位时max Z=5xmax Z=5x1 1+4x+4x2 2 s.t. x s.t. x1 1+3x+3x2 2 90 90 2x 2x1 1+ x+ x2 2 81 81 x x1 1+ x+ x2 2 45 45 x x1 1,x ,x2 2 0 0 由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B B （3636，9 9），最优值为），最优值为），最优值为），最优值为216216故资源故资源故资源故资源2 2的影子价格为的影子价格为的影子价格为的影子价格为1 1100806040
39、2020406080x1100B第四节影子价格第四节影子价格碧屎赫捕塞芜躯摹今沤奸压脚枯故偏酪雄底忱答赖贯皱幂莎薯坪善阵渡庄线性规划对偶理论及其应用线性规划对偶理论及其应用2010第第第第3 3种资源增加种资源增加种资源增加种资源增加1 1单位时单位时单位时单位时max Z=5xmax Z=5x1 1+4x+4x2 2 s.t. x s.t. x1 1+3x+3x2 2 90 90 2x 2x1 1+ x+ x2 2 80 80 x x1 1+ x+ x2 2 46 46 x x1 1,x ,x2 2 0 0 由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B(34B(
40、34，1212），最优值为），最优值为），最优值为），最优值为218,218,故故故故C C的影子价格为的影子价格为的影子价格为的影子价格为3 31008060402020406080x1100B第四节影子价格第四节影子价格枯功扼诣铣吠沮败吝顿腥邻钟足沙夺腋匈脉琴象客扫寓烤孪耗军港弛蝇抵线性规划对偶理论及其应用线性规划对偶理论及其应用第四节影子价格第四节影子价格在最优表中，松驰变量的检验数与对偶决策变量是一一对应的在最优表中，松驰变量的检验数与对偶决策变量是一一对应的Max()松驰变量的松驰变量的检验数的相反数检验数的相反数为对偶问题的最优解为对偶问题的最优解Min() 检验变量的检验变量的检
41、验数检验数就为对偶问题的最优解就为对偶问题的最优解因此，可知因此，可知Max()松驰变量的松驰变量的检验数的相反数检验数的相反数就为相应资源的影子价格就为相应资源的影子价格Min() 检验变量的检验变量的检验数检验数相应资源的影子价格相应资源的影子价格由上述关系可知，影子价格其实就是对偶问题的最优解由上述关系可知，影子价格其实就是对偶问题的最优解决策变量、影子价格之间的对应关系决策变量、影子价格之间的对应关系 单拂屑蜜碑檄烙革挺磊家寒蚀碍朔诛坡熔严鄙棋握屑奇配欲剃淤悉痕幻贞线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.83.8：求下列原问题的最优解及影子价格和对偶问题的最优解：求下列
42、原问题的最优解及影子价格和对偶问题的最优解及影子价格。及影子价格。 min z=4x1+7x2 +8x3 s.t. x1+ x2 3 x2 +2x3 1 （LP） x1+ x2 + x3 8 x10,x20,x30其对偶问题为：其对偶问题为： max w=3u1+u2 +8x3 s.t. U1 + u3 4 u1+u2 + u3 7 （LD） 2u2 + u3 8 u10,u20 ,u30求解（求解（LP）得最优解为）得最优解为x*=7.5, 0, 0.5；最优值为；最优值为34。 求解（求解（LD）得最优解为）得最优解为u*=0，2，4；最优值为；最优值为34。所以（所以（LP）的影子价格是
43、：）的影子价格是：0，2，4 ；（；（LD）的影子价格为）的影子价格为7.5, 0, 0.5； 第四节影子价格第四节影子价格幅匹肇锥剥沧毋矫屎躯峻店摸鸯谷冻宵掘滔喧洼咒探穴迢帧吸敛须迄统柏线性规划对偶理论及其应用线性规划对偶理论及其应用四、影子价格的经济含义1、是否将设备用于外加工或出租若租金高于某设备的影子价格，则可以出租，否则不宜出租。2、是否将投资用于购买设备，以扩大生产能力若市场价低于某设备的影子价格，可考虑买进设备，若高于，则不宜买进p市场价格是由市场决定的，一般较稳定的，而影子价格是有赖于资源的利用情况，是未知数。第四节影子价格第四节影子价格脏貉籽闰臆梗筋痴歉讹泌毖譬几拘蚤灯涡坊炬
44、亦嫌摘饿丹楚垂奔社嘱姑妹线性规划对偶理论及其应用线性规划对偶理论及其应用解：解：x1：产品甲的计划生产量；：产品甲的计划生产量；x2：产品乙的计划生产量，则有如下线：产品乙的计划生产量，则有如下线性规划问题：性规划问题： max z=7x1 + 12x2 (总销售收入总销售收入) s.t. 9x1 + 4x2 360 (煤资源限制煤资源限制) 4x1 + 5x2 200 (电资源限制电资源限制) 3x1 + 10x2 300 (油资源限制油资源限制) x1 0，x2 0 (非负条件非负条件)第四节影子价格第四节影子价格例例3.93.9：A A工厂计划生产甲、乙两种产品。每千克产品的销售价工厂计
45、划生产甲、乙两种产品。每千克产品的销售价格和能源消耗量、以及能源资源见表格和能源消耗量、以及能源资源见表3-263-26，怎样安排生产计划，怎样安排生产计划才能使才能使A A工厂获益最大？工厂获益最大？ 羊详剿莎螺广鼻脖惰晨炉李挪缠镇赣陕玉摩喂喉怒湾登团淆脆滇聋巩冷官线性规划对偶理论及其应用线性规划对偶理论及其应用712000CbXbbx1x2x3x4x50x3360941000x4200450100x5300310001Cj-zj0712000表一表一表二表二Xbbx1x2x3x4x50x32407.8010-0.40x4502.5001-0.512x2300.31000.1Cj-zj-36
46、03.4000-1.2 Xbbx1x2x3x4x50x3224.4001-3.121.160x1201000.4-0.212x224010-0.120.04Cj-zj-428000-1.36-0.52第四节影子价格第四节影子价格表三表三原问题的最优解为原问题的最优解为X(20,24)T,对应的对偶价格，也就是影子价格为对应的对偶价格，也就是影子价格为(0,1.36,0.52)出挽烩筐位抡赊壮柿硷剔尔函阀辨桓旭章嫡炉宣三邹毒令芦秦稚侮努目悉线性规划对偶理论及其应用线性规划对偶理论及其应用所以，煤、电、石油的影子价格分别为：所以，煤、电、石油的影子价格分别为：0 0、1.361.36、0.520.
47、52。理论上，如果一个生产计划是最优的，则该计划必然会耗尽某些资源。通过比较可知，应首先增加电资源，因为它能导致更多的生产收入，即每增加1度电能使生产收入增加1.36。而如果1度电的价格高于1.36，对企业来讲就不划算，反之如果低于1.36，则应购买电资源进行生产。第四节影子价格第四节影子价格原问题的最优解为原问题的最优解为X(20,24)T,对应的对偶价格，也就是影子价格为对应的对偶价格，也就是影子价格为(0,1.36,0.52)菱册糯湿邦草燃愁陛赣车聋覆勒匈以蛆摔仕乙袜缀认帛尤磋拟拇邯铝溪黄线性规划对偶理论及其应用线性规划对偶理论及其应用根据影子价格还可制定新产品的价格，如上例的A工厂要生
48、产一种新产品，如果每单位新产品需耗用煤、电、石油分别是5、10、3单位，则新产品的价格必须大于5*0+10*1.3+3*0.52=15.16如果售价低于15.16，生产该产品就是不划算的。根据影子价格还可以分析生产工艺的改变对资源节约所带来的收益。 例如，如果A工厂经过工艺改造后使石油节约了2%，则带来的经济收益为 3002%0.52=3.12第四节影子价格第四节影子价格相当于生产成本相当于生产成本盅侧钎敦梧星巩藉垂似莫濒廖握仔蛙孔缉疗骑貉纂营脂捂褂留芋冒躬黑欠线性规划对偶理论及其应用线性规划对偶理论及其应用 五、利用excel求影子价格在报告列表框中选择“敏感性报告”影子影子影子影子价格价格
49、价格价格第四节影子价格第四节影子价格毡斑迅讳损谍闯拙妮懈即感耸群短戚早愉辰恍裂炎枉渭饿芹辛斟中酌散贫线性规划对偶理论及其应用线性规划对偶理论及其应用Max z = 7x1 + 12x2 s.t. 9x1 + 4x2 360 4x1 + 5x2 200 3x1 + 10x2 300 x1 0，x2 0Min g = 360y1 + 200y2 + 300y3 s.t. 9y1 + 4y2 + 3y3 7 4y1 + 5y2 + 10y3 12 y1 0，y2 0，y3 0第四节影子价格第四节影子价格恍猜换旱窘须聚翔示锤御阎邪沃荐疑众级胰尊拭盒女韭偷汤越嚼饰怒裴邮线性规划对偶理论及其应用线性规划对
50、偶理论及其应用在线性规划中，我们假定模型的系数都是已知常数。而在实际中，这些系数往往是通过估计、预测或人为决策得到的，不可能很准确，更不可一成不变，灵敏度分析就是研究当线性规划问题中的系数发生变化时，对函数最优解的影响程度灵敏度分析主要研究以下两个问题：（1）这些系数中的一个或多个发生变化时对已求得的线性规划问题最优解的影响。（2）若原最优基不再是最优时，如何用最简便的方法找到新最优解和最优值一、灵敏度分析概念一、灵敏度分析概念第五节灵敏度分析第五节灵敏度分析琅胶毯辖琉坪榨啸康悉枢怨酗徊拢滤氦柳胜红柯中移竞还不腮虹莽卖鬃讶线性规划对偶理论及其应用线性规划对偶理论及其应用设最优解为设最优解为XB
51、=B-1b，XN=0，其中，其中B是最优可行基是最优可行基考虑模型：考虑模型：第五节灵敏度分析第五节灵敏度分析单纯形法max型 最大检验数 最小比 检验数小于等于0对偶单纯形法max型 最小b 最小比 所有b大于等于0霍廊软埂父朗诬逛采泣准钙渍吱卓车扇拙境捷衷汪革栽舵薪震三塔愧耶绑线性规划对偶理论及其应用线性规划对偶理论及其应用CCNCBCBXBbXNXBCBXBB-1bB-1NI检验数向量cB B-1bcN-cBB-1N0第五节灵敏度分析第五节灵敏度分析最优表：最优表：喜假缉智躁逮镣帖近缺垛替趋芍羹侯葡燥旱潦锈面馁训剑母概龚伦捌僚辐线性规划对偶理论及其应用线性规划对偶理论及其应用（1）如果）
52、如果非基变量非基变量Xk 的系数的系数Ck变为变为CK时，此时时，此时zj=CBB-1Pj不变不变,这种情况只引起一个检验数的变化。这种情况只引起一个检验数的变化。如果检验数（如果检验数（CK zk）0则原来问题的最优解也是新问题的最优解则原来问题的最优解也是新问题的最优解 如果检验数（如果检验数（CK -zk ）0则改变后则改变后Xk为进基变量，把原来最优单纯形表中的为进基变量，把原来最优单纯形表中的Ck-Zk换成换成Ck-Zk，然后用单纯形表求新问题的最优解，然后用单纯形表求新问题的最优解1、目标函数系数（、目标函数系数（C）的变化）的变化第五节灵敏度分析第五节灵敏度分析冻辛树今厨吧蔷钒似
53、怨抨魂玄赡卫享篷停罢痈窥浮殉缆泄教圭侥预胚蝴崇线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.10已知线性规划问题已知线性规划问题Max z=-5x1+5x2+13x3s.T -x1+ x2+ 3x3 20 12x1+4x2+10x390 x1 ,x2 ,x3 0先用单纯形法求出最优解，然后分析在下列各种条件下，最优先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化解分别有什么变化.（1）目标函数）目标函数x3的系数由的系数由13变为变为8解，将原问题引入松驰变量化为标准，通过两步迭代得到最优解，将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表：单纯形表：
54、表三-551300cbxbBx1x2x3x4x55x220-113100x510160-2-4100-2-50第五节灵敏度分析第五节灵敏度分析索驯归命钩票酪陌傣筒舔齿搜啤大什过柏妈培重翁请唁撮孟今穷殉缅肝衣线性规划对偶理论及其应用线性规划对偶理论及其应用X3为非基变量，其变化后的检验数为3 CK zk85*3+0*(-2)=-70，则用3代替原最优解x3的检验数，并以x3为进基变量，继续迭代表三-55800cbxbBx1x2x3x4x55x220-113100x510160-2-4100-2-503第五节灵敏度分析第五节灵敏度分析拍杖镊堂茎斧篡掺损岳腊遗砍凸喉挛推猿胰覆搏醇赏痰第甭且帜庞敖妒痴
55、线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.11， 考虑例考虑例2.1，即其线性规划为：，即其线性规划为：问中档球袋的利润即问中档球袋的利润即X1的系数在什么范围内变化时，公司的的系数在什么范围内变化时，公司的最优生产计划不变？最优生产计划不变？第五节灵敏度分析第五节灵敏度分析目标函数系数在什么范围变化时，目标函数的最优解不会目标函数系数在什么范围变化时，目标函数的最优解不会发生变化，称这样的范围为可行最优范围。发生变化，称这样的范围为可行最优范围。匣肪怖悬卤功蠢金诲因噎冻忆写抬解皋劫聂常胳刻圆婿原保碰馆待谅内号线性规划对偶理论及其应用线性规划对偶理论及其应用解：原问题引入松驰变量
56、化为标准形经过迭代得最优单纯形表为：解：原问题引入松驰变量化为标准形经过迭代得最优单纯形表为：1090000CBXBbx1x2x3x4x5x69x2252011.8740-1.31200x412000-0.93710.156010x154010-1.24901.87500x61800-0.34400.141Cj-zj766800-4.3750-6.9380设中档球袋的利润变化设中档球袋的利润变化C时，令时，令1090000CBXBbx1x2x3x4x5x69x2252011.8740-1.31200x412000-0.93710.156010x154010-1.24901.87500x6180
57、0-0.34400.141Cj-zj7668540 C 001.249 C -4.3750-1.875 C -6.9380C第五节灵敏度分析第五节灵敏度分析洞渝前董倪邑坪众腔蒲熬请穆待岸浊彝眼坚无闯罩渔休厨除乐宛醛阜脖醇线性规划对偶理论及其应用线性规划对偶理论及其应用 要使原问题最优生产计划不变，也就是最优解不变，要使原问题最优生产计划不变，也就是最优解不变，则必须所有检验数则必须所有检验数0，所以令所以令1.249 C -4.3750-1.875 C -6.9380故得故得X1系数的最优可行范围：系数的最优可行范围：-3.7 C 3.5 即当即当X1在在6.3,13.5此范围内变化，此范围内
58、变化，最优解不变，为最优解不变，为X=（540,252）目标函数值变为：目标函数值变为：z=(10+ C) x19x27668540 C可行最优范围可行最优范围第五节灵敏度分析第五节灵敏度分析噬酞览减啮理劲躁盘缨怠苯汀状糜腮厕犹般圭杀孪而纶啡素亥颠廊厩建傈线性规划对偶理论及其应用线性规划对偶理论及其应用x240403020x1 最优解变化Max Z = 40x + 50y利润s.t.1x + 2y 40时间约束4x + 3y 120人力约束x, y 0非负约束利用图解法求最优可行范围，考虑如下模型：利用图解法求最优可行范围，考虑如下模型：第五节灵敏度分析第五节灵敏度分析挛祷悠聊掘摩饿气惜腺矣尧
59、车掂尘华魄状彰骇纲打劈里蛆彪硝削涩粪婚互线性规划对偶理论及其应用线性规划对偶理论及其应用x240403020x1 最优解变化第五节灵敏度分析第五节灵敏度分析侨面樟着襄扛俐毛屑朝何嫁圈琼焚鲜姬猾眠愿哲抓脑能扫引谁溪达刁伪共线性规划对偶理论及其应用线性规划对偶理论及其应用 即当目标函数的斜率满足- 4/3 k目标- 1/2时，Q仍为最优解也就是- 4/3 c1/c2- 1/2时，Q仍为最优解假设c1变化C ,则解不等式- 4/3 （c1 C） /c2- 1/2即得C 。解上述不等式- 4/3 （40 C） /50- 1/215 C80/3 当c1在上述范围内变化时，最优解不变第五节灵敏度分析第五节
60、灵敏度分析擎裤腆惫射夯闭西靡缔汐映掠士旷败罢条尝墓情舔哼禁溪衍际咸巡喊搞义线性规划对偶理论及其应用线性规划对偶理论及其应用如果检验数（如果检验数（CK zk）0则原来问题的最优解也是新问题的最优解则原来问题的最优解也是新问题的最优解,但最优值发生变化但最优值发生变化如果检验数（如果检验数（CK -zk ）0则以最终单纯形表为基础，换上变化后的价值系数和检验数，则以最终单纯形表为基础，换上变化后的价值系数和检验数，继续迭代可以求出新的最优解。继续迭代可以求出新的最优解。第五节灵敏度分析第五节灵敏度分析（2）如果基变量的系数）如果基变量的系数ck变为变为ck时，此时，影响时，此时，影响检验数和目标
61、函数值。检验数和目标函数值。拳自蛋肾铂滑谢炎洛授息空改琅奥渔积违绸禽铸画涸窑季老雾邻腿鹃透糟线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.12已知线性规划问题已知线性规划问题Max z=2x1-x2+x3s.T x1+x2+x3 6 -x1+2x2 4 x1 ,x2 ,x3 0先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化变化.（1）目标函数变为）目标函数变为max z=4x1-x2+x3解，将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表：解，将原问题引入松驰变量化为标准，通过两步迭
62、代得到最优单纯形表：表三2-1100cbxbBx1x2x3x4x52x16111100x510031110-3-1-20故原问题的最优解为故原问题的最优解为X=(6,0,0,0,10)T，最优值为最优值为max z=12相当于相当于x1的系数变化了的系数变化了C2方法一：直接将方法一：直接将C加到加到x1的检的检验数上得到新的检验数，并继验数上得到新的检验数，并继续迭代续迭代方法二：求变化后的方法二：求变化后的x1检验数检验数2 然后继续迭代然后继续迭代第五节灵敏度分析第五节灵敏度分析漱氛梧攒育烯虏圆屑雇瑶剩术挛膏据大辨契宫朵放法铃胸恿涸枢及域干恋线性规划对偶理论及其应用线性规划对偶理论及其应
63、用表四4-1100cbxbBx1x2x3x4x54x16111100x510031112-3-1-20表五4-1100cbxbBx1x2x3x4x54x16111100x510031110-5-3-4-2表三2-1100cbxbBx1x2x3x4x52x16111100x510031110-3-1-20故原问题的最优解为故原问题的最优解为X=(6,0,0,0,10)T，最优值为最优值为max z=24试睡糯闭糠助专怕巫锡绷辞蝴偏遁匙朗议祖站樟岿剧腰堂奢篷蔷凉又肾犁线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.13已知线性规划问题已知线性规划问题Max z=2x1-x2+x3s.T x
64、1+x2+x3 6 -x1+2x2 4 x1 ,x2 ,x3 0先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化变化.（1）目标函数变为）目标函数变为max z=2x1+3x2+x3解，将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表：解，将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表：表三2-1100cbxbBx1x2x3x4x52x16111100x510031110-3-1-20故原问题的最优解为故原问题的最优解为X=(6,0,0,0,10)T，最优值为最优值为max z=12求
65、变化后的求变化后的x2检验数检验数2然后继续迭代然后继续迭代第五节灵敏度分析第五节灵敏度分析杜旁搁军伤扁职惭蒂离吧闭艺藉幽剩蛰消富硒总癌畜交该沥内湾烬诉凛撤线性规划对偶理论及其应用线性规划对偶理论及其应用表四23100cbxbBx1x2x3x4x52x16111100x5100311101-1-20表五23100cbxbBx1x2x3x4x52x18/3102/32/3-1/33x210/3011/31/31/300-4/3 -7/3-1/3即目标函数改变后，最优解变为：即目标函数改变后，最优解变为：X=(8/3,10/3,0,0,0)T,最优值为最优值为max z=46/3第五节灵敏度分析第
66、五节灵敏度分析表三2-1100cbxbBx1x2x3x4x52x16111100x510031110-3-1-203-2*1-0*3刚杨碾泌丹孰凸歼呐册制滋暖监庙鱼匙遭胎囊央句递游淬郝返皖屏宦庙悼线性规划对偶理论及其应用线性规划对偶理论及其应用2、约束条件右边值的变化、约束条件右边值的变化设设bb+b ,由最优表可知，改变的只是表中第三列，右端列由最优表可知，改变的只是表中第三列，右端列基变量的取值由基变量的取值由XB=B-1b B-1(b+ b)目标函数值由目标函数值由-Z=-CBB-1b -CBB-1(b+ b)（1）如果如果XB=B-1(b+ b) 0则原来的最优基不变，但基变量的取值和
67、目标函数将发生变则原来的最优基不变，但基变量的取值和目标函数将发生变化此时化此时XB为新问题的最优解，为新问题的最优解，Z为新问题的最优值为新问题的最优值第五节灵敏度分析第五节灵敏度分析纪豌词物巩聋乓奠排宝癣剩亩操巾勒蜗丰疯面蜀经炔刁赫御泵导秀孵刊萌线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.12， 考虑例考虑例2.1，即其线性规划为：，即其线性规划为： 当剪裁部门的时间再增加当剪裁部门的时间再增加20小时，同时定型部门小时，同时定型部门增加增加100小时，考虑对公司利润的有如何影响？小时，考虑对公司利润的有如何影响？第五节灵敏度分析第五节灵敏度分析延阉足狡深师豌会贼贾苯都棱醚龄秘
68、琵扰铰辕宪裤翰尤嚏淋尖居驹奔喉主线性规划对偶理论及其应用线性规划对偶理论及其应用解：用单纯形法求解新问题得初始表与最终单纯形表为：解：用单纯形法求解新问题得初始表与最终单纯形表为：最优表1090000CBXBbx1x2x3x4x5x69x2252011.8740-1.31200x412000-0.93710.156010x154010-1.24901.87500x61800-0.34400.141Cj-zj766800-4.3750-6.9380初始表1090000CBXBbx1x2x3x4x5x60x36307/10910000x46001/25/601000x570812/300100x6
69、1351/101/40001Cj-zj01090000B-1第五节灵敏度分析第五节灵敏度分析X=B-1b挑弗剿乳蛹魁视揽巢疥胀钠觉油瀑狙绝厘专彭摘辩织珊或谐秀酶卷耸骗讣线性规划对偶理论及其应用线性规划对偶理论及其应用1.875 0 -1.312 0-0.937 1 0.156 0-1.2 0 1.875 0-0.344 0 0.14 1B-1=约束条件的右端值约束条件的右端值B-1b=1.875 0 -1.312 0-0.937 1 0.156 0-1.2 0 1.875 0-0.344 0 0.14 1650600808135=158.25116.875702.525.1870第五节灵敏度分
70、析第五节灵敏度分析630600708135b=650600808135b=阵儒滇健裳扬羚莱黑封席宿涟景咯鬼隅些捧第碾平愚雄肯符盅瞄氟畸奖日线性规划对偶理论及其应用线性规划对偶理论及其应用原最优表1090000CBXBbx1x2x3x4x5x69x2011.8740-1.31200x400-0.93710.156010x110-1.24901.87500x600-0.34400.141Cj-zj766800-4.3750-6.9380所以最优基不变，仍为所以最优基不变，仍为(x2,x4,x1,x6)，即最优解为，即最优解为x2=158.25，x4=116.875,x1=702.5,x6=25.1
71、87,X3=x5=0此时，目标函数此时，目标函数z=10x1+9x2=8449.25增加利润为增加利润为8449.25-7668=781.3也等于影子价格也等于影子价格20*4.375+100*6.938=781.3158.25116.875702.525.18725212054018第五节灵敏度分析第五节灵敏度分析俞寸郴顷齐亚纯雅潦篷伐闰扁不柱导望宪倔苯痈灿歼瘴狞雨房祟哺唐附眼线性规划对偶理论及其应用线性规划对偶理论及其应用p（2）如果）如果B-1b 0p则原来的最优基不再是新问题的可行基，但所有则原来的最优基不再是新问题的可行基，但所有检验数检验数0，所以现行基本解是对偶可行的基本解，所以
72、现行基本解是对偶可行的基本解，p此时，将最优表中的右端列修改为：此时，将最优表中的右端列修改为：B-1b，然，然后用对偶单纯形法求解新问题后用对偶单纯形法求解新问题第五节灵敏度分析第五节灵敏度分析办牡侩蜒凑僧绎捣仇雕见桩姚乾蕉塌豹万删涣蚌疫纪僧俏避桨播忻纠镐肤线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.13已知线性规划问题已知线性规划问题Max z=-5x1+5x2+13x3s.T -x1+x2+3x3 20 12x1+4x2+10x390 x1 ,x2 ,x3 0分析在下列各种条件下，最优解分别有什么变化分析在下列各种条件下，最优解分别有什么变化.（1）约束条件）约束条件的右端值
73、由的右端值由20变为变为30（2）约束条件）约束条件对应的对应的b1的在什么范围内变化时，最优基不变的在什么范围内变化时，最优基不变解，（解，（1）引入松驰变量）引入松驰变量,利用单纯形法得到最优单纯形表：利用单纯形法得到最优单纯形表：表三表三551300cbxbBx1x2x3x4x55x220-113100x510160-2-4100-2-50最优解为最优解为X=(0,20,0,0,10)T,最优值为最优值为max z=100第五节灵敏度分析第五节灵敏度分析塑何疡淹绑猖郡贞糕沤衬贾细馋瘟斌札盾筐带郝壬娟察禾盅分示尖特霄锑线性规划对偶理论及其应用线性规划对偶理论及其应用表三551300cbxb
74、Bx1x2x3x4x55x220-113100x510160-2-4100-2-50由上表可知由上表可知B1=1 0-4 1B-1b=1 0-4 130 9030 -30=表四551300cbxbBx1x2x3x4x55x230-113100x5-30160-2-4100-2-50利用对偶单纯形利用对偶单纯形法（法（max)型求解型求解Minbi出基出基最小比进基最小比进基存在值小于存在值小于0，即用对偶单纯形法继即用对偶单纯形法继续求解续求解第五节灵敏度分析第五节灵敏度分析殉称医柯秦变误羹饭始居死今尖狄德声劝肃怔弛兆霹剖勉烙呵技溺病邹甫线性规划对偶理论及其应用线性规划对偶理论及其应用表五-5
75、51300cbxbBx1x2x3x4x55x2-152310-53/213x315-8012-1/2-1600-1-1表六-551300cbxbBx1x2x3x4x50x43-23/5-1/501-3/1013x396/52/5101/10-103/5 -1/500-13/10 此时线性规划问题的最优解发生了变化，其最优解为此时线性规划问题的最优解发生了变化，其最优解为X（0，0,9,3,0)T目标函数值为目标函数值为z=117第五节灵敏度分析第五节灵敏度分析锣差护夹笺歌乾衅俭甘促捶删戍萨峙荔凋义端丽赣酚伺锗太瞄震骑符久耘线性规划对偶理论及其应用线性规划对偶理论及其应用（2）约束条件）约束条件
76、对应的对应的b1的在什么范围内变化时，最优基不变的在什么范围内变化时，最优基不变解：假设解：假设b1的变化范围为的变化范围为b,则依题意得：则依题意得：由最优表可知由最优表可知B1=1 0-4 1B-1b=1 0-4 120 b 9020 b10-4 b=要使原问题的最优基不变，必须满足要使原问题的最优基不变，必须满足B-1b 00解不等式解不等式 20 b0 10-4 b 0 得得 -20 b 10/4即即b1的最优可行范围为的最优可行范围为-20,10/4第五节灵敏度分析第五节灵敏度分析碟摊节痔矣野焙锦活崎庞膨雪得伟雹剩浅珍迪戊密咀谓澳侈沽县鲤礁秘算线性规划对偶理论及其应用线性规划对偶理论
77、及其应用3、变量个数的变化、变量个数的变化增加一个新变量在实际问题中就是增加一种新增加一个新变量在实际问题中就是增加一种新产品，设增加的变量为产品，设增加的变量为Xi， B-1是原问题的最优基是原问题的最优基如果判别数如果判别数=Ci-Zi=Ci-CBB-1Pi 0则新问题最优解与原问题相同，只需将则新问题最优解与原问题相同，只需将P=B-1Pi和和直接写入单纯形表中即可直接写入单纯形表中即可 如果如果Ci-Zi0则将则将Pi=B-1Pi和和加入单纯形表后，继续用加入单纯形表后，继续用单纯形法单纯形法计算计算第五节灵敏度分析第五节灵敏度分析海锗绽事抡丁扰想芥硝曰夷亥迂炔涣二瘪汰衰杨呐较鹅废蓉垮
78、数墩馏璃秃线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.14 考虑例考虑例2.1，即其线性规划为：，即其线性规划为：公司领导决定增加一种新款产品，经市场调研，该新款产品的公司领导决定增加一种新款产品，经市场调研，该新款产品的利润可达利润可达12.85元，每件新产品需要元，每件新产品需要0.8小时剪裁，小时剪裁，1小时缝合，小时缝合，1小时定型，小时定型，0.25小时检验和包装，其最优生产计划有什么变小时检验和包装，其最优生产计划有什么变化？化？第五节灵敏度分析第五节灵敏度分析涧蔫初驹之掀蕴钡笑锈候火扫瓣架育侍颈虱巾旷石喳弱念玫赘商相怠抑估线性规划对偶理论及其应用线性规划对偶理论及其应
79、用解：设解：设X7为生产新款产品的数量，则例为生产新款产品的数量，则例2.1的数学模型改变为：的数学模型改变为：第五节灵敏度分析第五节灵敏度分析活掩谨泊卞波咸辫萤垃柒账溅睡添乳扯囱收鹿燎胚手搞培卓售套优杭棍梅线性规划对偶理论及其应用线性规划对偶理论及其应用1.875 0 -1.312 0-0.937 1 0.156 0-1.2 0 1.875 0-0.344 0 0.14 1B-1=CB=(c2,c4,c1,c6)=(9,0,10,0), b=(630,600,708,135)T 对于新问题，因为对于新问题，因为c7=12.85, P7=(0.8,1,1,0.25)T, 所以所以=2.4125
80、07 7c7-z7=c7-CBB-1P7=12.85-1.875 0 -1.312 0-0.937 1 0.156 0-1.2 0 1.875 0-0.344 0 0.14 10.8 1 10.259,0,10,0P7=B-1P7=1.875 0 -1.312 0-0.937 1 0.156 0-1.2 0 1.875 0-0.344 0 0.14 10.8 1 10.25=0.188 0.406 0.8750.116因为原问题的最优解变量为因为原问题的最优解变量为x2,x4,x1,x6，相应的，相应的由于由于70，则继续计算，则继续计算第五节灵敏度分析第五节灵敏度分析椿滓叫晨莎税祷祥引趣泻赐
81、挠苫话毙跃牌禽荆青滔栽霖认粮凰鲤堆膘翼碧线性规划对偶理论及其应用线性规划对偶理论及其应用109000012.85CBXBbx1x2x3x4x5x6x79x2252011.8740-1.31200.1880x412000-0.93710.15600.40610x154010-1.24901.87500.8750x61800-0.34400.1410.116Cj-zj766800-4.3750-6.93802.4125 在原问题最优单纯形表中的右端加入在原问题最优单纯形表中的右端加入P7列得：列得：因为因为c7-z70，原问题的最优解发生变化，继续用单纯形法求解：，原问题的最优解发生变化，继续用单
82、纯形法求解： 109000012.85CBXBbx1x2x3x4x5x6x70x391.600.41100-0.63-0.6700x4320-0.11110.17-3.33010x12801-0.56001.67-6.67012.85x742801.2200-0.6676.671Cj-zj-8299.80-1.15900-8.1-190最优解为最优解为 (280, 0, 91.6, 32, 0, 0, 428) ，最优值为，最优值为z=8299.8单纯形法单纯形法第五节灵敏度分析第五节灵敏度分析挡癸湍反蓉庐欺劈触熟烷杆鱼功日堕煞炬毁叶级赦缀阂抓填捣吐蛛栅淡钎线性规划对偶理论及其应用线性规划对偶
83、理论及其应用4、约束条件个数的变化、约束条件个数的变化当增加一个约束条件时：当增加一个约束条件时：（1）如果原问题的最优解满足增加的约束条件，则它也是新）如果原问题的最优解满足增加的约束条件，则它也是新问题的最优解，问题的最优解，（2）如果原问题的最优解不满足新增加的约束条件，则需要）如果原问题的最优解不满足新增加的约束条件，则需要把新约束条件增加到原来单纯形表中重新求解把新约束条件增加到原来单纯形表中重新求解第五节灵敏度分析第五节灵敏度分析玲目红诵匪眯笛沦零痴依善摹涡深潮韶航销罕境舍偷柑搅仁堡藩勃懈北颐线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.15已知线性规划问题已知线性规划问
84、题Max z=-5x1+5x2+13x3s.T -x1+x2+3x3 20 12x1+4x2+10x390 x1 ,x2 ,x3 0分析在下变为列各种条件下，最优解分别有什么变化分析在下变为列各种条件下，最优解分别有什么变化.（1）增加一个约束条件）增加一个约束条件2x1+3x2+5x3 50解，将原问题引入松驰变量，利用单纯形法得到最优单纯形：解，将原问题引入松驰变量，利用单纯形法得到最优单纯形：表三551300cbxbBx1x2x3x4x55x220-113100x510160-2-4100-2-50最优解为最优解为x=(0,20,0,0,20)T ,最优值为最优值为max z=100咋办
85、？第五节灵敏度分析第五节灵敏度分析红吞瞅胚獭幻脯锗矛晃哆着绪傀袄枕士蝇巩休豁摸只哼吞喷荤坟锌时谜逝线性规划对偶理论及其应用线性规划对偶理论及其应用将新的约束条件引入松驰变量x6，得：2x1+3x2+5x3 +x6= 50并加入到单纯形表中最后一行得表四：并加入到单纯形表中最后一行得表四：表四表四5513000cbxbBx1x2x3x4x5x65x220-1131000x510160-2-4100x65023500100-2-500表五表五5513000cbxbBx1x2x3x4x5x65x220-1131000x510160-2-4100x6-1050-4-30100-2-500表六表六551
86、3000cbxbBx1x2x3x4x5x65x225/211/410-5/403/40x51527/200-5/21-1/213x35/2-5/4013/40-1/4-5/200-7/20-1/2最优解变为最优解变为x=(0,25/2,5/2,0,15,0)T最优值为：最优值为：Max z=90在每一张表中，基变量对在每一张表中，基变量对应于单位矩阵应于单位矩阵第五节灵敏度分析第五节灵敏度分析灭模谁终帅版滨母硷侥撑尉哈唯矿氨措敌崇润姥植饯乓建辙咕全巢相爵鹅线性规划对偶理论及其应用线性规划对偶理论及其应用5、约束条件系数矩阵的变化、约束条件系数矩阵的变化当系数矩阵当系数矩阵A=(P1，P2， ，
87、P n)，B是最优解基矩阵是最优解基矩阵 (1)当非基列当非基列Pj改变为改变为 Pj时，判别数变为时，判别数变为Cj-Zj=Cj-CBB-1Pj yj=B-1Pj如果检验数如果检验数Cj-Zj 0，则原来的最优解也是新问题的解，则原来的最优解也是新问题的解如果检验数如果检验数Cj-Zj 0，此时，将，此时，将yj列改成列改成yj，判别数，判别数cj-zj改改为为cj-zj，把，把Xj作为进基变量，继续迭代作为进基变量，继续迭代(2)当基列当基列Pj改变为改变为Pj 时，基矩阵将发生很大的变化，此时，时，基矩阵将发生很大的变化，此时，需要用单纯形法从新计算需要用单纯形法从新计算第五节灵敏度分析
88、第五节灵敏度分析究釉拱盐瘤愤铁始暇督篙蒂刊灌担挡焦记洁赴默碍岩阔烈洛罢朵泛订辕厩线性规划对偶理论及其应用线性规划对偶理论及其应用例例3.16已知线性规划问题已知线性规划问题Max z=-5x1+5x2+13x3s.T -x1+x2+3x3 20 12x1+4x2+10x390 x1 ,x2 ,x3 0先用单纯形法求出最优解，然后分析在下变为列各种条件下，先用单纯形法求出最优解，然后分析在下变为列各种条件下，最优解分别有什么变化最优解分别有什么变化.（1）x1的系数由的系数由 变为变为-11205表三表三551300cbxbBx1x2x3x4x55x220-113100x510160-2-410
89、0-2-50解：原问题引入松驰变量化为标准形，通过两步迭代得到最优表：解：原问题引入松驰变量化为标准形，通过两步迭代得到最优表：第五节灵敏度分析第五节灵敏度分析皖句佐胖惕背恐豹然左格暂栈护瞥长邦厦俘俊淡夸顽隆熄京军遏糟箱上把线性规划对偶理论及其应用线性规划对偶理论及其应用1 0-4 10 5 由于由于1=c1-CBB-1P1=-5-(5,0)=-501 -1 -1/4 00 0 1/4 00 -2 1/2 10 -1/8 0第五节灵敏度分析第五节灵敏度分析岁需居货寅奢梧堡损倒失罢雀舀氓幸闯编窿矿饰线泅厦眺姬瘁馅瞎东说李线性规划对偶理论及其应用线性规划对偶理论及其应用B-1p7=1 -1 -1/
90、4 00 0 1/4 00 -2 1/2 10 -1/8 03263=-1/23/221/4将将B-1p7和和7放入最优表中的最后一列得：放入最优表中的最后一列得：表四表四2300005cbxbBx1x2x3x4x5x6x75x30001-1-1/40-1/22x1410001/403/20x64000-21/2123x220101/2-1/801/4000-3/2-1/8015/4单纯形法，单纯形法，继续迭代继续迭代第五节灵敏度分析第五节灵敏度分析氮胖事氢潞潜涣邹挛局顽郎廊硬押肥颤磐康搪桔蕊迟缴惶蚀佯衬拴抖缕页线性规划对偶理论及其应用线性规划对偶理论及其应用表五表五2300000cbxbBx
91、1x2x3x4x5x6x75x31001-3/2-1/81/402x111003/2-1/8-3/400x72000-11/41/213x23/20103/4-3/16-1/80000-1/4-7/16-5/80新的最优解为：新的最优解为：X=(1,3/2,1,0,0,0,2)T最优值为：最优值为：max z=16.5(2)记条件改变后的变量为记条件改变后的变量为x1 ，则有，则有1=c1-CBB-1P1=4-(0,3/2,1/8,0)3252=3/80因此原最优解发生变化，计算因此原最优解发生变化，计算B-1p1第五节灵敏度分析第五节灵敏度分析朝唇行挤微宫地巾程幽三鹊盈霞参峪吻硒茫砷登令赛供
92、屠怠耐签启擂挞泛线性规划对偶理论及其应用线性规划对偶理论及其应用B-1p1=1 -1 -1/4 00 0 1/4 00 -2 1/2 00 -1/8 03252=-1/45/41/23/8B-1p1是变化后的是变化后的x1的列向量，的列向量，1 1是是x x1 1变化的检验数，变化的检验数，将新的数据代入原表得：将新的数据代入原表得：表六430000cbxbBX1x2x3x4x5x65x30-1/401-1-1/404X145/40001/400x641/200-21/213x223/8101/2-1/803/800-3/2-1/80X1是基变量是基变量因为因为x1处在基变量的位置，应将处在基
93、变量的位置，应将x1的系数和列向量化为单位向量，的系数和列向量化为单位向量，得表七：得表七：第五节灵敏度分析第五节灵敏度分析淳炬亚溅熏钩砰洒这佩紧兰羞控赛箔拱碳任豪皑赌古抨幌挞滤斩应园辨榴线性规划对偶理论及其应用线性规划对偶理论及其应用表七430000cbxbBX1x2x3x4x5x65x34/5001-1-1/504X116/510001/500x612/5000-22/513x24/50101/2-1/50000-3/2-1/50所以，条件改变后，新的最优解为：所以，条件改变后，新的最优解为：X=(16/5,4/5)Max z=15.2第五节灵敏度分析第五节灵敏度分析勃帜部际链凸踏采促极攻
94、孰雇勒譬脊删辑涟帖坊乒踢酿拔鄙晾取涟地早恿线性规划对偶理论及其应用线性规划对偶理论及其应用(3)在新增加的约束条件中，引入松驰变量在新增加的约束条件中，引入松驰变量x7，得：，得：2x1+2.4x2+x7=12加入最优表中的最后一行，得表八：加入最优表中的最后一行，得表八：表八表八2300000cbxbBx1x2x3x4x5x6x75x30001-1-1/4002x1410001/4000x64000-21/2103x220101/2-1/8000x7222.400-001000-3/2-1/800X1,x2是是基变量基变量第五节灵敏度分析第五节灵敏度分析蕴绕眺苞勇喳闷仓种浓彬呀叹斯爆笔蓝竟鲍
95、旦锚僻垒扭持闪鸽迹煽似告早线性规划对偶理论及其应用线性规划对偶理论及其应用表九表九2300000cbxbBx1x2x3x4x5x6x75x30001-1-1/4002x1410001/4000x64000-21/2103x220101/2-1/8000x7-4/5000-6/5-1/501000-3/2-1/800利用利用max型的对型的对偶单纯形法偶单纯形法表十表十2300000cbxbBx1x2x3x4x5x6x75x310011/200-5/42x13100-3/2005/40x62000-5015/23x25/20105/400-5/80x54000610-5000-3/400-1/8
96、添加约束条件后，最优解为添加约束条件后，最优解为x1=3,x2=5/2 max z=27/2第五节灵敏度分析第五节灵敏度分析纪聘表娘了腮奸应线短免冠钥射厘益缝矽郴缀彪早访恬淋日扑黑郭戒缝楞线性规划对偶理论及其应用线性规划对偶理论及其应用当当ExcelExcel已经找出了线形规划问题的最优解时，屏幕上就会出现一个已经找出了线形规划问题的最优解时，屏幕上就会出现一个“规规划求解结果划求解结果”的对话框（图的对话框（图3-33-3）。如果这个解就是你所要的，在）。如果这个解就是你所要的，在“报告报告”一栏里选择一栏里选择“敏感性报告敏感性报告”，单击，单击“确定确定”，有关灵敏度分析的报告，有关灵敏
97、度分析的报告就会保存在同一个就会保存在同一个ExcelExcel工作簿的另外一张工作表上。对于球袋公司，我工作簿的另外一张工作表上。对于球袋公司，我们得到最优解所在的工作表如图们得到最优解所在的工作表如图2-72-7和敏感性分析所在的工作表如图和敏感性分析所在的工作表如图3-43-4。图图 3-3 3-3图图 2-7 2-7利用计算机管理软件进行灵敏度分析利用计算机管理软件进行灵敏度分析第五节灵敏度分析第五节灵敏度分析驳狱筷港捻验浙恤碑刊肋魁企宵峭驻痊锥汽毅搪朔货厅凳盯矾骨絮酪锥饱线性规划对偶理论及其应用线性规划对偶理论及其应用图图 3-4 3-4第五节灵敏度分析第五节灵敏度分析鸯淀妥姬秽力庄
98、肃额询见烟幼肋评涛驾牢昔褂穿脱捅赁稿警矿腕粥寨掇涅线性规划对偶理论及其应用线性规划对偶理论及其应用此报告中将包含缩减成本、影子价格、目标系数此报告中将包含缩减成本、影子价格、目标系数( (允许有小量增幅允许有小量增幅) )以及右侧约束区域。以及右侧约束区域。 注：必须选择注：必须选择 “假定线性模型假定线性模型” 才能提供完整的敏感性报才能提供完整的敏感性报告告接受求解结果，并接受求解结果，并将其输入可变单元将其输入可变单元格中。格中。用用Excel对例对例3.8的敏感性报告的敏感性报告第五节灵敏度分析第五节灵敏度分析撩宴荚怨嫉茄士班掀血秆妮蝴颇域钧蔑脖价辈妓扳田柿买江谊锅巡昧仔克线性规划对偶
99、理论及其应用线性规划对偶理论及其应用在不改变最优解在不改变最优解结构的前提下，结构的前提下，单个目标系数的单个目标系数的可变上下限。可变上下限。如果其中有如果其中有0 0出出现，表明存在现，表明存在多个最优解。多个最优解。仅当资源增幅在仅当资源增幅在允许的范围内，允许的范围内，才能利用影子价才能利用影子价格进行分析。格进行分析。即产品的边际收入与按影子价格折算的边际成本之差。当递减成本小于零时，表示不应该安排该产品的生产。第五节灵敏度分析第五节灵敏度分析臆憋吼颈巨乡妙丈淮寓欧粹黔浆滇冯持穴酗驰寞未跋粒功碴嚷在爬弓亩编线性规划对偶理论及其应用线性规划对偶理论及其应用列出目标单元格和可变单元格列出
100、目标单元格和可变单元格以及它们的初始值、最终结果、以及它们的初始值、最终结果、有关约束条件的信息。有关约束条件的信息。运算结果报告运算结果报告漫束烛商导拿迈霜私莹汕朵啥盘曲春椽汀行才霖士言盾僧链军饱喧绘及颖线性规划对偶理论及其应用线性规划对偶理论及其应用列出目标单元格和可变单元及列出目标单元格和可变单元及其数值、在满足约束条件和保其数值、在满足约束条件和保持其它可变单元格数值不变情持其它可变单元格数值不变情况下的上下限和目标值。况下的上下限和目标值。极限值报告极限值报告第五节灵敏度分析第五节灵敏度分析贩好夺怀刮嗓宛萤橱惺聂援测夫妇补掏蒂魂名曳烛肌键膊势臼式极妓们著线性规划对偶理论及其应用线性规
101、划对偶理论及其应用原问题： max Z=60x1+30x2 +20 x3 s.t. 8x1+6x2+ x3 48 M机器 4x1+ 2x2 +1.5x3 20 N机器 2x1+ x2 + 0.5x3 8 P机器 x1,x2，x3 0 对偶问题： Min w= 48 y1 + 20 y2 +8 y3 s.t. 8y1 + 4 y2 +2 y3 60 6y1 + 2y2 +y3 30 y1 + 1.5y2 +0.5y3 20 y1, y2 , y3 086 142 1.52 1 0.5A=48208b=60 30 20c=8 4 26 2 11 1.5 0.5B=603020 b= 48 20 8
102、c=maxmin一、对偶问题与原问题的对应关系本章小结本章小结稀慰京拣彝狭砾忘弗囊蛰目鸳榷签昧顷检矗垣藏筏信计逛缕丛辑檬澜猫鸿线性规划对偶理论及其应用线性规划对偶理论及其应用 二、对偶变换二、对偶变换 约束条件的类型约束条件的类型(规范与否规范与否)与非负条件相互对应与非负条件相互对应非标准的约束条件类型对应非正常的非负条件非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的对偶变换是一一对应的本章小结本章小结咨诬渗也等侣挛难蔚最嫂工貌歼荣牲饺泵舍辖液衡锄塔睁乒撑吊镐妒瘸窃线性规划对偶理论及其应用线性规划对偶理论及其应用定理定理3.1 （对称性定理）（对称性定理）对偶问题的对偶问题是原
103、问题。对偶问题的对偶问题是原问题。三、对偶性质三、对偶性质本章小结本章小结舷挨廉缨玲奥岩忠目歪泵愈化钓爬宿算载哲旗蔽亚鹃册诬占迈娜颧位作弄线性规划对偶理论及其应用线性规划对偶理论及其应用证证: :由于由于X X0 0,Y,Y0 0分别为原问题和对偶问题的可行解分别为原问题和对偶问题的可行解, ,故有故有: : 定理定理3.2 （弱（弱对偶定理）对偶定理） 对偶问题对偶问题(min)的任何可行解的任何可行解Y0，其目标函数，其目标函数值总是不小于原问题值总是不小于原问题(max)任何可行解任何可行解X0的目标函数的目标函数值。值。 定理定理3.3 （主对偶（主对偶定理）定理） 如果原问题和对偶问
104、题都有可行解，则它如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解所对应的目标函们都有最优解，且它们的最优解所对应的目标函数值相等。数值相等。本章小结本章小结琢虱让球西收磐茄此吊科冯赶最雍效珍俐橱称抱旁郭噎梅酚休藤敷斋垮滋线性规划对偶理论及其应用线性规划对偶理论及其应用 若原问题的某个可行解若原问题的某个可行解X0的目标函数值的目标函数值与对偶问题某个可行解与对偶问题某个可行解Y0的目标函数值相等，的目标函数值相等，则则X0, Y0分别是相应问题的最优解分别是相应问题的最优解 定理定理3.4 （最优解判别（最优解判别定理）定理）本章小结本章小结簇阮藏辣挎铱臆聘瑞枯澈辜办械做敖偿
105、赁溅掺小定吓驼洁糜搅筐娇泄洗非线性规划对偶理论及其应用线性规划对偶理论及其应用定理定理3.53.5松驰性定理松驰性定理设设x,yx,y分别是原问题和对偶问题的可行解，分别是原问题和对偶问题的可行解，则则x,yx,y是最优解的充要条件是对所有的是最优解的充要条件是对所有的i,ji,j，下列关系成立：，下列关系成立：1.1.如果如果x xj j0 0 ，则有，则有ypypj j=c=cj j2. 2. 如果如果ypypj jccj j, ,则有则有x=0x=03. 3. 如果如果yyi i00，则有，则有A Ai ix xi i =b=bi i; ;4.4.如果如果A Ai ix xi i b,0
106、，由松驰性质得到原问题约束条件应取等号即，由松驰性质得到原问题约束条件应取等号即w10 2x3+3x4=20w2 0 3x3+2x4=20， 解方程组，得解方程组，得x3=x4=4w1+2w212w1+w222w1+3w2=33w1+2w2=4x1=0x2=0本章小结本章小结赖郝谢茂铀普铜噶循乏纫击鞋绍捂绎氰兰迸疽踏梭侥锰碱鲜秃爵樟裴绅凯线性规划对偶理论及其应用线性规划对偶理论及其应用四、对偶单纯形法的计算步骤：四、对偶单纯形法的计算步骤：1、给定一个初始对偶可行的基本解，设相应的基为B；2若 ，则停止计算，现行对偶可行的基本解为最优解。否则令 ，则该行所对应的变量xr 为换出基的变量； 3若
107、对所有j， ，则停止计算，原问题无可行解。否则，令则 为换入基的变量；4以 为主元进行主元消去，返回2。本章小结本章小结卿贮眺际无街移巧杀进制晨坑踞亦域稍悔姥团牧栓针庇潍蔡耐烦容潜欺签线性规划对偶理论及其应用线性规划对偶理论及其应用单纯形法与对偶单纯形法总结单纯形法max型 最大检验数 最小比 检验数小于等于0min型 最小检验数 最小比 检验数大于等于0对偶单纯形法min型 最小b 最大比 所有b大于等于0max型 最小b 最小比 所有b大于等于0农裁木禄奥神蹭暗败嫩卡邻键形挞羞存陨轧戴柑阮瞬掉眷诌涯咨商苍宁驱线性规划对偶理论及其应用线性规划对偶理论及其应用五、原问题与对偶问题的解的对应关系
108、五、原问题与对偶问题的解的对应关系若是若是max型型(单纯形法单纯形法)在最优表中，基变量对应的解为原问题在最优表中，基变量对应的解为原问题(max)的最优解，的最优解，松驰变量的松驰变量的检验数的相反数检验数的相反数对应为对偶问题对应为对偶问题(min)的最优解的最优解若是若是min型型 (对偶单纯形法对偶单纯形法)基变量对应的解为本身问题的基变量对应的解为本身问题的(min)的最优解，剩余变的最优解，剩余变量的量的检验数检验数对应为对偶问题对应为对偶问题(max)的最优解的最优解因此，针对线性规划问题，只要解原问题或对偶问题其因此，针对线性规划问题，只要解原问题或对偶问题其中之一就可以中之
109、一就可以本章小结本章小结瓮战待矮龙磊停抠捻甄热颈京祖罩絮呜妓义篱躇敝舱沦过绥损铝磋栅椎夫线性规划对偶理论及其应用线性规划对偶理论及其应用在最优表中，松驰变量的检验数与对偶决策变量是一一对应的在最优表中，松驰变量的检验数与对偶决策变量是一一对应的Max()松驰变量的松驰变量的检验数的相反数检验数的相反数为对偶问题的最优解为对偶问题的最优解Min() 检验变量的检验变量的检验数检验数就为对偶问题的最优解就为对偶问题的最优解因此，可知因此，可知Max()松驰变量的松驰变量的检验数的相反数检验数的相反数就为相应资源的影子价格就为相应资源的影子价格Min() 检验变量的检验变量的检验数检验数相应资源的影
110、子价格相应资源的影子价格影子价格其实就是对偶问题的最优解影子价格其实就是对偶问题的最优解六、影子价格六、影子价格 本章小结本章小结敌耶贴烷刊舍筷挫扰批缨个贷姜夏向伟琳丝咏滚居逢掷虱磊硕支机扮溶注线性规划对偶理论及其应用线性规划对偶理论及其应用在线性规划中，我们假定模型的系数都是已知常数。而在实际中，这些系数往往是通过估计、预测或人为决策得到的，不可能很准确，更不可一成不变，灵敏度分析就是研究当线性规划问题中的系数发生变化时，对函数最优解的影响程度灵敏度分析主要研究以下两个问题：（1）这些系数中的一个或多个发生变化时对已求得的线性规划问题最优解的影响。（2）若原最优基不再是最优时，如何用最简便的方法找到新最优解和最优值七、灵敏度分析概念七、灵敏度分析概念本章小结本章小结娟远皆唇枚烃锑汤剥逻直队纺虹辑僳粤肚义砖矮刺狞聚贯挖毒背饶秉宦琢线性规划对偶理论及其应用线性规划对偶理论及其应用
