国防科技大学《运筹学》课件-第1章概论

第一章

绪论国防科技大学《运筹学》射线在杀伤癌细胞的同时，也破坏正常细胞；如何确定射向与辐射剂量，在保障疗效情况下尽量少伤害正常细胞？从“RadiationTherapy”说起以两个射向为例从“RadiationTherapy”说起区域吸收的部分(平均)总体平均剂量约束（Kilorad）射线1射线2健康的解剖组织0.40.5Minimize关键组织0.30.1≤2.7肿瘤一般区域0.50.5=6肿瘤中心0.60.4≥6归结为如下的运筹学模型：可解得x1=7.5,x2=4.5，即两个射向的辐射剂量分别为7.5和4.5单位，达到问题优化目标。从“RadiationTherapy”说起事情能做的更好吗？——目标：最小→“优”资源与条件的限制？——约束：前提与界限能选择或改变什么？——变量：主观能动的范围

针对这三个方面进行定量化、模型化与优化！运筹学

——运用定量方法研究“决策优化”的应用学科从“RadiationTherapy”说起1.运筹学释义2.运筹学的发展简史3.运筹学的研究对象与基本特征4.运筹学的研究步骤5.运筹学的研究分支6.运筹学的展望7.课程说明绪论二战期间，由于作战的迫切需要，盟军对作战中出现的一些问题尝试运用数学方法研究，取得了显著成效，由此使得军事研究者越来越多地将数学方法应用到军事领域中。战后，相关理论方法逐渐在民用领域得到拓展应用，由此产生了一门新的学科——运筹学（OperationalResearch,OR）。运筹学最初是从军事领域中发展起来的运筹学释义绪论1938年，英国人A.P.罗威，提出“OperationalResearch”这个术语；OperationalResearch在美国称为OperationsResearch，

英文缩写均为OR；50年代起，欧美一些国家将用于作战研究的理论和方法广泛用于社会经济各领域，但仍沿用原词，使OR的含义有了扩展；1956年,中国学术界通过钱学森、许国志等科学家的介绍，了解这门学科后，有关专家共同商定将OR译为“运筹学”。运筹学释义绪论

“…夫运筹帷幄之中，决胜于千里之外,吾不如子房；镇国家，抚百姓，给馈饷，不绝粮道，吾不如萧何；连百万之众，战必胜，攻必克，吾不如韩信…”——《史记·高祖本纪》运筹学（OperationalResearch,OR）运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者优化决策提供定量依据。——《中国大百科全书》运筹学释义绪论1.运筹学释义2.运筹学的发展简史3.运筹学的研究对象与基本特征4.运筹学的研究步骤5.运筹学的研究分支6.运筹学的展望7.课程说明绪论19451960’s萌芽时期形成时期发展时期大致可分为三个时期：now运筹学的发展简史绪论朴素的运筹学思想自古有之萌芽时期绪论田忌赛马丁渭主持皇宫修建《孙子兵法》是千百次战争中，军事运筹经验的总结《三国演义》可称之为军事运筹实用专著

“…用兵之法，十则围之，五则攻之，倍则分之，敌则能战之，少则能逃之，不若则能避之。故小敌之坚，大敌之擒也”——《孙子兵法·谋攻》萌芽时期绪论哥尼斯堡七桥问题L.Euler（1707-1783）图1736年，欧拉解决了柯尼斯堡七桥问题，并且发表了论文《关于位置几何问题的解法》，对一笔画问题进行了阐述，是最早运用图论和拓扑学的典范朴素的运筹学思想自古有之1916年，英国工程师兰彻斯特（Lanchester）建立了描述作战双方兵力损耗的数学方程——Lanchester方程。萌芽时期绪论F.

W.

LanchesterA.K.Erlang1917年，丹麦工程师爱尔朗（Er-lang）在哥本哈根电话公司研究电话通信系统时，提出了排队论的一些著名公式。1947年，美国数学家丹捷格（Dantzig）提出了解决一种最优化问题的单纯形法，该方法奠定了线性规划的基础，使得经济学、环境科学、统计学应用等学科获得了迅速发展。萌芽时期绪论G.

B.Dantzig

1939年，前苏联学者康托洛维奇（Kantorovich）在解决工业生产组织和计划问题时，已提出类似线性规划模型，并给出了“解乘数法”的求解方法。L.V.Kantorovich1944年，冯·诺依曼和摩根斯坦合著的《对策论和经济行为》是对策论的奠基作，同时该书隐约指出了对策论与线性规划对偶理论的紧密联系。萌芽时期绪论J.

V.Neumann

最早投入运筹学领域工作的诺贝尔奖金获得者，美国物理学家勃拉凯特领导了第一个以运筹学命名的小组。由于人员复杂，人们称之为“勃拉凯特”马戏团。P.M.S.Blackett第二次世界大战期间，美、英等国，特别是海空军，广泛开展了相关研究应用，获得众多成果和巨大效益，直接促成（军事）运筹学学科的形成。随之产生的理论成果主要有：线性规划、整数规划、图论、网络流、几何规划、非线性规划、大型规划、随机服务理论、随机模拟技术、存储理论及最优控制理论等。两次世界大战极大促进了相关理论方法的发展萌芽时期绪论运筹学的形成时期是第二次世界大战结束到60年代中期。19451960’s萌芽时期形成时期发展时期now运筹学的发展简史绪论英国于1945年底成立了军事部门所属的运筹小组，并着手研究：后勤、武器装备、战斗训练、供应和管理等方面的问题。1946年10月，美空军成立了作战分析部，和工业部门建立了紧密的联系，在其支持下著名的兰德公司得以成立和发展。50年代末，在美国大约有半数的大型公司在自己的经营管理中应用运筹学。战后对相关理论方法的整理直接促成了学科的形成形成时期绪论RandCorp.

各类研究组织成立、开始出版专著、大学也设置相关专业，标志运筹学作为学科的形成二战后，很多国家相继成立了运筹学会，包括英国(1948)，美国(1952)、法国(1956)、日本(1957)等第一本专著为《MethodsofOperationsResearch》(1952年)，1950年代美国、英国的大学陆续开始开设运筹学专业课程第一本专业杂志《OperationalResearchQuarterly》于1950年在英国出版，1959年成立了国际运筹学联合会(IFORS)，我国于1982年加入20世纪50年代，钱学森、许国志等教授将运筹学引入我国，开始了我国学科意义上的运筹学研究和应用形成时期绪论运筹学的发展时期是上世纪60年代中期到现在。19451960’s萌芽时期形成时期发展时期now运筹学的发展简史绪论运筹学的发展是与现代社会的发展、特别是工业生产、经济管理以及计算机技术的广泛应用密切联系在一起的。广泛渗透到现代社会的各个领域，应用范围不断拓展，产生了巨大的经济和社会效益运筹学的理论不断得到完善，形成了一系列强有力的分支学科，同时数学基础日益成熟运筹学工作者（运筹分析家）逐步成为一类数量庞大的职业，美国当前从业人员超过10万人，并成为热门职业计算机技术的发展，为运筹学提供了强大的计算工具发展时期绪论发展时期绪论运筹学应用产生的巨大经济效益（举例）组织应用效益（美元）联合航空公司以最低成本进行订票及安排机场工作班次600万Citgo石油优化炼油程序及产品供应、配送及营销7000万荷马特发展公司优化商业区和办公楼销售程序4000万AT&T优化商业用户的电话销售中心选址4.06亿，更多销售标准品牌公司控制成品库存（制定最优再订购点和订购量，确保库存）380万施乐公司缩短维修机器的反应时间和改进维修人员的生产率生产率提高50%以上宝洁公司重新设计北美生产和分销系统以降低成本并加快了市场进入速度2亿法国国家铁路制定最优铁路时刻表并调整铁路日运营量1500万Delta航空公司进行上千个国内航线的飞机优化配置来最大化利润1亿IBM重组全球供应链，保持最小库存的同时满足客户需求第一年7.5亿Merit青铜制品公司安装统计销售预测和成品库存管理系统，改进客户服务更优的服务国际运筹与管理科学协会（INFORMS）统计我国运筹学在该时期迅速发展1980年成立运筹学会，《运筹学学报》在上海创刊1982年加入国际运筹学联合会1984年我军军事运筹学学会成立，办事机构设在国防科大《运筹与管理》、《军事运筹与系统工程》等杂志相继问世发展时期绪论1.运筹学释义2.运筹学的发展简史3.运筹学的研究对象与基本特征4.运筹学的研究步骤5.运筹学的研究分支6.运筹学的展望7.课程说明绪论传统自然科学是广义的“物理”学，“硬件”人类的生产生活中还有“人”与“事”的方面，“软件”运筹学的研究对象绪论

“事”－－事情、事务凡人们从事的活动，包括人与人的交往、合作、争斗都包括了人对物的使用和改造以及人与人的对抗活动。

“事理”－－做事的道理

主要解决如何去安排所拥有的人力、物力等资源来取得更好的效果，集中于回答“怎样去做，怎么做好”的问题。运筹学以“事理”为研究对象

“物理-事理-人理”（WSR）综合方法懂物理、明事理与通人理物理事理人理对象与内容客观物质世界的法则；物的原理资源的组织运用（人与物之间的关系）；做事的道理;人与人之间的关系；为人处理的道理等核心问题是什么？功能分析怎么做？逻辑分析最好怎么做？人文分析目标与原则诚实；追求真理协调；追求效率和谐；追求成效知识领域自然科学类运筹学系统科学管理学社科科学等运筹学的研究对象绪论

整体观念

多学科综合

模型方法的应用

“事理”研究的综合性、复杂性决定运筹学研究的基本特征：运筹学研究的基本特征绪论模型有三种基本形式：

（1）形象模型；（2）模拟模型；（3）符号或数学模型。构造模型是一种创造性劳动，成功的模型往往是科学和艺术的结晶。运筹学在解决问题时，按研究对象不同可构造各种不同的模型运筹学研究的基本特征绪论1.运筹学释义2.运筹学的发展简史3.运筹学的研究对象与基本特征4.运筹学的研究步骤5.运筹学的研究分支6.课程说明绪论提出和形成问题建立模型模型求解解的检验解的控制解的实施反馈与迭代以优化为目标，以量化为手段，以模型为核心运筹学的研究步骤绪论1.运筹学释义2.运筹学的发展简史3.运筹学的研究对象与基本特征4.运筹学的研究步骤5.运筹学的研究分支6.运筹学的展望7.课程说明绪论运筹学的研究分支线性规划（LinearProgramming）图与网络分析（GraphTheoryandNetworkAnalysis）排队论，存储论，对策论，决策论整数规划（IntegerProgramming）非线性规划（NonLinearProgramming）动态规划（DynamicProgramming）绪论

[放射治疗问题]确定最好的治疗方案线性规划问题——示例1线性规划的数学模型绪论整数规划问题——示例

[指派问题]

要将一份中文说明书，要译成英、日、德、俄四种文字，记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书译成不同语种的说明书所需时间如表所示。问应指派每人去完成何工作（每人做一件，每件一人做），使所需总时间最少？绪论[中国邮递员问题]

一个邮递员送信，从邮局出发，要走完他负责投递的全部街道，完成后又回到邮局。应该按什么路线走，所走的路程最短。把此问题抽象为图的语言就是：给定一个连通图，在每边上赋予一个非负的权。求一个圈，过图的每边至少一次，并使圈的总权最小。图与网络分析——示例绪论[排队系统的优化问题]某医院手术室根据病人来诊和完成手术时间的纪录，任意抽查100个工作小时，每小时来就诊的病人数n的出现次数如下左面的表。又任意抽查了100个完成手术的病历，所用时间v（小时）出现的次数如下右面表。问该手术室的繁忙程度如何，病人做手术平均需要多长时间，新病人到来一般要等多长时间，是否应考虑增加手术台？排队论——示例到达的病人数n出现次数fn

0123456以上

102829161061合计100手术时间v(小时)出现次数fv

0.0-0.20.2-0.40.4-0.60.6-0.80.8-1.01.0-1.21.2以上3825179650合计100绪论

[探油决策问题]石油公司欲在某地钻探石油，有两个方案：先做试验再决定钻井与否；不试验而只凭经验决定钻井与否。试验费每次0.3百万元，钻井费为1百万元。直接钻井，出油的概率为0.55，不出油的概率为0.45。若先进行试验，依地质条件估计，地质条件好与不好的可能为0.6和0.4，而好的地质条件出油与不出油的概率分别为0.85和0.15，不好的地质条件出油与不出油的概率分别为0.10和0.90。若出油公司有4百万元收益，不出油则收益为0。如何决策公司期望收益最大。决策论——示例绪论决策树－－多级决策绪论决策论——示例已经在现代社会中的诸多领域得到深入应用，包括市场销售，生产计划，库存管理，运输问题，财政和计划，人事管理，设备维修与更新，工程的优化设计，计算机和信息系统，城市管理等。运筹学方法有助于提高分析、解决社会卫生和医疗事业管理及相关政策制定的水平。医疗收费与财务管理医疗卫生资源优化配置饮食与疾病预防治疗方案评价与优化运筹学的应用领域

……绪论1.运筹学释义2.运筹学的发展简史3.运筹学的研究对象与基本特征4.运筹学的研究步骤5.运筹学的研究分支6.运筹学的展望7.课程说明绪论

作为新兴学科，运筹学将向哪个方向发展？运筹学的展望绪论

美国前运筹学会主席邦特认为运筹学应在三个领域发展：运筹学应用、运筹科学、运筹数学。并强调发展前两者，从整体上讲应协调发展。运筹学界一些观点：20世纪70、80年代注意研究大系统，注意与系统分析相结合除了常用的数学方法外，还引入了一些非数学的方法和理论“将过分理想化的最优解换成满意解”，“以易变