运筹学导论第八绪论

演示文稿运筹学导论第八版绪论当前1页，总共41页。运筹学导论第八版绪论ppt课件当前2页，总共41页。3当前3页，总共41页。4当前4页，总共41页。51942年，BarnesWallis巴恩斯·沃利森就设计出了专门用来炸毁混凝土拱形水坝的专用炸弹，起名为“跳跃炸弹”。这种炸弹在水坝上游释放，投放前先在炸弹架上赋予它500转/分的自转速度，炸弹投下后会像小孩玩石头“打水漂”一样，在水面上多次跳跃前进，可以越过水坝前敷设的防弹网。在接触水坝时，炸弹利用自身的旋转，向水坝水线下深入，在水线下炸出大洞。拱形水坝一旦在支撑点上被炸毁，强大的水压将使水坝立即溃决。当前5页，总共41页。6中文：运筹（夫运筹帷幄之中，决胜于千里之外）——《史记•高祖本纪》英文：

OperationalResearch（英国）OperationsResearch（美国）

（直译为“作战研究”或“作业研究”、“运作研究”）当前6页，总共41页。7丁谓的皇宫修复工程运筹学的起源北宋年间，丁谓负责修复焚毁的开封皇宫，他的施工方案是：Step1.先将工程皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。Step2.使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；Step3.修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、生产、运输及废墟物的处理用“一沟三用”巧妙地解决了。当前7页，总共41页。8田忌赛马齐王与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。著名的军事谋略家孙膑如何指导田忌的？齐王： 上 中 下

田忌： 下 上 中

最终净胜一局，赢得1000金。当前8页，总共41页。9北宋科学家、军事家沈括,在率兵抗击西夏征途中利用各兵种背负粮食的基本数据，盘算后勤兵与战士在不同的行军天数中的差异比例关系；盘算了用种种牲口运粮与人力运粮之间的利弊，做出了从敌国就地征粮，保障前线提供的决策。优化后勤职员比例，增强了前线战斗力。这种军事运筹是运筹思想的典范，也是现代军事运筹的核心问题。沈括调整军队构成当前9页，总共41页。10运筹学真正的发展起源于二次大战的一门新兴交叉学科与作战问题相关雷达设置、运输船队护航、反潜战中深水炸弹起爆深度、飞行员编组、军事物资存储等战后在经济、管理和机关学校及科研单位继续研究1948年英国首先成立运筹学会1952年，Morse和Kimball出版《运筹学方法》1952年美国成立运筹学会1959年成立国际运筹学联合会(IFORS)我国于1982年加入IFORS，并于1999年8月组织了第15届大会当前10页，总共41页。11PhilipM.Morse运筹学发展的主要推动者WassilyW.Leontief投入产出法Dantzig,1914-2005单纯形法VonNeumann,MonteCarlo方法JohnForbesNashJr博弈论当前11页，总共41页。12运筹学的内容丰富，分支众多。根据解决问题的主要特征可分两大类：确定型和概率型。其中确定型包含：线性规划，整数规划，动态规划，非线性规划，多目标决策及确定性存贮等；概率型中包含：回归分析，决策论，对策论，排队论，马尔可夫链，图论与网络，概率存贮及搜索技术等。本课将阐述运筹学中最基本的部分——规划论（即线性规划，对偶理论与灵敏度分析、整数规划，网络规划）、排队论运筹学分支及模型类型当前12页，总共41页。13运筹学的研究问题与对象资源最佳利用问题方法：线性规划、整数规划、网络图、动态规划、目标规划等竞争现象如战争、投资、商品竞争方法：对策论（博弈论）拥挤现象如公共汽车排队、打电话、买东西、飞机着陆、船舶进港等方法：排队论当前13页，总共41页。14运筹学的关键在于模型的建立和使用；应用运筹学处理问题时，要从系统观点来分析问题；提出需要解决的问题和希望达到的目标；理清问题所处的环境和约束条件，包括：时间、地点、资金、原材料、设备、人力、能源、动力、信息、技术等；问题中的主要因素、各种环境和约束条件之间的逻辑关系运筹学应用前提当前14页，总共41页。15运筹学的发展趋势运筹学的危机脱离实际应用，陷入数学陷阱IT对运筹学的影响MIS,MRP-II,CIMS,ERPORDept.-->Dept.OfOR&IS运筹学与行为科学结合群决策和谈判、对策理论、多层规划、合理性分析服务行业中的应用金融服务业、信息、电信服务业、医院管理当前15页，总共41页。16研究深水炸弹起爆深度问题。当飞机发现潜艇后，飞机何时投掷炸弹及炸弹的引爆引度是多少？运筹学工作者对大量统计数字进行认真分析后，提出如下决策：仅当潜艇浮出水面或刚下沉时，方投掷深水炸弹。炸弹的起爆深度为离水面25英尺（这是当时深水炸弹所容许的最浅起爆点）。空军采用上述决策后，所击沉潜艇增加5倍。运筹学的研究意义当前16页，总共41页。17纽约消防车辆调度。都市求救电话是一个复杂的分布在不同地点的多个服务台的排队系统，涉及资源的空间配置、警车巡逻线路最优设计、警力配备、电话调度；部署在纽约、圣迭戈、萨克拉门托、达拉斯、波特兰、加拉加斯和鹿特丹。提高生产率10%~15%，特别是极大的降低了响应时间。运筹学的研究意义当前17页，总共41页。18假设有70艘油轮向70个港口运货，已知每艘油轮驶向每个港口的费用，油轮公司需制订出最优运输方案。采用全枚举法（穷举法）需计算方案数为70!(大于10100

）；IBM公司生产的大计算机1秒种大约可算出1012（即1000亿）个方案。若要算出全部方案，则需调用占有空间为1050个地球一样大的计算机计算几百亿年以上。而在这种大机器上用线性规划的单纯形法计算只需几秒钟（这是整数规划问题）。运筹学的研究意义运筹学是研究从众多方案（甚至无限多方案）中选择最优方案的技术，那么在当代计算机技术迅速发展的今天，这种优化技术是否会丧失其重要性？当前18页，总共41页。19运筹学的研究意义新型计算机的出现，不能代替运筹学优化需求。运筹学与计算机科学及其它科学结合应用，可以将人解放出来，产生更好的实施效果。

当前19页，总共41页。20运筹学在工程和商业管理的应用:生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等；库存管理：多种物资库存量的管理，库存方式、库存量等；运输问题：确定最小成本的运输线路、物资的调拨、运输

工具的调度以及建厂地址的选择等；人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等；市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等；财务会计：预测、贷款、成本分析、定价、证券管理、

现金管理等；当前20页，总共41页。21公司实施手段每年节支联合航空满足乘客需求前提下，以最低成本进行订票及安排机场工作班次600万Citgo石油优化炼油程序及产品供应、配送及营销7000万荷马特发展优化商业区和办公楼销售程序4000万AT&T优化商业用户的电话销售中心选址4.06亿标准品牌制定最优再订购点和订购量，确保安全库存380万施乐通过战略调整，缩短维修机器的反应时间和改进维修人员的生产率提高生产率50%宝洁重新设计北美生产和分销系统以降低成本并加快了市场进入速度2亿法国铁路制定最优铁路时刻表并调整铁路日运营量1500万Delta航空进行上千个国内航线的飞机优化配置来最大化利润1亿IBM重组全球供应链，保持最小库存同时满足客户需求7.5亿当前21页，总共41页。22本课程课程背景、教材、参考书

先修课：高等数学，概率与统计、线性代数1.教材：HamdyA.Taha,运筹学导论（第8版），邮电出版社，20072．参考书：希利尔，利伯曼，运筹学导论（第9版）,清华大学出版社,2010运筹与管理（运筹学50周年纪念特刊），2004傅家良，运筹学方法与模型，复旦大学出版社，2006胡运权，运筹学教程，清华大学出版社出版，2007．当前22页，总共41页。23国际著名运筹学刊物：InterfacesManagementScienceOperationsResearchEuropeanJournalofOperationsResearchTransportationScienceMathematicsofOperationsResearchOperationsResearchLettersMathematicalProgramming当前23页，总共41页。24本课程特点及要求目的：不仅掌握优化理论方法的专业知识，更重要的是提高分析问题和解决问题的能力。方法：强调思路、观点及弄清物理概念，掌握一定的理论推导能力，但不搞纯数学公式。避免2种倾向：只罗列方法，不讲本质；或只追求数学推导，掩盖物理概念。当前24页，总共41页。25本课程授课方式与考核

本课程授课方式：对话式教学

作业：计算机编程或者软件操作

考核：课程设计(汇报24%+报告36%)+期末考试成绩（40%）当前25页，总共41页。26绪论线性规划建模单纯形法与敏感性分析对偶与后最优分析运输模型网络模型整数线性规划排队论本课程授课内容当前26页，总共41页。27第1章什么是运筹学当前27页，总共41页。28设想你需要完成一项工作任务，需要5周完成，期间需要往返于Fayetteville（FYV）与Denver（DEN）之间，每个星期一你都要乘飞机从Fayetteville出发，星期三返回，普通的往返机票是400美元，但是如果购买跨周末的往返机票，可以享受20%的折扣，如果是单程的机票则为往返票的75%，那么如何购买这5周的机票？有哪些可能的决策方案？决策受到哪些限制条件？评价这些方案的标准是什么？1.1运筹学模型当前28页，总共41页。29购买5张普通的FYV-DEN-FYV往返机票，每周一出发，周三返回；购买1张FYV-DEN单程机票，4张跨周末的DEN-FYV-DEN往返机票，再买1张DEN-FYV单程；先购买1张第一周星期一出发，最后一周星期三返程的FYV-DEN-FYV往返机票，再买4张跨周末的DEN-FYV-DEN往返机票。该方案使得所有机票都至少跨越一个周末。所有方案的约束条件：必须周一从FYV出发，在本周的星期三返回。有哪些可能的决策方案？当前29页，总共41页。30评价所提出的各种方案好坏标准是购买这些机票的总费用，花费最少的方案最佳。方案1的费用=5×400=$2000方案2的费用=0.75×400+4×(400×0.8)+0.75×400=$1880方案3的费用=5×(400×0.8)=$1600所以，应该选择方案三上例表明，运筹学模型的3个主要构成：备选方案目标评判标准约束条件3个备选方案花费最少周一去周三回当前30页，总共41页。31

考虑长度为L的电线围成一个矩形，要使得该矩形面积最大，长度和宽度如何选取？

令w=矩形的长；h=矩形的宽.则限制条件可以叙述为

(1)矩形长+矩形宽=电线长度一半；(2)长宽不能为负值以数学形式表示为

(1)2(w+h)=L；(2)w≥0,h≥0

问题的目标（评判的标准），即矩形面积最大，令z为矩形的面积，模型变为Maxz=wh

St.2(w+h)=L；w,h≥0w=h=L/4对于可能的方案数是无限的情形，必须需要最优化模型！当前31页，总共41页。32

从上面的例子，可以归纳出一般的运筹学模型具有以下通用的格式：max或min

目标函数St.(Subjectto)约束条件一个模型的解若满足所有约束条件，则解是可行的(feasible)；如果既是可行的，又取得了目标的最佳（最大或最小）值，则解是最优的(optimal).在购票的例子中3个方案是可行的，第三方案是最优的。构造矩形的例子中，可行方案要满足w+h=L/2，w和h非负，则有无穷多的可行解。当前32页，总共41页。33虽然运筹学的模型是在一组约束条件下，使得某一具体的目标评判标准达到最优，但是它所得出的解的质量取决于模型对实际问题刻画的完全性。以购机票问题为例，假如我们不能找到所有的方案的话，那么所得到的解只相对于所选模型是最优的。例如方案3没有在模型中，则“最优”解就要用1880美元，这是一个次最优（suboptimal）解。因此，一个模型的“最优”解只是对这个模型是最好的，当模型完全的表达了实际问题时，他的解对实际才是最优的。当前33页，总共41页。341.2运筹学模型的求解在OR中，没有一种万能的技术能求解出实践中所有的数学模型；在OR中，常用的技术有：线性规划、整数规划、动态规划、网络规划、非线性规划等，除此之外还有很多运筹学方法。运筹学的问题解通常不是某种解析式形式的，需要反复迭代，逐步向最优解靠近，每步迭代的计算规则是一致的，这需要计算机来计算。对于非常复杂的数学模型，可能必须放弃最优解，可能利用某些启发式算法或经验方法，找到较好的解（非最优的）。当前34页，总共41页。351.3排队模型和模拟模型排队模型和模拟模型用于研究等待队列，他们不属于最优化技术，而是用来度量等待队列的性能，例如队长、等待时间、设施利用率等；排队论基于各种概率分布采用概率论随机模型分析队列，而模拟可以分析任何排队情形，是观察实际系统最好的方法；建立模拟模型的过程非常费时费力，计算过程非常耗时。当前35页，总共41页。361.4建模的艺术运筹学的建模过程实际上是对现实问题的抽象和近似。我们应该把研究的重点聚焦在控制实际系统行为的主要变量上，从现实世界中抽象出假定的实际系统。现实世界假设现实世界模型当前36页，总共41页。37Tyko制造公司生产各种塑料容器制品，当生产订单到达生产部门的时候，必要的原材料要从公司库存或采购。完成生产后，销售部门负责向客户分销产品。问题：生产批量应该是多少？如何用模型来表达？许多变量都可以直接表示生产水平，下面是各部门的变量：生产部门：机器数、工人工作时间、半成品库存、质量控制标准表示的生产能力；原材料部门：原材料库存量、采购供货安排、库存限量销售部门：销售预测、分销网能力、广告促销能力、竞争水平。这些变量均影响生产量，建立上述所有因素的模型极为困难当前37页，总共41页。38第一个抽象水平需要定义出假定实际系统的边界。通过分析，可以用下面两个主要变量来近似描述实际系统：

生产率

(2)消费率计算生产率要用到生产能力、质量控制标准、现有原材料等变量；消费率则可以从与销售部门有关的变量计算。本质上，从现实世界到假定现实世界的简化，是通过多个现实世界变量“简化”成为单一的假定现实世界变量来实现的。利用生产率和消费率，就可以建立起库存剩余和不足的度量