高等运筹学(总)

1、1,高 等 运 筹 学,符 卓 Tel: 82655051Email: 中南大学 交通运输工程学院 （办公室：交通楼415）,2,课程内容特点,基础运筹学：单目标优化，精确算法。 高等运筹学：多目标优化，启发式算法。,3,主要内容,概论 现代运筹学的理念柔性 多目标规划 经典启发式方法 模拟退火算法 禁忌搜索算法 遗传算法,4,第1章 概论,1.1 运筹学概述 1.2 最优化问题及其分类 1.3 计算复杂性概述 1.4 优化算法及其分类 1.5 邻域与局部搜索,5,1.1 运筹学概述,1.运筹学的产生和发展 二战期间，英国海军部召集了一个专家小组，称为“Operati

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

3、ational Research Society”。 美国：1952年成立运筹学会，并创刊“Operations Research”。 中国：1956年在中科院成立我国第一个运筹学小组，1980年成立运筹学会，1982年成为国际运筹学联合会会员国。现创办的主要刊物有“运筹学学报”和“运筹与管理”、“Journal of the Operations Research Society of China” 。 相关的学术刊物还有很多。 “运筹帷幄之中，决胜千里之外”与“运筹学” 。 OR的发展与计算机的发展分不开。如果没有计算机，OR只不过是一种理论科学，不会成为应用科学。,7,8,2. 运筹学的

4、组成部分 运筹学研究的现象有三类：一是资源运用的问题，二是竞争现象，三是拥挤现象。 其内容相应地划分为三个组成部分：运用分析理论，竞争理论，随机服务理论。 运用分析理论：包括分配、选址、资源最佳利用、设备最佳运行等。常用的数学方法有线性规划、非线性规划、网络规划、动态规划、最优控制等。 竞争理论：主要方法是对策论。 随机服务理论：主要方法是排队论。,9,3. 运筹学的性质 核心：运用数学方法研究各种系统的优化途径和方案，为决策者提供科学决策依据。 研究对象：人类对各种资源的运用及筹划活动。 研究方法：定量化和模型化，尤其是运用各种数学模型和优化技术。 研究目的：了解和发现这些运用及活动的基本规

5、律，发挥有限资源的最大效益。 OR：The Science of Better Decisions. OR uses mathematics, but it is not a branch of mathematics.,10,4. 运筹学的特点 强调研究过程的完整性：问题的提出建立模型提出解案付诸实施。 强调理论与实践的结合。 5. 运筹学的应用领域 其影响继续扩大：国际运筹学联合会已有50个成员国。 应用领域不断增加：如军事运筹学、管理运筹学、交通运输运筹学、工业运筹学、农业运筹学、工程技术运筹学、计算运筹学等。 总之，凡是在某些有限的资源限制下寻求一个最优的行动方案，运筹学就有可能用得上

6、。,11,1.2 最优化问题及其分类,最优化指最小化或最大化，本课程以最小化为例。 最优化问题可分为函数优化问题和组合优化问题两大类。 1.函数优化问题 优化的对象是可在一定区间内取值的连续变量。 2.组合优化问题 优化的对象是解空间中的离散状态，即哪一个组合对象最优？ 解决的是离散事件的最优编排、分组、次序或筛选等问题，是运筹学中一个经典且重要的分支。涉及管理、交通运输、通信网络等诸多领域。,12,组合优化问题可用数学模型描述为： min f (x) s.t. g (x) 0, xS, 其中，f (x)为目标函数，g (x)为约束函数，x为决策变量，S表示有限个点组成的集合。 一个组合优化问

7、题也可用三个参数（S, F, f）来描述： S：决策变量的定义域，即解空间； F = x | xS, g (x)0：可行解区域； f ：目标函数值，满足f (x*) = min f (x)| xF 的可 行解x*称为该问题的最优解。 组合优化的特点：可行解集合为有限点集。,13,几个典型组合优化问题： (1) 旅行商问题（traveling salesman problem, TSP） 一个商人欲到n个城市巡回推销商品，已知城市i和j之间的距离为dij，如何确定一条巡回路线，使得商人从其中的某一城市出发，经过其他城市一次且仅一次后回到原出发点，且所走的路程最短。 设,14,则该问题的一种数学模

8、型为： s.t. xij0,1, i,j =1,2,n, ij. 参考指派问题数学模型,15,指派问题数学模型为： s.t. xij=0或1, i,j =1,2,n,.,16,(2) 0-1背包问题（knapsack problem） 对于n个体积分别为ai (1,2,n)，价值分别为ci (1,2,n)的物品，如何将它们装入总体积为b的背包中，使得所选物品的总价值最大？ 设 则该问题可用数学模型表示为： s.t. xi0,1, i =1,2,n,17,(3) 装箱问题（bin packing problem） 如何以个数最少的尺寸为1单位的箱子装入n个尺寸不超过1单位的物品。 (4) 机器排

9、序问题（machine scheduling problem） 。 有n个工件需要在机床A、B上加工，每个工件都必须经过先A而后B的两道工序。以Aj和Bj分别表示工件j（j=1, 2, , n）在A和B上的加工时间。问应如何安排各工件加工的顺序，才能使从机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止，所用的加工总时间最少？ 在组合优化问题中，有些可以用整数规划模型表示，有些则用文字叙述更易理解。 上述问题描述均非常简单，但求其最优解确很困难。,18,1.3 计算复杂性概述,1.算法及算法分析 算法:能被机械地执行的动作（或规则）的有限集合，一个动作的一次执行称为一步。 算法特征

10、：输入、确定性、可执行性、有限性、输出。 算法分析：对算法性能的讨论。 算法分析目的： 对同一问题的各种可实现的算法进行比较，对它们的性能作出定量的判断。 确定算法是否存在什么性能上的限制，给算法设计提供理论上的指导。,19,算法复杂性：算法对时间和空间的需要量分别称为算法的时间复杂性和空间复杂性。 算法执行基本操作的次数定义为算法的时间复杂性，记为T(n)； 算法执行期间占用的计算机存储单元定义为算法的空间复杂性，记为S(n)。 对于占用存储空间不是太多的问题，一般只讨论算法的时间复杂性。 算法的复杂性的表示：一般表示为问题规模n（如TSP中的城市数）的函数。 当一个算法A对于规模为n的问题

11、进行求解计算时，若所需的基本操作次数的上界（指在最坏情况下）为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等形式。 算法性能：多项式算法是有效算法；指数算法不是有效算法。另外，多项式算法有较好的“闭”性。 问题的难易性：若一个问题找到了多项式算法，就可以认为这个问题基本解决了。若一个问题不存在多项式算法，

12、则称这个问题是难解的。 有少数复杂度为指数函数的算法，在实践中却被证明是有效的算法，如求解线性规划问题的单纯形法就是一个突出的例子。,21,2. P, NP, NP完全和NP难 P类和NP类问题 若问题有求解它的多项式算法，则属于P类问题。 若问题仍没有找到求其最优解的多项式算法，则称这类问题为非多项式确定问题，即NP类问题。 NP完全问题 NP完全（NP-complete, NP-C）问题是NP类问题中难度最大的一类问题。 为证明一个问题是NP完全的，须证明：该问题是NP的；所有其他NP问题可多项式归约（变换）到该问题。 现已证明的NP完全问题已上千个，但没有找到任一问题的多项式算法。 性质

13、：任一NP完全问题都不能用任何已知的多项式算法求解；若任一NP完全问题有多项式算法，则一切NP完全问题都有多项式算法。,22,NP难问题 有些问题，不能验证它属于NP类，但可以证明所有NP问题都可以多项式归约为该问题，则这类问题称为NP难问题（NP-hard）。 一个问题是NP难问题不要求该问题属于NP类，但至少和NP完全问题有同等的难度。,P NP NP完全 NP难 图1.1 四类问题的关系图,23,1.4 优化算法及其分类,优化算法：是基于某种思想和机制建立起来的、能求出满足问题要求的解的一种搜索途径或规则。 按求解精度分类： 精确算法（exact algorithm）：基于严格的数学推导

14、和证明建立起来的、可求出问题最优解的算法，且一般要求问题能用数学模型表示，但对大规模问题计算量大，应用范围常常受到限制。 启发式算法（heuristic algorithm）：基于直观或经验构造的算法，且一般不要求将问题表述为某种标准数学模型；在可接受的计算量内求出问题的可行解，但不能保证解的最优性。,24,按优化机制与行为分类： 经典算法：包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传统算法。 构造算法：用构造的方法快速建立问题的一个可行解。如运输问题中的最小元素法。 邻域搜索算法：从任一初始解出发，对其邻域的不断搜索和当前解的替换来逐步实现优化。根据搜索行为，又可将其分为局部搜索

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

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

17、表示为有4个城市的TSP的一个解。那么，k个点的交换就可认为是一种邻域结构，即 Nk = xj N(xi ) | xj可由xi经一次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)，则称x*为f 在F上的全局最小（最大）解（点）。,28,以一维变量x为例，

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

19、以下山法为例介绍求目标函数值最小的局部搜索算法：从一个初始解x0F出发，利用邻域结构持续地在当前解x i的邻域中搜索比它更好的解，若能够找到这样的解，就用这个解取代x i，成为新的当前解，再对当前解重复上述过程；否则搜索过程终止，并以当前解作为算法的最终解。,30,用伪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均有

20、f(x j) f(x i) End. 以图1.2为例，若以x=4为起点用局部搜索算法搜索最小值点，则搜索到x=5这个局部最优（最小）点时就会停止。,31,局部搜索算法具有以下优点： 通用性，易实现。 灵活性。 局部搜索算法有以下不足： 搜索性能和最终解的质量依赖于初始解和邻域结构。 最终解往往是某个局部最优解。 算法的时间复杂性很难确定，取决于问题的性质与邻域结构的复杂程度。 可能的改善途径： 对大量初始解执行算法，再从中选优。 设计更复杂的邻域结构，使算法能对解空间的更大范围进行搜索。,32,改变局部搜索算法在求解过程中只接受优化解的迭代准则，在一定限度内接受恶化解，甚至是不可行解，以便跳出

21、局部最优，逼近全局最优。 需要确定新的当前解接受准则，使局部搜索算法演变为一类新的具有全局优化性能的指导性搜索算法，即通用启发式算法（metaheuristics，也称智能优化算法、现代启发式算法等），如模拟退火算法、禁忌搜索算法、遗传算法等。,33,第2章 现代运筹学理念柔性,2.1 柔性理念的内涵 2.2 运用分析中的柔性 2.3 决策分析中的柔性,34,2.1 柔性理念的内涵,运筹学内涵的要点: 以最优性或合理性为核心。 以定量化、模型化为基本方法。 以计算机为实现的主要手段。 以强烈的系统性、交叉性为特征。 现代管理与决策中,决策者的作用更加突出，他们的参与、偏好、经验与政策取向，已构

22、成决策分析的最重要的部分。 决策支持、系统分析和运用研究等都需要从理念和方法论上加以反思与发展。,35,诺贝尔奖得主Simon对管理决策问题的属性作了一种划分： 结构化问题：指问题可以明确界定，组成部分间的联系清晰，可以描述其数量关系。 非（半）结构化问题：决策目标不十分明确，问题的描述有不同程度的模糊，组成部分间的联系不能或部分不能建立数量关系。 系统分析中提出要包含人文或非结构化因素。 运筹学需要在理念、方法及模型中有新的突破、新的发展。这个发展的主要特征有： 决策者要更多地参与，并能在模型与方法中实现。 能够以恰当的方式涵盖必要的非结构化因素。 最优性的度量由纯客观的指标转向容许某些主观

23、的判断，即以“满意解”来适当取代“最优解”。 运行方式由纯程序化求解转为适当的人-机交互式求解。,36,上述特征所反映的就是要增加运筹学模型与方法的柔性。 柔性：指在解决运用分析中要处理所遇到的非结构化因素，以及在实施决策支持过程中，需要考虑决策者的经验、智慧、偏好及政策和策略因素的介入。 在模型中注入和强化其柔性，即对人文因素的接纳； 在方法论上，应注意交互式过程，即程序式求解将变为人-机交互式求解； 在追求的目标上，往往要从传统意义下的最优解改为可接受的满意解。 柔性运筹学的主要特点： 决策者的介入； 包含一些非结构化因素。,37,2.2 运用分析中的柔性,运用分析是运筹学中专门研究如何使

24、各种资源运用效率最高的理论。 企业产品结构优化问题 产品结构的优化：合理安排各种主要产品的产量，以保证获取最佳效益。 是线性规划可以解决的有代表性的问题之一，其核心是企业资源的合理利用。如：,s.t. AX b X 0,38,面对新情况,传统的解决办法遇到了困难，主要有： 除考虑资源合理配置外，还需考虑市场销售的因素，包括现实市场与潜在市场。 在买方市场环境下，产品结构的优化需涵盖一些非结构化的因素，如营销策略、产品调整战略及分段实施，还可能包含企业高层的若干秘而不宣的考虑。 要更多考虑市场信息、环境信息，应具有较快的反应能力，即动态性。 模型与方法要给决策者的介入提供可运作的方式与足够的空间

25、。,39,柔性模型：打开一个人-机接口，用来沟通与决策者的联系，并成为辅助信息的进出通道。如： (1) (2) J1J2 = J1J2 =1,2,n s.t. AX b X 0 J1为结构化变量下标集。J2为非结构化变量下标集，其选择由决策者决定。J2 =时，该模型就为传统的线性规划模型。 目标函数(1)由决策准则选定，目标函数(2)由决策者进行判定，称为人-机接口。,40,柔性模型的解的定义： 满足约束条件的解称为模型的可行解。 满足约束条件和目标函数(1)的解称为模型的部分最优解。 满足约束条件和目标函数(2)的解称为模型的部分满意解。 满足约束条件、以及目标函数(1)和(2)的解称为模型

26、的整体满意解。,41,求解过程：通过人-机会话及滚动式运行进行求解。 步骤1：令J2 =，使问题变为传统的线性规划问题，并用单纯形法对其求解，得最优解为X*。 步骤2：提交X*，请决策者评判，若满意，则X*即为整体满意解，停止；否则给出J2，并对xj（jJ2）提出修改值xj。 步骤3：将xj(jJ2)输入到柔性模型中。 步骤4：用单纯形法求解柔性模型，得部分最优解xi(iJ1)，于是有X*= (xi, xj)T,转步骤2。,42,2.3 决策分析中的柔性,多目标规划 多目标规划属多目标决策的范畴，研究在约束域中依据多个评判（或决策）准则的优化问题。 数学模型： Min (Max) Z = (f

27、1(x), f2(x), fm(x) s.t. xF 其中x = (x1, x2, , xn)T，F为可行解集合，f1(x), f2(x), fm(x)为m个目标函数。,43,“绝对最优解 ”、“非劣解” 、“选好解 ”。 在如何得到最后选用的解的方式上，可分为三种： 决策者向分析者提供偏好信息，使得分析者按此偏好信息找出的解就是选好解。 分析者只管提供非劣解，由决策者依据自己的理念、经验从中自行选出一个选好解。 决策者与分析者不断交换对解的看法，交互式地逐步改进非劣解，直到最后找到使决策者满意的选好解为止。 可见，在处理多目标规划时，融入了决策者的偏好，甚至还可以交互式地进行，体现了运筹学的

28、柔性理念。,44,第3章 多目标决策,3.1 基本概念 3.2 目标规划法 3.3 化多目标为单目标的其它方法 3.4 引进次序法 3.5 直接求非劣解法 3.6 层次分析法,45,3.1 基本概念,解的概念 劣解：可淘汰的解。 非劣解：没有其它解可以淘汰它们，但又非绝对最优解。 单目标中：任何两个解都可以比较优劣，是完全有序的。 多目标中：任何两个解不一定都可以比较出其优劣，因此只能是半序的。 多目标优化的几类方法 化多目标为单目标 引进次序法 直接求非劣解法,f2(体重) 12 10 13 9 11 8 4 7 3 6 1 5 2 f1(身高) 图3-1,46,3.2 目标规划法,对每一个

29、目标fi (x)预先规定了一个目标值fi*(i=1, 2, , m)，可构造下述评价函数,如果对其中的不同目标，要求满足的程度不一样，则可对每个目标赋予不同的优先因子Pi，评价函数变为,求评价函数u (x)最小的问题就称为目标规划（Goal Programming）问题，求解这类问题的方法称为目标规划法。,47,评价函数的构造可有多种形式，上述形式只是其中的一种。 经典的运筹学方法强调单目标的最优化。 目标规划则强调多目标的满足，即寻找一个“尽可能”满足所有这些目标值的解。 根据其模型的特征，目标规划可分为如下几种类型： 线性目标规划 线性整数目标规划 非线性目标规划,48,1. 线性目标规划

30、问题的提出 例3.1 某工厂生产I、II两种产品，已知有关数据如表3.1。问I、II两种产品各生产多少，才能使工厂获利最大？ 表3.1,解 这是一个单目标规划问题。设x1, x2分别表示产品I、II的产量，则问题的线性规划模型为 Max Z = 8x1+10 x2 s.t. 2 x1+ x211 x1+2x210 x1, x20 可求得最优解为x1=4，x2=3，目标函数的最大值为z = 62元。,49,因经营管理的需要，在制定生产计划时，除了利润之外，还需考虑其它情况，其优先顺序如下： (1)原材料的消耗不得超过拥有量。 (2)根据市场信息，考虑产品I的产量不应大于产品II。 (3)充分利用

31、设备的有效台时，尽量不加班。 (4)力争利润额不少于56元。 这样的生产计划就得综合考虑多项指标，这些指标的度量单位和各自的重要程度都不同。因此，传统的线性规划就难以给出符合要求的答案。 解决这类问题的一种有效方法：线性目标规划法。 基本思想：面对一组预定的管理目标及其轻重缓急次序，寻求一个与管理目标偏差最小的满意解。,50,2.基本概念和数学模型 偏差变量：用来表示实际值与目标值之间的差距。 d：超出目标值的差距，称正偏差变量； d：未达到目标值的差距，称负偏差变量。 绝对约束和目标约束 绝对约束：必须严格满足的等式约束和不等式约束，不满足约束条件的解称为不可行解。如例1中的(1): 2x1

32、+ x211 目标约束：可以有偏差的管理目标约束。把约束右端项看作要追求的目标值，允许发生正或负偏差，因此在这些约束中可加入正、负偏差变量。如 x1x2+ d1d1 =0,51,x1+2x2 +d2d2 =10 8x1+10 x2+d3d3 =56 目标规划的目标函数。基本形式有三种： 要求恰好达到目标值，即正、负偏差变量都要尽可能地小： min Z=f (d+ d) 要求不超过目标值，即允许达不到目标值，但正偏差变量要尽可能地小： min Z=f (d) 要求超过目标值，即超过量不限，但负偏差变量要尽可能地小： min Z=f ( d),52,对例3.1中的每个目标进行分析： 产品I的产量不

33、应大于产品II x1x2+ d1d1 =0 min Z= d1 充分利用设备的有效台时，尽量不加班 x1+2x2 +d2d2 =10 min Z= d2+ d2 希望利润值不少于56元 8x1+10 x2+d3d3 =56 min Z= d3 优先因子与权系数 最重要的目标赋予优先因子P1，次位的目标赋予优先因子P2，并规定Pk Pk+1，表示Pk比Pk+1有更大的优先权。 目标的优先级是一个定性概念，体现决策者偏好。,53,例3.1中： 产量要求为首位目标，赋予优先因子P1； 设备台时的利用为次位目标，赋予P2； 利润为第三位目标，赋予P3。 权系数wj：区别同一优先级、且度量单位相同的不同

34、目标间的差别。是一个可用数量衡量的定量指标。 优先因子与权系数由决策者按其偏好确定。 综上所述，例3.1的目标规划模型可以写为： min Z= P1 d1+ P2 ( d2+ d2)+ P3 d3 s.t. 2x1+ x211 x1x2+ d1d1 =0 x1+2x2 +d2d2 =10 8x1+10 x2+d3d3 =56 x1, x2, di, di0, i=1,2,3,54,例3.2 某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩电的销售量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的

35、目标顺序为： (1)充分利用装配线每周计划开动40小时； (2)允许装配线加班，但加班时间每周尽量不超过10小时； (3)装配电视机的数量尽量满足市场需要，因彩电的利润高，取其权系数为2。 试建立求解该问题的目标规划模型。,解 设x1, x2分别为彩色和黑白电视机的产量，则该问题的目标规划模型为 s.t. x1 + x2+ d1d1 =40 x1 + x2 + d2d2 =50 x1 + d3d3 =24 x2 + d4d4=30 x1, x2, di, di0, i=1,4 min Z=P1d1+P2d2+P3(2d3+d4),55,目标规划特点： (1)目标函数表示为偏差变量的函数，把多目

36、标的优化要求，统一到一个表达式中，把多目标问题化为单目标问题。 (2)由于引进定性化的优先因子Pk和定量化的权系数wj，因此，目标规划的目标函数是一种定性与定量分析相结合的决策公式。 (3)决策者通过调整目标的优先级和权系数，便可求出多种不同的备选方案。 (4)允许对计量单位不同的目标进行综合评价。 (5)目标规划中的约束柔性，给决策方案的选择带来了很大的灵活性。,56,3.求解线性目标规划的单纯形法 计算步骤如下： (1)建立初始单纯形表，在表中将检验数行按优先因子个数及优先顺序分别列成K行，置k=1。 (2)检查该行中是否存在负检验数，且对应的前k1行的检验数是零。若有取其中最小者对应的变

37、量为换入变量，转(3)。若无负数，则转(5)。 (3)按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。 (4)按单纯形法进行运算，建立新的计算表，返回(2)。 (5)当k=K时，计算结束。表中的解即为满意解。否则置k := k+1，返回(2)。,57,例3.3 试用单纯形法来求解例3.1。 解 将例3.1的数学模型化为标准型： min Z= P1 d1+ P2 ( d2+ d2)+ P3 d3 s.t. 2x1+ x2+ xs=11 x1x2+ d1d1 =0 x1+2x2 +d2d2 =10 8x1+10 x2+d3d3 =56 x1,

38、 x2, xs,di, di0, i=1,2,3 取xs, d1, d2, d3为初始基变量，列初始单纯形表:,58,59,进行基变换运算，得：,60,再进行一次基变换运算，得最终表：,61,3.3 化多目标为单目标的其它方法,1.分层系列法 基本思想：把目标按重要程度给出一个序列，如f1 (x), f2 (x), fm (x)，然后就逐个地求最优。 设方案变量xR0，则：,该方法有解的前提是R1, R2, , Rm-1非空。,62,2.乘除法 min 3.主要目标法 思想：解决主要目标，兼顾其它目标。 选中其中一个目标作为主要目标，而对其它目标只满足一定规格要求即可，化成求下述规划问题： R

39、= x | fifi (x)fi, i= 2, 3, m, xR,63,3.4 引进次序法,多目标问题的任何两个解只能是半序的，难以比较优劣 引进次序法的思想：另外制订一些规则，使非劣解有可能重排次序决定解的去留，一直到最后找到选好解,64,3.5 直接求非劣解法,直接求非劣解法：尽可能先把非劣解都找出来，然后让决策者自己去进一步挑选；或者是决策者和提供非劣解者互相讨论，逐步修正，最后找到一个选好解,65,3.6 层次分析法（AHP）,1.问题的提出 例3.5 设某企业拥有一笔资金，现有三种可能的投资去向：办实业、购买股票和存入银行由于不同去向所冒风险大小不等，资金利润率不一样，资金周转快慢也

40、不同问如何选择投资去向才能得到最佳投资效益？ 目标层G 准则层C 方案层P 权重 w1 w2 w3,投资效益,风险C1,利润C2,周转C3,存款P3,股票P2,实业P1,66,2.层次分析法的基本原理 以特征向量方法为基础的数学原理 设有n件物体A1, A2, An；它们的重量分别为w1, w2, wn若将它们两两地比较重量，其比值可构成nn阶矩阵A,若用重量向量 右乘矩阵A，得到,67,即AW = nW 由正矩阵的有关理论可知，W为矩阵A的特征向量，n为矩阵A的特征值 AHP法的基本思路：有一组与某一目标有关的因素，需要知道它们对目标影响程度，就可以把这些因素成对比较，构成比较判断矩阵 ，通

41、过求解判断矩阵 的最大特征值及其对应的特征向量，即可得到这些因素对目标影响的程度权重,68,根据正矩阵理论，可以证明若矩阵A（设aij = wi /wj）具有以下特点： (1) aii = 1 (i = 1,2,.,n) (2) aij = 1/ aji (i,j = 1,2,.,n,i j) (3) aij = aik / ajk (或aik akj) (i,j = 1,2,.,n,i j) 则该矩阵一定存在唯一的不为零的最大特征值max，且max = n 若求解时所构造的完全具备上述三个特性，称矩阵完全满足一致性 但在实际问题中，在两两比较时，不可能做到判断的完全一致性而存在估计误差必然导

42、致特征值及特征向量也有偏差，变成,69,为了避免使误差过大，需要检验的一致性 可用一致性比例指标CR来检验的一致性， 其中， 当 max = n 时，CI = 0，为完全一致；RI的值如下： 当CR 0.1时，认为判断矩阵一致性是可以接受的,70,3.AHP法的基本步骤 (1)建立递阶层次结构模型 需要达到的目标类； 判断好坏的准则类； 解决问题的方案措施类 (2)构造判断矩阵 判断同一层次的元素对上一级某一元素的影响程度，并将其定量化 元素aij表示对于元素Cs， Pi比Pj的相对重要程度的标度， 即两两比较的比率的赋值,71,19标度法： 一个递阶层次结构，可以构建若干个判断矩阵，其数目是

43、图中除最低一层以外的所有各层的元素之和 在建立判断矩阵时，通常只遵守aii = 1和aij = 1/ aji两个条件，再按一致性检验方法进行检验,72,(3)层次单排序及其一致性检验 层次单排序：把本层所有各元素对相邻上一层元素来说排出一个权重次序，即求判断矩阵的特征向量 根据判断矩阵进行层次单排序的方根法： 先求判断矩阵中每行元素之积Mi： 再求Mi的n次方根，得 然后对向量 进行归一化，得 得到特征向量 ,73,层次单排序的一致性检验： 计算判断矩阵的最大特征根（值）： 计算 计算 若判断矩阵不满足一致性条件（ 0.1），则需修改 ,74,(4)层次总排序及其一致性检验 层次总排序：利用层

44、次单排序的计算结果，进一步综合计算出对更上一层（或总目标层）的权重次序,75,层次总排序的一致性检验： 当CR0.10时，认为层次总排序结果具有满意的一致性，否则需要重新调整判断矩阵的元素取值,76,4.实例分析 某企业拟引进一台新设备，希望设备的功能强、价格低、维修容易，现有P1、P2、P3三种型号的设备可供选择，试运用层次分析法进行决策分析 (1)建立递阶层次结构模型 目标层G 准则层C 方案层P 权重 w1 w2 w3,引进一台满意设备,功能强C1,价格低C2,易维修C3,型号P3,型号P2,型号P1,77,(2)构造判断矩阵 G-C判断矩阵 对于总目标（G）来说，假设准则层（C）的优先

45、次序是首先考虑要功能强（C1），其次要求易维修（C3），再次才考虑价格低（C2）,Cs-P判断矩阵: 已知三种备选设备中的功能、价格和维修情况如下：,78,可分别构造C1-P、C2-P和C3-P判断矩阵：,79,(3)层次单排序及一致性检验 以G-C判断矩阵为例：,80,查表，n=3时，得RI=0.58，于是 可见，判断矩阵G-C具有满意的一致性,81,(4)层次总排序及其一致性检验 经检验，总排序具有满意的一致性 根据上述计算结果，W = (w1, w2, w3)T= (0.190, 0.511, 0.298)T，故选择设备型号P2为最优,82,5.对层次分析法的几点评价 能将决策者的主观判

46、断与偏好用数量形式表达和处理，是柔性运筹学的一项有代表性的方法. AHP是一种定性与定量相结合的方法. 标度方法及一致性判断具有认知基础. AHP运用过程中决策者偏好的合理性问题.,83,第4章 经典启发式方法,4.1 启发式方法的提出 4.2 经典启发式方法的策略 4.3 应用举例 4.4 启发式方法的特点分析,84,4.1 启发式方法的提出,精确算法：能求出问题的最优解，主要适用于解决具有良性结构的问题（即结构化问题） 良性结构问题：问题的结构比较清晰，所含各元素之间的关系明确，容易为人们所认识，能够通过建模和使用一定的算法求得最优解 良性结构问题特征： 能建立起反映该问题性质的一种“可接

47、受”模型，与问题有关的主要信息可纳入模型之中 模型所需要的数据能够得到 有判定解的可行性和最优性（或满意性）的明确准则 模型可解 求解工作所需的计算量和所需费用可以接受,85,“易解问题” ：能用精确算法求解的结构化问题，如线性规划问题、最短路径问题、最小费用流问题等 精确算法不能很好地解决的问题： 某些整数规划问题、组合优化问题，如NP难问题 不具有良性结构（非结构化）的实际问题 可能的解决途径： 忽略某些条件，使问题简化，以便使用某种标准模型而易于求解但由于问题的模型失真，得到的解通常难以付之实施 保持问题的本来面目，建立基本符合问题实际情况的非标准模型分析人员必须运用自己的感知和洞察力，

48、从有关的模型及算法中寻求其中的联系，从中得到启发，去发现可用于解决该问题的思路和途径称这种方法为启发式方法，用这种方法建立的算法为启发式算法（heuristics, heuristic algorithm）,86,4.2 经典启发式方法的策略,1.限定（Restriction） 限定所要考虑的解集合的范围 2.松弛（Relaxation） 去掉某一约束条件，以便得到一个松弛问题，使得一个精确算法或启发式算法可行有时是求出原问题的解的下界 3.逐步构解策略（Solution Building Strategy） 建立一套明确的规则，一个分量一分量地构造一组解，直至得到一个完整的解为止 分解合成策

49、略（Break-make Strategy） 将一个较大的问题，首先将其分解为若干个较小的子问题分别求解，再将子问题的解综合起来作为总问题的解,87,表上作业法初始方案,最小元素法,基本思想：“就近供应”或称“就廉供应”,3,4,2,3,4,5,Z=139543247422100,88,5.解改进策略（Local Improvement Strategy） 构造一组规则，使得从任何一初始解出发，朝着最优解方向不断地对原来的解进行改进 6.分枝定界（Branch and Bound, Tree Search） 利用在求解过程中提供的新信息，来引导新的启发式方向，消去不必要的搜索范围 在实际应用中

50、，一个启发式算法常常是上述两种或多种策略的组合 一个成功的启发式算法往往是那些有效地利用了所研究的特定问题的特殊结构的算法,89,4.3 应用举例,1多个工件在设备上加工的排序问题 例4.1 设有6个工件需要在机床A、B上加工，每个工件都必须经过先A而后B的两道工序以Aj和Bj分别表示工件j在A和B上的加工时间（分），如下表所示问应如何在两机床上安排各工件加工的顺序，才能使从机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止，所用的加工总时间最少？,90,91,算法的迭代步骤： (1)建立工件加工时间的工时矩阵,(2)在M中找出最小元素（若最小的不止一个，可任选其一）；若它在上行，

51、则将相应的工件排在最前位置；若它在下行，则将相应的工件排在最后位置 (3)将排定位置的工件所对应的列从M中划掉，然后对余下的工件重复按步骤(2)进行但此后的最前位置或最后位置是在已排定位置的工件之后或之前如此继续下去，直至把所有工件都排完为止,92,用上述算法步骤求解例4.1 工件的加工顺序为:(， ， ， ， ， ),93,2.旅行商问题(TSP) TSP：一个商人从某一城市出发，访问n个城市各一次且仅一次，然后回到原出发城市问他应走什么样的路线才能使总行程最短？ 有许多重要的应用,如： 集成电路板上插件的插接顺序问题； 物流配送车辆的行车路线编排问题（在一辆送货车装载量能满足的前提下） 求

52、解难度 还没有找到多项式算法 已证明TSP属于NP-难问题 只有对很小规模的问题才能求出最优解 对于较大规模的TSP（n40）需用启发式算法求解,94,1. Clarke-Wright节约算法 于1964年提出，是按“逐步构解策略”构造的 基本思想： 设有n个城市（点），取其中的一点，例如点1，作为起点先将每个点与起点相连，构成线路1j1(j =2, 3, , n)，即n 1条仅含一个访问点的线路总费用为,其中假设c1j= cj1然后，计算将i和j（i, j 1）连接在一条线路上所引起的路程节约值S (i, j)）： S (i, j) = 2c1i+2c1j(c1i + cij +c1j) =

53、 c1i +c1jcij S (i, j)越大，说明把i和j连接在一起使总费用减少越多若根据S (i, j)的大小来构造线路，就有可能得到总费用较小的解,95,节约算法迭代步骤： 选取起点，将起点与其它各点连接，得到n 1条线路1j1（j =2, 3, , n） 对不违背限制条件的所有可连接点对(i, j)计算节约值S (i, j) = c1i +c1jcij 将算出的S (i, j)0，按从大到小的顺序排列 按S (i, j)的上述顺序，逐个考察其端点i和j，若满足以下条件，就将弧(i, j)插入到线路中，其条件是：点i和点j不在一条线路上，且均与点1相邻（不是线路的内点） 返回步骤(4)，

54、直至考察完所有可插入弧(i, j)为止,96,例4.2 用节约算法求下述的旅行商问题，其中点1为起（终）点，各点对间的距离由下表给出,97,(1)将各点分别与点1相连，组成7条线路. (2)计算节约值S (i, j) = c1i +c1jcij 如S (2, 3) = c12 +c13c23 = 8+58 = 5 (3)将算出的S (i, j)按从大到小的顺序排列于下表中 (4)按照S(i, j)的大小顺序，考虑连接点i和点j,98,2.最邻近法 步骤如下： 任取一点作为线路的起点 寻找与上一次加进线路中的点距离最近的点，把此点加到线路中去 重复(2)，直到所有的点都已考虑，这就得到了一条线路

55、 例4.3 用最邻近法求解上例,99,1 4 2 3 5 6 7 8,100,k-交换(k-最优，k-opt)，一般取k =2, 3, 4 是用解改进策略构造的算法 基本原理是应用局部搜索的概念，通过对k条边(弧)进行交换，在初始解的邻域中对初始解进行调整，每次调整接受得到改进的可行解，直至解在其邻域内不能改进为止最终解就叫做k-最优解(k-opt) 3.2-交换(2-opt)算法,u-1,u,u+1,v-1,v,v+1,101,4.3-交换(3-opt)算法,102,4.4 启发式方法的特点分析,是寻求解决问题的一种基本原理和策略建立在经验和直观推断的基础上. 根据所采用的策略不同，算法一般

56、终止于一个可行解（如逐步构解策略），或者是一个与初始解密切相关的局部最优解（如解改进策略） 用启发式方法解决问题时强调“满意”，但不能保证得到最优解常常是得到“满意解”决策者就认为可以了，其原因主要是： 有很多问题不存在严格（绝对）最优解 有些问题，如NP难问题，要得到最优解需花费过大的代价，不合算 从实际需求出发，有时不要求问题的解具有很高的精度,103,经典运筹学中的解析式求解算法，是以数学证明和已知的性质为根据，以演绎推理为基础的；而启发式算法是以归纳推理为基础的 好的启发式算法与精确算法相比有下述优点： (1)计算步骤简单，易于实现 (2)通常不需要高深和复杂的理论知识 (3)常可以减

57、少大量的计算工作量. (4)易于将定量分析与定性分析相结合 主要缺点：担心出现所求出的最终解远离最优解 能够较好地改善此不足之处的一个有效途径，就是运用将在后续各章中介绍的通用启发式算法（metaheuristics）来构造求解相关问题的算法,104,第5章 模拟退火算法,模拟退火算法（Simulated Annealing, 简称SA）是Kirkpatrick等人于1982年提出的一种适合求解大规模组合优化问题，特别是NP-难问题的通用启发式算法 算法思想源于对固体物质退火过程的模拟；采用Metropolis接受准则；并用一组称之为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解 SA的物理背景：固体物质退火过程 使算法跳离局部最优的关键：Metropolis接受准则 算法应用的前提：冷却进度表的合理选择,105,主要内容,5.1 固体退火过程和Metropolis准则 5.2 模拟退火算法的基本思想和步骤 5.3 模拟退火算法关键参数和操作的设计 5.4 模拟退火算法实现与应用 5.5 模拟退火算法的改进,106,5.1 固体退火过程和Metr