运筹学第四版·清华大学出版社·运筹学教材组·1绪论.ppt

运 筹 学,Operations Research,Chapter1 运筹学概论,一 运筹学简史,1、“运筹学”的释义 Operational Research(英)； Operations Research(美) 直译为“运作研究”或“运用研究”，简称OR。 中文名称：运用学运筹学 夫运筹帷幄之中，决胜于千里之外，吾不如子房。 -刘邦史记高祖本记,2、我国古代运筹思想的运用 田忌赛马,一 运筹学简史,晋国公重建皇城,晋国公重建皇城的施工方案，体现了运筹学的朴素思想。要使重建工,程的各个工序,在时间、空间上彼此协调,环环相扣,就需要运用行列式的相关知识,进行精确计算.,一 运筹学简史,约1000年前，开封一场大火，北宋皇城毁于一旦。宋真宗命晋国公丁渭，主持重建皇城。 丁渭先在皇宫前的大道上挖土烧砖备料；待把大道挖成深沟后，引城外汴水使之与汴水连通成为“临时运河”，用船把其他建筑材料直接运入工地；等到皇宫修复后，将碎砖石填入河道，修复原来皇宫前的大道。挖街取土，就地烧砖，渠成引水，运送建材,宫殿完工，渣土回填，恢复街道。这就巧妙地解决了取土之难，运输之难，清场之难，可谓“一石三鸟”。,沈括运粮,沈括(1031-1095年),北宋时期大科学家、军事家.在率兵抗击西夏侵扰的征途中,曾经从行军中各类人员可以背负粮食的基本数据出发,分析计算了后勤人员与作战士兵在不同行军天数中的不同比例关系,同时也分析计算了用各种牲畜运粮与人力运粮之间的利弊,最后做出了从敌国就地征粮,保障前方供应的重要决策.从而减少了后勤人员的比例,增强了前方作战的兵力.,假设一个民夫可以背六斗米,士兵自带五天的干粮. 如果一个民夫供应一个士兵,单程只能进军十八天六斗米,每人每天吃二升,二人吃十八天*). 如果两个民夫供应一个士兵,单程可进军二十六天.(两个民夫背一石二斗米,三个人 每天要吃六升.八天以后,其中一个民夫背的米已经吃光,给他六天的口粮让他先返回,以后的十八天,二人每天吃四升米,) 如果三个民夫供应一个士兵,单程可进军三十一天，如果要计回程的话, 只可进军十六天，而三个民夫供应一个士兵,已经到极限了. 如果要出动十万军队,辎重占去三分之一兵源,还要用三十万民夫运粮,再要扩大规模很困难了.,如果用牲畜运输,骆驼可以驮三石,马或骡可以驮一石五斗,驴子可以驮一石.与人工 相比,虽然能驮的多,花费也少,但如果不能及时放牧或喂食,牲口就会瘦弱而死.一头牲口死了,只能连它驮的粮食也一同丢弃.所以与人工相比,实际上是利害相当. 利弊分析后的结论是：从敌国就地征粮。这种军事后勤问题的分析计算是具有现代意义的运筹思想的范例.,一 运筹学简史,3、运筹学的发展历程,（1）萌芽时期 1914年，英工程师Lanchester用微分方程研究作战双方的兵力使用，提出了军事运筹学中的Lanchester战斗方程。 1909年丹麦工程师爱尔朗在哥本哈根电话公司研究电话交换机的效率开始提出了排队论的一些著名公式。 1920年Harris提出了库存论的EOQ公式。 1930年列温逊运用运筹学思想分析商业广告和顾客心理。,一 运筹学简史,一 运筹学简史,（2）产生,运筹学作为一门系统的科学，产生的背景为第二次世界大战。主要用于解决如何在与德军的对抗中最大限度地杀伤敌人，减少损失。 “运作研究(Operational Research)小组”:解决复杂的战略和战术问题。例如： 如何合理运用雷达有效地对付德军德空袭； 对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少； 在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。,1938年7月，波得塞（Bawdsey）雷达站的负责人罗伊（A.P.Rowe）提出立即进行整个防空作战系统运行的研究，并用“Operational Research” 一词作为这方面研究的描述，这就是O.R. 名词的起源。 1940年9月英国成立了由物理学家布莱克特（P.M.S. Blackett）领导的第一个运筹学小组，后来发展到每一个英军指挥部都成立运筹学小组。 1942年美国和加拿大也都相继成立运筹学小组。这些小组在确定扩建舰队规模、开展反潜艇战侦察和组织有效对敌轰炸等方面作了大量研究，为取得反法西斯战争的胜利及运筹学有关分支的建立作出了贡献。,一 运筹学简史,典型战例,不列颠之战 1941年，希特勒为了实施在英伦三岛登陆的计划，命令德国空军轮番对英国进行狂轰滥炸。当时英国皇家空军以一比七的数量劣势迎战，为此需要尽可能地保持飞机处于飞行状态。于是，空军司令部规定保持70%的飞机在天上巡逻。但是，英军很快发现要保持这么高的飞行比例有困难，因为飞机的被击落的、有需要维修的，飞行员也有伤亡。这一决策的后果是在空中飞行的飞机数量越来越少。,不列颠之战 究竟保持多大比例的飞机在巡逻才能持久作战呢？OR小组的专家纷纷研究这个问题，这个问题最后被生物学家康顿解决了。他根据计算生物平均寿命的方法，运用飞机飞行时间、维修时间、空战特点和飞机被落击伤状况等数据，得出的结论是：只要保持35%的飞机在飞行状态，就能使全部飞机的飞行战斗时间最多。这一研究成果为取得不列颠之战的胜利作出了贡献。,典型战例,盟军封锁直布罗陀海峡（猎潜战例）,1944年初，为帮助美国海军在连接大西洋和地中海的直布罗陀海峡封锁过往的德军潜艇，美军OR小组的约翰佩芝姆博士提出了一种“屏障巡逻”飞行战术。,典型战例,盟军封锁直布罗陀海峡（猎潜战例）,在深水航道的最窄处划出一个4英里长、1英里宽的长方形，两架飞机保持在长方形两边线的对称位置上，同时以115英里/小时的速度绕长方形飞行。这样，在长,方形上的每一点，每隔3分钟就有一架飞机巡逻通过。潜艇通过这个区域时，巡逻的飞机至少有两次机会去发现它。就这样，在2月24日到3月16日短短三个星期内，一个巡逻机中队击沉击伤德军潜艇3艘，自己无一伤亡。,典型战例,（3）发展 英美以兰德公司（Rand）为首的部门着重研究战略性问题，未来的武器系统的设计和其可能合理运用的方法。为美国空军评价各种轰炸机系统，讨论未来战争的策略。研究苏联政治局的行动原则和将来的行动预测。 除了在军事应用研究以外，相继在工业、农业、经济和社会问题等各领域的应用。,（4）成熟期 建立运筹学会：英（1948）美（1952）、法（1956）、日本和印度（1957）、中（1980）,一 运筹学简史,1、运筹学的定义 Morse and Kimball:为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。 运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。 英国运筹学会：运筹学是把科学方法应用在指导人员、工商企业政法和国防方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测、比较公众决策及产生的后果以帮助决策者科学地决定工作方针和政策。 美国运筹协会：运筹学是在要求分配有限资源的条件下，科学地决定如何最好地设计和运营人机系统。,二 运筹学的性质和特点,引入数学方法解决实际问题 -定性与定量方法结合 系统与整体性 -从全局考察问题 应用性 -源于实践、为了实践、服务于实践 交叉学科 -涉及经济、管理、数学、工程和系统等 多学科 开放性 -不断产生新的问题和学科分支 多分支 -问题的复杂和多样性,2、运筹学的特点,二 运筹学的性质和特点,线性规划,数 学 规 划,非线性规划,整数规划,动态规划,运 筹 学,多目标规划,双层规划,组 合 优 化,最优计数问题,图论与网络优化,排序问题,统筹图,随 机 优 化,对策论,排队论,库存论,决策论,可靠性分析,三 运筹学的内容,系统仿真,1、排队论：研究关于公用服务系统的排队和拥挤现象的随机特性和规律的理论，使服务机构对被服务对象得到某指标最优。于1909年丹麦工程师爱尔朗研究电话交换机的效率开始的。如一个港口应该有多少个码头，银行应该开设多少个服务窗口等。,三 运筹学的内容,1.囚徒困境问题,两个小偷甲和乙联手作案，因私入民宅被警方抓住但未获证据。警方将两人分别置于两间房间分开审讯，政策是若一人招供但另一人未招，则招者立即被释放，未招者判入狱10年；若二人都招，则两人各判刑8年；若两人都不招，则未获证据但因私入民宅各拘留1年。,尽管甲不知道乙是否招供，但他认为自己选“招”最好，因而甲会选择“招”，乙也同样会选择“招”，结果各判8年；但若两人都不招，结果是每人只被判1年，但在“人是理性的，即人人都会在约束条件下最大化自身的利益”的基本假设下，这种结果是不会出现的。 甲和乙是参与博弈的人，称为“局中人”。上表中每一个小方格内的数字被称为局中 人的支付，其中左边的数字代表甲的支付，右边的是乙的支付。表上中的双变量矩阵称为博弈支付矩阵。局中人所选择的策略构成的组合（招，招）被称为博弈均衡。这个组合中前后两个策略分别表示甲和乙所选择的策略。,纳什均衡（非合作博弈均衡）,对于一个博弈问题，如果在每一个局势中，全体局中人的得失相加都是零，则称此博弈为零和博弈（非合作博弈），否则称为非零和博弈（合作博弈）。 在二人零和博弈中，双方局中人寻求的最优解是一种纳什均衡；达到这种均衡时，只要其他局中人不改变自己的策略，则任何一方单独改变策略，只能带来收益或效用的减少。,纳什均衡”首先对亚当斯密的“看不见的手”的原理提出挑战：按照斯密的理论，在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。但是我们可以从“纳什均衡”中引出“看不见的手”原理的一个悖论：从利己目的出发，结果损人不利己，既不利己也不利他。,3、库存论（又称存储论）：研究合理经济地进行物资储备的控制策略的理论。 4、决策论：研究决策者如何有效进行决策的理论与方法，根据信息和评价标准用数量方法寻找或选取最优决策方案的科学。,运筹数学,系统工程,管理与运筹学,问题与方法,方法与应用,核心算法与工具,基础理论,应用理论,应用技术,运筹学,运筹学的学科地位,1.市场营销: 广告预算、媒介选择、定价、产品开发与销售计划制定等; 2.生产计划: 生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等; 3.库存管理: 多种物资库存量的管理, 库存方式、库存量等; 4.运输问题: 确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等; 5.财务和会计: 预测、贷款、成本分析、定价、证券管理、现金管理等;,四 运筹学的应用,6.人事管理: 对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等; 7.财务和会计: 预测、贷款、成本分析、定价、证券管理、现金管理等; 8.设备维修、更新和可靠性，项目选择、评价； 9.工程优化设计与管理： 10.城市管理：紧急服务系统设计和应用，供水和污水处理系统的规划等,四 运筹学的应用,由国际运筹与管理科学协会（INFORMS）主持评奖的负有盛名的弗兰茨埃德曼（Frany Edelman）奖，就是为奖励优秀的运筹学在管理中的应用的成就设立的，该奖每年举行一次，在对大量富有竞争力的入围者进行艰苦的评审后，一般有六位优胜者获奖。关于这些获奖项目的文章都在第二年发表在著名刊物Interface的第一期上，下面列表就是发表在Interface期刊的一些获奖项目。,四 运筹学的应用,2008年度大奖-荷兰铁路,项目：荷兰火车新时刻表 问题：1970年80亿人千米到2006年154亿人千米 解决方法：构建改进的循环的时刻表，每一个小时可重复，这是一个组合优化问题，设计4个程序 效果：公众意见从负面批评道正面肯定，每年增加了4000万欧元的利润。,运筹学方法使用情况(美1983),运筹学方法在中国使用情况(随机抽样),软运筹学（发源于英国） 软系统方法论 问题结构法 战略假设表面化与检验 战略选择 超对策 亚对策 生存系统模型 对