00-运筹学概述

容忍容忍仍然,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,第,*,页,期末考试笔试 80%,平时作业考勤 20%,考试与要求,1,运 筹 学 课 程 内 容,2,运筹学概况简述,运筹学(Operational Research),直译为“运作研究”。,运筹学是运用科学的方法(如分析、试验、量化等)来决定如何最佳地运营和设计各种系统的一门学科。,3,举例：囚徒困境,（prisoners dilemma),囚徒困境,坦白,不坦白,坦白,不坦白,8，8,0，10,10，0,1，1,4,运筹学概况简述,运筹学能够对经济管理系统中的人力、物力、财力等,资源,进行统筹安排，为,决策者,提供有依据的最优方案，以实现最有效的管理。,通常以最优、最佳等作为决策目标，避开最劣的方案。,5,运筹学在工商管理中的应用,生产计划,：,生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。,库存管理,：,多种物资库存量的管理，库存方式、库存量等。,运输问题,：,确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。,6,运筹学在工商管理中的应用,人事管理,：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。,市场营销,：广告预算、媒介选择、定价、产品开发与销售计划制定等。,7,运筹学在工商管理中的应用,财务和会计,：包括预测、贷款、成本分析、定价、证券管理、现金管理等。,其他,：设备维修、更新，项目选择、评价，工程优化设计与管理等。,8,运筹学的发展,七八十年代,成熟,五六十年代,发展,二战期间,产生,二战以前,萌芽,9,丁谓一举三得修复皇宫,北宋真宗年间，皇宫失火，真宗皇帝令丁谓限期重建皇宫。,三大难题：,1、建房用土量大。若到郊外取土，路途太远。,2、运输难。大批建筑材料，从外地只能先由水,路运到汴水，再靠车马运到皇宫的工地。,3、大量的废墟垃圾需要处理。如果运到郊外，需要花费大量的人力、物力、时间。,10,丁谓一举三得修复皇宫,丁谓经过再三思索，想出了一个一举三得的办法。,他的施工方案是：,首先在施工现场到汴水的路上挖一条大沟，挖出的土就地制砖，解决了用土问题；,然后，把汴水引入沟中，形成河道，来承担繁重的,运输任务；,皇宫建成后，排掉沟中的水，将废墟垃圾填入沟中，修复成平地。,丁谓“一沟三用”巧妙地解决了取材、运输及废墟垃,圾的处理问题，体现了运筹学的整体优化思想。,11,运筹学的发展,七八十年代,成熟,五六十年代,发展,二战期间,产生,二战以前,萌芽,12,二战期间的案例,鲍德西（Bawdsey）雷达站的研究,二战期间，德国已拥有一支强大的空军，起飞17分钟即到达英国本土。在如此短的时间内，如何预警和拦截成为一大难题。1939年，英国在Bawdsey建立了一个秘密雷达站，以曼彻斯特大学的物理学家Blackett为首，组织了一个小组，代号“Blackett马戏团”。,13,二战期间的案例,鲍德西（Bawdsey）雷达站的研究,小组成员：心理学家3名,数学家2名,应用数学家2名,天文物理学家1名,普通物理学家1名,海军和陆军军官各1名,测量员1名。,14,二战期间的案例,鲍德西（Bawdsey）雷达站的研究,研究的问题：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并且获得了成功。“Blackett马戏团”在秘密报告中使用了“Operational Research”，即“运筹学”。,15,二战期间的案例,鲍德西（Bawdsey）雷达站的研究运筹学的特色：,项目具有实际价值；,明确的目标改善防空系统；,整体优化的思想信息的采集、传递，指挥系,统与武器系统的协调，整体的最优；,数量化的分析不是主观的臆断；,多学科的协同；,最优化的结果快速地预警和拦截德军飞机；,简明朴素的表述。,16,二战期间的案例,大西洋反潜战Morse小组的工作,1941-1942年，德国潜艇严密封锁了英,吉利海峡，企图切断英国的“生命线”。海,军几次反封锁，均不成功。应英国要求，,美国派麻省理工学院的Morse教授率领一,个,小,组去协助。,17,二战期间的案例,大西洋反潜战Morse小组的工作,Morse教授经过多方实地考察和计算，最后提出了,两条重要建议：,1、由反潜潜艇投掷水雷，改为飞机投掷深水炸弹，并,且起爆深度由100米左右改为25米左右。即当潜艇刚下,潜时攻击效果最佳。(提高效率4-7倍),2、运送物资的船队及护航舰队编队，由小规模多批,次，改为加大规模、减少批次，这样，损失率将减少。,（25%下降到10%）,18,二战期间的案例,大西洋反潜战Morse小组的工作,丘吉尔采纳了Morse的建议，最终成功地打,破封锁，并重创了德国潜艇。Morse 个人也因此,同时获得英国和美国战时的最高勋章。这是史无,前例的，足以体现运筹学在军事上的重要作用。,19,运筹学的发展,七八十年代,成熟,五六十年代,发展,二战期间,产生,二战以前,萌芽,20,运筹学的分支,线性规划,非线性规划,整数规划,动态规划,多目标规划,随机规划,模糊规划等,21,运筹学的分支,图与网络理论,存储论,排队论,决策论,对策论,排序与统筹方法,可靠性理论等,22,运筹学的工作步骤,(1).提出和形成问题：,即要弄清问题的,目标,，可能的,约束,，确定的,决策变量,以及相关,参数,；,(2).建立模型：,即把问题中决策变量、参数和目标与约束之间的,关系,用一定的模型表示出来；,(3).求解：,用各种手段(主要是数学方法，也可用其他方法)将模型求解。解可以是,最优解、次优解、满意解,。复杂模型的求解需用计算机，解的精度要求可由决策者提出；,(4).解的检验：,首先检查求解步骤和程序有无错误，然后检查解是否反应现实问题；,(5).解的控制（灵敏性分析）：,通过控制解的变化过程决定对解是否要作一定的改变；,(6).解的实施。,是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。,23,如何学习运筹学课程,学习运筹学要把,重点,放在分析、理解有关的概念、思路上。在自学过程中，应该多向自己提问，例如一个方法的实质是什么，为什么这样进行，怎么进行等。,自学时要掌握三个,重要环节,：,24,如何学习运筹学课程,1.认真阅读教材和参考资料，以,指,定教材,为主。,2.,在理解了基本概念和理论的基础,上要仔细研究,例题,。,3,.,要学会做学习,小结,。,25,基础知识,（一）、,向量,1、,定义：,n,个实数,a,1,a,2,a,n,组成的,有序数组,。,n,维,行向量,记作,：,=,（,a,1,a,2,a,n,）,；,n,维,列向量,记作,：,=或=,（,b,1,b,2,b,n,）,T,b,1,b,2,.,.,.,b,n,26,基础知识,（一）、,向量,2、,线性组合：,给定向量,1,2,s,，,如果存在一组数,k,1,k,2,k,s,使关系式,=k,1,1,+k,2,2,+k,s,s,成立，则称向量,是向量组,1,2,s,的,线性组合,或称,可由向量组,1,2,s,线性表示,。,27,基础知识,（一）、,向量,3、,线性相关与线性无关,：,设,1,2,s,为一组,n,维向量，如果存在一组不全为零的数,k,1,k,2,k,s,使得,k,1,1,+k,2,2,+k,s,s,=0,成立，则称向量组,1,2,s,线性相关,；,如果上式仅当,k,1,=k,2,=k,s,=0,时成立，则称向量组,1,2,s,线性无关,。,28,基础知识,（一）、,向量,4、,极大线性无关组,：,设,1,2,s,为一组,n,维向量，如果向量组中有,r,个向量,线性无关,，,且向量组的任意,r+1,个向量,线性相关,，,则这,r,个,线性无关,的向量称为向量组,1,2,s,的一个,极大线性无关组,。,向量组,1,2,s,中的每一个向量都可由其,极大线性无关组,线性表示,。,29,基础知识,（二）、,矩阵,1,、定义,：,由,mn,个数,a,ij,(i=1,2,m;j=1,2,n),排列成,m,行,n,列的数表,称为,mn,矩阵,，,简记为,A=（a,ij,）,mn,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,mn,30,基础知识,（二）、,矩阵,2、,矩阵A的秩,：,设,A=（a,ij,）,mn,为一个,mn,阶矩阵，若矩阵中极大线性无关,列向量,的个数为,k，,则称矩阵,A,的秩为,k，,记作,r（A）=k。,A=,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,mn,31,基础知识,（二）、,矩阵,3、,矩阵的初等行变换,：,1,。,交换矩阵的两行,；,2,。,以一个非零的数,k,乘以矩阵的某一行,；,3,。,把矩阵的某一行的,k,倍加到另一行,。,矩阵的初等变换,不改变矩阵的秩，且不改变其行（列）向量间的线性关系,。,32,一般形式,Opt.,f,(,x,i,y,j,),s.t,.,g,h,(,x,i,y,j,),0,h=1,2,m,其中,：,f,g,h,为（一般或广义）函数,x,i,为决策变量（可控制）,y,j,为已知参数,实例,:,线性规划模型,最优化模型,33,