我眼中的运筹学.ppt

的运筹学,我眼中的运筹学,我眼中,学号：0923105035 姓名：扎西尖措 班级：09自动化,运筹学简述,运筹学（Operations Research） 系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话： “依照给定条件和目标，从众多方案中选择最佳方案” 故有人称之为最优化技术。,运筹学简述,运筹学的历史,“运作研究(Operational Research)小组”:解决复杂的战略和战术问题。例如： 如何合理运用雷达有效地对付德军德空袭 对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少； 在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。,在中国战国时期，曾经有过一次流传后世的赛马比赛，相信大家都知道，这就是田忌赛马。田忌赛马的故事说明在已有的条件下，经过筹划、安排，选择一个最好的方案，就会取得最好的效果。可见，筹划安排是十分重要的。 现在普遍认为，运筹学是近代应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用数学方法进行解决。前者提供模型，后者提供理论和方法。 运筹学的思想在古代就已经产生了。敌我双方交战，要克敌制胜就要在了解双方情况的基础上，做出最优的对付敌人的方法，这就是“运筹帷幄之中，决胜千里之外”的说法。 但是作为一门数学学科，用纯数学的方法来解决最优方法的选择安排，却是晚多了。也可以说，运筹学是在二十世纪四十年代才开始兴起的一门分支。 研究对象,历史起源：,运筹学的主要内容,线性规划 对偶规则和灵敏度分析 整数规划 运输问题 对策论 动态规则 网络计划技术 图和网络 决策分析 存储论,运筹学在工商管理中的应用,运筹学在工商管理中的应用涉及几个方面： 生产计划 运输问题 人事管理 库存管理 市场营销 财务和会计 另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。,Chapter1 线性规划,线性规划问题 图解法 单纯形法,线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素. 内容：,Chapter2 对偶规则和灵敏 分析,内容： 线性规划的对偶模型 对偶性质 灵敏度分析 对偶单纯形法,对称性：对偶问题的对偶问题是原问题 弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 (鞍型图) 无界性：原问题无界，对偶问题无可行解 对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1,Chapter3 运输规划 ( Transportation Problem ),内容： 运输规划问题的数学模型 表上作业法 运输问题的应用,运输型问题 具有上述特点的线性规划问题通常被称为运输型问题。现已发现的运输型问题有以下6类:一般运输问题,又称希契科克运输问题，简称H问题。网络运输问题，又称图上运输问题,简称T问题。最大流量问题,简称F问题。最短路径问题,简称S问题。任务分配问题，又称指派问题,简称A问题。生产计划问题，又称日程计划问题,简称CPS问题。其中一般运输问题、任务分配问题和生产计划问题通常都可以用表上作业法求解，而网络运输问题、最大流量问题和最短路径问题一般可用图上作业法或网络技术求解。,Chapter4 整数规划,内容： 整数规划的特点及应用 分支定界法,整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的 ，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即 ，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。,Chapter6 图与网络分析,内容： 树与图的最小树 最短路问题 网络的最大流,图论中图是由点和边构成，可以反映一些对象之间的关系。 一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。 近代图论的历史可追溯到18世纪的七桥问题穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不可能存在这样的路线。,1最短路问题： 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 . 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用 2网络的最大流： . 容量网络：队网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点，网络的最大流是指网络中从发点到收点之间允许通过的最大流量。,运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。当然，随着客观实际的发展，运筹学的许多内容不但研究经济和军事活动，有些已经深入到日常生活当中去了。运筹学可以根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，以达到最好的效果。 运筹学作为一门用来解决实际问题的学科，在处理千差万别的各种问题时，一般有以下几个步骤：确定目标、制定方案、建立模型、制定解法。 随着科学技术和生