运筹学（广东外语外贸大学）.docx

《运筹学（广东外语外贸大学）.docx》由会员分享，可在线阅读，更多相关《运筹学（广东外语外贸大学）.docx（310页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、现代管理科学的重要基础和手段经济和管理的重要工具具有适用性强,应用面广的特点广东外语外贸大学Guangdong University of Foreign Studies课程目的我们学习这门课程的目的是要树立优化思想,认识运筹学对实现管理的科学 化和现代化的重要意义和作用,掌握运筹学的基本思想和方法,并能结合相关软 件的使用解决管理中的实际问题。运筹学主导教材和主要参考书主导教材:管理运筹学（第2版）,韩伯棠编著,高等教育出版社。主要参考书:ll.运筹学（修订版）,钱颂迪主编,清华大学出版社;2 .数据模型与决策（第11版）,David R. Anderson, etc.,侯文华等译，机 械工

2、业出版社;3 .运筹学教程,胡运权主编,清华大学出版社4 .运筹学模型与方法教程,程理民等,清华大学出版社;5 .运筹学应用案例集，胡运权主编,清华大学出版社;6 .运筹学模型与方法教程例题分析与解题，刘满凤等,清华大学出版社;7 .运筹学方法及其微机实现,汪遐昌,电子科技大学出版社。主要参考期刊及网站运筹与管理,中国运筹学会运筹学学报，中国运筹学会系统工程理论与实践,中国系统工程学会系统工程，湖北省系统工程学会中国运筹学会运筹学网络资源导航Operations ResearchEuropean Journal of Operational Researchhttp:/Jib.pku.edu/

3、is/Navigation/Mathematics /operations.htmhttp:/.ors43x/a/第一章绪论1决策、定量分析与管理运筹学2运筹学的分支3运筹学在工商管理中的应用4学习运筹学必须使用相应的计算机软件,必须注重于学以致用的原则第一章绪论“运筹学”的释义运筹学（Operational Research（英式）；Operations Research（美式）直译为 “运作研究”、“作业研究”或“运用研究”,简称0R。中文“运筹”二字取自史记?高祖本记中,刘邦“夫运筹帷幄之中， 决胜于千里之外,吾不如子房”。运筹学是门决策科学,优化科学。第一章绪论我国古代运筹思想运用的典

4、故1 .“田忌赛马”“田忌赛马”是家喻户晓的历史故事。战国时齐威王与齐相田忌赛马, 双方各出三匹马比赛,每胜场赢得一千金。由于王府的马比相府的马好,所以 田忌每次比赛都要输掉三千金。后来田忌的谋士孙膑献了一计:在每次开赛前要求对方先报马名,由此 区分对方参赛的是上马、中马还是下马;然后以自己的上马对对方的中马、自己 的中马对对方和下马、自己的下马对对方的上马。这样,两胜负反而赢得一千 金。第一章绪论我国古代运筹思想运用的典故2 .晋国公重建皇城晋国公重建皇城的施工方案,体现了运筹学的朴素思想。要使重建工程的各个序,在时间、空间上彼此协调,环环相扣,就需要运用行列 式的相关知识,进行精确计算.点

5、击图连接相关网页第一章绪论运筹学的产生和发展运筹学作为门系统的科学,产生的背景为第二次世界大战。主要用于解决 如何在与德军的对抗中最大限度地杀伤敌人,减少损失。二战期间英国为解决空袭的早期预警,作好反侵略战争准备,积极进行雷 达”的研究。但随着雷达性能的改善和配置数量的增多,出现了来自不同雷达站 的信息以及雷达站同整个作战系统的协调配合问题。第一章绪论1938年7月,波得塞(Bawdsey)雷达站的负责人罗伊(A.P.Rowe)提出立 即进行整个防空作战系统运行的研究,并用“Operational Research词作为 这方面研究的描述,这就是OR名词的起源。1940年9月英国成立了由物理学

6、家布莱克特(P.M.S. Blackett)领导的第一 个运筹学小组，后来发展到每个英军指挥部都成立运筹学小组。1942年美国和加拿大也都相继成立运筹学小组。这些小组在确定扩建舰队 规模、开展反潜艇战侦察和组织有效对敌轰炸等方面作了大量研究,为取得反法 西斯战争的胜利及运筹学有关分支的建立作出了贡献。第一章绪论运筹学在第二次世界大战中成功运用的例子:如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员 的编组、军事物资的存储等。典型战例:1 .不列颠之战2 .盟军封锁直布罗陀海峡第一章绪论不列颠之战1941年,希特勒为了实施在英伦三岛登陆的计划,命令德国空军轮番 对英国进行狂轰滥炸。

7、当时英国皇家空军以比七的数量劣势迎战,为此需要尽 可能地保持飞机处于飞行状态。于是,空军司令部规定保持70%的飞机在天上巡 逻。但是,英军很快发现要保持这么高的飞行比例有困难,因为飞机的被击落的、 有需要维修的,飞行员也有伤亡。这决策的后果是在空中飞行的飞机数量越来 越少。第一章绪论不列颠之战究竟保持多大比例的飞机在巡逻才能持久作战呢? OR小组的专家纷纷 研究这个问题,这个问题最后被生物学家康顿解决了。他根据计算生物平均寿命 的方法,运用飞机飞行时间、维修时间、空战特点和飞机被落击伤状况等数据, 得出的结论是:只要保持35%的飞机在飞行状态,就能使全部飞机的飞行战斗时 间最多。这研究成果为取

8、得不列颠之战的胜利作出了贡献。盟军封锁直布罗陀海峡（猎潜战例）1944年初,为帮助美国海军在连接大西洋和地中海的直布罗陀海峡封 锁过往的德军潜艇,美军OR小组的约翰佩芝姆博士提出了一种“屏障巡逻” 飞行战术。第一章绪论盟军封锁直布罗陀海峡（猎潜战例）在深水航道的最窄处划出个4英里长、1英里宽的长方形,两架飞机 保持在长方形两边线的对称位置上，同时以115英里/小时的速度绕长方形飞行。 这样,在长方形上的每一点,每隔3分钟就有架飞机巡逻通过。潜艇通过这个区域时, 巡逻的飞机至少有两次机会去发现它。就这样,在2月24日到3月16日短短三 个星期内,个巡逻机中队击沉击伤德军潜艇3艘,自己无一伤亡。第

9、一章绪论第一章绪论二战以后,运筹学得到了快速的发展,形成了许多分支,并且计算 机的应用极大地推动了运筹学的应用与普及。运筹学有广泛应用运筹学不仅在军事上,而且在生产、决策、运输、存储等经济管理领 域有着广泛的应用。第一章绪论运筹学的定义运筹学是运用分析，试验,量化的方法,对经济管理系统中人、财、物（时 间）等有限资源,进行统筹安排,为决策者提供有依据的最优方案（满意方案）， 以实现最有效地管理。中国企业管理百科全书辞海对运筹学解释为:“二十世纪四十年代开始形成的一门科学，主要 研究经济活动与军事活动中能用数量来表达的有关运用,筹划与管理方面的问 题,它根据问题的要求,通过数学的分析与运算，作出

10、综合性的合理的安排,以 达到较经济、较有效地使用人、物力。近年来,它在理论与应用方面都有较大 发展。其主要分支有规划论、对策论、排队论及质量控制等。”第一章绪论运筹学的特点科学性:运筹学是以研究事物内在规律,并从定量分析的角度探求更好 地解决问题的门科学。第一章绪论运筹学的特点应用性:运筹学既对各种经营进行创造性的科学研究,又涉及到组织的 实际管理问题,它具有很强的实践性，最终应能向决策者提供建设性意见,并应 收到实效;第一章绪论运筹学的特点多学科的交叉性、综合性:运筹学研究中吸收了来自不同领域的经验, 并被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题, 故其应用不受行业、

11、部门之限制;第一章绪论运筹学的特点系统性和最优性:它以整体最优为目标,从系统的观点出发,力图以整个系 统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解, 寻求最佳的行动方案,所以它也可看成是门优化技术,提供的是解决各类问题的 优化方法。 1.1 策、定量分析与管理运筹学决策的定义现代管理科学创始人,诺贝尔奖金获得者世界著名经济学家西蒙 （H.A.Simon）：管理就是决策。原中国社会科学院副院长于光远:决策就是作决定。为了实现一定目标,运用科学的理论和方法,系统地分析主、客观条件, 在掌握大量有关信息的基础上,提出若干预选方案并从中选择出最优方案（满意 方案）的分析判断过

12、程（科学的决策）。1.1 1.1决策、定量分析与管理运筹学决策方法定性分析方法借助决策者的知识、经验、分析和判断能力等进行决策的 方法。定量分析方法量化决策问题并建立数学模型进行决策的方法。定性与定量相结合的分析方法学习运筹学能够培养和提高定量分析能力解决问题与制定决策明确问题确定目标提出方案分析方案选择方案实施方案分析结果解决问题决策决策结果评估各个方案:解的检验、灵敏性分析等。确定目标或评估方案的标准执行此方案:回到实践中进行后评估：考察问题是否得到圆满解决.不满意检查1.2 运筹学的分支线性规划整数（线性）规划目标规划图与网络模型排序与统筹方法存储论决策分析排队论对策论动态规划预测非线性

13、规划、多目标规划、随机规划、模糊规划等1.3 运筹学在工商管理中的应用生产计划:生产作业的计划、日程表的编排、合理下料、配料问题、物料 管理等;库存管理:多种物资库存量的管理,库存方式、库存量等;运输问题:确定最小成本的运输线路、物资的调拨、运输工具的调度以及 建厂地址的选择等;人事管理:对人员的需求和使用的预测,确定人员编制、人员合理分配,建 立人评价体系等;1.4 运筹学在工商管理中的应用市场营销:广告预算、媒介选择、定价、产品开发与销售计划制定等； 财务和会计:预测、贷款、成本分析、定价、证券管理、现金管理等;*设备维修、更新,项目选择、评价,工程优化设计与管理等;1.3运筹学在工商管理

14、中的应用由国际运筹与管理科学协会(INFORMS)和它的管理科学实践学会(College for the Practice of the Management Sciences)主持评奖的负有盛名的弗兰茨厄 德曼(Frany Edlman)奖,就是为奖励优秀的运筹学在管理中的应用的成就设立 的,该奖每年举行次,在对大量富有竞争力的入闱者进行艰苦的评审后,一般 有六位优胜者获奖。关于这些获奖项目的文章都在第二年发表在著名刊物 Interface的第一期上,下面列表就是发表在Interface期刊的些获奖项目。更优的服务11993安装统计销售预测和成品库存管理系统,改进客户服务Merit青铜制品公

15、司第一年7.5亿1-2/2000重组全球供应链,保持最小库存的同时满足客户需求IBM1亿1-M994进行上千个国内航线的飞机优化配置来最大化利润Delta航空公司1500万更多年收入101998制定最优铁路时刻表并调整铁路日运营量法国国家铁路2亿1-M997重新设计北美生产和分销系统以降低成本并加快了市场进入速度 宝洁公司生产率提高50%以上11/1975第二部分通过战略调整,缩短维修机器的反应时间,改进维修人员的生产率 施乐公司380万17/1981控制成品库存（制定最优再订购点和订购量,确保安全库存）标准品牌公司4.06亿,更多销售11990优化商业用户的电话销售中心选址AT&T4

16、000 万121987优化商业区和办公楼销售程序荷马特发展公司7000 万1-7/1987优化炼油程序及产品供应、配送及营销Citgo石油600万1-y1986满足乘客需求前提下,以最低成本进行订票及安排机场工作班次 联合航空公司每年节支（美元）Interface应用组织运筹学方法使用情况（美1983）运筹学方法在中国使用情况（随机抽样）运筹学的发展趋势面向问题服务行业中的应用金融服务业信息、电信服务业医院管理后勤（Logistics）全球供应链管理电子商务:集成特性1.3运筹学在工商管理中的应用运筹学的发展趋势运筹学与行为科学结合群决策和谈判对策理论多层规划合理性分析随机和模糊OR问题本身的

17、不确定性人类知识的局限性1.3运筹学在工商管理中的应用运筹学的发展趋势软计算面向强复杂系统的计算、实时控制、知识推理智能算法:模拟退火、遗传算法、人工神经网络、戒律算法等系统仿真IT对运筹学的影响MIS, DSS, MRP-II, CIMS, ERPOR Dept. -> Dept. Of OR & IS1.3运筹学在工商管理中的应用1.4学习管理运筹学必须使用相应的计算机软件,必须注重于学以致用的 原则学习运筹学要结合实际的应用,不要被些概念、理论的困难吓倒。学习运筹学要把注意力放在“结合实际问题建立运筹学模型”和“解决问题 的方案或模型的解”两头,中间的计算过程尽可能让计算机

18、软件去完成。本书附有运筹学教学软件,使用方法很简单。学员必须尽快学会使用这个运 筹学教学软件,并借助它来学好本课程。学习运筹学是为了用于实践,解决实际 问题。以前重视人工计算是因为没有计算机,现在有了就应该好好利用。谢谢大家第一章绪论广东外语外贸大学Guangdong University of Foreign Studies 2.1 的提出 2.2 解法 2.3 解法的灵敏度分析第二章线性规划的图解法 第二章线性规划的图解法 解决以下两类问题资源一定产出最大（产出:如产量、销售量、利润等）任务一定投入最小（投入:如资金、人员、时间、原材料等）线性规划（Linear program, LP）在

19、工商管理,生产计划安排,交通运输,财贸工作等各项经济活动 中，如何应用科学的方法统筹安排，合理利用资源（包括人力、物力、财力等资 源）,并使其经济效益达到最优,这些正是现代社会生产规模日益扩大以及各部 门和各系统之间的关系日益复杂所面临的新问题。1939年前苏联数学家康托洛 维奇提出了生产组织与计划中的线性规划（Linear Programming简写为:LP）模 型，为以上问题的解决提出了一种可行的方法。四十年代末旦茨基和查恩斯等人 提出的线性规划问题求解方法一单纯形法,为线性规划的理论和应用奠定了基 础,这些都是线性规划的最卓著的开创性工作。2.1线性规划问题的提出线性规划是研究在线性不等

20、式或等式的限制条件下,使得某个线 性目标函数取得最大（或最小）的问题。常见的线性规划问题有：（）运输问题（二）生产的组织与计划问题（三）合理下料问题（四）配料问题（五）布局问题（六）分派问题线性规划研究的内容和问题2.1线性规划问题的提出线性规划与其它现代技术或方法相结合产生新的定量分析的技术 已成为当前出现的个极为重要的发展趋势。特别是随着计算机的出现,线性规 划与计算机结合形成的应用软件已成为了流行的“商业工具”。据美国商业和科 学计算中心的研究可知,线性规划的计算机应用软件已获得了数十亿的经济效 益,有很高的市场价值。预计在下个十年里,线性规划与计算机的分界线将会 逐渐消失，并将脱离各自

21、原来的领域,组合成更通用和应用面更广泛的应用科学 的形式。线性规划发展前景 2.1线性规划问题的提出另一方面,以线性规划为基础而发展起来的多部门的线性规划,多 时期的线性规划,模糊线性规划,随机线性规划,以及整数规划,非线性规划, 目标规划等等,为现代管理中各类实际问题的解决提供了科学的方法。目前线性 规划的理论研究仍十分活跃,其应用前景也越来越广阔,它已成为国家重点推广 的现代管理方法之。线性规划发展前景2.1线性规划问题的提出例1.某工厂在计划期内要安排I、II两种产品的生产,已知生产单位产品 所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表:问题:厂应分别生产多少单位I、II产

22、品才能使工厂获利最多?问题分析:如何安排I、II两种产品的生产使得厂获利最大?设定决策变量:设I、II产品的产量分别为xl,x2目标:获利最大的利润制约条件：生产能力和原材料的供给量例1.某工厂在计划期内要安排I、II两种产品的生产，已知生产单位产品 所需的设备台时及A、B两种原材料的消耗、资源的限制,如下表:问题:厂应分别生产多少单位i、n产品才能使工厂获利最多?线性规划模型（I、H产品的产量分别为xl,x2）：目标函数:Max z = 50xl + 100x2约束条件:s.t.xl+ x2 W 3002x1+ x2 400x2 250xl , x2 三 0LP模型三要素决策变量约束条件（线

23、性等式或线性不等式）目标函数（线性函数,最大化或最小化）2.1线性规划问题的提出生产组织与决策问题例2.某汽车厂可生产大轿车和载重汽车,已知生产每辆汽车所用的钢材 均为2吨,该厂每年供应的钢材为1600吨,生产能力为每2.5小时生产辆载 重汽车,每5小时生产辆大汽车,工厂全年有效工时为2500小时;已知供应 给该厂大轿车用的座椅每年可装配400辆。据市场调查,出售辆大轿车可获利 4千元,出售辆载重车可获利3千元。问在这些条件下,如何安排生产使得 厂获利最大?2.1线性规划问题的提出分析：问题是如何安排生产使得厂获利最大?设大轿车和载重车的产量分别为xl和x2 （辆）,则34利润（千元?辆）（吨

24、?辆）2.5（小时?辆）载重车1600（吨）2500（小时?年）提供量4002（吨?辆）5（小时?辆）大轿车装配座椅（辆?年）钢材生产能力项目产品解:原材料的限制:工时的限制:大轿车座椅的限制:非负限制:分析：问题是如何安排生产使得厂获利最大?3利润（千元?辆）22.5（小时?辆）载重车16002500（小时?年）提供量40025（小时?辆）大轿车装配座椅（辆?年）钢材（吨）生产能力项目产品目标:利润最大因此该问题的数学模型为:目标函数约束条件2.1线性规划问题的提出 实际问题LP模型最优解2.1 线性规划问题的提出建模过程1 .理解要解决的问题,了解解题的目标和条件;2 .定义决策变量（xl

25、 , x2，xn ）,每组值表示-个方案;3 .用决策变量的线性函数形式写出目标函数,确定最大化或最小化目标;4 .用组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条 件一般形式目标函数:Max （Min） z = cl xl + c2 x2 + + cn xn约束条件:s.t. all xl + al2 x2 + + aln xn （ =, 2 ） bla21 xl + a22 x2 + + a2n xn （2 ） b2ami xl + am2 x2 + , + amn xn W (2 ) bmxl , x2 , , xn 2 0 2.1 线性规划问题的提出 2.2 2.2图解法例

26、1.目标函数：Max z = 50x1 + 100x2约束条件：xl + x2 W 300 (A)2x1 + x2 400 (B)x2 . 250 (xl 2 0(D)(E)x2 2 0得到最优解:xl = 50, x2 = 250最优目标值z = 27500对于只有两个决策变量的线性规划问题,可以在平面直角坐标系上 作图表示线性规划问题的有关概念,并求解。下面通过例1详细讲解其方法:100元50元单位产品获利250千克10原料B400千克12原料A300台时11设备资源限制III 2.2图解法(1)分别取决策变量XI , X2为坐标向量建立直角坐标系。在直角坐标系里, 图上任意一点的坐标代表

27、了决策变量的组值,例1的每个约束条件都代表个 半平面。x2xlX220X2=0x2xlXlOX1=O2.2图解法（2）对每个不等式（约束条件）,先取其等式在坐标系中作直线,然后确定 不等式所决定的半平面。100200300100200300xl+x2300xl+x2=3001001002002xl+x24002xl+x2=400300200300400 2.2图解法（3）把五个图合并成一个图,取各约束条件的公共部分,如图2-1所示。100x2 250x2=250200300200300xlx2x2=0xl=0x2=250xl+x2=3002xl+x2=400图2-1(4)目标函数z=50xl+

28、100x2,当z取某固定值时得到一条直线,直线上 的每一点都具有相同的目标函数值,称之为“等值线”。平行移动等值线,当移 动到B点时,z在可行域内实现了最大化。A,B,C,D,E是可行域的顶点,对有限 个约束条件则其可行域的顶点也是有限的。xlx2z=20000=50xl+100x2图2-2z=27500=50xl+100x22=0=50x1+100x2z=10000=50xl+100x2CBAD图解法的运算步骤0xlx21.1 别以L.P.模型中的两个变量为横轴和竖轴建立平面直角坐标系（例如可 以以例1中的xl为横轴,以x2为竖轴）。1.2 2图解法1.3 2.2图解法例 1. max Z

29、= xl+3x2s.t. xl+ x2 6xl+2x2 8xl 20, x220可行域64-860xlx22.在所建立的平面坐标系中画出约束条件所围成的区域图形可行（解集） 域（the feasible region）,并将其用阴影表示出来。例 1. max Z = xl+3x2s.t. xl+ x2 6xl+2x2 8xl 20, x220可行域640xlx2Z=xl+3x2= 03.画出目标函数的图形（通常可画出当目标函数值为零时的（基准）目标函 数图）,确定目标函数平行移动的方向,并沿目标函数直线的法向用小箭头标出。 2.2图解法4 .将（基准）目标函数直线沿所标示的方向平行移动直至可行

30、域的边界, 若这时目标函数的直线与可行域的边界点或边界线重合,则其重合点或重合线段 上的点即为此L.P.问题的最优解,当重合部分为一点,则该点的坐标即为原L.P.的 唯一解，当重合部分为一条线段时,则该线段上的任一点的坐标即为原L.P.的解, 这时原L.P.问题有无穷多个解;否则,原LP.问题无解。5 2.2图解法- xl+2x2 = 8可行域目标函数等值线最优解64- 860xlx2目标函数基准线 Z=xl+3x2= 0Pxl+ x2 = 6设点P的坐标为（xl,x2）,则可由以下方程解得xl, x2 ：xl+ x2 = 6-xl+2x2 = 8解得:xl =明x2 = 14/3max Z

31、= xl+3x2max Z = xl+3x2最优值为:max Z = xl+3x2 =转+3X 14/3=43-xl+2x2=8可行域目标函数等值线最优解64- 860xlx2目标函数基准线Z=xl+3x2= 0Pxl+ x2 = 6故最优解为:xl =钻,x2 =14/32.2图解法例2.求解L.P.问题:max Z = xl+x2s.t. xl+x2W6xl+2x2W8xl 20, x220解:以xl为横轴,以x2为竖轴建立直角坐标系,并根据题意画图。max Z = xl+x2xl+ x2 = 6可行域目标函数等值线最优解64-860xlx2目标函数基准线Z=xl+x2= 0PQ-xl+2

32、x2 = 8由图可知例2的目标函数在线段PQ上任一点处均取最大值,原问题有无穷 多个最优解。设点P的坐标为(xl, x2),则可解得点P的坐标为(利,1%)。故原问题的一个最优解为:xl =明，x2 = l转其最优值为:max Z = xl+3x2 =* + 1必=6例3. 2.2图解法max Z = xl+x2s.t. 2xl-x222-xl+2x2 8x!20,x220目标函数等值线-810xlx2Z=xl+x2= 0可行域目标函数无上界,无最优解例4. 2.2 解法min Z = xl+x2s.t. 2xl-x222xl+2x2W8xl NO, x20-24-810xlx2Z=xl+x2

33、= 0可行域最优解目标函数等值线2.2图解法重要结论:如果线性规划有最优解,则一定有一个可行域的顶点对应一个最优解;无穷多个最优解。如例3,线段PQ上的所有点都代表了最优解;无界解。即可行域的范围延伸到无穷远,目标函数值可以无穷大或无穷小, 如例4。一般来说,在实际问题中,这说明模型有错,忽略了一些必要的约束条 件;无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x221200,则 可行域为空域,不存在满足约束条件的解,当然也就不存在最优解了。2.2图解法练习.max Z = -xl+2x2s.t. xl3xl-x2 2 0xl 20, x220可行域30xlx2Z= -xl+2x2

34、=0解得P点坐标为:xl=3, x2 =3最优值为:maxZ=3最优解P线性规划模型一般形式目标函数:Max (Min) z = cl xl + c2 x2 + . + cn xn约束条件:s.t. all xl + al2 x2 + + aln xn ( =, 2 ) bla21 xl + a22 x2 + a2n xn W ( =, 2 )ami xl +am2 x2 + , +amn xn （）bmxl , x2 ,xn 2 0标准形式目标函数:Max z = cl xl + c2 x2 + + cn xn约束条件:s.t. all xl + al2 x2 + + aln xn = bl

35、a21 xl + a22 x2 + . + a2n xn = b2 ami xl + am2 x2 + . + amn xn = bmxl , x2 ,xn 2 0, bi 20 2.3图解法的灵敏度分析 2.3图解法的灵敏度分析灵敏度分析:建立数学模型和求得最优解后,研究线性规划的个或多个参 数(系数)ci,aij,bj变化时,对最优解产生的影响。3.1目标函数系数ci的灵敏度分析考虑例1的情况,显然,ci的变化只影响目标函数等值线的斜率。z=0=50x1+100x2目标函数 z = 50 xl + 100 x2 在 z = x2 (x2 = z 斜率为 )到 z = xl + x2 (x2

36、 = -xl + z斜率为1)之间时，原最优解xl = 50, x2 = 250仍是最优解。一般情况:z = clxl + c2x2 写成斜截式:x2= - (cl /c2)xl+ z/c2目标函数等值线的斜率为:-(cl /c2 ),当1? - (cl /c2)?0 (*)时,原最优解仍是最优解。z=0=50xl+100x2 2.3图解法的灵敏度分析假设产品H的利润100元不变,即c2=100,代到式(*)并整理得0? cl ? 100假设产品I的利润50元不变,即cl= 50 ,代到式（*）并整理得50? C2 ? + ?假若产品I、II的利润均改变,则可直接用式（*）来判断。 2.3图解

37、法的灵敏度分析假设产品I、II的利润分别为60元、55元,贝-2 ? -（60/55） ? -1那么,最优解为z = xl + x2和z = 2xl+ x2的交点:xl = 100, x2 = 2002.3图解法的灵敏度分析3.2约束条件中右边系数bj的灵敏度分析当约束条件中右边系数bj变化时,线性规划的可行域也变化,可能引起 最优解的变化。考虑例1的情况:假设设备台时增加10个台时,即bl变化为310,这时可 行域扩大,最优解为x2= 250和xl+x2=310的交点xl=60, x2= 250 xl+x2=310最优解 2.3图解法的灵敏度分析变化后总利润变化前总利润=增加的利润（50 X

38、 60+100 X250）- （50 X 50+100 X 250）= 500500 / 10 = 50 元说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减 少）50元利润,称为该约束条件的对偶价格。 2.3图解法的灵敏度分析假设原料A增加10千克时,即b2变化为410,这时可行域扩大,但最优解仍为x2 = 250和xl +x2 = 300的交点 xl = 50, x2 = 250 2xl+x2=410此变化对总利润无影响,该约束条件的对偶价格为.解释:原最优解没有把原料A用尽,有5千克的剩余，因此增加10千克值增 加了库存,而不会增加利润。z=0=50xl+100x2最优解 2.

39、3图解法的灵敏度分析在一定范围内,当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0I则其最优目标函数值得到改善（变 好）；（2）若约束条件的对偶价格小于0,则其最优目标函数值受到影响（变 坏）；（3）若约束条件的对偶价格等于,则最优目标函数值不变。作业第二章作业:P23. 2. （1）、（2）、（5）； P25. 6. （1）-（4）第三章线性规划问题的计算机求解广东外语外贸大学Guangdong University of Foreign Studies运筹学第三章线性规划问题的计算机求解 1 “管理运筹学”软件的操作方法2 “管理运筹学”软件的输出信息分析第三章线性规划问题

40、的计算机求解随书软件为“管理运筹学” 2.0版（Window版）,是1.0版（DOS版）的升 级版。它包括;线性规划、运输问题、整数规划（0-1整数规划、纯整数规划和混 合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费 用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法,共 15个子模块。1 “管理运筹学”软件的操作方法1.软件使用演示:（演示例1）第一步:点击“开始”->； “程序”->； 管理运筹学2.0”,弹出主窗口.例1.目标函数:Max z=50 xl+100x2约束条件:s.t.xl + x2 300(A)2xl + x2 400(B)

41、x2 250(C)xl 2 0(D)x2 N 0(E)1 “管理运筹学”软件的操作方法第二步：选择所需子模块,点击主窗口中的相应按钮。本题中选用“线性规 划”方法。点击按钮弹出如下界面：例1.目标函数:Max z=50 xl+100x2约束条件：s.t.xl + x2 300(A)2xl + x2W 400(B)x2 250(C)xl 2 0(D)x2 2 0(E)1 “管理运筹学”软件的操作方法第三步:点击“新建”按钮,输入数据。本题中共有2个变量,4个约束条 件,目标函数取MAX。点击“确定”后,在表中输入Cj,bi和aij等值,并确定变 量的正负约束。输入数值后的界面如下。例1.目标函数

42、:Max z=50 xl+100x2约束条件:xl + x2 W 300(A)2xl + x2 400(B)x2 250(C)xl 2 0(D)x2 N 0(E)1 “管理运筹学”软件的操作方法第四步:点击“解决”按钮,得出计算结果。本题的运行结果界面如下。相差值表示相应的决策变量的目标系数需要改进的数量,使得决策变量为正 值,当决策变量已为正数时,相差数为零。例1.目标函数：Maxz=50xl +100x2约束条件：s.t.xl + x2300(A)2xl + x2W400(B)x2 W250(C)xl 20(D)x2 20(E)松弛/剩余变量的数值表示还有多少资源没有被使用。如果为零,则表

43、示与 之相对应的资源已经全部用上。例1.目标函数：Maxz=50xl +100x2约束条件:xl + x2300(A)2xl + x2400(B)x2 250(C)xl NO(D)x2 20(E)对偶价格表示其对应的资源每增加一 个单位,将增加多少个单位的最优值。例1.目标函数:Maxz=50xl +100x2约束条件:s.t.xl + x2300(A)2xl + x2400(B)x2 250(C)xl NO(D)x2 20(E)目标函数系数范围表示最优解不变的情况下,目标函数的决策变量系数的变 化范围.当前值是指当前的最优解中的系数取值.例1.目标函数：Maxz=50xl +100x2约束条件：s.t.xl + x2 300(A)2xl + x2W400(B)x2 250(C)xl 20(D)x2 20(E)常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变化时,与其对应的约束条件的对偶价格不变。当前值是指现 在的取值。例1.目标函数:Maxz=50xl +100x2约束条件:s.t.X1 + X2 300(A)2xl + x2W400(B)x2 250(C)xl 20(D)