运筹学01绪论

现代工程数学（运筹学）北航软件学院李卫国[e-mail]2011.9培养运用各种运筹学方法和技术去解决实际问题的能力。数学规划部分以线性规划和整数规划为重点，组合优化部分主要讲网络优化，随机优化部分主要简介决策论和对策论。以课堂授课为主，课内外相结合。要求：投入一定课外时间读书、翻资料、案例分析和课后习题（1：2）教学计划•考核内容上课考勤10%案例分析论文40%期末考试50%考试要求•胡运权，运筹学基础及其应用（主教材），高等教育出版社，北京，2004年•邱菀华等，运筹学教程，机械工业出版社，北京，0004年•HillierandLieberman，IntroductiontoOperationsResearchMcGraw-HillPublishingCompany教材与参考资料绪论运筹学（OperationsResearch）是系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学——ManagementScience运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，应用分析、试验、量化的方法,从众多方案中为决策者提供有依据的最优方案,解决从生产与社会实践提炼出来的问题”，故又称为最优化技术。•名称的由来OperationResearch（运作研究？）运筹学——运筹帷幄“史记”•发展历程运筹学的由来与发展二战以前萌芽二战期间产生五六十年代发展七八十年代成熟1938年英国最早出现了军事运筹学，命名为“OperationalResearch”,1942年，美国从事这方面工作的科学家命其名为“OperationsResearch”这个名字一直延用至今。美国运筹学的早期著名工作之一是研究深水炸弹起爆深度问题。当飞机发现潜艇后，飞机何时投掷炸弹及炸弹的引爆度是多少？运筹学工作者对大量统计数字进行认真分析后，提出如下决策：1)仅当潜艇浮出水面或刚下沉时，方投掷深水炸弹。2)炸弹的起爆深度为离水面25英尺（这是当时深水炸弹所容许的最浅起爆点）。空军采用上述决策后，所击沉潜艇成倍增加，从而为运筹学增添了荣誉。运筹学在中国中国运筹学会理事长章祥荪运筹学在中国中国古代运筹思想OperationsResearch(OperationalResearch)在中文里翻译为“运筹”。来源——公元前三世纪楚汉相争中，汉高祖刘邦的谋士张良常出谋献策，为刘邦打败项羽，推翻秦朝，统一中国立下大功。刘邦称誉他“运筹帷幄之中，决胜千里之外”。运筹学在中国运筹学的性质运筹学是从本世纪三四十年代发展起来的一门新兴学科，它的研究对象是人类对各种资源的运用及筹划活动，它的研究目的在于了解和发现这种运用及筹划活动的基本规律，以便发挥有限资源的最大效益，来达到总体、全局最优的目标。这里所说的“资源”是广义的，既包括物质材料，也包括人力配备；既包括技术装备，也包括社会结构。运筹学在中国现代运筹学发展简史真正作为一门新兴学科的系统研究并予以正式命名的运筹学这段辉煌的创业史，是在二次大战前后揭开的。二次大战胜利后，美英各国运筹学的研究不但在军事部门继续予以保留，而且研究队伍还进一步得到扩大和发展，同时在政府和工业部门也开始推行运筹学方法，筹建运筹学小组。运筹学在中国中国古代的对策论公元前四世纪战国时期齐国的将军田忌与齐王赛马的故事。双方各遣三马一对一比赛。孙膑发现田忌的马虽然不如齐王的，但相差不多。于是献策：以下马对齐王的上马，以上马对齐王中马，以中马对齐王下马，结果田忌以二比一获胜。今天来讲，这就是简单的对策论。运筹学在中国古代工程中的运筹思想宋真宗时（公元1008-1017）宫廷失火，需要重建。采取了如下方案：先在通向宫殿的大道上就近取土，取土后大道形成深沟,于是引入汴水,成为人工小河。由此基建材料可由水路运入工地；宫殿修成后，又将基建废料弃置沟中，重新建成大道。这一方案取土近、弃土近、运输便，是工程的优化。运筹学在中国古代工程中的运筹思想宋朝沈括所著《梦溪笔谈》中记载:“庆历（公元1048）中,河决北都商胡,久之未塞。三司度支副使郭申锡亲往董作。凡塞河决，垂合，中间一埽，谓之‘合龙门’，功全在此。是时屡塞不合。时合龙门埽长六十步。有工高超者献议，以谓：‘谓埽身太长，人力不能压，埽不至水底，故河流不断，而绳缆多绝。今当以六十步为三节，每节埽长二十步，中间以索连属之。先下第一节，待其至底，方压第二、第三。’旧工争之，以为不可，云：‘二十步埽不能断漏，徒用三节，所费当倍，而决不塞。’超谓之曰：‘第一埽水信未断，然势必杀半。压第二埽，止用半力，水纵未断，不过小漏耳。第三节乃平地施工，足以尽人力。处置三节既定，即上两节自为浊泥所淤，不烦人功。’申锡主前议，不听超说。……既定而埽果流，而河决愈甚，申锡坐谪。卒用超计，商胡方定。”运筹学在中国现代运筹学在中国的兴起现代运筹学被引入中国是在五十年代后期。中国第一个运筹学小组在钱学森、许国志先生的推动下在1956年于中国科学院力学研究所成立。钱学森先生在MIT取得硕士学位，在加州理工大学（CaliforniaInstituteofTechnology）取得博士学位后成为该校的第一位Goddard讲座教授。许国志先生在堪萨斯大学取得博士学位后，在马里兰大学流体力学和应用数学研究所当研究员。他们两人是第一个运筹学小组的领导者。运筹学在中国1959年，第二个运筹学部门在中国科学院数学研究所成立，这是大跃进中数学家们投身于国家建设的一个产物。力学所小组与数学所的小组于1960年合并成为数学研究所的一个研究室，当时的主要研究方向为排队论、非线性规划和图论，还有人专门研究运输理论、动态规划和经济分析（例如投入产出方法）。运筹学在中国1963年是中国运筹学教育史上值得一提的一年，数学研究所的运筹学研究室为中国科技大学应用数学系的第一届毕业生（58届）开设了较为系统的运筹学专业课，这是第一次在中国的大学里开设运筹学专业和授课。运筹学在中国五十年代后期，运筹学在中国的应用集中在运输问题上，其中一个广为流传容易明白的例子就是“打麦场的选址问题”，目的在于解决当时手工收割为主的情况下如何节省人力和实践。国际上大家都知道的“中国邮路问题”（ChinesePostmanProblem）模型也是在那个时期由管梅谷教授提出的。所以，现在非常热门的“物流学”，在当时就有一些雏形的研究，但可惜中国的大工业落后，又不是市场环境，使我们在相当长的时期中远离了当代“物流学”的发展主流。运筹学在中国运筹学在中国的一些近期应用（1）中国运筹学近期应用的亮点是由华罗庚教授点燃的。在文化大革命期间，身为中国数学会理事长和中科院院士的他，亲自率领一个小组，大家称为“华罗庚小分队”，到农村、工厂讲解基本的优化技术和统筹方法（PERT），使用于日常的生产和生活中。自1965年起的十年中，他到了约二十个省和无数个城市，受到各界人士的欢迎，他的工作得到了毛泽东主席的肯定和表扬。华罗庚先生这一时期的推广工作播下了运筹学哲学思想的种子，大大推动了运筹学在中国的普及和发展。直到今天，许多中国公民还记得“优选法”这个词汇，但不一定知道“运筹学”。运筹学在中国粮食产量预测（2）中科院陈锡康教授提出了系统综合因素方法预测粮食产量。关键技术包括投入占用产出分析、考虑边际收益率递减的非线性预测方程，以及最小绝对和方法。自1980年始，在每年的四月底成功地预测中国全年的粮食产量，五月初报送给中国政府主要领导以及相关的政府职能部门。三个突出的特点：预测提前期在半年以上（一般预测方法提前期一般是2个月）；平均预测误差为1.6%（一般预测方法的平均预测误差为5-10%）；预报粮食产量丰、平、欠方向正确。1999年陈锡康研究员等在北京召开的第十五届IFORS大会上获得一等奖。陈锡康提供（[e-mail]）运筹学在中国金融管理与经济发展方面的运筹学应用（3）将优化及决策分析方法，应用于金融风险控制与管理、资产评估与定价分析模型等；例如陕西省运筹学会近年的一些运筹学应用:证券投资：沪深股市股指波动的交互影响效应分析深圳股市内幕交易（例资产重组）的实证分析经济发展（预测、评价、优化）：陕北果业发展决策的优化分析系统结构模型在陕北果业开发中的应用陕北水果生产基地战略方针多层次分析决策模型陕西省经济、资源、环境协调发展的相对有效性评价陕西工业可持续发展的评价及对策徐渝提供（[e-mail]）运筹学在中国工程管理基于多层次灰色决策模型的施工方案评价应用灰色理论、方法结合工程实例建立了多层次灰色决策模型对工程施工方案进行综合评价，得到了满意的结果。建设项目投资风险的仿真分析结合赢利性民用建筑项目的特点，建立了经济模型及其投资回收期仿真模型，并对仿真模型进行了精度估计徐渝提供（[e-mail]）运筹学在中国社会保障与服务业1、运用排队理论方法对超市收费系统进行分析，建立了在一定的顾客满意度条件下超市的运营费用模型，按运营成本最小的目标进行了优化；2、住院排队系统病床配置调整方法的分析研究3、还应用排队理论建立了门诊排队模型与住院排队模型，进行了某医院的住院排队系统计算机仿真，针对扩建、新建医院建立了线性规划决策模型。徐渝提供（[e-mail]）运筹学在中国现代物流与供应链管理供应链上库存协调的利益分享机制研究应用库存理论及其整合模型建立并分析了竞争型与协商型库存协调的利益分享模型，对其效率和特征进行了比较企业供应链模型和采购满意度评价研究与陕西省物资储运总公司合作的《陕西省区域现代物流配送示范工程》项目可行性分析与初步设计徐渝提供（[e-mail]）运筹学在中国最近的一些理论研究方向(1)数学规划研究•开展对非线性规划信赖域方法的深入和细致的研究(袁亚湘);•开展对非线性共轭梯度法进行深入研究工作者(戴域虹、袁亚湘、韩继业、邓乃扬、王长钰等);•邓乃扬教授提出一类使用PCG技术的不精确牛顿法，大型问题显示出其巨大潜在作用;•研究求解变分不等式问题的一类投影和收缩算法(何炳生、孙德峰、修乃华、王长钰、王宜举等);•开展对求解变分不等式问题的非光滑算法研究，以及开展对求解变分不等式问题的非内点光滑化算法研究。修乃华提供（[e-mail]）运筹学在中国最近的一些理论研究方向(2)不确定性决策研究•供应链管理。主要研究基于信息更新下，供应链模型的优化和决策。•随机存储模型。主要用博弈理论和随机比较理论来研究供应商和销售商之间的协调问题。•在不确定性环境下实时供应链控制和应急管理•具有多类顾客到达的随机排队网络优化与设计。主要研究优化与设计中最基本的两个问题，即具有多类顾客到达随机排队网络的稳定性与扩散逼近。张汉勤提供（[e-mail]）运筹学在中国最近的一些理论研究方向(3)离散与组合优化研究基于判定树计算模型的计算复杂性理论：Rivest-Vuillemin猜想(堵丁柱[e-mail],高随祥[e-mail])近似算法：NP-难解问题的近似算法设计和分析Steiner树问题：Steiner树问题的几何,网络和各种推广模型计算机和通讯网络：交换网络，光纤网络，无线网络和移动网络(堵丁柱[e-mail],胡晓东[e-mail])排序问题：排序问题的在线，半在线和离线模型(何勇[e-mail])装箱问题：装箱问题的在线，离线和高维模型(张国川[e-mail])胡晓东提供（[e-mail]）运筹学在中国最近的一些理论研究方向(4)信息科学、生命科学中的运筹学研究将全局最优化、图论、神经网络等运筹学理论及方法应用于分子生物信息学中的DNA与蛋白质序列比较、芯片测试、生物进化分析、蛋白质结构预测等问题的研究；最近中科院数学