运筹学Operationalresear.ppt

运筹学 Operations Research 绪论-预备知识,管理学院管理科学与工程 -郝海,运筹实例-田忌赛马,上等马,中等马,下等马,上等马,中等马,下等马,齐 王,田 忌,上等马,中等马,下等马,上等马,中等马,下等马,齐 王,田 忌,运筹实例-田忌赛马,运筹实例-丁渭修复皇宫,皇宫遗址,各种建筑用材料,宫 前 大 街,护 城 河,护 城 河,挖土成砖,运筹实例-丁渭修复皇宫,丁渭修复皇宫,皇宫,宫 前 大 街,护 城 河,护 城 河,废砖修街,丁渭修复皇宫,丁渭智修皇宫宋代符详年间，皇宫中发生火灾，要进行皇宫修复工程。当时需要解决“取土”、“外地材料的运送”、“被烧坏皇宫的瓦砾处理”等三大问题。主管该工程的是大臣丁渭。他便在皇宫前的大街上挖沟取土，免去到很远的地方取土；很快，路就挖成了大沟，又让汴河决口，将水引进壕沟。于是各地运来的竹木都被编成筏子，连同船运来的各种材料，都通过这条水路运进来。皇宫修复后，他又让大家将拆下来的碎砖瓦连同火烧过的灰，都填进沟里，重新修成大路。经过这一处理，不仅节约了大量时间，还节省了上亿的经费。丁渭智修皇宫，就是充分把握要素之间的相生关系，使系统往有序和互相促进的方向发展，同时又把握了系统要素的相克性质，促使其向反面演化，最终达到最理想的效果。,运筹实例-沈括运粮,（原文）：凡师行，因粮于敌，最为急务。运粮不但多费，而势难行远。予尝计之，人负米六斗，卒自携五日干粮，人饷一卒，一去可十八日；米六斗，人食日二升，二人食之，十八日尽；若计复回，只可进九日。二人饷一卒，一去可二十六日；（米一石二斗，三人食日六升，八日则一夫所负已尽，给六日粮遣回，后十八日，二人食日四或并粮）。叵计复回，止可进十三日。（前八日日食六升，后五日并回程，日食四升并粮）三人饷一卒，一去可三十一日，米一石八斗，前六日半四人食日八升，减一夫，给四日粮；十七日三人食日六升，又减一夫，给九日粮；后十八日，二人食日四升并粮。计复回止可进十六日，（前六日半日食八升，中七日日食六升，后十一日并回程日食四升并粮）。三人饷一卒，极矣。若兴师十万，辎重三之一，止得驻战之卒七万人，已用三十万人运粮，此外难复加矣。（放回运夫须有援卒，缘运行死亡疾病，人数稍减，且以所减之食，备援卒所费）。运粮之法，人负六斗，此以总数率之也。其间队长不负，樵汲减半，所余皆均在众夫，更有死亡疾病者，所负之米，又以均之，则人所负，常不啻六斗矣。故军中不容冗食，一夫冗食，二三人饷之，尚或不足。若以畜乘运之，则駞负三石，马、骡一石五斗，驴一石，比之人运，虽负多而费寡，然刍牧不时，畜多瘦死，一畜死，则并民负弃之，较之人负，利害相半。（卷十一）,（译）：一般军队出行，从敌方获取军粮是最要紧的急务。运粮不仅费用多，而且难以载粮远行。我曾经计算过，每人背米六斗，士兵自己携带五日干粮，每人供一个士兵，一行可达十八天；六斗米，每人一天吃两升，两个人吃，正好十八天吃完；如果以往返计算，只可吃九天的行程。两个人供一个士兵食粮，一行可以达二十六天；（一石二斗米，三人每天吃六升，八天的话一个背夫所负的粮食已经吃完，给他六天的粮食遣回，后十八天，二个人每天吃四升或干粮）。如果以往返计，只可有十三天的路程。（前八天每天吃六升，后五天加回程，每天吃四升加干粮）三个人供一个士兵，一行可供三十一天，一石八斗米，前六天半四个人每天吃八升，派返一个背夫，给他四天口粮；十七天三人每天吃六升，又送加一个民夫，给他九天口粮；后十八天，二个人每天吃四升加干粮。计算往返的话只可前行十六天的里程，（前六天半，每天吃八升，中间七天每天吃六升，后十一天加回程每天吃四升加干粮）。三个人供一个士卒吃用，已为最大极限。,运筹实例-沈括运粮,如果兴兵十万人，管护辎重的有三分之一，能够战斗的士兵只有七万人，而运粮的民夫要用三十万人，此外很难再增人了。（放回运夫要有兵卒护援，由于路途中死亡疾病，人数会不断减少，而那些省下来的粮食，以备护援兵卒吃用。运粮的制度，每人平均以六斗计算，这是个总计方法。其中队长不背东西，打柴汲水的人背负减半，多出斤重部分平摊给众民夫，更有死亡疾病不能背米的，他们应负的重量，又平均分摊，那么每个人所负的重量，常常不止六斗的重量。因此军中不容许多余的饭口，一个多余的人吃饭，就要两三个人供应他，还有可能供不够。如果以牲畜运粮，骆驼可以负三石，马、骡一石五斗，驴一石，相比于以人运粮，虽然负多费少，但如果不按时喂草，牲畜多会死亡，一个牲口死掉，它驮负的粮食也得扔掉，相比用人背扛，有利有弊，利害均半。 （评）：宋时战争中还没有特别重的军械，仅粮食一项就耗费人力量力如此，可以想见穷兵黩武之罪。隋炀帝三伐高丽，最多一次共有战士一百三十八万人，可以想象要用多少民夫啊。,运筹实例-沈括运粮,运筹学的来源,正式在二战期间解决复杂的战略和战术问题： 如何合理运用雷达有效地对付德国空袭； 对商船队如何进行编队护航； 反潜深水炸弹在各种情况下如何调整其爆炸深度。,名 称 英国称为Operational research， 美国称为operations research (缩写为OR) 我国从1957年开始译作运筹学,运筹学的来源,一、从l945年到50年代初，被称为创建时期。 第一本运筹学杂志运筹学季刊 (ORQuarterly)1950年于英国创刊， 第一个运筹学会英国运筹学会于1948年成立。,运筹学的发展,二、50年代初期到50年代末期，被认为是运筹学的成长时期。 最早建立运筹学会的国家是英国（1948），接着是美国（1952），法国（1956），日本和印度（1957）。我国的运筹学会建立在1980年。最初是50年代中期由钱学森，许国志等教授引入我国。 三、自60年代以来，认为是运筹学迅速发展和开始普及的时期。,运筹学的发展,运筹学释义,1957年我国从“夫运筹帷幄之中，决胜千里之外”（见史记高祖本纪)这句古语中摘取“运筹”二字，将OR正式译作运筹学，包含运用筹划以策略取胜等意义，比较恰当地反映了这门学科的性质和内涵。,运筹帷幄决胜千里,大英百科全书释义,“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具 ”,“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学它可以用来预测发展趋势制定行动规划或优选可行方案”,中国大百科全书 释义,辞海释义,“主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排以达到较经济较有效地使用人力物力。”,“应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。”,中国企业管理百科全书释义,运筹学研究的基本特征,系统的整体观念运筹学研究中不是对各子系统的决策行为孤立评价，而把有关子系统相互关联的决策结合起来考虑，把相互影响和制约的各个方面作为一个统一体从系统整体利益出发，寻一些优化协调的方案。 多学科的综合 运筹学研究中吸收来自不同领域、具有不同经验和技能的专家。 模型方法的应用 运筹学研究的系统不能搬到实验室来，而是建立这个问题的数学和模拟的模型。制定决策是运筹学应用的核心，而建立模型则是运筹学方法的精髓。,系统整体,数学模型方法,运筹学的工作步骤,提出和形成问题,建立模型,模型求解,解的检验,解的控制,解的实施,模型是研究者对客观现实经过思维抽象后用文字、图表、符号、关系式以及实体模样描述所认识到的客观对象。,运筹学的工作步骤,运筹学模型的建立和运用是一个不断改进的过程。在这个过程中，需要不断地修正目标、改进模型和改进算法等。只有不断改进，才能在实践过程中不断提高运用运筹学理论知识分析问题和解决问题的能力。 P11,运筹学主要研究分支,一、线性规划(Linear programming) 二、非线性规划(nonlinear programming) 三、动态规划(dynamic programming) 四、图与网络分析(graph theory and network analysis) 五、存储论(inventory theory) 六、排队论(queueing theory, or waiting line) 七、对策论(game theory) 八、决策论(decision theory),运筹学主要分支简介,一、线性规划 (Linear programming) 用数学语言表达统筹问题，先根据问题要达到的目标选取适当的变量，问题的目标通过用变量的函数形式来表示（称为目标函数），对问题的限制条件用有关变量的等式或不等式表达（称为约束条件）。当变量连续取值，且目标函数和约束条件均为线性时，称这类模型为线性规划的模型。 用线性规划求解的典型问题由运输问题、生产计划问题、下料问题、混合配料问题等。,线性规划问题,某医院护士值班班次、每班工作时间及各班所需护士数如下表所示。每班护士值班开始时向病房报到，并连续工作8小时。试决定该医院最少需多少名护士，以满足轮班需要？,运筹学主要分支简介,二、非线性规划 (nonlinear programming) 如果现行规划建模中的目标函数或者是约束条件不全是线性的，对这类模型的研究构成非线性规划的分枝。 由于大多数工程物理量的表达式是非线性的，因此非线性规划在各类工程的优化设计中得到较多应用。它是优化设计的有力工具。,非线性规划问题,某工地有4个工点，各工点的位置及对混凝土的需求量列入下表，现需建一中心混凝土搅拌站，以供给各工点所需要的混凝土，要求混凝土的总运输量（运量运距）最小，试决定搅拌站的位置？,运筹学主要分支简介,三、动态规划 (dynamic programming) 动态规划研究多阶段决策过程最优化。有些经营管理活动由一系列相互关联的阶段组成，在每个阶段一次进行决策，而且上一阶段的输出状态就是下一阶段的输入状态，各阶段决策之间互相管理，因此构成一个多阶段的决策过程。 动态规划研究多阶段决策过程的总体优化，即从系统总体出发，要求各阶段决策所构成的决策序列使目标函数值达到最优。,动态规划问题,某公司打算在3个不同地区设置4个销售点，根据市场预测部门估计，在不同地区设置不同数量的销售站，每月可得利润如下表所示，试问应如何在各地区设置销售站，可使每月总利润最大？,运筹学主要分支简介,四、图与网络分析(graph theory and network analysis) 运筹学中把一些研究对象用节点表示，对象之间的联系用连线表示，用点、线的集合构成图。根据研究的具体网络对象，赋予图中各边某个具体的参数，如时间、流量、费用、距离等，规定图中各节点代表具体网络中任何一种流动的起点、中转点或终点，然后利用图论方法来研究各类网络结构和流量的优化分析。 工序间的合理衔接搭配问题，设计中遇到研究各种管道、线路的通过能力，以及仓库、附属设施的布局等问题 。,图与图络分析,求解如图所示的中国邮路问题，A点是邮局。,运筹学主要分支简介,五、存贮论 (inventory theory) 存贮策略研究在不同需求、供货及到达方式等情况下，确定在什么时间点订货，以及一次提出多大的批量，使用于订购、储存和可能发生短缺的费用的总和为最少。,存贮论,对电子元件每月需求量为4000件，每件成本为150元，每年的存贮费为成本的10，每次订购费为500元。求： (1)不允许缺货条件下的最优存贮策略； (2)允许缺货(缺货费为每件每年100元)条件下的最优存贮策略。,运筹学主要分支简介,六、排队论 (queueing theory, or waiting line) 排队轮研究顾客不同输入、各类服务时间的分布、不同服务员数及不同排队规则情况下，排队系统的工作性能和状态，设计新的排队系统及改进现有系统的性能提供数量依据。,排队论,某店仅有一个修理工人，顾客到达过程为Poisson流，平均每小时3人，修理时间服从负指数分布，平均需10分钟。求： (1)店内空闲的概率； (2)有4个顾客的概率； (3)至少有1个顾客的概率； (4)店内顾客的平均数； (5)等待服务的顾客的平均数 (6)平均等待修理时间；,七、对策论 (game theory) 对策论用于研究具有对抗局势的模型。在这类模型中，参与对抗的各方成为局中人，每个局中人均有一组策略可供选择，当各局中人分别采取不同策略时，对应一个收益或需要支付的函数。对策论为局中人在高度不确定和充满竞争的环境中提供一套完整的、定量化和程序化的选择策略的理论和方法。 对策论已应用于商品、消费者、生产者之间的供求平衡分析，利益集团的协商和谈判，以及军事上各种作战模型的研究等。,运筹学主要分支简介,对策论,“二指莫拉问题”，甲、乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的指数叫出来。如果只有一个人猜测正确，则他的赢得分数为二人所出指数之和、否则重新开始。试写出该对策中各局中人的策略集及甲的赢得矩阵，并说明是否存在某一种策略比其它策略更有利。,八、决策论 (decision theory) 决策是指为最优的达到目标，依据一定准则，对若干备选方案进行选择。决策论是对整个决策过程中涉及方案目标选取、度量、概率值确定、效用值计算，一直到最优方案和策略选取的有关科学理论。,运筹学主要分支简介,决策论,根据以往的资料，一家面包店每天所需面包数(当天市场需求量)可能是下列当中的某一个，100，150，200，250，300，但其概率分布不知道。如果一个面包当天没有卖掉，则可在当天结束时每个0.15元处理掉。新鲜面包每个售价为0.49元，成本为0.25元，假设进货量限制在需求量中的某一个，要求： (1)做出面包进货问题的决策矩阵； (2)分别用处理不确定性决策问题的各种方法确定最优进货量。,运筹学的应用,市场营销 生产计划 库存管理 运输问题 财政与会计,人事管理 设备维护、更新 工程优化设计 IT信息系统 城市管理,管理科学的兴起,伯法的管理科学学派（1975） 埃尔伍德斯潘赛伯法（Elwood Spenc