运筹学

1运筹学(OperationResearch)MBA学位课程衷心希望本课程能让大家受益2教师介绍姓名：刘满凤职称：教授博士单位：江西财经大学科研处副处长电话：3823072（O）3816926（H)，13627086942E-mail:[e-mail]3课程内容简介与学习要求•课程内容简介运筹学是一门应用性学科，它主要是应用定性分析和定量分析相结合的方法，通过建立实际问题的数学模型，应用合适的优化算法对模型进行求解，从而解决实际问题。其主要内容有：线性规划、运输模型、整数规划、动态规划、图与网络分析、排队论、存贮论、对策论、决策论、等。•学习要求本课程将通过重点讲授原理方法、上机解题、个人研究与小组讨论相结合的案例分析等环节，培养学员全局优化的思想，使学员掌握若干类常用的运筹学模型，并能用其解决经济管理中的复杂问题。因此要求学员：对布置的思考、案例讨论题进行认真准备，按进度完成平时作业和上机练习，按要求完成大作业书面报告。•参考资料（1）刘满凤、付波、聂高飞编著《运筹学模型与方法教程例题分析与题解》，清华大学出版社，2001年。（2）《运筹学》教材编写组编《运筹学》（修订版），清华大学出版社，1996年。（3）DimitrisBertsimas,RobertM.Freund,《数据、模型与决策》,中信出版社，2004。（4）弗雷德里克.S.希利尔,马克.S.希利尔,《数据、模型与决策》，中国财政经济出版社。2004（5）胡运权主编《运筹学》（修订版），清华大学出版社，2002年（6）FrederickS.Hillier《IntroductiontoOperationsResearch》，机械工业出版社，19994本课程内容安派：第一部分线性规划及其应用第三部分动态规划1、动态规划的基本概念和最优化原理2、动态规划模型的建立和求解方法3、建模训练与求解第四部分对策论模型第五部分决策论1、两人有限零和对策模型及其解法2、两人有限非零和对策1、图与网络的基本概念2、最短路问题3、最大流问题4、最小费用最大流问题5、关键路线（CPM）与计划评审法（PERT）第二部分整数规划及其应用1、整数规划的数学模型及其特点2、分枝定界法3、0-1规划的解法4、指派问题的解法1、问题的数学模型与求解2、单纯形法与计算机求解3、对偶理论与灵敏度分析4、运输问题及其解法第六部分图与网络分析1、决策问题的基本概念2、决策问题的基本方法3、信息分析5第一章绪论1.1运筹学的定义1.2运筹学的工作步骤1.3运筹学的模型1.4运筹学的发展简史61.1运筹学定义（OperationsResearchOR）由于运筹学研究的广泛性和复杂性，人们至今没有形成一个统一的定义。以下给出二种有代表性定义：运筹学是依据给定目标和条件从众多方案中选择最优方案的最优化技术。运筹学是一门寻求在给定资源条件下，如何设计和运行一个系统的科学决策的方法71.2运筹学的工作步骤运筹学在解决大量实际问题的过程中形成了自己的工作步骤：1.提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数，搜集有关资料。2.建立模型：即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来。3.求解：用各种手段(主要是数学方法，也可用其它方法)将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机,解的精度要求由决策者提出。84.解的检验：首先检验求解步骤和程序有无错误，然后检查解是否反映现实问题。5.解的控制：通过控制解的变化过程决定对解是否要作一定的修改。6.解的实施：是指将解用到实际中去，必须考虑到实际的问题，如向实际部门讲清楚解的用法，在实施中可能产生的问题等。以上过程应反复进行。9真实系统系统分析问题描述模型建立与修改模型求解与检验结果分析与实施数据准备运筹学工作的步骤101.3运筹学模型运筹学研究的模型主要是抽象模型——数学模型。数学模型的基本特点是用一些数学关系（数学方程、逻辑关系等）来描述被研究对象的实际关系（技术关系、物理定律、外部环境等）。11运筹学模型的一个显著特点是它们大部分为最优化模型。一般来说，运筹学模型都有一个目标函数和一系列的约束条件，模型的目标是在满足约束条件的前提下使目标函数最大化或最小化。121.4运筹学的发展简史1、朴素的运筹思想：都江堰水利工程战国时期（大约公元前250年）川西太守李冰父子主持修建。其目标是：利用岷江上游的水资源灌溉川西平原。追求的效益有防洪与航运。其总体构思是系统思想的杰出运用。13都江堰由三大工程及120多项配套工程组成：1.“鱼嘴”岷江分水工程：将岷江水有控制地引入内江。2.“飞沙堰”分洪排沙工程：将泥沙排入外江。3.“宝瓶口”引水工程：除沙后的江水引入水网干道。14它们巧妙结合，完整而严密，相得益彰。两千多年来，这项工程一直发挥着巨大的效益，是我国最成功的水利工程。都江堰水利工程15丁谓的皇宫修复工程北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、运输及清废用“一沟三用”巧妙地解决了，体现了系统规划的思想。16田忌赛马齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排：齐王上中下田忌下上中最终净胜一局，赢得1000金。172、早期的军事运筹学特拉法加尔（Trafalgar）海战和纳尔森（Nelson）秘诀19世纪中叶，法国拿破伦统帅大军要与英国争夺海上霸主地位，而实施这一战略的最主要的关键是消灭英国的舰队。英国海军统帅、海军中将纳尔森亲自制定了周密的战术方案。181805年10月21日，这场海上大战爆发了。英国是纳尔森亲自统帅的地中海舰队，由27艘战舰组成；另外一方是由费伦纽夫（Villenuve）率领的法国——西班牙联合舰队，共有33艘战舰。Trafalgar大海战的概况是：费伦纽夫（Villenuve）率领的法国——西班牙联合舰队采用常规的一字横列，以利炮火充分展开，而纳尔森的战术使费伦纽夫大出意外。19英国的舰队分成两个纵列：前卫上风纵列由12艘战舰组成，由纳尔森亲自指挥，拦腰将法国——西班牙联合舰队切为两段；后卫下风纵列由英国海军中将科林伍德(Collingwood)指挥，由15艘战舰组成。在一场海战后，法国——西班牙联合舰队以惨败告终：联合舰队司令费伦纽夫连同12艘战舰被俘，8艘沉没，仅13艘逃走，人员伤亡7000人。而英国战舰没有沉没，人员伤亡1663人，但是，作为统帅的纳尔森阵亡。20秘密备忘录中的纳尔森（Nelson）秘诀：预期参加战斗的英国舰队：40艘。法国—西班牙联合舰队：46艘。预计联合舰队战斗队形一字横列。英国舰队的战斗队形与任务：分成两个主纵列及一个小纵列。21英国舰队：主主小纵纵纵列2列1列（16艘）（16艘）（8艘）（12艘）（3-4艘）联合舰队（23艘）（46艘）22主纵列1：16艘，由纳尔森亲自指挥，拦腰将法国——西班牙联合舰队切为两段，并攻击联合舰队的中间部分。主纵列2：16艘，由英国海军中将科林伍德指挥，从联合舰队后半部再切断，分割并攻击后部12艘。小纵列：8艘，在中心部分附近攻击其先头部分的3-4艘。23兰彻斯特（F.W.Lanchester）作战分析兰彻斯特方程：设两军对抗中一方有x个战斗单位（战舰、战车、战机、步兵单位等），另外一方有y个战斗单位。基本假设：每一方战斗单位的损失率与对方战斗单位的数量成正比。24于是，双方战斗损失的微分方程为：dy/dt=-ax,dx/dt=-by.其中，a0与b0表示双方的平均战斗力。因此可以得到：ax2=by2上式称为兰彻斯特N2定律。25用兰彻斯特N2定律可以对“纳尔森（Nelson）秘诀”进行分析：整体战斗实力。设双方单个战斗单位的战斗力相同，则有：英国舰队：402=1600联合舰队：462=2116此时联合舰队占优势，设想联合舰队全歼英国舰队后，联合舰队还有5161/2=23艘。26•将联合舰队拦腰切断，23+23=46，是将联合舰队实力减弱的最小分割法。此时，联合舰队的实力为：232+232=1058而英国舰队的实力为：（16+16）2+82=1088，已略占有优势。27在英国舰队两个主纵列共32艘，攻击联合舰队的后一半23艘，此时，英国舰队实力：（16+16）2=322=1064联合舰队的实力为：232=52928英国舰队已占有优势。在全歼联合舰队后部后，英国舰队两个主纵列还可以保留：（1064-529）1/2=5161/2=23艘，再与小纵列中舰队联合对联合舰队前部作战还占有优势。即在最坏情况下，“纳尔森（Nelson）秘诀”也可以使英国舰队获得胜利。29鲍德西（Bawdsey）雷达站的研究（1935年）1935年，英国科学家R.Watson-Wart发明了雷达。丘吉尔命令在英国东海岸的Bawdsey建立了一个秘密雷达站。当时，德国已拥有一支强大的空军，起飞17分钟即到达英国本土。在如此短的时间内，如何预警和拦截成为一大难题。301939年由曼彻斯特大学物理学家、英国战斗机司令部顾问、战后获得诺贝尔奖金的P.M.S.Blackett为首，组织了一个小组，代号“Blackett马戏团”。这个小组包括三名心理学家、一名理论数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官、一名测量员。31研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。“Blackett马戏团”在秘密报告中使用了“OperationalResearch”，即“运筹学”。32大西洋反潜战（1942年）1942年，美国大西洋舰队反潜战官员W.D.BAKER舰长请求成立反潜战运筹组，麻省理工学院的物理学家P.W.MORSE被请来担任计划与监督。33MORSE出色的工作之一，是协助英国打破了德国对英吉利海峡的封锁。1941-1942年，德国潜艇严密封锁了英吉利海峡，企图切断英国的“生命线”。海军几次反封锁，均不成功。34应英国要求，美国派MORSE率领一个小组去协助。MORSE经过多方实地考察，最后提出了两条重要建议：•将反潜攻击由反潜潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由100米左右改为25米左右。即当潜艇刚下潜时攻击效果最佳。(提高效率4-7倍)35•运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次，这样，损失率将减少。（25%下降到10%）丘吉尔采纳了MORSE的建议，最终成功地打破封锁，并重创了德国潜艇。MORSE同时获得英国和美国的最高勋章。36战略核武器杀伤力模型美国和苏联从六十年代起就展开了激烈的核武器竞争。六十年代初期，苏联主张武器往大型化方向发展，其理由是武器的威力越大，杀伤力越强。但美国有人认为：虽然武器的威力越大，杀伤力越强，但武器杀伤力不全取决威力，还与准确度有关，如果武37器的威力大而准确度低，其杀伤力未必就大。反之，虽然威力小但准确度高，杀伤力也可能大。杀伤力K不仅与威力Y有关，而且与精度C有关。经过大量的模拟试验，将有关数据经过处理和分析，利用蒙特卡洛拟合而得K、Y、C的函数关系：K=Y2/3/C238由这个模型，容易得当Y*=8Y时，K*=4K，即威力提高8倍，杀伤力仅提高4倍。当C*=C/8时，K*=64K，即精度提高8倍，杀伤力可以提高64倍。这说明提高精度合理，因而美国走提高武器精度的道路。39海湾战争中的作战模拟（1990年8月）《TheCommanders》一书描述了美国最高当局如何策划入侵巴拿马和如何策划海湾战争，书中透露美国国防部长切尼在海湾战争准备阶段曾因拿不准美国在这场战