高等运筹学(总)资料.ppt

高 等 运 筹 学 符 卓 Tel:mail: zhfu@csu.edu.cn 中南大学 交通运输工程学院 课程内容特点 基础运筹学：单目标优化，精确算法。 高等运筹学：多目标优化，启发式算法。 主要内容 概论 现代运筹学的理念——柔性 多目标规划 经典启发式方法 模拟退火算法 禁忌有哪些信誉好的足球投注网站算法 遗传算法 第1章 概论 1.1 运筹学概述 1.2 最优化问题及其分类 1.3 计算复杂性概述 1.4 优化算法及其分类 1.5 邻域与局部有哪些信誉好的足球投注网站 1.1 运筹学概述 1.运筹学的产生和发展 二战期间，英国海军部召集了一个专家小组，称为“Operational Research”小组，美国武装部队的规划总部也建立了一个类似的专家小组，称为“Operations Research”小组，从事军事运筹方面的研究。 战后，运筹学的方法广泛应用于民用企业，以解决复杂的经营管理问题，并促进运筹学发展成为一门独立的学科。该学科的英文名称就是Operational Research或Operations Research, 简称OR。 英国：1948年成立运筹学俱乐部，1950年创办第一份运筹学刊物“Operational Research Quarterly”，该俱乐部于1953年改名为运筹学会，刊物也更名为“Journal of the Operational Research Society”。 美国：1952年成立运筹学会，并创刊“Operations Research”。 中国：1956年在中科院成立我国第一个运筹学小组，1980年成立运筹学会，1982年成为国际运筹学联合会会员国。现创办的主要刊物有“运筹学学报”和“运筹与管理”。 “运筹帷幄之中，决胜千里之外”与“运筹学” 。 OR的发展与计算机的发展分不开。如果没有计算机，OR只不过是一种理论科学，不会成为应用科学。 2. 运筹学的组成部分 运筹学研究的现象有三类：一是资源运用的问题，二是竞争现象，三是拥挤现象。 其内容相应地划分为三个组成部分：运用分析理论，竞争理论，随机服务理论。 运用分析理论：包括分配、选址、资源最佳利用、设备最佳运行等。常用的数学方法有线性规划、非线性规划、网络规划、动态规划、最优控制等。 竞争理论：主要方法是对策论。 随机服务理论：主要方法是排队论。 3. 运筹学的性质 核心：运用数学方法研究各种系统的优化途径和方案，为决策者提供科学决策依据。 研究对象：人类对各种资源的运用及筹划活动。 研究方法：定量化和模型化，尤其是运用各种数学模型和优化技术。 研究目的：了解和发现这些运用及活动的基本规律，发挥有限资源的最大效益。 OR：The Science of Better Decisions. OR uses mathematics, but it is not a branch of mathematics. 4. 运筹学的特点 强调研究过程的完整性：问题的提出→建立模型→提出解案→付诸实施。 强调理论与实践的结合。 5. 运筹学的应用领域 其影响继续扩大：国际运筹学联合会已有50个成员国。 应用领域不断增加：如军事运筹学、管理运筹学、交通运输运筹学、工业运筹学、农业运筹学、工程技术运筹学、计算运筹学等。 总之，凡是在某些有限的资源限制下寻求一个最优的行动方案，运筹学就有可能用得上。 1.2 最优化问题及其分类 最优化指最小化或最大化，本课程以最小化为例。 最优化问题可分为函数优化问题和组合优化问题两大类。 1.函数优化问题 优化的对象是可在一定区间内取值的连续变量。 2.组合优化问题 优化的对象是解空间中的离散状态，即哪一个组合对象最优？ 解决的是离散事件的最优编排、分组、次序或筛选等问题，是运筹学中一个经典且重要的分支。涉及管理、交通运输、通信网络等诸多领域。 组合优化问题可用数学模型描述为： min f (x) s.t. g (x) ≤0, x∈S, 其中，f (x)为目标函数，g (x)为约束函数，x为决策变量，S表示有限个点组成的集合。 一个组合优化问题也可用三个参数（S, F, f）来描述： S：决策变量的定义域，即解空间； F = { x | x∈S, g (x)≤0}：可行解区域； f ：目标函数值，满足f (x*) = min{ f (x)| x∈F }的可 行解x*称为该问题的最优解。 组合优化的特点：可行解集合为有限点集。 几个典型组合优化问题： (1) 旅行商问题（traveling salesman problem,