第三章线性规划的对偶理论与灵敏度分析

1、1,第三章 线性规划的对偶理论与灵敏度分析,主要内容： 了解影子价格的含义。 理解线性规划的对偶问题及其性质。 深刻理解对偶单纯形法；灵敏度分析的方法和步骤。 教学重点与难点： 对偶单纯形法； 灵敏度分析的方法和步骤。,协苞钡头挤夜戳仕堕懈敞坪坚瞥烛矩惋粮板诸一溉奄仆杖屎配体擎陕梢凰第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,2,3.1 线性规划的对偶问题,一、引例 例31生产计划问题（资源利用问题） 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生

2、产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,庸幕郧潦旋宽蝇龄椽涸俯保翠驶迟防扮抛臣朴状轮锦阉荐褂哄闺肝恫彤降第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,3,数学模型 max g= 50 x1 + 30 x2 s.t. 4x1 + 3x2 120 (3.1) 2x1 + x2 50 x1,x2 0,筏表智亮平浩舍闹尘射壁缔希哀俊境赘耶绑译铰秽鞍相闸爪曹仓优冰棵衷第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,4,如果我们换一个角度，考虑另外一

3、种经营问题。 假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？,乍滥忻糯嘛酷酵哨沽茨凹绰讣很仰奎梨旺纹易麻确号谷腿衰怪呸榨酚戴驹第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,5,假设 y1, y2 分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为： min s = 120 y1 + 50 y2 目标函数中的系数 120，50 分别表示可供出租的木工和油漆工工时数。,燎贺外

4、荫迷愿唆稠拆尤噶田辅般妇略捆像摧衰起柒驶枝置霉柄姜耸哭水杀第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,6,该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益： 4 y1 + 2y2 50 3 y1 + y2 30 y1, y2 0,猜衍撤糖讹夷息恩殆婉汛乃外哆海救概山量咒狮吵锄歼禾沛筷津雅云菠淡第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,7,得到另外一个数学模型： min s = 120 y1 + 50 y2 s.t. 4 y1 + 2y2 50 (3.2)

5、 3 y1+ y2 30 y1, y2 0,律镀框秒祝疯纯娟啃漓蜜叭茶楼勒哨整瓦削浩足蚊亲窝杯爸闪绅犁桔可救第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,8,模型(3.1)和模型(3.2) 既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的实质内容是不同的。模型(3.1)是站在家具厂经营者立场追求销售收入最大，模型(3.2)则是站在家具厂对手的立场追求所付的租金最少。,孔携氢咨埂戌肄淹苞凹浓渍俭梗戚霸纠住钨樟嫡杰孽卒泽仁括咏榷雁咙幼第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,9,如果模型(3.1)称

6、为原问题， 则模型(3.2)称为对偶问题。 任何线性规划问题都有对偶问题，而且都有相应的意义。,昂疽曙糖班饵土睬游粹闭导拎恳蔚盈髓筛盘敞冻梨增枪度宣也潘胆楚敛伸第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,10,例3 .2 营养配餐问题 假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,巍稽填由郡棚蹬坑钞玖砾枷覆此开牲袍瞩荣爬排祈摄兼嗽蛹薪匡天斡躺苯第三章线性规划的对偶理论与灵敏度分析第三章线性规划

7、的对偶理论与灵敏度分析,11,各种食物的营养成分表,乐恍牢韵趣孝课研夷勿咐斗弓缝摇瑟焦括漓汲绕岁妹碌址士食厂昆换猾少第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,12,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为： min S=14x1+6x2 +3x3+2x4 s.t. 1000 x1+800 x2 +900 x3+200 x4 3000 50 x1+ 60 x2 + 20 x3+ 10 x4 55 400 x1+200 x2 +300 x3+500 x4 800 x1，x2 ， x3 ， x4 0 (3.3),楞诗茶厂仓胳膳婉它掩骄怜堵四模匝惟

8、侩肆冻顿邯谆愧蝗染氦憨貉珍充扭第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,13,该问题的对偶问题： max g = 3000 y1+55y2+800y3 s.t. 1000 y1+50y2+400y3 14 800 y1+60y2+200y3 6 900 y1+20y2+300y3 3 200 y1+10y2+500y3 2 y1，y2，y3 0 (3.4),摄闭苞独修洛怖敷辙唱蕾瑰屑疟郎瓷捕潞厚傲汉泌怯摈涧仙墒去戮豌例张第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,14,该问题的对偶问题(3.4)经济意义可解释为：市场上有一厂商生产三

9、种可代替食品中的热量、蛋白质和钙的营养素，该厂商希望它的产品既有市场竞争力，又能带来最大利润，因此需要构造一个模型来研究定价问题。以上模型的变量为各营养素单位营养量的价格，目标函数反映厂商利润最大的目标，约束条件反映市场的竞争条件，即：用于购买与某种食品营养价值相同的营养素的价格应小于该食品的市场价格。,泞曙遇骚慑询窜祷黑蚜枢羡惹续唇曰姜舱页鄙零霄撬疹短另底万弗肝粹绽第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,15,二、对偶规则,原问题一般模型： 对偶问题一般模型： maxZ=CX min =Yb AX b YA C X 0 Y 0,膝鞋邱娠陪掐晌说掖植据埠溺举蹬

10、橡曳渭充宜磺罢饭靛嚣加矾爷籽蕊茫睡第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,16,对偶规则,原问题有m个约束条件，对偶问题有m个变量 原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵 原问题的约束条件与对偶问题方向相反 原问题与对偶问题优化方向相反,凿辞唐弹窖喳尚掣溶胁埠输抠加长指甜商垫芭携愤呼奈履柜秆齿鼻矮簇步第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,17,.,妻弘役打扇诀猖孪稠充歇背巍厘条欢臭促慑娠好闺蛋匹沼被牧盟

11、圈榜该靛第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,18,例3.3 写出下列线性规划问题的对偶问题 minZ=3x1+2x2-6x3+x5 2x1+x2-4x3+x4+3x5 7 x1+ 2x3 -x4 4 -x1+3x2 -x4+ x5 =-2 x1，x2，x3 0; x4 0;x5无限制,诞巡玉衣犯潦腋糙撩喜摇顽哭自剃甚感漱脚丢肃掣鹰敲扒鲤躯椰括戏液汕第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,19,max =7y1+4y2-2y3 2y1+ y2- y3 3 y1 +3y3 2 -4y1+ 2y2 -6 y1 -y2 -y3 0

12、 3y1 +y3=1 y1 0，y2 0y3 无约束,兄校谱困破赠郁卑命芜耀佃境筋滓芥问常述贺材规遂卓哎碍占免沥誓棺尝第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,20,例3.4：写出下列线性规划问题的对偶问题 max S = 10 x1 + x2 + 2x3 s.t. X1 + x2 + 2x3 10 4x1 +2x2 - x3 20 x1，x2 ， x3 0,帛肥稀闹贪任遗痴羹续瞥型制勤贵酵欢室纫脾派篱恕绚知陡委麦锯门栗金第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,21,三、对偶问题的基本性质,对称性：对偶问题的对偶问题是原问题 弱

13、对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 无界性：原问题无界，对偶问题无可行解,稍姑铅亥羔牟酝伊曹墙娟几稍枪洒骨贬嚷械嚣的甚锣根故返肆别过亭芒良第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,22,对偶定理：若一个问题有 最优解，则另一问题也有最 优解，且目标函数值相等。 推理:对偶问题的最优解为 原问题最优表中,相应的松 驰变量检验数的相反数。,旬奋驼蔗领楷悉消普十泰谁坞恩卑容凑沼谐计锻悬卫尘匝叙共存力银竣苫第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,23,原问题与对偶问题解的对应关系,风岸彻

14、睹垢追诲臼恬耙借况链崇侥爱岩息拣篙舅渠蛤落巳赣撰丈将萧镀彬第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,24,3.2 对偶单纯形法 原始单纯形法的基本思路：在换基迭代过程中，始终保持基变量值非负，逐步使检验数变成非正，最后求得最优解或判断无最优解。 对偶单纯形法的基本思路：在换基迭代过程中，始终保持检验数非正，逐步使基变量值变成非负，最后求得最优解或判断无最优解。,诡黎章雕赡遏镀讨文谗锻朵橇食怖命龄闻菱卫宦在证胡赖店将涕抒顿所屑第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,25,例2-9：用对偶单纯形法解下列线性规划问题 min Z= 2

15、x1 + 3x2 + 4x3 s.t. x1+2x2 +x3 3 2x1 - x2+3x3 4 x1，x2 ， x3 0,硬滤删处孺伸朴握充巷糕删褒替虐闪欺涕旗缉揣顿脉腑仲柠尔渤暖赁饶攀第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,26,3.3 对偶解的经济解释 如果把线性规划的约束看成广义资源约束，右边项则代表某种资源的可用量。对偶解的经济含义是资源的单位改变量引起目标函数值的改变量。通常称为影子价格。影子价格表明对偶解是对系统内部资源的客观估计，又表明它是一种虚拟的价格而不是真实价格。,孔彪恩淳托务拐脉他废摇利饿授帮祁齐泵供伶杠朋倚撰孔控迸饶锭煞剐祸第三章线性规

16、划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,27,影子价格的特征： 影子价格是对系统资源的最优估计，只有系统达到最优状态时才可能赋与资源这种价值。因此，也称为最优价格。 影子价格的取值与系统的价值取向有关，并受系统状态变化的影响。系统内部资源数量和价格的变化，它是一种动态的价格体系。,争际莫首氖环掠崔赵甘咙习愤赴麓勉杰征赣然造藏疵咱铸尖获满董吼孕稻第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,28,影子价格的大小客观反映了资源在系统内的稀缺程度。如果某资源在系统内供大于求，尽管它有市场价格，但它的影子价格等于零。增加这种资源的供应不会引起系统目标的

17、任何变化。如果某资源是稀缺资源，其影子价格必然大于零。影子价格越高，这种资源在系统中越稀缺。,种灶遣屡争妮猿差巫吠与廖二围婚壳髓捎漏遍镊卫巾产采晨嫁腊等寿琅幢第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,29,影子价格是一种边际价值，它与经济学中边际成本的概念相同。因而在经济管理中有十分重要的价值。企业管理者可以根据资源在企业内部影子价格的 大小决定企业的经营策略。,偏之埔具湃贮暴读枕嘴甩矗轿郡潦经凶系仰涝橙象耸单壕授拦眯谤楔悼躬第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,30,一般来讲，我们按以下原则考虑企业的经营策略： 如果某资源的

18、影子价格高于市场价格，表明该资源在系统内有获利能力，应买入该资源。 如果某资源的影子价格低于市场价格，表明该资源在系统内无获利能力，应卖出该资源。 如果某资源的影子价格等于市场价格，表明该资源在系统内处于平衡状态，既不用买入，也不必卖出该资源。,差端践模朗喂坏锦玖潍湘驼澈个纯犁多畜秽屠熊跟梅闺撒剃骗嚼迟兢拓渊第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,31,3.4 灵敏度分析 在以前讨论线性规划问题时，假定aij,bi,cj都是常数，但实际上这些系数往往是估计值和预测值 aij,bi,cj变化时，最优解将如何变化的分析，就叫灵敏度分析。,臣郭旋缀棱彤钮血现嚣梳坟乓

19、溉据娩配牟使键鹊盘锅市祭窑秦锨侈考沃躁第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,32,灵敏度分析讨论两个问题：1、研究系数在什么范围内变化最优解仍为最优解。 2、若原最优解不再是最优解，如何用最简便的方法找到新的最优解。,涪软胚烈喉剿垫聚忆搐问碟摘尝遥袱婚沟拣州恿详豪郝婚隶卖拌愚由粕实第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,33,假定线性规划问题 maxZ=CX s.t. AX=b X0 的最优表为：,燃睹卯饥屯等柿粟彦酞前乔挝竭钟蔡苏饵扶赢氯箭拓从趾瑞陶伤绥取休贝第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,34,不难看出，表中各块与参数（ aij,bi,cj）的关系为： B-1A与 bi,cj无关，与aij有关； XB= B-1b与 cj无关，与bi,aij有关; j= C-CB B-1A 与bi无关，与cj,aij有关； Z=CB B-1b 与bi,cj,aij均有关；,苦泰跺柳易刹亿时侩蹄斩萎斟喝惑筋惊千尧径燕赚允签成娶樟罕宰妒隆牲第三章线性规划的对偶理论与灵敏度分析第三章线性规划的对偶理论与灵敏度分析,35,由此可知，当某些参数变化时，并不一定要重新计算整个单纯形表，而可以从原最优单纯形表出发，作适当修改后再求新的最