(精品)运筹学(绪论).ppt

运筹帷幄之中,决胜千里之外 运 筹 学Operations ResearchOperations Research管理科学与工程学院管理科学与工程学院主讲：王永成主讲：王永成 E-mail： 运筹学是一门应用学科，它广泛应用现有的科学运筹学是一门应用学科，它广泛应用现有的科学运筹学是一门应用学科，它广泛应用现有的科学运筹学是一门应用学科，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，技术知识和数学方法，解决实际中提出的专门问题，技术知识和数学方法，解决实际中提出的专门问题，技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量的依据。随着计算为决策者选择最优决策提供定量的依据。随着计算为决策者选择最优决策提供定量的依据。随着计算为决策者选择最优决策提供定量的依据。随着计算机技术与信息技术的发展，运筹学的方法已广泛应机技术与信息技术的发展，运筹学的方法已广泛应机技术与信息技术的发展，运筹学的方法已广泛应机技术与信息技术的发展，运筹学的方法已广泛应用于工农业、国防、交通、金融、能源和通信等领用于工农业、国防、交通、金融、能源和通信等领用于工农业、国防、交通、金融、能源和通信等领用于工农业、国防、交通、金融、能源和通信等领域，诸如市场销售、生产计划、库存管理、运输问域，诸如市场销售、生产计划、库存管理、运输问域，诸如市场销售、生产计划、库存管理、运输问域，诸如市场销售、生产计划、库存管理、运输问题、财政和会计、人事管理、设备维修更新和可靠题、财政和会计、人事管理、设备维修更新和可靠题、财政和会计、人事管理、设备维修更新和可靠题、财政和会计、人事管理、设备维修更新和可靠性项目选择和评价、工程优化设计、计算机和信息性项目选择和评价、工程优化设计、计算机和信息性项目选择和评价、工程优化设计、计算机和信息性项目选择和评价、工程优化设计、计算机和信息系统、城市管理等领域。系统、城市管理等领域。系统、城市管理等领域。系统、城市管理等领域。运筹学是一门研究如何有效组织和管理人机系统运筹学是一门研究如何有效组织和管理人机系统运筹学是一门研究如何有效组织和管理人机系统运筹学是一门研究如何有效组织和管理人机系统的科学的科学的科学的科学.运筹学能够对经济管理系统中的人力、物运筹学能够对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。供有依据的最优方案，以实现最有效的管理。通常以最优、最佳等作为决策目标，避开通常以最优、最佳等作为决策目标，避开最劣的方案。最劣的方案。预备知识：高等数学、概率统计、线性代数预备知识：高等数学、概率统计、线性代数预备知识：高等数学、概率统计、线性代数预备知识：高等数学、概率统计、线性代数教材：教材：教材：教材：胡运权主编：胡运权主编：运筹学教程运筹学教程（第三版），（第三版），清华大学出版社，清华大学出版社，20082008年年教学参考书教学参考书教学参考书教学参考书 运筹学教材编写组：运筹学教材编写组：运筹学运筹学（修订（修订 版），清华大版），清华大学出版社，学出版社，19901990年年 胡运权等著：胡运权等著：运筹学基础及应用运筹学基础及应用（第三版），哈（第三版），哈尔滨工业大学出版社，尔滨工业大学出版社，19981998年年 胡运权编写：胡运权编写：运筹学习题集运筹学习题集（第三版），清华大（第三版），清华大学出版社，学出版社，20022002年年教学内容 绪论绪论第一章第一章 线性规划及单纯形法线性规划及单纯形法第二章第二章 线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第三章第三章 运输问题运输问题第四章第四章 目标规划目标规划第五章第五章 整数规划整数规划第六章第六章 图与网络分析图与网络分析 绪绪 论论运筹学（运筹学（Operations ResearchOperations Research，Operational ResearchOperational Research）其含义：其含义：由一支综合性的队伍由一支综合性的队伍 ，采用科学的方法，为一些涉及到有机，采用科学的方法，为一些涉及到有机系统（人系统（人-机）的控制系统问题提供解答，为该系统的总目标服机）的控制系统问题提供解答，为该系统的总目标服务的学科。务的学科。钱学森等钱学森等 事有常规，物有定理。事物的活动也有其规律可事有常规，物有定理。事物的活动也有其规律可事有常规，物有定理。事物的活动也有其规律可事有常规，物有定理。事物的活动也有其规律可进行研究，这些规律统称为进行研究，这些规律统称为进行研究，这些规律统称为进行研究，这些规律统称为“事理事理事理事理”；OROROROR就是研就是研就是研就是研究事物活动规律的科学，亦称究事物活动规律的科学，亦称究事物活动规律的科学，亦称究事物活动规律的科学，亦称“事理学事理学事理学事理学”。许国志许国志许国志许国志运用科学方法来解决工业、商业、政府、国防等运用科学方法来解决工业、商业、政府、国防等运用科学方法来解决工业、商业、政府、国防等运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物资、金钱等大型系统部门里有关人力、机器、物资、金钱等大型系统部门里有关人力、机器、物资、金钱等大型系统部门里有关人力、机器、物资、金钱等大型系统的指挥或管理中所出现的复杂问题的一门学科。的指挥或管理中所出现的复杂问题的一门学科。的指挥或管理中所出现的复杂问题的一门学科。的指挥或管理中所出现的复杂问题的一门学科。其目的是其目的是其目的是其目的是“帮助管理者以科学方法确定其方针和帮助管理者以科学方法确定其方针和帮助管理者以科学方法确定其方针和帮助管理者以科学方法确定其方针和行动行动行动行动”。英国运筹学会英国运筹学会英国运筹学会英国运筹学会(世界上最早的运筹学会）世界上最早的运筹学会）世界上最早的运筹学会）世界上最早的运筹学会）运筹学是应用系统的、科学的、数学分析的方法，运筹学是应用系统的、科学的、数学分析的方法，运筹学是应用系统的、科学的、数学分析的方法，运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的通过建模、检验和求解数学模型而获得最优决策的通过建模、检验和求解数学模型而获得最优决策的通过建模、检验和求解数学模型而获得最优决策的科学。科学。科学。科学。近代一些运筹学工作者近代一些运筹学工作者近代一些运筹学工作者近代一些运筹学工作者 二十世纪四十年代开始形成的一门学科，主要研二十世纪四十年代开始形成的一门学科，主要研二十世纪四十年代开始形成的一门学科，主要研二十世纪四十年代开始形成的一门学科，主要研究经济活动与军事活动中能用数量来表达的有关运究经济活动与军事活动中能用数量来表达的有关运究经济活动与军事活动中能用数量来表达的有关运究经济活动与军事活动中能用数量来表达的有关运用、筹划与管理等方面的问题。它根据问题的要求，用、筹划与管理等方面的问题。它根据问题的要求，用、筹划与管理等方面的问题。它根据问题的要求，用、筹划与管理等方面的问题。它根据问题的要求，通过数学分析和运算，作出综合性的合理安排，以通过数学分析和运算，作出综合性的合理安排，以通过数学分析和运算，作出综合性的合理安排，以通过数学分析和运算，作出综合性的合理安排，以达到较经济、较有效地使用人力、物力。近年来，达到较经济、较有效地使用人力、物力。近年来，达到较经济、较有效地使用人力、物力。近年来，达到较经济、较有效地使用人力、物力。近年来，它在理论与应用方面都有较大的发展。运筹学的分它在理论与应用方面都有较大的发展。运筹学的分它在理论与应用方面都有较大的发展。运筹学的分它在理论与应用方面都有较大的发展。运筹学的分支有规划论、对策论、排队论及质量控制等。支有规划论、对策论、排队论及质量控制等。支有规划论、对策论、排队论及质量控制等。支有规划论、对策论、排队论及质量控制等。辞海辞海辞海辞海发展简史：1 1、萌芽期：萌芽期：萌芽期：萌芽期：早在早在19301930年代以前，朴素的运筹学思想已经存在。年代以前，朴素的运筹学思想已经存在。2 2、初创期：初创期：初创期：初创期：2020世纪的第二次世界大战，是运筹学成长发展的世纪的第二次世界大战，是运筹学成长发展的标志时期。由于战争的需要，运筹学作为一门科学在标志时期。由于战争的需要，运筹学作为一门科学在2020世纪世纪3030年代末正式出现。年代末正式出现。3 3、成长期：成长期：成长期：成长期：第二次世界大战结束到第二次世界大战结束到19501950年代末是运筹学快速年代末是运筹学快速成长的时期。其特点是，运筹学从军事转为民用。成长的时期。其特点是，运筹学从军事转为民用。4 4、发展、成熟期：发展、成熟期：发展、成熟期：发展、成熟期：19601960年代以来是运筹学发展、成熟的黄金年代以来是运筹学发展、成熟的黄金时期，各种刊物、书籍、学术团体在全世界迅速增多，尤其是时期，各种刊物、书籍、学术团体在全世界迅速增多，尤其是电子计算机的出现，使运筹学在更广泛的领域得到了应用和发电子计算机的出现，使运筹学在更广泛的领域得到了应用和发展，如交通、国民经济计划安排等。展，如交通、国民经济计划安排等。5 5、衰退、更新期：衰退、更新期：衰退、更新期：衰退、更新期：偏离理论与实践结合的主流方向形成偏离理论与实践结合的主流方向形成“运运筹学危机筹学危机”黄 河黄 汴 水护 城 河御 街皇城船舶 理论成果理论成果19471947年年年年DantzigDantzig提出单纯形法提出单纯形法提出单纯形法提出单纯形法50-5650-56年线性规划对偶理论诞生年线性规划对偶理论诞生年线性规划对偶理论诞生年线性规划对偶理论诞生19511951年年年年Kuhn-TuckerKuhn-Tucker定理奠定非线性规划理定理奠定非线性规划理定理奠定非线性规划理定理奠定非线性规划理论基础论基础论基础论基础19541954年网络流理论建立年网络流理论建立年网络流理论建立年网络流理论建立19551955年创立随机规划年创立随机规划年创立随机规划年创立随机规划19581958年创立整数规划及割平面解法年创立整数规划及割平面解法年创立整数规划及割平面解法年创立整数规划及割平面解法19581958年求解动态规划的年求解动态规划的年求解动态规划的年求解动态规划的BellmanBellman原理发表原理发表原理发表原理发表19601960年年年年Dantzig-WolfeDantzig-Wolfe建立大建立大建立大建立大LPLP分解算法分解算法分解算法分解算法运筹学研究的基本特征运筹学研究的基本特征整体观念整体观念 多学科的综合多学科的综合 模型方法的应用模型方法的应用 运筹学的工作程序和步骤运筹学的工作程序和步骤1 1、分析和表述问题、分析和表述问题2 2、建立模型、建立模型3 3、求解模型和优化方案、求解模型和优化方案4 4、对模型导出的解进行检验、对模型导出的解进行检验5 5、建立对解的有效控制、建立对解的有效控制6 6、方案的实施、方案的实施 运筹学主要分支运筹学主要分支 确定性模型确定性模型 数学规划：线性规划、非线性规划、数学规划：线性规划、非线性规划、数学规划：线性规划、非线性规划、数学规划：线性规划、非线性规划、整数规划、动态规划、几何规划、参数规划、多整数规划、动态规划、几何规划、参数规划、多整数规划、动态规划、几何规划、参数规划、多整数规划、动态规划、几何规划、参数规划、多目标规划、图论与网络分析、组合优化等目标规划、图论与网络分析、组合优化等目标规划、图论与网络分析、组合优化等目标规划、图论与网络分析、组合优化等随机性模型随机性模型、决策分析、排队论（随机服务系决策分析、排队论（随机服务系决策分析、排队论（随机服务系决策分析、排队论（随机服务系统）、可靠性理论、库存论、对策论、搜索论、统）、可靠性理论、库存论、对策论、搜索论、统）、可靠性理论、库存论、对策论、搜索论、统）、可靠性理论、库存论、对策论、搜索论、计算机随机模拟等计算机随机模拟等计算机随机模拟等计算机随机模拟等前沿与热点前沿与热点在在在在“数字地球数字地球数字地球数字地球”的关键技术中寻求的关键技术中寻求的关键技术中寻求的关键技术中寻求OROROROR的切入点的切入点的切入点的切入点（大规模科学计算，海量存储，高精度卫星图（大规模科学计算，海量存储，高精度卫星图（大规模科学计算，海量存储，高精度卫星图（大规模科学计算，海量存储，高精度卫星图象，宽带网，交互操作）象，宽带网，交互操作）象，宽带网，交互操作）象，宽带网，交互操作）复杂巨系统与计算机模拟复杂巨系统与计算机模拟复杂巨系统与计算机模拟复杂巨系统与计算机模拟生物信息学中的生物信息学中的生物信息学中的生物信息学中的OROROROR方法方法方法方法DPDPDPDP引入生物分子序列比较，预测外显子和内引入生物分子序列比较，预测外显子和内引入生物分子序列比较，预测外显子和内引入生物分子序列比较，预测外显子和内含子含子含子含子寻找基因、启动子和序列对齐等隐藏统计规寻找基因、启动子和序列对齐等隐藏统计规寻找基因、启动子和序列对齐等隐藏统计规寻找基因、启动子和序列对齐等隐藏统计规律的隐马氏过程方法律的隐马氏过程方法律的隐马氏过程方法律的隐马氏过程方法DNADNADNADNA分子生物计算机分子生物计算机分子生物计算机分子生物计算机前沿与热点前沿与热点经济博弈论与宏观金融博弈分析经济博弈论与宏观金融博弈分析经济博弈论与宏观金融博弈分析经济博弈论与宏观金融博弈分析供应链管理供应链管理供应链管理供应链管理现代优化算法现代优化算法现代优化算法现代优化算法禁忌搜索禁忌搜索禁忌搜索禁忌搜索模拟退火模拟退火模拟退火模拟退火遗传算法遗传算法遗传算法遗传算法人工神经网络人工神经网络人工神经网络人工神经网络模糊模糊模糊模糊OROROROR与随机与随机与随机与随机OROROROR现代军事现代军事现代军事现代军事OROROROR运筹学方法在中国使用情况运筹学方法在中国使用情况 (随机抽样随机抽样)如何学习运筹学课程如何学习运筹学课程学习运筹学要把学习运筹学要把学习运筹学要把学习运筹学要把重点重点重点重点放在分析、理解有关的概念、放在分析、理解有关的概念、放在分析、理解有关的概念、放在分析、理解有关的概念、思路上。在自学过程中，应该多向自己提问，例思路上。在自学过程中，应该多向自己提问，例思路上。在自学过程中，应该多向自己提问，例思路上。在自学过程中，应该多向自己提问，例如一个方法的实质是什么，为什么这样进行，怎如一个方法的实质是什么，为什么这样进行，怎如一个方法的实质是什么，为什么这样进行，怎如一个方法的实质是什么，为什么这样进行，怎么进行等。么进行等。么进行等。么进行等。自学时要掌握三个自学时要掌握三个自学时要掌握三个自学时要掌握三个重要环节重要环节重要环节重要环节：1.1.1.1.认真阅读教材和参考资料，以指定教材为主，认真阅读教材和参考资料，以指定教材为主，认真阅读教材和参考资料，以指定教材为主，认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运筹学教材同时参考其他有关书籍。一般每一本运筹学教材同时参考其他有关书籍。一般每一本运筹学教材同时参考其他有关书籍。一般每一本运筹学教材都有自己的特点，但是基本原理、概念都是一致都有自己的特点，但是基本原理、概念都是一致都有自己的特点，但是基本原理、概念都是一致都有自己的特点，但是基本原理、概念都是一致的。注意主从，参考资料会帮助你开阔思路，使的。注意主从，参考资料会帮助你开阔思路，使的。注意主从，参考资料会帮助你开阔思路，使的。注意主从，参考资料会帮助你开阔思路，使学习深入。但是，把时间过多放在参考资料上，学习深入。但是，把时间过多放在参考资料上，学习深入。但是，把时间过多放在参考资料上，学习深入。但是，把时间过多放在参考资料上，会导致思路分散，不利于学好。会导致思路分散，不利于学好。会导致思路分散，不利于学好。会导致思路分散，不利于学好。2.2.2.2.要在理解了基本概念和理论的基础上研究例题，要在理解了基本概念和理论的基础上研究例题，要在理解了基本概念和理论的基础上研究例题，要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助理解概念、理论的。作业练注意例题是为了帮助理解概念、理论的。作业练注意例题是为了帮助理解概念、理论的。作业练注意例题是为了帮助理解概念、理论的。作业练习的主要作用也是这样，它同时还有让你自己检习的主要作用也是这样，它同时还有让你自己检习的主要作用也是这样，它同时还有让你自己检习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。因此，做题要有信心，要独查自己学习的作用。因此，做题要有信心，要独查自己学习的作用。因此，做题要有信心，要独查自己学习的作用。因此，做题要有信心，要独立完成，不要怕出错。因为，整个课程是一个整立完成，不要怕出错。因为，整个课程是一个整立完成，不要怕出错。因为，整个课程是一个整立完成，不要怕出错。因为，整个课程是一个整体，各节内容有内在联系，只要学到一定程度，体，各节内容有内在联系，只要学到一定程度，体，各节内容有内在联系，只要学到一定程度，体，各节内容有内在联系，只要学到一定程度，知识融会贯通起来，你自己就能够对所做题目的知识融会贯通起来，你自己就能够对所做题目的知识融会贯通起来，你自己就能够对所做题目的知识融会贯通起来，你自己就能够对所做题目的正确性作出判断。正确性作出判断。正确性作出判断。正确性作出判断。3 3 3 3、要学会做学习小结。每一节或一章学完后，必、要学会做学习小结。每一节或一章学完后，必、要学会做学习小结。每一节或一章学完后，必、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来概述该书所讲内容。这样，须学会用精炼的语言来概述该书所讲内容。这样，须学会用精炼的语言来概述该书所讲内容。这样，须学会用精炼的语言来概述该书所讲内容。这样，你才能够从较高的角度来看问题，更深刻地理解你才能够从较高的角度来看问题，更深刻地理解你才能够从较高的角度来看问题，更深刻地理解你才能够从较高的角度来看问题，更深刻地理解有关知识和内容。这就称作有关知识和内容。这就称作有关知识和内容。这就称作有关知识和内容。这就称作“把书读薄把书读薄把书读薄把书读薄”，若能，若能，若能，若能够结合相关参考文献并深入理解，把相关知识从够结合相关参考文献并深入理解，把相关知识从够结合相关参考文献并深入理解，把相关知识从够结合相关参考文献并深入理解，把相关知识从更深入、广泛的角度进行论述，则称为更深入、广泛的角度进行论述，则称为更深入、广泛的角度进行论述，则称为更深入、广泛的角度进行论述，则称为“把书读把书读把书读把书读厚厚厚厚”。思考讨论题思考讨论题1 1、运筹学学科特点是什么？、运筹学学科特点是什么？2 2、结合你的专业背景，描述几个可以用、结合你的专业背景，描述几个可以用运筹学思想、方法解决的问题。运筹学思想、方法解决的问题。线性规划内容框架线性规划内容框架线性规划内容框架线性规划内容框架