《运筹学导论第八版1绪论》由会员分享，可在线阅读，更多相关《运筹学导论第八版1绪论（42页珍藏版）》请在金锄头文库上搜索。
1、名不正,则言不顺; 言不顺,则事不成;事不成,则礼乐不兴;礼乐不兴,则刑罚不中 1231942年，Barnes Wallis巴恩斯沃利森就设计出了专门用来炸毁混凝土拱形水坝的专用炸弹，起名为“跳跃炸弹”。这种炸弹在水坝上游释放，投放前先在炸弹架上赋予它500转/分的自转速度，炸弹投下后会像小孩玩石头“打水漂”一样，在水面上多次跳跃前进，可以越过水坝前敷设的防弹网。在接触水坝时，炸弹利用自身的旋转，向水坝水线下深入，在水线下炸出大洞。拱形水坝一旦在支撑点上被炸毁，强大的水压将使水坝立即溃决。 4中文：运筹（夫运筹帷幄之中，决胜于千里之外） 史记高祖本纪英文： Operational Resear
2、ch（英国） Operations Research（美国） （直译为“作战研究”或“作业研究”、“运作研究”）5丁谓的皇宫修复工程丁谓的皇宫修复工程运筹学的起源北宋年间，丁谓负责修复焚毁的开封皇宫，他的施工方案是：Step1. 先将工程皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。Step2. 使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；Step3. 修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、生产、运输及废墟物的处理用“一沟三用”巧妙地解决了。6田忌赛马齐王与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。著名
3、的军事谋略家孙膑如何指导田忌的？齐王：上上中中下下田忌：下下上上中中最终净胜一局，赢得1000金。7北宋科学家、军事家沈括,在率兵抗击西夏征途中n利用各兵种背负粮食的基本数据，盘算后勤兵与战士在不同的行军天数中的差异比例关系；n盘算了用种种牲口运粮与人力运粮之间的利弊，做出了从敌国就地征粮，保障前线提供的决策。优化后勤职员比例，增强了前线战斗力。这种军事运筹是运筹思想的典范，也是现代军事运筹的核心问题。 沈括调整军队构成8运筹学真正的发展n起源于二次大战的一门新兴交叉学科n与作战问题相关雷达设置、运输船队护航、反潜战中深水炸弹起爆深度、飞行员编组、军事物资存储等n战后在经济、管理和机关学校及科
4、研单位继续研究1948年英国首先成立运筹学会1952年，Morse 和 Kimball出版运筹学方法1952年美国成立运筹学会1959年成立国际运筹学联合会(IFORS)我国于1982年加入IFORS，并于1999年8月组织了第15届大会9Philip M. Morse运筹学发展的主要推动者Wassily W. Leontief 投入产出法Dantzig,1914-2005单纯形法 Von Neumann,Monte Carlo方法John Forbes Nash Jr博弈论10运筹学的内容丰富，分支众多。根据解决问题的主要特征可分两大类：确确定定型型和概概率率型型。其中确定型包含：线线性性规
5、规划划，整整数数规规划划，动动态态规规划划，非非线线性性规规划划，多多目目标标决决策策及确确定定性性存存贮贮等；概率型中包含：回回归归分分析析，决决策策论论，对对策策论论，排排队队论论，马马尔尔可可夫夫链链，图图论与网络论与网络，概率存贮概率存贮及搜索技术搜索技术等。本课将阐述运筹学中最基本的部分规划论（即线性规划，对偶理论与灵敏度分析、整数规划，网络规划）、排队论 运筹学分支及模型类型11运筹学的研究问题与对象n资源最佳利用问题方法：线性规划、整数规划、网络图、动态规划、目标规划等n竞争现象如战争、投资、商品竞争方法：对策论（博弈论）n拥挤现象如公共汽车排队、打电话、买东西、飞机着陆、船舶进
6、港等方法：排队论12n运筹学的关键在于模型的建立和使用；n应用运筹学处理问题时，要从系统观点来分析问题；n提出需要解决的问题和希望达到的目标；n理清问题所处的环境和约束条件，包括：时间、地点、资金、原材料、设备、人力、能源、动力、信息、技术等；n问题中的主要因素、各种环境和约束条件之间的逻辑关系运筹学应用前提13运筹学的发展趋势n运筹学的危机脱离实际应用，陷入数学陷阱nIT对运筹学的影响MIS, MRP-II, CIMS, ERPOR Dept. - Dept. Of OR & ISn运筹学与行为科学结合群决策和谈判、对策理论、多层规划、合理性分析n服务行业中的应用金融服务业、信息、电信服务业
7、、医院管理14研究深水炸弹起爆深度问题。当飞机发现潜艇后，飞机何时投掷炸弹及炸弹的引爆引度是多少？运筹学工作者对大量统计数字进行认真分析后，提出如下决策：1.仅当潜艇浮出水面或刚下沉时，方投掷深水炸弹。2.炸弹的起爆深度为离水面25英尺（这是当时深水炸弹所容许的最浅起爆点）。3.空军采用上述决策后，所击沉潜艇增加5倍倍。运筹学的研究意义15纽约消防车辆调度。都市求救电话是一个复杂的分布在不同地点的多个服务台的排队系统，涉及资源的空间配置、警车巡逻线路最优设计、警力配备、电话调度；部署在纽约、圣迭戈、萨克拉门托、达拉斯、波特兰、加拉加斯和鹿特丹。提高生产率10%15%，特别是极大的降低了响应时间
8、。运筹学的研究意义16假设有70艘油轮向70个港口运货，已知每艘油轮驶向每个港口的费用，油轮公司需制订出最优运输方案。采用全枚举法（穷举法）需计算方案数为70!(大于10100 ）；IBM公司生产的大计算机1秒种大约可算出1012（即1000亿）个方案。若要算出全部方案，则需调用占有空间为1050个地球一样大的计算机计算几百亿年以上。而在这种大机器上用线性规划的单纯形法计算只需几秒钟（这是整数规划问题）。运筹学的研究意义运筹学是研究从众多方案（甚至无限多方案）中选择最优方案的技术，那么在当代计算机技术迅速发展的今天，这种优化技术是否会丧失其重要性？17运筹学的研究意义新型计算机的出现，不能代替
9、运筹学优化需求。运筹学与计算机科学及其它科学结合应用，可以将人解放出来，产生更好的实施效果。 18运筹学在工程和商业管理的应用运筹学在工程和商业管理的应用:生产计划：生产作业的计划、日程表的编排、合理下料、 配料问题、物料管理等；库存管理：多种物资库存量的管理，库存方式、库存量等；运输问题：确定最小成本的运输线路、物资的调拨、运输 工具的调度以及建厂地址的选择等；人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等；市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等；财务会计：预测、贷款、成本分析、定价、证券管理、 现金管理等；19公司公司实施手段实施手
10、段每年节支每年节支联合航空满足乘客需求前提下，以最低成本进行订票及安排机场工作班次600万Citgo石油优化炼油程序及产品供应、配送及营销7000万荷马特发展 优化商业区和办公楼销售程序4000万AT&T优化商业用户的电话销售中心选址4.06亿标准品牌制定最优再订购点和订购量，确保安全库存380万施乐通过战略调整，缩短维修机器的反应时间和改进维修人员的生产率提高生产率50%宝洁重新设计北美生产和分销系统以降低成本并加快了市场进入速度2亿法国铁路制定最优铁路时刻表并调整铁路日运营量1500万Delta航空进行上千个国内航线的飞机优化配置来最大化利润1亿IBM重组全球供应链，保持最小库存同时满足客
11、户需求7.5亿20本课程课程背景、教材、参考书 先修课：高等数学，概率与统计、线性代数1. 教材： Hamdy A.Taha, 运筹学导论（第8版），邮电出版社，20072参考书： 希利尔，利伯曼，运筹学导论（第9版）, 清华大学出版社, 2010运筹与管理（运筹学50周年纪念特刊），2004傅家良，运筹学方法与模型，复旦大学出版社，2006 胡运权，运筹学教程，清华大学出版社出版，200721国际著名运筹学刊物：国际著名运筹学刊物：InterfacesManagement ScienceOperations ResearchEuropean Journal of Operations Res
12、earchTransportation ScienceMathematics of Operations ResearchOperations Research LettersMathematical Programming22本课程特点及要求 目的：不仅掌握优化理论方法的专业知识，更重要的是提高分析问题和解决问题的能力。方法：强调思路、观点及弄清物理概念，掌握一定的理论推导能力，但不搞纯数学公式。避免2种倾向：只罗列方法，不讲本质；或只追求数学推导，掩盖物理概念。23本课程授课方式与考核 n 本课程授课方式：对话式教学n 作业：计算机编程或者软件操作n 考核：课程设计(汇报24%+报告36%
13、)+期末考试成绩（40%）241.绪论2.线性规划建模3.单纯形法与敏感性分析4.对偶与后最优分析5.运输模型6.网络模型7.整数线性规划8.排队论本课程授课内容 25第1章 什么是运筹学26设想你需要完成一项工作任务，需要5周完成，期间需要往返于Fayetteville（FYV）与Denver（DEN）之间，每个星期一你都要乘飞机从Fayetteville出发，星期三返回，普通的往返机票是400美元，但是如果购买跨周末的往返机票，可以享受20%的折扣，如果是单程的机票则为往返票的75%，那么如何购买这5周的机票？1.有哪些可能的决策方案？有哪些可能的决策方案？2.决策受到哪些限制条件？决策受
14、到哪些限制条件？3.评价这些方案的标准是什么？评价这些方案的标准是什么？1.1 运筹学模型271.购买5张普通的FYV-DEN-FYV往返机票，每周一出发，周三返回；2.购买1张FYV-DEN单程机票，4张跨周末的DEN-FYV-DEN往返机票，再买1张DEN-FYV单程；3.先购买1张第一周星期一出发，最后一周星期三返程的FYV-DEN-FYV往返机票，再买4张跨周末的DEN-FYV-DEN往返机票。该方案使得所有机票都至少跨越一个周末。所有方案的约束条件：必须周一从FYV出发，在本周的星期三返回。有哪些可能的决策方案？28评价所提出的各种方案好坏标准是购买这些机票的总费用，花费最少的方案最
15、佳。方案方案1的费用=5400=$2000方案方案2的费用=0.75400+4(4000.8)+0.75400=$1880方案方案3的费用=5 (4000.8) =$1600所以，应该选择方案三上例表明，运筹学模型的3个主要构成：1.备选方案2.目标评判标准3.约束条件3个备选方案花费最少周一去周三回29考虑长度为L的电线围成一个矩形，要使得该矩形面积最大，长度和宽度如何选取？令w=矩形的长；h=矩形的宽.则限制条件可以叙述为 (1)矩形长+矩形宽=电线长度一半；(2)长宽不能为负值以数学形式表示为 (1) 2(w+h)=L； (2) w0, h0 问题的目标（评判的标准），即矩形面积最大，令
16、z为矩形的面积，模型变为 Max z=wh St. 2(w+h)=L； w, h0w=h=L/4对于可能的方案数是无限的情形，必须需要最优化模型！30从上面的例子，可以归纳出一般的运筹学模型具有以下通用的格式：max或min 目标函数St. (Subject to) 约束条件一个模型的解若满足所有约束条件，则解是可行的(feasible)；如果既是可行的，又取得了目标的最佳（最大或最小）值，则解是最优的(optimal). 在购票的例子中3个方案是可行的，第三方案是最优的。构造矩形的例子中，可行方案要满足w+h=L/2，w和h非负，则有无穷多的可行解。31虽然运筹学的模型是在一组约束条件下，使
17、得某一具体的目标评判标准达到最优，但是它所得出的解的质量取决于模型对实际问题刻画的完全性。以购机票问题为例，假如我们不能找到所有的方案的话，那么所得到的解只相对于所选模型是最优的。例如方案3没有在模型中，则“最优”解就要用1880美元，这是一个次最优（suboptimal）解。因此，一个模型的“最优”解只是对这个模型是最好的，当模型完全的表达了实际问题时，他的解对实际才是最优的。321.2 运筹学模型的求解n在OR中，没有一种万能的技术能求解出实践中所有的数学模型；n在OR中，常用的技术有：线性规划、整数规划、动态规划、网络规划、非线性规划等，除此之外还有很多运筹学方法。n运筹学的问题解通常不
18、是某种解析式形式的，需要反复迭代，逐步向最优解靠近，每步迭代的计算规则是一致的，这需要计算机来计算。n对于非常复杂的数学模型，可能必须放弃最优解，可能利用某些启发式算法或经验方法，找到较好的解（非最优的）。331.3 排队模型和模拟模型n排队模型和模拟模型用于研究等待队列，他们不属于最优化技术，而是用来度量等待队列的性能，例如队长、等待时间、设施利用率等；n排队论基于各种概率分布采用概率论随机模型分析队列，而模拟可以分析任何排队情形，是观察实际系统最好的方法；n建立模拟模型的过程非常费时费力，计算过程非常耗时。341.4 建模的艺术n运筹学的建模过程实际上是对现实问题的抽象和近似。n我们应该把
19、研究的重点聚焦在控制实际系统行为的主要变量上，从现实世界中抽象出假定的实际系统。现实世界假设现实世界模型35Tyko制造公司生产各种塑料容器制品，当生产订单到达生产部门的时候，必要的原材料要从公司库存或采购。完成生产后，销售部门负责向客户分销产品。问题：生产批量应该是多少？如何用模型来表达？许多变量都可以直接表示生产水平，下面是各部门的变量：生产部门生产部门：机器数、工人工作时间、半成品库存、质量控制标准表示的生产能力；原材料部门原材料部门：原材料库存量、采购供货安排、库存限量销售部门销售部门：销售预测、分销网能力、广告促销能力、竞争水平。这些变量均影响生产量，建立上述所有因素的模型极为困难这
20、些变量均影响生产量，建立上述所有因素的模型极为困难36第一个抽象水平需要定义出假定实际系统的边界。通过分析，可以用下面两个主要变量来近似描述实际系统：(1) 生产率 (2) 消费率计算生产率要用到生产能力、质量控制标准、现有原材料等变量；消费率则可以从与销售部门有关的变量计算。本质上，从现实世界到假定现实世界的简化，是通过多个现实世界变量“简化”成为单一的假定现实世界变量来实现的。利用生产率和消费率，就可以建立起库存剩余和不足的度量，建立起模型以平衡库存剩余或短缺所引起的冲突成本，使得库存费用最低。通过上述过程，比较容易对假定的现实世界建立模型。371.5 仅有数学是不够的n运筹学模型是数学模
21、型，数学是运筹学的基石；n运筹学决策模型总是受到人的因素影响，运筹学的成败与心理因素密切相关。几个例子：电梯等待时间优化问题；机场柜台紧急插队问题；钢锭产量均衡问题n是否可能采用“突破常规的”思路解决问题；n必须考虑人的因素（文化差异、国民习性）；n数学模型应该去适应现实问题；而不是反之；381.6 运用运筹学的几个步骤n运用运筹学解决实际问题需要团队精神，需要OR人员的专业技能必须与客户的经验与合作相配合，必须面向客户的问题开展研究。n运筹学是科学，也是艺术。科学性：体现数学的优点（定量分析） ；艺术性：成功与否取决于OR团队的创造性和经验（技术的判断力、与人沟通及组织的能力与技巧） 39运
22、用运筹学解决实际问题的通行步骤：运用运筹学解决实际问题的通行步骤：问题定义：确定研究问题的范围，即确定 (1) 可能的决策方案; (2) 问题的目标; (3) 模型限制条件.模型构造：将问题的定义转化为数学关系。产生的模型是某种标准的数学模型，比如线性规划模型。反之，如果数学模型过于复杂而得不到解析解，则需要进一步简化模型，使用启发式方法求解。模型求解：利用成熟的求解算法求解，如有必要进行灵敏度分析。模型验证：验证解的合理性。方法包括基于历史数据合理地再现结果；缺乏历史数据，可以模拟手段来验证实 施：将模型结果（往往是数学结果）翻译为能让人理解的操作指令或方案40明确问题建立模型设计算法整理数据求解模型评价结果简化？满意？YesNoNo411.7 运筹学的定义nMorse 和 Kimball：为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法。n英国运筹学会：把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策。n中国百科全书：运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理。现代运筹学涵盖了一切领域的管理与优化问题，称为管理科学42
