运筹学Chap.1绪论

第1页运筹帷幄之中决胜千里之外OPERATIONSRESEARCH运筹学第2页运筹学的产生与发展运筹学的主要内容与学时安排运筹学在管理中的应用学科特点及学习方法考试与要求参考文献绪论(Introduction)第3页•公元前4世纪，战国时期的孙膑“斗马术”是我国古代运筹思想中争取总体最优的脍炙人口的著名范例（记载于《史记·孙子吴起列传》）。齐将田忌与齐王赛马，孙膑献策：以下马对齐王上马，以上马对齐王中马，以中马对齐王下马，结果田忌以一负两胜而获胜。他的基本思想是不强求一局的得失，而争取全盘的胜利(局部最优、全局最优)。（乒乓运动团体赛）第4页20世纪40年代初，是第二次世界大战最紧张时期，当时英、美两国发明和制造了包括雷达、火炮、深水炸弹等一批新式武器，但如何有效地使用这些武器却远远落后于这些武器的制造。运筹学作为一门学科，起源于第二次世界大战期间的军事运筹活动。第5页•1939-1942年，运筹学的研究在英国军队各个部门迅速扩展，并纷纷成立运筹学小组。美国人很快注意到英国运筹学对作战指挥成功的运用，并在自己的军队中也逐渐建立起各种运筹学小组，美国人称这种工作为“OperationsResearch”或“OperationsAnalysis”(运筹学或运筹分析，或直译为作战研究或作战分析)。•这些军事运筹学小组的工作从雷达系统的运行开始，一直到战斗机群的拦截战术，空军作战战术评价，防止商船遭受敌方潜艇的攻击，改进深水炸弹投放的反潜艇战术等等，第6页大西洋反潜战1941-1942年，德国潜艇严密封锁了英吉利海峡，企图切断英国的‘生命线’，英国海军数次反封锁均不成功。应英国的要求，美国派Morse率一个小组协助研究。两条重要建议1、将反潜攻击由反潜舰艇投掷水雷，改为飞机投掷深水炸弹，起爆深度由100米左右，改为25米左右，即当德方潜艇刚下潜时攻击效果最佳；使德国潜艇被摧毁数增加到400%；2、运送物资的船队及护航舰艇编队，由小规模多批次，改为加大规模，减少批次。第7页船只在受到敌机攻击时的逃避策略对付威胁美国太平洋舰队的日本神风攻击机（自杀飞机）的问题是军舰应该急速改变航向以扰乱俯冲的自杀飞机的瞄准，还是应保持航行不变以改善己方防空火力的瞄准？运筹小组分析了477次战例，自杀飞机命中战舰172次，击沉舰只27次。研究结果：大舰受到俯冲的神风机攻击时，应该急速地改变航线；而小舰则应该慢慢变。还发现当攻击机从高空俯冲时，舰只应以船舷迎向攻击机；而从低空俯冲时，应以首尾相向。中弹数由47%下降到29%。第8页•二次大战胜利后，美英各国不但在军事部门继续保留了运筹学的研究核心，而且在研究人员、组织的配备及研究范围和水平上，都得到了进一步的扩大和发展，同时运筹学方法也向政府和工业等部门扩展。在这些新领域的研究中，得到很多大学的支持，签订了不少协作研究的合同,大批专门从事研究的公司也逐渐成立，如著名的RAND（兰德）公司就是在1949年成立的。第9页•名称的由来：OperationResearch、运筹帷幄“史记”、运作研究•发展历程：运筹学作为一门数学学科，用纯数学的方法来解决最优方法的选择安排，却是在二十世纪四十年代才开始兴起。二战以前萌芽二战期间产生五六十年代发展七八十年代成熟一、运筹学的产生与发展第10页•1951年出版了新版（1946年的原版是保密的，1948年才撤销保密）的P.M.Morse（莫斯）和G.E.Kimball（金博尔）的《运筹学方法》（MethodsofOperationsResearch），这是二战结束后，对战时整个运筹学工作做系统的专业叙述的一本著作。运筹学的定义：1、为决策机构在其控制下业务活动进行决策时，提供以数量化为基础的科学方法。第11页2、运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。3、运筹学是一种给出问题坏的答案的艺术，否则的话问题的结果会更坏。4、运筹学是研究用科学方法来决定资源不充分的情况下如何最好地设计人—机系统，并使之最好运行的一门学科。第12页•成熟的学科分支向纵深发展•新的研究领域产生•与新的技术结合•与其他学科的结合加强•传统优化观念不断变化（并行子空间法、协同优化方法）运筹学的发展趋势第13页二、主要教学内容与学时安排第一章：绪论（2）第二章：线性规划和单纯形法（6）第三章：线性规划对偶理论及其应用（2）第四章：目标规划（4）第五章：整数规划（4）第六章：动态规划（4）第八章：库存论（3）第七章：网络优化模型（4）第五章：决策论（3）第14页•数学规划–线性规划约束条件和目标函数都是线性函数的数学规划；主要解法是：单纯形法；主要应用于企业规划和工农业的管理决策等方面。–非线性规划它是线性规划的进一步发展和继续。许多实际问题如设计问题、经济平衡问题都属于非线性规划的范畴。–整数规划整数规划是研究决策变量取正整数或部分取整数的一类规划问题。（人员分工指派问题）第15页某工厂用三种原料生产三种产品，已知的条件如表所示，试制订总利润最大的生产计划单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）354例:生产计划问题第16页问题分析可控因素：每天生产三种产品的数量，分别设为321,,xxx目标：每天的生产利润最大利润函数321453xxx受制条件：每天原料的需求量不超过可用量：原料1P：15003221xx原料2P：8004232xx原料3P：2000523321xxx蕴含约束：产量为非负数0,,321xxx第17页模型321453maxxxx15003221xxs.t.8004232xx2000523321xxx0,,321xxx是研究者对客观现实经过思维抽象后用文字、图表、符号、关系式以及实体模样描述所认识的客观对象。第18页计算结果OBJECTIVEFUNCTIONVALUE2675.000VARIABLEVALUEREDUCEDCOSTX1375.0000000.000000X2250.0000000.000000X375.0000000.000000ROWSLACKORSURPLUSDUALPRICES1)0.0000001.0500002)0.0000000.6250003)0.0000000.300000第19页•模型要素变量—可控因素目标—优化的动力和依据约束—内部条件和外部约束•研究内容建模概念最优性条件算法灵敏度分析最优化模型第20页设要从甲地调出物质2000吨，从乙地调出物质1100吨，分别供给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费(单位百元)如表所示：假定运费与运量成正比，问怎样才能找出运费最省的调拨计划?ABCD甲地2125715乙地51513715问题线性规划模型第21页建模分析可控因素：从输出地运往输入地的货物数量，记.4,3,2,1,2,1;jixij表示从i地运往j地的货物数量。目标：总运输费用达到最小费用函数为：2423222114131211153751511572521xxxxxxxx受限制条件：从某地运出的货物数量总和不超过该地可运总量，从某地运入货物总量不少于该地需要总量即100200110017001100200024142313221221112423222114131211xxxxxxxxxxxxxxxx线性规划模型第22页•模型2423222114131211153751511572521minxxxxxxxx1002001100170011002000..24142313221221112423222114131211xxxxxxxxxxxxxxxxts线性规划模型第23页参数规划参数规划是系数或常数项中带有参数的规划问题，主要研究问题的解法：当参数在什么范围变化时问题有解以及参数的变化对最优解的影响。动态规划它是与时间有关的规划问题，它是研究多阶段决策过程最优化问题。目标规划目标规划就是在给定的决策环境中，使决策结果与预定目标的偏差达到最小的数学模型。与线性规划有很大的区别，主要表现在：在线性规划中，要求单个目标的优化，而目标规划则强调使多个目标得到满意的解答。另一方面，线性规划中，为得到一个可行解，必须满足所有的约束条件。第24页•排队论它是运筹学的又一个分支，它也叫做随机服务系统理论。它的研究目的是要回答如何改进服务机构或组织被服务的对象，使得某种指标达到最优的问题。因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用研究随机现象的概率论作为主要工具。•库存论它是一种研究物资最优存储及存储控制的理论。第25页•图论图论是研究由节点和边所组成的图形的数学理论和方法•博弈论博弈论是使用严谨的数学模型研究冲突对抗条件下最优决策问题的理论。第26页囚徒A坦白不坦白囚徒B坦白不坦白－8,－80,－10－10,0－1,－1这个例子本身就部分奠定了非合作博弈论的基础。囚徒的困境(prisoners’dilemma)第27页市场进入阻挠猜硬币博弈石头·剪子·布默许在位者进入者进入不进入斗争40,50－10,00,3000,300猜硬币方正反正反盖硬币方－1,11,－11,－1－1,1石头剪子布石头剪子布0,01,－1－1,1－1,10,01,－11,－1－1,10,0AB第28页三、运筹学在管理中的应用1、市场营销管理（1）广告（广告费一定的情况下，受众面广，效益高等；报纸、电台、电视、广告牌、发传单等形式的优选）（2）产品定价（3）新产品开发（4）销售计划第29页三、运筹学在管理中的应用2、生产计划与管理生产、存储和劳动力的配合合理下料、配料问题、物料管理3、库存管理物质库存量管理、停车场的大小、计算机内存的大小第30页三、运筹学在管理中的应用4、交通运输问题空运、水运、公路运输、铁路运输、管道运输、厂内运输路线选择和行车时刻表（优化调度）5、会计与财务分析及管理预算、贷款、成本分析、资金管理第31页三、运筹学在管理中的应用6、人力资源管理人员需求、人员工作分配、人才评价、工资和津贴的确定等。7、设备维修、更新和可靠性、项目选择和评价等8、工程管理与优化设计9、城市规划与管理救火站、城市垃圾的清扫、搬运和处理第32页三、运筹学在管理中的应用10、计算机和信息系统内存分配、文件寻找第33页•引入数学方法解决实际问题--定性与定量方法结合•系统与整体性--从全局考察问题•应用性--源于实践、为了实践、服务于实践•交叉学科--涉及经济、管理、数学、工程和系统等多学科•开放性--不断产生新的问题和学科分支•多分支--问题的复杂和多样性四、学科特点与学习方法第34页1在数学学科中的地位运筹数学1在系统科学中的地位系统工程1在管理科学中的地位管理与运筹学1与经济学的关系问题与方法1与工程科学的关系方法与应用1与计算机科学的关系核心算法与工具基础理论应用理论应用技术运筹学运筹学的学科地位第35页•理论学习•方法应用•案例分析•上机练习学习方法第36页考核范围：课堂所讲授的内容考试：70%平时成绩：30%要求：能用最优化方法解决实际问题（1）从现实生活中抽出本质的要素来构造数学模型，寻求一个跟决策者的目标有关的解；（2）探索求解的结构并导出系统的求解过程；（3）从可行方案中寻求系统的最优解法。五、考试与要求第37页•廖敏，运筹学基础与应用，南京大学出版社，南京，2009年•徐玖平、胡知能，运筹学：数据-模型-决策科学出版社，北京，2009年•胡运权等，运筹学基础及应用（5版），高等教育出版社，北京，2008年•姚运，宋振明，运筹学基础教程，河海大学出版社，南京，2009年六、参考资料