高等运筹学(总)

1高等运筹学符卓Tel:82655051,13973134613Email:[e-mail]中南大学交通运输工程学院（办公室：交通楼415）2课程内容特点基础运筹学：单目标优化，精确算法。高等运筹学：多目标优化，启发式算法。3主要内容1.概论2.现代运筹学的理念——柔性3.多目标规划4.经典启发式方法5.模拟退火算法6.禁忌搜索算法7.遗传算法4第1章概论1.1运筹学概述1.2最优化问题及其分类1.3计算复杂性概述1.4优化算法及其分类1.5邻域与局部搜索51.1运筹学概述1.运筹学的产生和发展二战期间，英国海军部召集了一个专家小组，称为“OperationalResearch”小组，美国武装部队的规划总部也建立了一个类似的专家小组，称为“OperationsResearch”小组，从事军事运筹方面的研究。战后，运筹学的方法广泛应用于民用企业，以解决复杂的经营管理问题，并促进运筹学发展成为一门独立的学科。该学科的英文名称就是OperationalResearch或OperationsResearch,简称OR。6英国：1948年成立运筹学俱乐部，1950年创办第一份运筹学刊物“OperationalResearchQuarterly”，该俱乐部于1953年改名为运筹学会，刊物也更名为“JournaloftheOperationalResearchSociety”。美国：1952年成立运筹学会，并创刊“OperationsResearch”。中国：1956年在中科院成立我国第一个运筹学小组，1980年成立运筹学会，1982年成为国际运筹学联合会会员国。现创办的主要刊物有“运筹学学报”和“运筹与管理”、“JournaloftheOperationsResearchSocietyofChina”。相关的学术刊物还有很多。“运筹帷幄之中，决胜千里之外”与“运筹学”。OR的发展与计算机的发展分不开。如果没有计算机，OR只不过是一种理论科学，不会成为应用科学。782.运筹学的组成部分运筹学研究的现象有三类：一是资源运用的问题，二是竞争现象，三是拥挤现象。其内容相应地划分为三个组成部分：运用分析理论，竞争理论，随机服务理论。•运用分析理论：包括分配、选址、资源最佳利用、设备最佳运行等。常用的数学方法有线性规划、非线性规划、网络规划、动态规划、最优控制等。•竞争理论：主要方法是对策论。•随机服务理论：主要方法是排队论。93.运筹学的性质核心：运用数学方法研究各种系统的优化途径和方案，为决策者提供科学决策依据。研究对象：人类对各种资源的运用及筹划活动。研究方法：定量化和模型化，尤其是运用各种数学模型和优化技术。研究目的：了解和发现这些运用及活动的基本规律，发挥有限资源的最大效益。OR：TheScienceofBetterDecisions.ORusesmathematics,butitisnotabranchofmathematics.104.运筹学的特点强调研究过程的完整性：问题的提出→建立模型→提出解案→付诸实施。强调理论与实践的结合。5.运筹学的应用领域其影响继续扩大：国际运筹学联合会已有50个成员国。应用领域不断增加：如军事运筹学、管理运筹学、交通运输运筹学、工业运筹学、农业运筹学、工程技术运筹学、计算运筹学等。总之，凡是在某些有限的资源限制下寻求一个最优的行动方案，运筹学就有可能用得上。111.2最优化问题及其分类最优化指最小化或最大化，本课程以最小化为例。最优化问题可分为函数优化问题和组合优化问题两大类。1.函数优化问题优化的对象是可在一定区间内取值的连续变量。2.组合优化问题优化的对象是解空间中的离散状态，即哪一个组合对象最优？解决的是离散事件的最优编排、分组、次序或筛选等问题，是运筹学中一个经典且重要的分支。涉及管理、交通运输、通信网络等诸多领域。12组合优化问题可用数学模型描述为：minf(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*称为该问题的最优解。组合优化的特点：可行解集合为有限点集。13几个典型组合优化问题：(1)旅行商问题（travelingsalesmanproblem,TSP）一个商人欲到n个城市巡回推销商品，已知城市i和j之间的距离为dij，如何确定一条巡回路线，使得商人从其中的某一城市出发，经过其他城市一次且仅一次后回到原出发点，且所走的路程最短。设.,0,),(,1否则在选择的路线上若边jixij14则该问题的一种数学模型为：s.t.xij∈{0,1},i,j=1,2,…,n,i≠j.参考指派问题数学模型},3,2{,1,nRRxRjiijijijijxdfminnjxniij,,2,1,11nixnjij,,2,1,1115指派问题数学模型为：s.t.xij=0或1,i,j=1,2,…,n,.ninjijijxcZ11minnjxniij,,2,1,11nixnjij,,2,1,1116(2)0-1背包问题（knapsackproblem）对于n个体积分别为ai(1,2,…,n)，价值分别为ci(1,2,…,n)的物品，如何将它们装入总体积为b的背包中，使得所选物品的总价值最大？设则该问题可用数学模型表示为：s.t.xi∈{0,1},i=1,2,…,n.,0,,1否则个物品被装入若第ixiniiixcf1maxniiibxa1,17(3)装箱问题（binpackingproblem）如何以个数最少的尺寸为1单位的箱子装入n个尺寸不超过1单位的物品。(4)机器排序问题（machineschedulingproblem）。有n个工件需要在机床A、B上加工，每个工件都必须经过先A而后B的两道工序。以Aj和Bj分别表示工件j（j=1,2,…,n）在A和B上的加工时间。问应如何安排各工件加工的顺序，才能使从机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止，所用的加工总时间最少？在组合优化问题中，有些可以用整数规划模型表示，有些则用文字叙述更易理解。上述问题描述均非常简单，但求其最优解确很困难。181.3计算复杂性概述1.算法及算法分析算法:能被机械地执行的动作（或规则）的有限集合，一个动作的一次执行称为一步。算法特征：输入、确定性、可执行性、有限性、输出。算法分析：对算法性能的讨论。算法分析目的：•对同一问题的各种可实现的算法进行比较，对它们的性能作出定量的判断。•确定算法是否存在什么性能上的限制，给算法设计提供理论上的指导。19算法复杂性：算法对时间和空间的需要量分别称为算法的时间复杂性和空间复杂性。•算法执行基本操作的次数定义为算法的时间复杂性，记为T(n)；•算法执行期间占用的计算机存储单元定义为算法的空间复杂性，记为S(n)。对于占用存储空间不是太多的问题，一般只讨论算法的时间复杂性。算法的复杂性的表示：一般表示为问题规模n（如TSP中的城市数）的函数。•当一个算法A对于规模为n的问题进行求解计算时，若所需的基本操作次数的上界（指在最坏情况下）为f(n)，则称f(n)为算法A的时间复杂性函数。•在分析复杂性时，可用其函数主要项的阶O(f(n))来表示。20•若算法A的时间复杂性为T(n)=O(f(n))，且f(n)为n的多项式函数，如O(n)、O(n3)等，则称算法A为多项式算法。•时间复杂性函数不属于n的多项式函数的算法统称为指数算法，如f(n)为2n、n!、nn等形式。算法性能：多项式算法是有效算法；指数算法不是有效算法。另外，多项式算法有较好的“闭”性。问题的难易性：若一个问题找到了多项式算法，就可以认为这个问题基本解决了。若一个问题不存在多项式算法，则称这个问题是难解的。有少数复杂度为指数函数的算法，在实践中却被证明是有效的算法，如求解线性规划问题的单纯形法就是一个突出的例子。212.P,NP,NP完全和NP难P类和NP类问题•若问题有求解它的多项式算法，则属于P类问题。•若问题仍没有找到求其最优解的多项式算法，则称这类问题为非多项式确定问题，即NP类问题。NP完全问题•NP完全（NP-complete,NP-C）问题是NP类问题中难度最大的一类问题。•为证明一个问题是NP完全的，须证明：①该问题是NP的；②所有其他NP问题可多项式归约（变换）到该问题。•现已证明的NP完全问题已上千个，但没有找到任一问题的多项式算法。•性质：①任一NP完全问题都不能用任何已知的多项式算法求解；②若任一NP完全问题有多项式算法，则一切NP完全问题都有多项式算法。22NP难问题•有些问题，不能验证它属于NP类，但可以证明所有NP问题都可以多项式归约为该问题，则这类问题称为NP难问题（NP-hard）。•一个问题是NP难问题不要求该问题属于NP类，但至少和NP完全问题有同等的难度。PNPNP完全NP难图1.1四类问题的关系图231.4优化算法及其分类优化算法：是基于某种思想和机制建立起来的、能求出满足问题要求的解的一种搜索途径或规则。按求解精度分类：•精确算法（exactalgorithm）：基于严格的数学推导和证明建立起来的、可求出问题最优解的算法，且一般要求问题能用数学模型表示，但对大规模问题计算量大，应用范围常常受到限制。•启发式算法（heuristicalgorithm）：基于直观或经验构造的算法，且一般不要求将问题表述为某种标准数学模型；在可接受的计算量内求出问题的可行解，但不能保证解的最优性。24按优化机制与行为分类：•经典算法：包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传统算法。•构造算法：用构造的方法快速建立问题的一个可行解。如运输问题中的最小元素法。•邻域搜索算法：从任一初始解出发，对其邻域的不断搜索和当前解的替换来逐步实现优化。根据搜索行为，又可将其分为局部搜索法和指导性搜索法。•基于系统动态演化的方法：将优化过程转化为系统动态的演化过程，以系统动态的演化来实现优化。•混合型算法：上述各算法从结构或操作上相混合而产生的各类算法。按其它角度分类：如确定性算法和随机性算法；局部优化算法和全局优化算法等。251.5邻域与局部搜索1.邻域（neighbourhood）定义:•在距离空间中：是指以一点为中心的一个球体。•在组合优化中：设某问题所有解构成的解空间为S。对于每个解xi∈S，有一个在某种意义上是“邻近”xi的解的集合，称集合N(xi)为xi的邻域，每个xj∈N(xi)称为xi的一个邻域解或邻居（neighbour）。此外，通常约定xj∈N(xi)﹤==﹥xi∈N(xj)。262.邻域结构（neighbourhoodstructure，也称邻域函数或解产生函数）其作用是指导如何由一个解来产生一个新的解。设计往往依赖于问题的特性和解的表达方式。函数优化与组合优化中的邻域结构的具体方式存在明显差异：•函数优化中：利用距离的概念通过附加扰动来构造邻域结构是最常用的方法，如x′=x+ηξ，其中x′为新解，x为当前解，η为尺度参数，ξ为满足某种概率分布的随机数或梯度信息等。•组合优化中：因传统的距离概念不再适用，但邻域结构的基本思想仍旧是通过对一个解进行适当变换后产生另一个解。27如TSP的解可用置换排列来表示，如排列（1,2,3,4）可表示为有4个城市的TSP的一个解。那么，k个点的交换就可认为是一种邻域结构，即Nk={xj∈N(xi)|xj可由xi经一次k交换得到}如上述排列的2点交换对应的邻域结构将产生新解（2,1,3,4）、（3,2,1,4）等。3.局部最优和全局最