运筹学1-10章讲义

华北水利水电大学管理与经济学院任课老师：王红娜1课程说明课程简介运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。运筹学的核心思想是建立在优化的基础上。例如，在线性规划中体现为两方面：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进行，这样可以节省大量的人力和时间。教学目标：运筹学是经济与管理类专业学生的一门专业基础课。通过本课程的学习，使学生获得经济管理决策中常用的运筹学的基本概念、基本理论与基本方法的知识，为进一步学习与掌握现代管理理论奠定必要的理论基础，并培养与提升学生利用运筹学的基本理论进行管理分析和解决实际问题的能力，为以后在企业管理生产时，提供科学的决策依据，是实现管理科学化、现代化的有利工具。课程要求：掌握运筹学的基本理论与基本方法；熟练运用运筹学的知识与方法解决相应的经济与管理问题。先修课程：微积分、线性代数、概率论与数理统计、计算机基础知识课程介绍：运筹学是一门必修课，学时共56个，学分是3.5分，我们主要采取课堂教授的方式进行学习，考核方式是考试。内容包括线性规划及单纯形法、对偶理论及灵敏度分析、运输问题、目标规划、整数规划、动态规划、图与网络分析、排队论、决策论等。华北水利水电大学管理与经济学院任课老师：王红娜2作业：因为课程的性质，学习过程中有大量的习题和作业。全学期有3次未交作业或未达到教师提出的要求（晚交作业按不交作业论），将取消期末考试资格，成绩以0分记入。考核方式：平时（考勤、作业、课堂练习）；期末考试采用闭卷形式进行。成绩评定：课程总成绩依据下列权重评定：平时考勤、作业、课堂练习共占20%；期末考试占80%。参考资料：《运筹学》教材编写组编，运筹学（修订版），清华大学出版社；胡运权主编，运筹学习题集（第三版），清华大学出版社；胡运权主编，运筹学教程（第二版），清华大学出版社；钱颂迪主编，运筹学，清华大学出版社学习方法：学习运筹学要把重点放在分析、理解有关的概念、思路上。在学习过程中，应该多向自己提问，如一个方法的实质是什么，为什么这样做，怎么做等。学习时要掌握三个重要环节：1、认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运筹学教材都有自己的特点，但是基本原理、概念都是一致的。注意主从，参考资料会帮助你开阔思路，使学习深入。但是，把时间过多放在参考资料上，会导致思路分散，不利于学好。2、要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助你理解概念、理论的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。3、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来该节或该章所学内容。这样，你才能够从较高的角度来看问题，更深刻的理解有关知识和内容。这就称作“把书读薄”，若能够结合自己参考大量文献后的深入理解，把相关知识从更深入、广泛的角度进行论述，则称之为“把书读厚”。3第1章绪论重点与难点：1、从运筹学产生的背景认识本学科研究的内容和意义。2、了解运筹学的内容和特点，结合自己的理解思考学习的方法和途径。3、体会运筹学的学习特征和应用领域。1.1运筹学释义与发展简史运筹学作为科学名词最早出现在20世纪30年代，它的英文通用名称为“OperationsResearch”，简称OR，按照原意应译为“运作研究”或“作战研究”。它是一门基础性的应用学科，主要研究系统最优化的问题，通过对建立的模型求解，为管理人员作决策提供科学依据。我们首先介绍运筹学的具体定义。一、运筹学的含义Operations，汉语翻译是什么？工作、操作、行动、手术、运算OperationsResearch：日本——运用学、港台——作业研究、中国大陆——运筹学。OperationsResearch，原意是操作研究、作业研究、运用研究、作战研究，我国把它译作运筹学，是借用了《史记》“运筹于帷幄之中，决胜于千里之外”一语中“运筹”二字，既显示其军事的起源，也表明它在我国已早有萌芽，而且也比较恰当地反映了这门学科的性质和内涵。运筹学是一门应用科学，至今还没有一个统一的定义。我们在此介绍几种典型的定义：1.莫斯（P.M.Morse）和金博尔（G.E.Kimball）曾对运筹学下的定义是：“为决策机构在对其控制下的业务活动进行决策时，提供以数量化为依据的科学方法。”该定义首先强调的是科学方法，它强调以定量化为基础，必须利用数学工具。但任何决策都包含定量和定性两个方面，而定性方面又不能简单地用数学表示，如政治、社会等因素，只有综合多种因素的决策才是全面的。运筹学工作者的职责是为决策者提供可以量化方面的分析，并指出那些定性的因素。2．另一定义是：“运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。”该定义表明运筹学具有多学科交叉的特点，如综合应用经济学、心理学、物理学和化学中的一些方法。3.运筹学是强调最有决策，“最”是过分理想了，在实际生活中往往用次优、满意等概念代替最优。因此，运筹学的又一定义是：“运筹学是一种给出问题坏的答案的艺术，否则的话问题的结果会更坏。“4此外大英百科全书、中国大百科全书、辞海等都对运筹学做了释义（见教材），但目前我国普遍用的运筹学的定义就是《中国企业管理百科全书》（1984年版）中的释义：“运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。”二、运筹学的发展历史1、早期运筹思想中国古代的“田忌赛马”、“丁渭修宫”等都用到了比较朴素的运筹学思想。作为运筹学的早期工作其历史可追溯到1914年：1914年英国人兰彻斯特（F.W.Lanchester）曾发表过关于人与火力的优势与胜利之间的理论文章，这就是军事运筹学中著名的“兰彻斯特战斗方程”。排队论的先驱者丹麦工程师爱尔朗（A.K.Erlang）1917年在哥本哈根电话公司研究电话通信系统时，提出了排队论的一些著名公式。20世纪30年代，荷兰人荷雷斯﹒列文生（Horace.C.Levenson）用运筹学思想分析商业广告和顾客心理，由此提出了存储论中著名的“经济批量公式”。1947年，美国数学家丹捷格（G.B.Dantizg）发表了关于线性规划的研究成果，所解决的问题是美国空军军事规划时提出的，并给出了求解线性规划问题的单纯形算法。事实上，早在1939年苏联学者康托洛维奇在解决工业生产组织和计划问题时，已提出了类似线性规划的模型，并给出了“解乘数法”的求解方法。由于当时未被领导重视，直到1960年康托洛维奇再次发表了《最佳资源利用的经济计算》一书后，才受到国内外的一致重视。为此康托洛维奇获得了诺贝尔经济学奖。2、军事运筹学阶段运筹学作为科学名词出现是在20世纪30年代末，背景是英、美对付德国的空袭，雷达作为防空系统的一部分，从技术上是可行的，但实际运用时却不理想。为此，一些科学家就如何合理运用雷达开始进行一类新问题的研究。因为它与研究技术问题不同，就称之为“运用研究”或“操作研究”（OperationalResearch）。研究内容是：（1）运输船编队问题。研究护航舰队保护商船队的编队问题，即当船队遭受德国潜艇攻击时，如何使船队损失最小；（2）深水炸弹。研究反潜深水炸弹的合理爆炸深度，这使得德国潜艇被摧毁数增加到400%；（3）空袭逃避。研究船队在遭受敌机攻击时，大船应急转向而小船应缓慢转向的逃避方法，其结果，使船只在受敌机攻击时，中弹船只数由47%降到29%。3、管理运筹学阶段二战后，运筹学的活动扩展到工业和政府部门，该时期的发展大致分为三个阶段：5（1）从1945年到50年代初，创建时期。1950年在英国创办了第一本运筹学杂志《运筹学季刊》，1952年第一个运筹学会美国运筹学会成立。该时期从事运筹学研究的人数不多，范围较小，运筹学的出版物、学会寥寥无几。（2）从50年代初期到50年代末期，成长时期。该阶段由于电子计算机技术的迅速发展，使得运筹学中一些方法如单纯形法、动态规划方法等，可以用来解决实际管理系统中的优化问题，促进了运筹学的推广应用。（3）自60年代以来，普及和迅速发展时期。该阶段运筹学进一步细分为各个分支，学术团体迅速增多，运筹学期刊、书籍大量出版，更多学校把运筹学纳入教学计划当中。4、运筹学在中国在20世纪50年代中期，我国科学家钱学森、许国志等人将运筹学由西方引入我国，并结合了我国的特点在国内推广应用。在此期间，以华罗庚敎授为首的一大批数学家加入到运筹学的研究队伍，使运筹学的很多分支很快跟上当时的国际水平。我国各高等院校也普遍把运筹学作为一门专业主干课程列入教学计划中。1.2运筹学研究的基本特征与基本方法一、运筹学研究的基本特征运筹学研究的基本特征是：系统的整体观念，多学科的综合，以及模型方法的应用。1、系统的整体观念任何一个整体都是有很多子系统构成，运筹学研究中不是对各子系统的决策行为孤立评价，而把有关子系统相互关联的决策结合起来考虑，把相互影响和制约的各个方面作为一个统一体，从系统整体利益出发，寻找一个优化协调的方案。2、多学科的综合一个企业的有效管理涉及很多方面，因此运筹学研究中需要来自不同学科具有不同经验的专家一起发挥集体智慧，提出问题和解决问题。3、模型方法的应用由于运筹学的研究不能在实验室进行，只能通过建立问题的数学模型或模拟模型来进行研究。为制定决策提供数学依据是运筹学应用的核心，而建立模型则是运筹学方法的精髓。学习运筹学要掌握的最重要的技巧就是提高对运筹学数学模型的表达、运算和分析。二、运筹学研究的主要步骤任何一门学科从研究范畴上大致都可分为四个方面：从观察现象所得到的结果即进行观察需要的方法；理论或模型的建立；将理论和方法相结合，并从中得到预测结果；将预测结果和新的观察进行比较，并加以证实。运筹学围绕着模型的建立、修正和实施，也包括以下几个具体的步骤：61、分析和表述问题（提出和形成问题）。任何决策问题在进行定量分析前，都要进行定性分析，即要弄清决策的目标，选取决策时的有效性度量，决策中的关键因素，面临的可能约束，问题的可控变量以及有关参数，搜集有关资料。2、建立模型。模型的正确建立是运筹学研究中关键的一步，它是将实际问题、经验、科学方法三者有机结合的创造性工作。建立模型就是把问题中的可控变量、参数和目标与约束之间的关系用一定的模型表示出来。建立模型的时候一般建立数学模型，即用数学语言描述的一类模型。但有时问题中的关系很难用数学语言描绘，或问题中的随机因素很多，这时可以建立一个模拟模型，即将问题的因素、目标及关系用逻辑框图的形式表示出来（网络图）。3、求解模型和优化方案。用各种手段（主要是数学方法，也可用其它方法如编写计算机程序）将模型求解。解可以是最优解、次优解、满意解，复杂模型的求解需用计算机，解的精度要求由决策者提出，可以分为精确解和近似解。4、测试模型即对模型进行必要的修正。有的书上也称为解的检验，首先检验求解步骤和程序有无错误，然后检查解是否反映现实问题，符合实际情况。当有较大误差出现时，就需要将实际问题与模型重新对比，仔细检查，对已经构建的模型进行修正。5、建立对解的有效控制。由于模型都有一定的适用范围，当外界条件参数变化超出这个范围时，就需要对解进行修正。因此必须通过控制解的变化过程决定对解是否要作一定的修改。6、方案的实施。是指将解用到实际中去，必须考虑到实际的问题，如向实际部门讲清楚解的用法，在实施中可能产生的问题等。这一步是既关键又困难的一步，因此在进行方案实施时要明确：方案由谁实施，什