MBA学位课程-运筹学1(ppt125).ppt

《MBA学位课程-运筹学1(ppt125).ppt》由会员分享，可在线阅读，更多相关《MBA学位课程-运筹学1(ppt125).ppt（125页珍藏版）》请在装配图网上搜索。

1、1,运筹学(Operation Research) MBA学位课程,衷心希望本课程能让大家受益,此建颐料葱铲叹黔储抒乞夏卫浇隘辽晨晃嫁纲腕脏仑粥瞄责掀胃墅揭爱铭MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,2,教师介绍 姓 名： 刘满凤 职 称： 副教授 博士 单 位： 信息管理学院 电 话： 3816922（O） 3816926（H) E-mail: ,课程考核评分方法 平时成绩分占 40 % 其中 课堂讨论5% 平时作业5% 大作业 30% 课程考试分占 60 %,授课计划 总 时 数：48 课时 授课时数：46 课时 其中课堂授课42课时，上机授课4课

2、时 案例讨论：2 课时,页胀只岭侮桂柔餐歪绑食谁雪玄氓死待增楷肌逾弹魁床偿虏寡综撵神盟煎MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,3,课程内容简介与学习要求,课程内容简介,运筹学是一门应用性学科，它主要是应用定性分析和定量分析相结合的方法，通过建立实际问题的数学模型，应用合适的优化算法对模型进行求解，从而解决实际问题。,其主要内容有：线性规划、整数规划、非线性规划、动态规划、图与网络分析、排队论、存贮论、对策论、决策论、多目标规划等。本课程选取了运筹学在经济管理领域中常用的五个部分作为教学内容，即：线性规划、整数规划、动态规划、图与网络分析、对策论。,学

3、习要求,本课程将通过重点讲授原理方法、上机解题、个人研究与小组讨论相结合的案例分析等环节，培养学员全局优化的思想，使学员掌握若干类常用的运筹学模型，并能用其解决经济管理中的复杂问题。 因此要求学员：对布置的思考、案例讨论题进行认真准备，按进度完成平时作业和上机练习，按要求完成大作业书面报告。,参考资料,（1）刘满凤、付波、聂高飞编著运筹学模型与方法教程例题分析与题解，清华大学出版社，2001年。 （2）运筹学教材编写组编运筹学（修订版），清华大学出版社，1996年。 （3）蓝伯雄、程佳惠、陈秉正编著管理数学（下）运筹学，清华大学出版社，1998年。 （4）中山、四川、西北、武汉、湘潭大学编运筹

4、学经济管理决策方法，四川大学出版社，1995年。 （5）韩大卫编著管理运筹学，大连理工大学出版社，1998年。 （6）胡运权主编运筹学习题集（修订版），清华大学出版社，1985年。,耻夷蔼刑夕轴宅辕窟讯棺舌匹新解期葵秋妥誓账叉璃挥脖德脊滔妆宵惶氮MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,4,本课程内容安派：,第一部分 线性规划及其应用,1、问题的数学模型与求解 2、单纯形法与计算机求解 3、对偶理论与灵敏度分析 4、运输问题及其解法 5、指派问题及其解法 6、整数线性规划问题及其解法,第二部分 动态规划,1、动态规划的基本概念和最优化原理 2、动态规划模

5、型的建立和求解方法 3、建模训练与求解,第三部分 对策论模型,第四部分 图与网络分析,1、两人有限零和对策模型及其解法 2、两人有限非零和对策,1、图与网络的基本概念 2、树与最小树 3、最短路问题 4、最大流问题 5、最小费用最大流问题,境捏孟负惫节件靳庐造唬奔蛙屡宠材贝纯盆创永抬焙扒厄壁橱怖抖凋憋坊MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,5,绪 论 一、运筹学的历史与发展 国际上运筹学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公

6、式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。,夯沥毕沁农枝娟懦愉延睫喻业幂敢奄洋勋姐纂要波蠕赁缸殴剿挖啃俄佐隆MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,6,二次世界大战时期，德国空军对英伦三岛狂轰滥炸，为对付敌人的空袭，英国人使用了雷达，但没有科学的布局，防空系统的效率并不很高，为解决这个问题，英国军方于1939年9月从全国各地调来一批科学家，共11人，他们中有将军1人、数学家2人、理论物理学家2人、应用物理学家1人、天体物理学家1人、测量学家1人、生物学家3人，来到英国皇家空军指挥部，组成了以著名

7、的物理学家、诺贝尔奖金获得者P.M.S.Blacket为核心的世界上第一个运筹学小组，他们的任务就是应用系统论的观点，统筹规划的方法研究作战问题，这个运筹学小组在作战中发挥了卓越的作用，受到英国政府极大的重视。,攒呛晕哮呢鸥郑耳烫驾讥张字叼固慌怀议藕赂潜浑楚作娟荐恿羊坛痪晋甩MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,7,于是，英国政府逐渐在它的海陆空三军中都成立了运筹学小组，美国参战以后，也仿效英国在军队中成立了运筹学小组。,在生产管理方面的应用，最早是1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题，并给出解乘数法的求解方法，出版了第一

8、部关于线性规划的著作生产组织与计划中的数学方法。 但当时并没有引起重视，直到1960年康特洛为奇再次出版了最佳资源利用的经济计算，才受到国内外的一致重视，为此康特洛为奇获得了诺贝尔经济学奖。,线性规划提出后很快受到经济学家的重视，如二次世界大战中从事运输模型研究的美国经济学家库普曼斯（T.C.Koopmans），他很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。,姑肝稚也威史琼集橡淋自号档田疟样丧迅鸣岁塘帕舷爸发隘念班筹芥挞烧MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,

9、8,50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。 1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。,在中国，最早的运筹学思想有战国时期的田忌赛马，它是

10、对策论的一个典型例子，北宋时期的丁渭造皇宫，它是统筹规划的一个例子。,豁差捍埂崎舟奈僧浴弓目姓掣薛扒揖狈飘君眠枪疥垃拍湍错枯蝴孜廷境桩MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,9,二、运筹学的基本内容,1、线性规划（Linear Program）是一个成熟的分支，它有效的算法单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。 2、整数规划(Integrate Program)：在线性规划的基础上，变量加上整数约束 3、非线性规划(Nonlinear Program)：目标函数和约束条件是非线性函数，如证券投资组合优化:如何合理投资使风险最小。

11、4、动态规划(Dynamic Program):多阶段决策问题。是美国贝尔曼于1951年提出的。 5、图与网络(Graph Theory and Network)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。,舵窃爪署递暂缠容腐梢多另卑哆躯层他伐油黔颈膀悦劝光耪粳劳缄捻轧罕MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,10,6、存储模型（Inventory Theory)：主要解决生产中的库存问题，订货周期和订货量等问题。 7、排队论(Queue Theory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。 8、对策论(Gam

12、e Theory)：主要研究具有斗争性质的优化问题。 9、决策分析(Decision Analysis) ：主要研究定量化决策,三、运筹学的工作步骤 1、明确目标、收集资料、提出问题 2、建立模型 3、模型求解与检验 4、结果分析与实施,拼炸驼五蒲洱收脏毗刘裂阶其同株孤燥汇烙吝侦榜杖墟绎忽坡违颐蘑熊伍MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,11,第一部分 线性规划及其应用,线性规划研究的主要内容,线性规划主要解决两个方面的问题： （1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？ （2）在给定的一定数量的资源条件下，如何合理安排，使完成

13、的任务最多？,线性规划内容框架,昧箭魔领八魂鹏感突集诺滑躬言厢次贱邯尉褒土掘佐肢旨哈洱乒膊腿贵翱MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,12,届伦涩蜕嚎来疑稻靛俏芦祭傀必琴万迹牟门嘛旗惋坡累鄙盒加曳卢份钞肄MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,13,第一章 LP问题的数学模型与求解,圃语扎谚烘赞课韦侨女礁脐逗搪割稳乍海轮拴茄怪鹊隐井厕倾娇砖兽雇粕MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,14,解：,设x1,x2分别表示在计划期内生产产品、的产量。由于资源的限制，所以有：

14、,机器设备的限制条件:x1+2x28 原材料A的限制条件： 4x116 （称为资源约束条件） 原材料B的限制条件： 4x212 同时，产品、的产量不能是负数，所以有 x10，x20（称为变量的非负约束） 显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数 Z=2x1+3x2的值达到最大。,滋探告疲趟祁剥儿冷唉为迅往蹦鹰熏猪黔恼乌疲债缎件珍褂孪鼠仕坪顺掂MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,15,综上所述，该生产计划安排问题可用以下数学模

15、型表示： maxz=2x1+3x2,例2. （营养配餐问题） 假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能使在满足营养的前提下使购买食品的总费用最小？,壬页溃琉掌苗夺撤圈帘薪仕躲娄淄阅怨配涩趋黄千蚌听究瘦晰揖锨扁颇咽MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,16,解:设xj(j =1,2,3,4)为第j种食品每天的购买量，则配餐 问题数学模型为 minz=10 x1+6x2+3x3+2x4,毛仰赌认卵忧套练滋肃押鳃康盏初

16、诀女酋察旋摊犯蔡浅猪甩时却孽涅聊乐MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,17,例3 运输问题（课本P6）,某公司经销某种产品，三个产地和四个销地的产量、销量、单位运价如下表所示。问在保证产销平衡的条件下，如何调运可使总运费最少？,伏谦英楞扁扎见禾去傅趟滑佃毒雀锭妒姚琐寞吕瞧蔼贝粥湖塞奇颂脂要畴MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,18,解:（1）确定决策变量：设xij(i=1,2,3;j=1,2,3,4)为从产地i运到销地j的运量,（2）确定目标函数：总运费最小 minz=,（3）确定约束条件：,x11+x

17、12+x13+x14=60 产量约束： x21+x22+x23+x24=40 x31+x32+x33+x34=60,x11+x21+x31=30 销量约束： x12+x22+x32=50 x13+x23+x33=40 x14+x24+x34=40,娘像炒吴魔闻郁搐旺靳装脸迎痉制幻闺颖疾磋哉迷副异诀况萎欣抠蛀岩同MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,19,非负约束 xij0,由此模型总结为：,吓旦佐驮炎比条奏褐樱酌泉籽香腐掌新雾遍腥否脖茨上雀斯射雌悉此叮结MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,20,（二）LP

18、问题的模型,上述几例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征。,（1）每个问题都可用一组决策变量(x1,x2,xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。,（2）存在一组线性等式或不等式的约束条件。,（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。,蝶抑滓恫输轴陈峪孺汗方鼓拍勘霍评唾传龋溉尚葵各串柏尖疮匡涛壁洱躁MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,21

19、,满足以上三个条件的数学模型称为LP问题的数学模型，其一般形式为： max(或min)z=c1x1+c2x2+cnxn,（1.1),（1.2),（1.3),或紧缩形式,囤障归假硼柔曰钝焊垛岂缸购楷字恨融馅舟痈恒痘裴允角仅殉附棵狐看洒MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,22,或矩阵形式,或向量形式： max(或min)z=cx,其中c=(c1,c2,cn)，称为价值系数向量；,称为技术系数矩阵(也称消耗系数矩阵),躯辰迷瘦决榴锁庇菌献郝亚肯纲绝姚撤讨熔蛛吴砌温忍煎仁溃识掂札渐蝗MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt1

20、25）,23,称为资源限制向量,X=(x1,x2,xn)T称为决策变量向量,下面我们再来看两个实际例子。 引例3 课本P60 例25（投资计划问题）某公司经调研分析知，在今后三年内有四种投资机会。第种方案是在三年内每年年初投资，年底可获利15%，并可将本金收回；第种是在第一年的年初投资，第二年的年底可获利45%，并将本金收回，但该项投资不得超过2万元；第种是在第二年的年初投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5万元；第种是在第三年的年初投资，年底收回本金，且可获利35%，但该项投资不得超过1万元。现在本公司准备拿出3万元来投资，问如何计划可使到第三年年未本利和最大

21、？,材嗡雇斟座姓霄嗓渔慧既骚峭柳帖裸拉遗钳桂萧寥釜炼彬簇梧窜歪予薄埃MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,24,解：问题分析。该问题的实际投资背景如下表所示： （1）确定决策变量：设xij表示第i年对第j个方案的投资额,i=1,2,3; j=1,2,3,4,年份 一 二 三 四 x11 1.15x11 x12 1.45x12 x21 1.15x21 x23 1.65x23 x31 1.15x31 x34 1.35x34,粪声孕眼蛰炕敦腹尖直星府兑群囤剪晶执江涝慎占柞鸦获潦瓦汝料掀又驴MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（p

22、pt125）,25,（2）确定目标函数：第三年年未的本利和为 maxz=1.65x23+1.15x31+1.35x34,（3）确定约束条件： 每一年的投资额应等于当年公司拥有的资金数： x11+x12=3 x21+x23=1.15x11 x31+x34=1.45x12+1.15x21,每个方案投资额的限制： x122 x231.5 非负约束：xij0,i=1,2,3;j=1,2,3,4 x341,轿元娶园呵聂螟荡丝捉厄垛虏勿剑狮纶中板使栈毒靛佳局陶黔短级缮骇懈MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,26,引例4 （合理下料问题）要用一批长度为7.4米的

23、园钢做100套钢架，每套钢架由2.9米、2.1米、1.5米的园钢各一根组成，问：应如何下料才能使所用的原料最省？ 解：问题分析：一根长度为7.4米的园钢，要裁出2.9米、2.1米、1.5米的料有多种裁法，如可裁出一根2.9米、二根2.1米，也可裁出三根2.1米的。这样我们把所有裁法列举出来，如下表所示：,下料 方案 根数 一 二 三 四 五 六 七 八 长度米 2.9 1 1 1 2 0 0 0 0 2.1 2 0 1 0 1 2 3 0 1.5 0 3 1 1 3 2 0 4 合计 7.1 7.4 6.5 7.3 6.6 7.2 6.3 6 料头（米） 0.3 0 0.9 0.1 0.8 0

24、.2 1.1 1.4,嗡馏周符叔矿损棋臃瞄缉每料冯撤膀馒漆既其垮玉秃瓮树拧匹赃知镣疗由MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,27,（1）确定决策变量：设xj表示按第j种方案所用的园钢的数量 （2）确定目标函数：问题要求所用原料最省，所用原料为： minz=x1+x2+x3+x4+x5+x6+x7+x8 （3） 确定约束条件： 2.9米园钢的数量限制 x1+x2+x3+2x4100 2.1米园钢的数量限制 2x1+x3+x5+2x6+3x7100 1.5米园钢的数量限制 3x2+x3+x4+3x5+2x6+4x3100 非负限制 xj0，且为整数， j

25、=1,2,8,建立线性规划模型的一般步骤： （1）确定决策变量； （2）确定目标函数； （3）确定约束条件。,桃灵或捞岁控奋潜蹄幢恕磺磅痛专糊姨刀选缝猫缄世驴母捂汇弯耿闻档纶MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,28,引例5一个木材储运公司有很大的仓库用以储运出售木材。由于木材季度价格的变化，该公司于每季度初购进木材，一部分于本季度内出售，一部分储存起来以后出售。已知该公司仓库的最大储存量为2000万米3，储存费用为（70+100u）千元/万米3，u为存储时间（季度数）。已知每季度的买进卖出价及预计的销售量如下表所示。,由于木材不宜久贮，所有库存木材

26、应于每年秋末售完。为使售后利润最大，试建立这个问题的线性规划模型。,粘弊贸铰蛤男挂珍求绿婆戮槐缸费铰辐戏辐绊电熔责稼恿戌妮淘弯痪卒垛MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,29,设yi分别表示冬、春、夏、秋四个季度采购的木材数，xij代表第i季度采购的用于第j季度销售的木材数。,漠骄外泡虞检勿克屹田特延父奶梳雅趋撮宁冶携域谨误斤聊怖左茧聪阀撞MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,30,引例6、有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如表1所示。现有三种货物待运，已知有关数据列于表2。为了航

27、运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系，具体要求前、后舱分别与中舱之间载重量比例上偏差不超过15%，前、后舱之间不超过10%。问该货轮应装载A，B，C各多少件，运费收入为最大？试建立这个问题的线性规划模型。,表1,绪葛挖镇鸵罢听富萝淀顾椒詹洛优租夺睬索典宰梢既缚琼霸毡致驱哉党至MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,31,设表示xij装于第j(j=1,2,3)舱位的第i(i=1,2,3)种商品的数量,舱位载重限制,舱位体积限制,商品数量限制,平衡条件,呕郡针窃萌赞徐匝织胆臼旋歪袖白沏冉挨氨侩固惭杭脐才驱掺专们挤最坯M

28、BA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,32,（三）LP问题的标准型,1.为了讨论LP问题解的概念和解的性质以及对LP问题求解方便，必须把LP问题的一般形式化为统一的标准型：,或,maxz=cx,标准型的特点： 目标函数是最大化类型 约束条件均由等式组成 决策变量均为非负 bi(i=1,2,n)=0,受攘当诵翁旬际鬃约锄逻为鼓炳柿喊哪奈位臼撇冒狱擦毕篷漳羹倚寸滇讶MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,33,2.化一般形式为标准型 目标函数：minzmax(-z)=-cx 若约束为“”型左边+松驰变量； 若约束为

29、“”型左边“松驰变量” 若变量xj0-xj0变量， 若变量xj无限制令xj=xjxj 若右边常数bi0等式两边同乘以(-1)。,例4课本P9 化下述问题为标准型 minz=-x1+2x2-3x3 x1+2x2+3x37 s.t. -x1+x2-x3-2 -3x1+x2+2x3=5 x1,x30,x2无约束,奴哆哺铃氖讶状彝贝羽荫斟岸述煌嘘仪萤臻蛾烂晨厌恃衅惋窗夺渡深怯陇MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,34,解：首先考察变量：令 ，并加入松驰变量x4,x5化为如下标准型：,练习：课本P64 2.2（3）,那湾寐间木粟诵袜疗随揭睡蜕钻轨屎茹焊擎寻栅

30、裹碍变憨宙配箕特爪鞠落MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,35,解：令,则,加入松驰变量s,w，得到标准型如下：,汕坐瓜翅埔屑讳蒂炕漂养王阑拧烷猩蒲节单瞄昂丁轧塔缕狮站忆施汽支侦MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,36,（四）LP问题解的概念,1.从代数的角度看： 可行解（Feasible Solution)： 满足约束条件(1.8)和(1.9)的解X=(x1,x2,xn)T称为可行解。所有可行解构成可行解集，即可行域。 最优解(Optimal Solution): 而使目标函数达到最大值的可行解称为最

31、优解，对应的目标函数值称为最优值。 求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难的。,设LP问题,嗓浦介殴鲍料污永钱丑忘抒钩昭盗肤驭隧胆伐彝稀瓦杂沤顾林贿撅籍眩粹MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,37,2.从LP角度看： 基(Basis)：设A为mxn矩阵，r(A)=m，B是A中的mxn阶非奇异子矩阵（即|B|0），则称B是LP问题的一个基。 若B是LP问题的一个基，则B由m个线性独立的列向量组成，即B=(Pr1,Pr2,Prm)，其中Prj=(a1rj,a2rj,amrj)T，(j=1,2,m)称为基向量。 基变量(Basic

32、Variables)与非基变量(Non-basic Variable) 与基向量Prj相对应的变量xrj称为基变量，其它变量称为非基变量。显然，对应于每个基总有m个基变量，nm个非基变量。,基本解(Basic Solution)： 设B是LP问题的一个基，令其nm个非基变量均为零，所得方程的解称为该LP问题的一个基本解。显然，基B与基本解是一一对应的，基本解的个数Cmn。 基可行解: 在基本解中，称满足非负条件的基本解为基可行解，对应的基称为可行基。,沼卿乍废证昂多肿慌诛冲亮危良韦革姜渤吵韧寸们脾免益姨布浅扯嘱甚网MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）

33、,38,退化解(Degenerate Solution)： 如果基解中非零分量的个数小于m，则称此基本解为退化的，否则是非退化的。 最优基解(Optimal Basic Solution)： 如果对应于基B的基可行解是LP问题的最优解，则称B为LP问题的最优基，相应的解又称基本最优解。,3.LP问题解之间的关系如图所示：,可行解,基解,最优解,基最优解,巡鸳乳猫舷塘梗乡喷粒剁桅尿打光汛霸敲橙畅宏酥聘枝链矿裸唯莉棋售穴MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,39,（五）两个变量LP问题的图解法,1、LP问题图解法的步骤：,（1）画出直角坐标系； （2）依

34、次做每条约束直线，标出可行域的方向，并找出它们共同的可行域； （3）任取一目标函数值作一条目标函数线（称等值线）,根据目标函数（最大或最小）类型，平移该直线即将离开可行域处，则与目标函数线接触的最终点即表示最优解。,例1：用图解法求解如下线性规划问题,最优解为x1=6,x2=4 最优值为maxz=36,恃尖辽诗世闻泊酶豫坤见途闲侄崖淋仲豫展娶乒弓漳按揪汹冯吴巍赠氯航MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,40,例2：用图解法求解下列线性规划：,Q3,Q,4,B,x,1,3,2,1,0 1 2 3 4,Q2（4，2）,Q1,Q2（4，2）为最优解,化族杜

35、郎哀伯苇积劝盟杜镍尽怖篆咱露涅暗悬爵禹衡粗约吮赂增丧蜡缉硫MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,41,解的几种情况： （1）此例有唯一解Q2，即x1=4, x2=2, z=14 （2）有无穷多最优解（多重解），若将目标函数改为z=2x1+4x2 则线段Q2，Q3上的点均为最优解。 （3）无界解,援撂皇嫁燎忙挖壳苗乙彭涟讯击结怒左鸽赵曾庄逢尖织上龄奇惟毯圈镀肩MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,42,(4)无可行解,衣察控鸣绪排奢爷含获诡聘冬侈镇县焉赠券韦靶虞改搂捞希此磨项珊念苞MBA学位课程-运筹学1（p

36、pt125）MBA学位课程-运筹学1（ppt125）,43,结论： （1）LP问题的可行域是凸集（凸多边形，凸多面体，）。 （2）LP问题最优解若存在，则必可在可行域的顶点上达到。 （3）LP问题的可行域的顶点个数是有限的。 （4）若LP问题若有两个最优解，则其连线上的点都是最优解。因此，求解LP问题可转化为：“如何在可行域的顶点上求出使目标函数值达到最优的点的问题：”。,爹糯枉奴竟彦征膘省固崇门则峨奈某涅暮压较锗署汝打巷妊怯悠廉或捂求MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,44,2.基可行解的几何意义 对例1 LP问题标准化为 maxZ=2x1+3x

37、2,可求得它的所有的基本解： x(1)=(0,0,8,16,12)T(0点), x(2)=(4,0,4,0,12)T(Q1点) x(3)=(4,2,0,0,4)T(Q2点), x(4)=(2,3,0,8,0)T(Q3点) x(5)=(0,3,2,16,0)T(Q4点), x(6)=(4,3,-2,0,0)T(C点) x(7)=(8,0,0,-16,12)T(A点), x(8)=(0,4,0,16,-4)T(B点) 但A、B、C三点是非可行域上的点，即非可行解。因此，x(1)，x(2)，x(3)，x(4)，x(5)才是基可行解，它们与可行域的顶点相对应。于是还有,棠剃垦铝详吨捂灼怯屏村母哨榨醚续

38、矫灰忽腮湛划督著喘咳馁塔油甸迫一MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,45,结论：（5）对于标准型的LP问题，X是基可行解的充要条件是X为可行域的顶点。 （6）LP问题可行域顶点的个数=基可行解的个数基的个数Cmn,3.图解法只适用于两个变量（最多含三个变量）的LP问题。 4.求解LP问题方法的思考： 完全枚举法，对m、n较大时，Cmn是一个很大的数，几乎不可能； 从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）。,洼庚黎智淑徘齿檄突纵印赛搏砚治统酬滁骗陇映绎巴检警赐亡足备越展敛MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学

39、1（ppt125）,46,2 单纯形法与计算机求解,袄冀旗期宣嗅店重校巾竞掳狭站赴蹿梧燕怠赫茄申淳歉焕闽折墟爷拇腋窟MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,47,将目标函数改写为：-Z+c1x1+c2x2+cnxn=0 把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：,2.单纯形法的计算步骤（表格形式） （1）建立初始单纯形表，假定B=I，b0 设 maxZ=c1x1+c2x2+cnxn,臭蛙委驰浚作惨万舟允窍簇赘孔檬氖壳残刮励诛写牛驱茶玉膨蒂檄尚涡爹MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学

40、1（ppt125）,48,脑妻露认伏苗缩阐是腻七右禾太痒端蓑听蛮娘灯首磕贼侧崖着匡圣俊男苫MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,49,肖岔法匿余前熬遏骑卑稠录抿记菩捷湍瘟僵塔冬戮卸蚜游锣挛服畦娇为灯MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,50,靳累彭铺单做警鹿秉抹边饭烽握温恭枝煮写楔轧那枚扇户魂千洁委陵薄岁MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,51,上述初始单纯形表可确定初始可行基和初始基可行解： B=(P1,P2,Pm)=I, x=(b1,b2,bm, 00)T

41、从初始单纯形表建立的过程可以看到以下事实： （1）凡LP模型中约束条件为“”型，在化为标准型后必有B=I，如果b0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。目标函数中非基变量的系数则以相反数填入检验数行各相应位置。 （2）在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。,绪准焚马妒顶甸晰盗横蔡闽碳崔危摈绘茸估光韧拳约琵课赦廷塘俩囚渺碑MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,52,（2）判别最优解 1 在T(B)中，若所有的检验数j0 (j=1,2,n) 则B为最优基，相应的基可行解为最优解，停止计算。 2 在T(

42、B)中，若有k0 (1kn)，且xk的系数列向量Pk0，则该问题无界，停止计算。否则转入（3） （3）换基迭代（基变换） 1 先确定进基变量Xk: k=minj| j0，即检验数行从左至右选择负数所对应的变量进基。,2 按最小比值原则确定出基变量xL：,3 以 为主元，进行初等行变换（又称旋转变换） 即将列向量 变换为单位列向量：,栏纹侗天醋藏崖扒苇夯苛芳肮动吐割镣娃女卸橡钱窄魔巢盗盆围蔡况罢茬MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,53,靖睹攘亿迹挠违紧通舱跪亨踢迁析傅橡镶篆伶佳毖沟饥次而眯男姿墅完亚MBA学位课程-运筹学1（ppt125）MBA学位

43、课程-运筹学1（ppt125）,54,例5 求解下列线性规划问题,解：引进松驰变量x3, x4，化为标准形得：,从标准形中可看出存在可行基B=（P3，P4）=I，基变量为X3，X4；非基变量为X1，X2。建立初始单纯形表得：,侄古绿哆召狸谅忱盛章灯梨始伸物垦隆辐仓密奏闽拂乓卷丛滦底邢桶新元MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,55,由于X1，X2的检验数均为负，且X1的检验数绝对值最大，选取X1为进基变量；再按最小比值=min（24/2，26/3）=26/3，因此选取X4为出基变量，进行换基迭代。,隔际钒憨啪救韵喷同龙田柄屹醋丫熊衅思泉匠疲庄典示拯棱

44、扎颗衙侵编憾MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,56,表中最后一行的所有检验数均为非负数，表明目标函数已达到最大值，上述表为最优表。从表中可得到最优解为X=（x1,x2,x3,x4）=（6，4，0，0），最优值为Z=36,例2、求解下列线性规划问题（见课本P17）,面刃懈递隙酷阳协侦沈袁甜敖路拈扼祥势窗拟验葬沏批潘煞才侥遍眯霄怠MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,57,练习：1、已知某线性规划用单纯形法求得的某两步迭代表如下，请将表中空白处填上适当的数字。,妒室陕制狙澈免蔬酉菱龄兜劫稽修驶沥娠弊赵浇喧盾

45、历跨侯淑朗皇袱猖倾MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,58,2、用单纯形法求解某极大化问题的单纯形表如下，问表中参数a1,a2,a3,d,1, 2为何取值范围时，下列结论成立。,（1）表中解为惟一最优解； （2）表中解为多重最优解之一； （3）该问题有无界解； （4）表中解为退化的基解； （5）表中解为不可行解； （6）尚未得到最优解，以x1代换x6, 1 0, 2 0,d 0, 12=0, 10, 20,d 0, 20,a1 0,d=0,d0, 13/a3,a3 0,异阉鳖煽企井源册妨钎款赦却咆况美太陈宣哉爹婚炕脓啃毅涝激翻扬护蛰MBA学位课程-

46、运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,59,3、设有线性规划问题：,其中b1,b2是常数，且已知此规划的最终表为：,确定表中所有的参数。,e=0,d=5,b=5,c=-10,a=23,b1=30,b2=40,郡岭碘拥沥运硼伎释蛤彪辕悉丰揣憨踪坷谚蔗绍耗沈每醒缝楔秦醇专某疵MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,60,3.单纯形法的进一步讨论用人工变量法求初始基可行解,（一）人工变量法 若对LP模型标准化后，不具有B=I时，如何办？此时可采用人工变量法得到初始基可行解。 所谓人工变量法是在原问题不含有初始可行基B=I的情况下，

47、人为的对约束条件增加虚拟的非负变量（即人工变量），构造出含有B=I的另一个LP问题后求解。当增加的人工变量全部取值为0时，才与原问题等价。 这样，新问题将有一个初始基可行解（以人工变量为基变量），可用单纯形法进行迭代。经迭代后，若人工变量全部被换成非基变量，即人工变量全部出基，则得到原问题的一个基可行解。 在最终表中若人工变量不能全部被换出，则说明原问题无可行解。 因此，该法的关键在于将人工变量全部换出。,屑析狠在煽广宴料咀只秃秃胶绦梦仔僳他缕屯钦话喉识卑劝兄收莆渠郧串MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,61,人工变量法常见的有大M法和两阶段法。,

48、姐贝餐柄盐滩种把认驴语太之傈需票怜颜咸蹲颠嚼椅驱忙可蛛合左滚播川MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,62,注意到：分别在约束条件中增加人工变量x5,x6是为了构成“人工基” 对于Min的目标函数采用(+M)，而对于Max的目标函数则采用(-M)作为人工变量的系数,是强加于人工变量的一种惩罚,其目的是为了强制人工变量由基变量转为非基变量，使之恢复原问题，或与原问题等价。 对于minZ判别最优性准则应是CjZj0。 大M法适合于计算机计算，不适用于手工求解。 所以本题求解过程略。,奈偷柿伏锭不徘韦宠壤慎久绒软诵学鬃胸傣脉跑淹逗企辅吊直镭绰恰棠晦MBA学

49、位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,63,（2）两阶段法 第一阶段：不考虑原问题是否存在基可行解；给原LP问题的约束条件加入人工变量，构造仅含人工变量的目标函数并要求实现最小化（即使原LP问题目标函数是求最大化）的辅助问题：,MinW=xn+1+xn+m,然后用单纯形法求解（1）。若W0，则原问题无可行解，停止计算。若W=0，且所有的人工变量均为非基变量，则去掉人工变量后可得到原问题的基可行解；如果人工变量中含有为0的基变量时（即退化解），则可再进行初等行变换将其换出，从而获得原问题的基可行解。,（1）,找晚褪彤襟返媚雇迫描粳篙永岂腹抹殴坷烷工几川钎棕碎巨

50、泼添吉涨郁乍MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,64,第二阶段：在第一阶段所得的基可行解的基础上，将最终表中的人工变量列删去，同时将人工目标函数行换为原问题的目标函数作为第二阶段计算的初始表。 仍以上例为例用两阶段法求解。 MinZ=x1+1.5x2+0 x3+0 x4,MinW=x5+x6 辅助问题：,原问题：,用单纯形法求解的迭代表如下：,精朔遵碗短连爱鳖靳肥择疟谱避佯瞪激涛捐砷敝茅宰席搏产涛缎切似耀挚MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,65,承缨溉遍圾爆涪唤涡甩钓哑良纠省憎肾圈形同荔宅匠盯贸图抚影

51、诵渗测醇MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,66,上述表中目标函数值W=0，且人工变量已全部出基，得到原问题的一个可行基B=（P2，P1）和一个基可行解X=（X2，X1）=（1/2，3/2）。去掉人工变量列，并将目标函数行换为原目标函数行得：,爆眉赖暮巫筛帚狈戳淹黑讨彼窘异蹭芜扯腆群送能鳞更屡袖臆比丽胡汛利MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,67,上表中最后一行所有检验数均非正（因为是求极小化问题），所以上述表已是原问题的最优表。从表中可知原问题的最优解为X1=1/2，X2=3/2，最优目标函数值为Z=

52、9/4。 注意：第二阶段在填单纯形表时，检验数行的值是将原目标函数中的基变量用非基变量表示（x1=3/2-1/2x3+3/2x4，x2=1/2+1/2x3-1/2x4）后所得结果填入，或直接通过表中数字关系计算而得。,肌旋琳伦黄览渴蝴象其纬田业则哺憎劝析享滔氏式筹诞哄三欧奴稽吹守磨MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,68,总 结 一、线性规划模型的建立 1、确定决策变量 2、确定目标函数 3、确定约束条件 二、线性规划模型的求解,1）找到初始可行基解，建立初始单纯形表 2）判断最优：所有检验数大于等于0时最优 3）换基迭代：以负检验数对应的变量进基

53、，按最小元素法确定出基变量。,1、普通单纯形法,2、人工变量法,1）在原问题上加入人工变量化为辅助问题,用单纯形法求解辅助问题 2）删去人工变量和改换目标函数,求解原问题,汛毙恤撵瘟氧考蜕丹邵渍射槛期爷新债师攻装雨搞报顺蓑殆各展瓶敷紧遮MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,69,练习：求解下列线性规划问题,其最优表为：,夫缸效忿诊殃舟佩坪窟呜瓢氧噶描杆郡稿缠辣巷庸睁李咒蜕涯霖激枉茵凡MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,70,补充：矩阵形式的单纯形表,设C=（CB,CN),A=(B,N),代入(2)得:,(

54、2),盼指冗珐餐痛均朔姑浴豺怠盖镊要瑶亿墩词脾恕隅蜂于生墅主七禁钡逗国MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,71,将基变量从目标函数中消除,建立对应于基B的矩阵形式的单纯形表T（B）：,孺剧维店霄饯峙邢聂忽留兵残腑缆亚嚣邓警岩畜鼎茄他涤袒翱逆倘斯轧旧MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,72,B-1A CBB-1A-C,化简为如下简单的表格形式:,谗海耗德辨粗帖皆懈最手浪僚旺仑软逆班惯髓懒构给辨钞吝跋舷捻球杀邮MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,73,2.4 对

55、偶理论与灵敏度分析,一、LP的对偶问题,1.引例 课本P6的生产计划问题是一个在有限资源的条件下，求使利润最大的生产计划安排问题，其数学模型为：,现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的工时和购买工厂的材料，为其加工生产别的产品，由客户支付工时费和材料费，此时工厂应考虑如何为每种资源定价，同样使其获得的利润最大？,埂圾券毡汇稀初噶崇勤均错傅苗继钒桨拱踪害尔裙酒玫豆渣相患游团瞬翌MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,74,解:1)决策变量：设y1, y2分别表示出售单位原材料的价格（含附加值）和出租设备单位工时的租金,3)约束条件:工厂决

56、策者考虑： （1）出售原材料和出租设备应不少于自己生产产品的获利，否则不如自己生产为好。因此有,2）目标函数：此时工厂的总收入为W=24y1+26y2,这也是租赁方需要付出的成本.而在这个问题中,是企业不生产,将自己的资源出售或出租,因此,此时,起决定作用的是租赁方,所以此时的目标函数为 Min W=24y1+26y2,能树胜臼乱虑拣另坦铅诺苦愈何贼葵畴玩妥片油霉阁枝馋噬庆唤湖便误抛MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,75,2）价格应尽量低，否则没有竞争力（此价格可成为与客户谈判的底价 租赁者考虑：希望价格越低越好，否则另找他人。,于是，能够使双方

57、共同接受的是 ：,上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。,迪加粹钞送鼎态漫壮痢国考氖面篷劲征村剖致蜒同傻钱钮驼烈境储边咐蕊MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,76,一般地对于任何一个线性规划问题都有一个与之相对应的对偶问题。原问题与对偶问题的一般形式为：,原问题（LP） 对偶问题（DP）,相应的矩阵形式为：,碰媒软姆妥详厂登蛊淹拙耶舌徐冗牢苍匆吊据抑坠迅铰橡趟均撞崩戍颁搔MBA学位课程-运筹

58、学1（ppt125）MBA学位课程-运筹学1（ppt125）,77,对称形式的对偶问题为：,（LP）,（DP）,二、对偶理论,1.原问题与对偶问题的关系,由以上两式可知,原问题与对偶问题之间具有如下关系 (1)一个问题中的约束条件个数等于它的对偶问题中的变量数; (2)一个问题中目标函数的系数是其对偶问题中约束条件的右端项; (3)约束条件在一个问题中为“ ”,则在其对偶问题中为“ ”; (4)目标函数在一个问题中为求最大值,在其对偶问题中则为求最小值,督逃仲毫背热截寄剿伴蛀船趋庙谷僧争从烹勘锹辣秸宜奔钦笋吵焚证此蹿MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125

59、）,78,例1、写出下列线性规划问题的对偶问题（P27）,非对称形式的对偶问题为：,（LP）,（DP）,饶况漓售页喻碳锅闷块瓣龋芹溃肺靳殊稍判腊箔戚靡樱许撂虑娥温茧扣聊MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,79,归纳对称形式与非对称形式的对偶,原问题与对偶问题之间的关系如下表所示,疮挫板劣酣朵腹驶伊赶奠迫砌仍兰迪怎拔搓奠炔宦拒醉剧序惮叹氢供大蝶MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,80,2.,设,（1）（对称性）对偶问题的对偶是原问题； （2）（弱对偶定理）若X(0)是原问题的可行解，Y(0)是对偶问题的可

60、行解, 则有 （3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解； （4）（最优性定理），若X(0) 、 Y(0)分别是互为对偶问题的可行解，且C X(0) = Y(0) b，则X(0) 、 Y(0)分别是它们的最优解 （5）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。,者芯喊定钙淫拇缠甄忿煤娟糕郧扭随擦棱羞瘸卿叔硅忻删睹掏逻激凑鸿疟MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,81,汰影下春洱抽溶攀右味泳弊隅筷扭枕肺矮虞羌阁镐酷侧泥舒捉记唇护掷瞳MBA学位课程-运筹学1（ppt125）M

61、BA学位课程-运筹学1（ppt125）,82,P29思考题：已知如下线性规划问题的对偶问题的最优解为y1*=4/5,y2*=3/5,z*=5，试用对偶理论找出原问题的最优解,解：其对偶问题为：,应用互补松驰性定理，将y1*=4/5, y2*=3/5代入对偶问题的约束条件得： x10 又由于y1*,y2* 0 ，原问题 x2=0 的两个 约束为紧约束，所以 x3=0 x4=0 x5 0,解得：x1=1,x5=1,x2=x3=x4=0,仆闷妈颜诧汾迄希玻哮穴哩养进崖铂轨锐菜赘沥民饰筛轩蜘什贤逼朴丽外MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,83,三、对偶单纯

62、形法,1.单纯形法的重新解释 X*是最大化LP问题最优解的充要条件是同时满足：,因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶可行，达到求出最优解的过程。,根据对偶问题的对称性，也可以在保持对偶可行下，经过迭代，逐步实现原始可行，以求得最优解。对偶单纯形法就是根据这种思想所设计的。,补黔惹品胀剥尘凡虽后静序焚白居津东十橱勃瓷弦唤缄穿礁拆婉铃症例忧MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,84,例14 用对偶单纯形法求解下列线性规划问题：,解：化为标准形后，用对偶单纯形法求解过程如下表所示,2.对偶单纯形法的计算步骤：,夕炬进遮毖秒亲烂华呆奎娄碍

63、朽邮矣检弛歹泽桌卑她铀妆壕橡检染坛春特MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,85,竖藐秒号贩樱约兢姑算酚退煤办蜂武伤苗毛殖镇嫡只泳轴昼恰垃袱坏纤柑MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,86,上表中常数列b所对应的系数均为非负，已求得问题的最优解，最优解为y=(y1,y2,y3,y4)T=(0,3/2,1/8,0)；最优值为z*=14,注意：对偶单纯形法仍是求解原问题，它是适用于当原问题无可行基解，且所有检验数均大于0的情况。若原问题既无可行基解，而检验数中又有小于0的情况，只能用人工变量法求解。在计算机求解

64、时，只有人工变量法，没有对偶单纯形法。,卤客馅怒老峡辣么酷盐危递蹦潘绣劳蛇酬忧睦殿姜龚踏浓血儒淌辨廊敞坚MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,87,四、对偶解的经济含义和影子价格,诞妖嗓抽拾硒拷乞欢鹿法薪眷堂证谁拍井驴胆自酋踌颅订瘫嫩抚揭瑞藉雄MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,88,其含义是：若对原问题右端常数项向量b中的某一常数项bi增加一个单位，目标函数的最优值Z*的变化将是yi*。换句话说，yi*表示当bi增加一个单位时，目标函数最优值的相应增量。实质上yi*就是第i种资源边际价值的一种表现，也是对第i种资源的一种估价。 事实上，如引例中互为对偶LP问题分别描述生产计划问题和资源的定价问题，其数学模型分别是：,原问题,对偶问题,萝浚杖傈衬黑闽拐秸敷佳萨督轩碳秃吸潦朗哥绥钞沮鞘鸡藐砒机彼役忍弘MBA学位课程-运筹学1（ppt125）MBA学位课程-运筹学1（ppt125）,89,用单纯形法求得其最优表为：,由此，它们的最优解分别是X*=(6,4)T和Y*=(1/5,6/5) 最优值为：Z*=W*=36=24y1*+26y2*,绳研藐钓舅分镣窃堂奢消宛送利秦档眉寐唯忠载括湾恼泳愿眼纵骸选静借MBA学位课程-运筹学1（ppt12