高等运筹学(第1章).ppt

1、1,高 等 运 筹 学,2,课程内容特点,基础运筹学：单目标优化，精确算法。 高等运筹学：多目标优化，启发式算法。,3,主要内容,概论 现代运筹学的理念柔性 多目标规划 经典启发式方法 模拟退火算法 禁忌搜索算法 遗传算法,4,第1章 概论,1.1 运筹学概述 1.2 最优化问题及其分类 1.3 计算复杂性概述 1.4 优化算法及其分类 1.5 邻域与局部搜索,5,1.1 运筹学概述,1.运筹学的产生和发展 二战期间，英国海军部召集了一个专家小组，称为“Operational Research”小组，美国武装部队的规划总部也建立了一个类似的专家小组，称为“Operations Research

2、”小组，从事军事运筹方面的研究。 战后，运筹学的方法广泛应用于民用企业，以解决复杂的经营管理问题，并促进运筹学发展成为一门独立的学科。该学科的英文名称就是Operational Research或Operations Research, 简称OR。,6,英国：1948年成立运筹学俱乐部，1950年创办第一份运筹学刊物“Operational Research Quarterly”，该俱乐部于1953年改名为运筹学会，刊物也更名为“Journal of the Operational Research Society”。 美国：1952年成立运筹学会，并创刊“Operations Researc

3、h”。 中国：1956年在中科院成立我国第一个运筹学小组，1980年成立运筹学会，1982年成为国际运筹学联合会会员国。现创办的主要刊物有“运筹学学报”和“运筹与管理”。 “运筹帷幄之中，决胜千里之外”与“运筹学” 。 OR的发展与计算机的发展分不开。如果没有计算机，OR只不过是一种理论科学，不会成为应用科学。,7,2. 运筹学的组成部分 运筹学研究的现象有三类：一是资源运用的问题，二是竞争现象，三是拥挤现象。 其内容相应地划分为三个组成部分：运用分析理论，竞争理论，随机服务理论。 运用分析理论：包括分配、选址、资源最佳利用、设备最佳运行等。常用的数学方法有线性规划、非线性规划、网络规划、动态

4、规划、最优控制等。 竞争理论：主要方法是对策论。 随机服务理论：主要方法是排队论。,8,3. 运筹学的性质 核心：运用数学方法研究各种系统的优化途径和方案，为决策者提供科学决策依据。 研究对象：人类对各种资源的运用及筹划活动。 研究方法：定量化和模型化，尤其是运用各种数学模型和优化技术。 研究目的：了解和发现这些运用及活动的基本规律，发挥有限资源的最大效益。 OR：The Science of Better. OR uses mathematics, but it is not a branch of mathematics.,9,4. 运筹学的特点 强调研究过程的完整性：问题的提出建立模型提

5、出解案付诸实施。 强调理论与实践的结合。 5. 运筹学的应用领域 其影响继续扩大：国际运筹学联合会已有48个成员国。 应用领域不断增加：如军事运筹学、管理运筹学、交通运输运筹学、工业运筹学、农业运筹学、工程技术运筹学、计算运筹学等。 总之，凡是在某些有限的资源限制下寻求一个最优的行动方案，运筹学就有可能用得上。,10,1.2 最优化问题及其分类,最优化指最小化或最大化，本课程以最小化为例。 最优化问题可分为函数优化问题和组合优化问题两大类。 1.函数优化问题 优化的对象是可在一定区间内取值的连续变量。 2.组合优化问题 优化的对象是解空间中的离散状态。 解决的是离散事件的最优编排、分组、次序或

6、筛选等问题，是运筹学中一个经典且重要的分支。涉及管理、交通运输、通信网络等诸多领域。,11,组合优化问题可用数学模型描述为： min f (x) s.t. g (x) 0, xS, 其中，f (x)为目标函数，g (x)为约束函数，x为决策变量，S表示有限个点组成的集合。 一个组合优化问题也可用三个参数（S, F, f）来描述： S：决策变量的定义域，即解空间； F = x | xS, g (x)0：可行解区域； f ：目标函数值，满足f (x*) = min f (x)| xF 的可 行解x*称为该问题的最优解。 组合优化的特点：可行解集合为有限点集。,12,几个典型组合优化问题： (1)

7、旅行商问题（traveling salesman problem, TSP） 一个商人欲到n个城市巡回推销商品，已知城市i和j之间的距离为dij，如何确定一条巡回路线，使得商人从其中的某一城市出发，经过其他城市一次且仅一次后回到原出发点，且所走的路程最短。 设,13,则该问题的一种数学模型为： s.t. xij0,1, i,j =1,2,n, ij.,14,(2) 0-1背包问题（knapsack problem） 对于n个体积分别为ai (1,2,n)，价值分别为ci (1,2,n)的物品，如何将它们装入总体积为b的背包中，使得所选物品的总价值最大？ 设 则该问题可用数学模型表示为： s.t

8、. xi0,1, i =1,2,n,15,(3) 装箱问题（bin packing problem） 如何以个数最少的尺寸为1单位的箱子装入n个尺寸不超过1单位的物品。 (4) 机器排序问题（machine scheduling problem） 。 有n个工件需要在机床A、B上加工，每个工件都必须经过先A而后B的两道工序。以Aj和Bj分别表示工件j（j=1, 2, , n）在A和B上的加工时间。问应如何安排各工件加工的顺序，才能使从机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止，所用的加工总时间最少？ 在组合优化问题中，有些可以用整数规划模型表示，有些则用文字叙述更易理解。

9、上述问题描述均非常简单，但求其最优解确很困难。,16,1.3 计算复杂性概述,1.算法及算法分析 算法:能被机械地执行的动作（或规则）的有限集合，一个动作的一次执行称为一步。 算法特征：输入、确定性、可执行性、有限性、输出。 算法分析：对算法性能的讨论。 算法分析目的： 对同一问题的各种可实现的算法进行比较，对它们的性能作出定量的判断。 确定算法是否存在什么性能上的限制，给算法设计提供理论上的指导。,17,算法复杂性：算法对时间和空间的需要量分别称为算法的时间复杂性和空间复杂性。 算法执行基本操作的次数定义为算法的时间复杂性，记为T(n)； 算法执行期间占用的计算机存储单元定义为算法的空间复杂

10、性，记为S(n)。 算法的复杂性的表示：一般表示为问题规模n（如TSP中的城市数）的函数。 当一个算法A对于规模为n的问题进行求解计算时，若所需的基本操作次数的上界（指在最坏情况下）为f (n)，则称f (n)为算法A的时间复杂性函数。 在分析复杂性时，可用其函数主要项的阶O(f (n)来表示。,18,若算法A的时间复杂性为T(n) = O(f (n)，且f (n)为n的多项式函数，如O(n)、O(n3)等，则称算法A为多项式算法。 时间复杂性函数不属于n的多项式函数的算法统称为指数算法，如f(n)为2n、n!、nn等形式。 算法性能：多项式算法是有效算法；指数算法不是有效算法。另外，多项式算

11、法有较好的“闭”性。 问题的难易性：若一个问题找到了多项式算法，就可以认为这个问题基本解决了。若一个问题不存在多项式算法，则称这个问题是难解的。 有少数复杂度为指数函数的算法，在实践中却被证明是有效的算法，如求解线性规划问题的单纯形法就是一个突出的例子。,19,2. P, NP, NP完全和NP难 P类和NP类问题 若问题有求解它的多项式算法，则属于P类问题。 若问题仍没有找到求其最优解的多项式算法，则称这类问题为非多项式确定问题，即NP类问题。 NP完全问题 NP完全（NP-complete, NP-C）问题是NP类问题中难度最大的一类问题。 为证明一个问题是NP完全的，须证明：该问题是NP

12、的；所有其他NP问题可多项式归约（变换）到该问题。 现已证明的NP完全问题已上千个，但没有找到任一问题的多项式算法。 性质：任一NP完全问题都不能用任何已知的多项式算法求解；若任一NP完全问题有多项式算法，则一切NP完全问题都有多项式算法。,20,NP难问题 有些问题，不能验证它属于NP类，但可以证明所有NP问题都可以多项式归约为该问题，则这类问题称为NP难问题（NP-hard）。 一个问题是NP难问题不要求该问题属于NP类，但至少和NP完全问题有同等的难度。 P NP NP完全 NP难 图1.1 四类问题的关系图,21,1.4 优化算法及其分类,优化算法：是基于某种思想和机制建立起来的、能求

13、出满足要求的问题的解的一种搜索途径或规则。 按求解精度分类： 精确算法（exact algorithm）：可求出问题最优解的算法，且一般要求问题能用数学模型表示，但对大规模问题计算量大，应用范围常常受到限制。 启发式算法（heuristic algorithm）：基于直观或经验构造的算法，且一般不要求将问题表述为某种标准数学模型。在可接受的计算量内求出问题的可行解，但不能保证解的最优性。,22,按优化机制与行为分类： 经典算法：包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传统算法。 构造算法：用构造的方法快速建立问题的一个可行解。如运输问题中的最小元素法。 邻域搜索算法：从任一初始解

14、出发，对其邻域的不断搜索和当前解的替换来逐步实现优化。根据搜索行为，又可将其分为局部搜索法和指导性搜索法。 基于系统动态演化的方法：将优化过程转化为系统动态的演化过程，以系统动态的演化来实现优化。 混合型算法：上述各算法从结构或操作上相混合而产生的各类算法。 按其它角度分类：如确定性算法和随机性算法；局部优化算法和全局优化算法等。,23,1.5 邻域与局部搜索,1.邻域 定义: 在距离空间中：是指以一点为中心的一个球体。 在组合优化中：设某问题所有解构成的解空间为S。对于每个解xiS，有一个在某种意义上是“邻近”xi的解的集合，称集合N(xi)为xi的邻域（neighbourhood），每个x

15、jN(xi)称为xi的一个邻域解或邻居（neighbour）。此外，通常约定xjN(xi) =xiN(xj)。 2.邻域结构（neighbourhood structure，也称邻域函数或解产生函数）,24,其作用是指导如何由一个解来产生一个新的解。 设计往往依赖于问题的特性和解的表达方式。 函数优化与组合优化中的邻域结构的具体方式存在明显差异： 函数优化中：利用距离的概念通过附加扰动来构造邻域结构是最常用的方法，如x= x+，其中x为新解，x为旧解，为尺度参数，为满足某种概率分布的随机数或梯度信息等。 组合优化中：因传统的距离概念不再适用，但邻域结构的基本思想仍旧是通过对一个解进行适当变换后

16、产生另一个解。,25,如TSP的解可用置换排列来表示，如排列（1, 2, 3, 4）可表示为有4个城市的TSP的一个解。那么，k个点的交换就可认为是一种邻域结构，即 Nk = jN(i) | j可由i经一次k交换得到 如上述排列的2点交换对应的邻域结构将产生新解（2, 1, 3, 4）、（3, 2, 1, 4）等。 3.局部最优和全局最优 定义：令（S, F, f）为一个优化问题，其中S为所有解构成的解空间，F为S上的可行域，f 为目标函数，设 为解x*的邻域，若 xN(xi)F，满足f(x*)()f(x)，则称x*为f 在F上的局部最小（最大）解（点）；若 xF，满足f(x*)()f(x)，

17、则称x*为f 在F上的全局最小（最大）解（点）。,26,以一维变量x为例，假设可行域为区间1,10中的整数点，目标函数值如图1.2所示，如果采用如下邻域定义： N(x) = yZ+|y-x|1， 则x=9为全局最小点；x=5为局部最小点；而x=4既不是局部最大点也不是局部最小点。 f(x) + + + + + + + + + + O 1 2 3 4 5 6 7 8 9 10 x 图1.2 局部最优解示意图,27,4.局部搜索算法（local search） 是一种传统的优化算法，是基于贪婪思想利用邻域结构进行搜索的。又两种实现方式： 上（下）山法：一旦搜索到一个更好的解，就立即接受其作为新的当

18、前解； 最陡下降法：只接受当前解整个邻域中的最好解作为下一当前解。 以下山法为例介绍求目标函数值最小的局部搜索算法：从一个初始解x0F出发，利用邻域结构持续地在当前解x i的邻域中搜索比它更好的解，若能够找到这样的解，就用这个解取代x i，成为新的当前解，再对当前解重复上述过程；否则搜索过程终止，并以当前解作为算法的最终解。,28,用伪Pascal语言描述的局部搜索算法： Procedure Local_Search; Begin 任选一初始解x0； x i := x0 （置初始解为当前解） repeat 从邻域N(x i)中随机选一个x j； if f(x j) f(x i) then x i := x j； until 对邻域N(x i)中的所有x j均有f(x j) f(x i) End. 以图1.2为例，若以x=4为起点用局部搜索算法搜索最小值点，则搜索到x=5这个局部最优（最小）点时就会停止。,29,局部搜索算法具有以下优点： 通用性，易实现。 灵活性。 局部搜索算法有以下不足： 搜索性能和最终解的质量依赖