运筹学入门基础课件学习赵秀霞.ppt

运 筹 学,授课：赵秀霞 2014.3,田 忌 赛 马,上等马,中等马,下等马,上等马,中等马,下等马,齐 王,田 忌,上等马,中等马,下等马,上等马,中等马,下等马,齐 王,田 忌,田 忌 赛 马,丁渭修复皇宫,皇宫遗址,各种建筑用材料,宫 前 大 街,护 城 河,护 城 河,挖土成砖,丁渭修复皇宫,皇宫,宫 前 大 街,护 城 河,护 城 河,废砖修街,大英百科全书释义,“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具 ”,中国大百科全书 释义,“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学它可以用来预测发展趋势制定行动规划或优选可行方案”,辞海释义,“主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排以达到较经济较有效地使用人力物力。”,中国企业管理百科全书释义,“应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。”,运筹学的来源,正式使用在二战期间解决复杂的战略和战术问题： 如何合理运用雷达有效地对付德国空袭； 对商船队如何进行编队护航； 反潜深水炸弹在各种情况下如何调整其爆炸深度。,运筹学的来源,名 称 英国称为Operational research， 美国称为operations research (缩写为OR) 我国从1957年开始译作运筹学,运筹学的发展,一、从l945年到50年代初，被称为创建时期。 第一本运筹学杂志运筹学季刊(ORQuarterly)1950年于英国创刊， 第一个运筹学会英国运筹学会于1948年成立。,运筹学的发展,二、50年代初期到50年代末期，被认为是运筹学的成长时期。 最早建立运筹学会的国家是英国（1948），接着是美国（1952），法国（1956），日本和印度（1957）。我国的运筹学会建立在1980年。最初是50年代中期由钱学森，许国志等教授引入我国。 三、自60年代以来，认为是运筹学迅速发展和开始普及的时期。,运筹学的应用,一、市场营销 二、生产计划 三、库存管理 四、运输问题 五、财政和会计,运筹学的应用,六、人事管理 七、设备维修、更新、 项目选择、评价和可靠性分析 八、工程的优化设计 九、计算机和信息系统 十、城市管理,运筹学的发展方向,一、运筹学应用 二、运筹科学 三、运筹数学,运筹学研究的基本特征,系统的整体观念运筹学研究中不是对各子系统的决策行为孤立评价，而把有关子系统相互关联的决策结合起来考虑，把相互影响和制约的各个方面作为一个统一体从系统整体利益出发，寻找了个优化协调的方案。,运筹学研究的基本特征,多学科的综合 运筹学研究中吸收来自不同领域、具有不同经验和技能的专家。 模型方法的应用 运筹学研究的系统不能搬到实验室来，而是建立这个问题的数学和模拟的模型。 制定决策是运筹学应用的核心 建立模型则是运筹学方法的精髓,运筹学研究的基本方法,一、分析和表述问题 1、确定决策目标，明确主要决策什么； 2、要辨认哪些是决策的关键影响因素，在选取这些关键因素时存在哪些资源和环境的限制； 3、列出表述问题的各种基本要素，并确定优化和改进方案的目标是什么。,运筹学研究的基本方法,二、建立模型 三、求解模型和优化方案 四、对模型和由模型导出的解进行检验 五、建立起对解的有效控制 确定最优解保持稳定时的参数变化范围。 六、方案的实施,运筹学的模型,模型是研究者对客观现实经过思维抽象后用文字、图表、符号、关系式以及实体模样描述所认识到的 客观对象。,运筹学的模型,模型有三种基本形式： 形象模型 模拟模型 符号或数学模型,构模的方法和思路,直接分析法 应用已有模型：运筹学中的线性规划模型、投入产出模型、排队模型、决策和对策模型等。 类比法 不同系统之间的类同现象，类比构模。如物理学中的机械系统、气体动力学系统、水力学系统、热力学系统及电路系统之间就有不少彼此类同的现象。,构模的方法和思路,数据分析法 依据大量数据用统计分析法建模。 试验分析法 通过局部试验数据加上分析来构造模型。 想定（构想）法 在已有的知识、经验和某些的基础上，对于将来可能发生的情况给出逻辑上合理的设想和描述，然后用已有的方法构造模型，并不断修正完善，直至比较满意为止。,运筹学主要分支简介,一、线性规划 (Linear programming) 二、非线性规划 (nonlinear programming) 三、动态规划 (dynamic programming) 四、图与网络分析(graph theory and network analysis) 五、存贮论 (inventory theory) 六、排队论 (queueing theory, or waiting line) 七、对策论 (game theory) 八、决策论 (decision theory),运筹学主要分支简介,一、线性规划 (Linear programming) 用数学语言表达统筹问题，先根据问题要达到的目标选取适当的变量，问题的目标通过用变量的函数形式来表示（称为目标函数），对问题的限制条件用有关变量的等式或不等式表达（称为约束条件）。当变量连续取值，且目标函数和约束条件均为线性时，称这类模型为线性规划的模型。 用线性规划求解的典型问题由运输问题、生产计划问题、下料问题、混合配料问题等。,线性规划问题,某医院护士值班班次、每班工作时间及各班所需护士数如表119所示。每班护士值班开始时向病房报到，并连续工作8小时。试决定该医院最少需多少名护士，以满足轮班需要？,运筹学主要分支简介,二、非线性规划 (nonlinear programming) 如果现行规划建模中的目标函数或者是约束条件不全是线性的，对这类模型的研究构成非线性规划的分枝。 由于大多数工程物理量的表达式是非线性的，因此非线性规划在各类工程的优化设计中得到较多应用。它是优化设计的有力工具。,非线性规划问题,某工地有4个工点，各工点的位置及对混凝土的需求量列入下表，现需建一中心混凝土搅拌站，以供给各工点所需要的混凝土，要求混凝土的总运输量（运量×运距）最小，试决定搅拌站的位置？,运筹学主要分支简介,三、动态规划 (dynamic programming) 动态规划研究多阶段决策过程最优化。有些经营管理活动由一系列相互关联的阶段组成，在每个阶段一次进行决策，而且上一阶段的输出状态就是下一阶段的输入状态，各阶段决策之间互相管理，因此构成一个多阶段的决策过程。 动态规划研究多阶段决策过程的总体优化，即从系统总体出发，要求各阶段决策所构成的决策序列使目标函数值达到最优。,动态规划问题,某公司打算在3个不同地区设置4个销售点，根据市场预测部门估计，在不同地区设置不同数量的销售站，每月可得利润如表721所示，试问应如何在各地区设置销售站，可使每月总利润最大？,运筹学主要分支简介,四、图与网络分析(graph theory and network analysis) 运筹学中把一些研究对象用节点表示，对象之间的联系用连线表示，用点、线的集合构成图。根据研究的具体网络对象，赋予图中各边某个具体的参数，如时间、流量、费用、距离等，规定图中各节点代表具体网络中任何一种流动的起点、中转点或终点，然后利用图论方法来研究各类网络结构和流量的优化分析。 工序间的合理衔接搭配问题，设计中遇到研究各种管道、线路的通过能力，以及仓库、附属设施的布局等问题 。,图与图络分析,求解如图855所示的中国邮路问题，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)分别用处理不确定性决策问题的各种方法确定最优进货量。,