高等运筹学 (2)精选文档.ppt

高等运筹学1 1本讲稿第一页，共二十页4.1 启发式方法的提出 精确算法：能求出问题的最优解，主要适用于解决具有良性结构的问题（即结构化问题）良性结构问题：问题的结构比较清晰，所含各元素之间的关系明确，容易为人们所认识，能够通过建模和使用一定的算法求得最优解 良性结构问题特征：(1)(1)能建立起反映该问题性质的一种能建立起反映该问题性质的一种“可接受可接受”模型，与问模型，与问题有关的主要信息可纳入模型之中题有关的主要信息可纳入模型之中 (2)(2)模型所需要的数据能够得到模型所需要的数据能够得到 (3)(3)有判定解的可行性和最优性（或满意性）的明确准则有判定解的可行性和最优性（或满意性）的明确准则 (4)(4)模型可解模型可解(5)(5)求解工作所需的计算量和所需费用可以接受求解工作所需的计算量和所需费用可以接受 2 2本讲稿第二页，共二十页“易解问题”：能用精确算法求解的结构化问题，如线性规划问题、最短路径问题、最小费用流问题等精确算法不能很好地解决的问题：某些整数规划问题、组合优化问题，如某些整数规划问题、组合优化问题，如NPNP难问题难问题 不具有良性结构（非结构化）的实际问题不具有良性结构（非结构化）的实际问题可能的解决途径：忽略某些条件，使问题简化，以便使用某种标准模型而易于求忽略某些条件，使问题简化，以便使用某种标准模型而易于求解但由于问题的模型失真，得到的解通常难以付之实施解但由于问题的模型失真，得到的解通常难以付之实施 保持问题的本来面目，建立基本符合问题实际情况的非标准模保持问题的本来面目，建立基本符合问题实际情况的非标准模型分析人员必须运用自己的感知和洞察力，从有关的模型及型分析人员必须运用自己的感知和洞察力，从有关的模型及算法中寻求其中的联系，从中得到启发，去发现可用于解决该算法中寻求其中的联系，从中得到启发，去发现可用于解决该问题的思路和途径称这种方法为问题的思路和途径称这种方法为启发式方法启发式方法，用这种方法建立，用这种方法建立的算法为的算法为启发式算法启发式算法（heuristics,heuristic algorithmheuristics,heuristic algorithm）3 3本讲稿第三页，共二十页4.2 经典启发式方法的策略 1.限定（Restriction）限定所要考虑的解集合的范围 2.松弛（Relaxation）去掉某一约束条件，以便得到一个松弛问题，使得一个精确算法或启发式算法可行有时是求出原问题的解的下界 3.逐步构解策略（Solution Building Strategy）建立一套明确的规则，一个分量一分量地构造一组解，直至得到一个完整的解为止分解合成策略（Break-make Strategy）将一个较大的问题，首先将其分解为若干个较小的子问题分别求解，再将子问题的解综合起来作为总问题的解 4 4本讲稿第四页，共二十页5.解改进策略（Local Improvement Strategy）构造一组规则，使得从任何一初始解出发，朝着最优解方向不断地对原来的解进行改进 6.分枝定界（Branch and Bound,Tree Search）利用在求解过程中提供的新信息，来引导新的启发式方向，消去不必要的搜索范围在实际应用中，一个启发式算法常常是上述两种或多种策略的组合一个成功的启发式算法往往是那些有效地利用了所研究的特定问题的特殊结构的算法 5 5本讲稿第五页，共二十页4.3 应用举例 1多个工件在设备上加工的排序问题 例4.1 4.1 设有设有6 6个工件需要在机床个工件需要在机床A A、B B上加工，每个工件都必须经过先A而后B的两道工序以的两道工序以A Aj j和和B Bj j分别表示工件分别表示工件j j在在A和和B B上的加工时间（分），如下表所示问应如何在两机床上上的加工时间（分），如下表所示问应如何在两机床上安排各工件加工的顺序，才能使从机床安排各工件加工的顺序，才能使从机床A上加工第一个工件上加工第一个工件开始到在机床开始到在机床B B上将最后一个工件加工完为止，所用的加工上将最后一个工件加工完为止，所用的加工总时间最少？总时间最少？工件工件加工时间加工时间设备设备 A AB B 6 6本讲稿第六页，共二十页工件加工件加工顺序工顺序 设设备备 时间时间 20 40 60 80 100 120 140 160 20 40 60 80 100 120 140 160 1801801-2AA A1 1A A2 2BB B1 1B B2 22-1AA A2 2A A1 1BB B2 2B B1 1工件加工件加工顺序工顺序 设设备备 时间时间 20 40 60 80 100 120 140 160 20 40 60 80 100 120 140 160 1801802-3AA A2 2A A3 3BB B2 2B B3 33-2AA A3 3A A2 2BB B3 3B B2 27 7本讲稿第七页，共二十页算法的迭代步骤：(1)建立工件加工时间的工时矩阵(2)(2)在在MM中找出最小元素（若最小的不止一个，可任选其中找出最小元素（若最小的不止一个，可任选其一）；若它在上行，则将相应的工件排在最前位置；若一）；若它在上行，则将相应的工件排在最前位置；若它在下行，则将相应的工件排在最后位置它在下行，则将相应的工件排在最后位置 (3)(3)将排定位置的工件所对应的列从将排定位置的工件所对应的列从M中划掉，然后对余下的工件重复按步骤(2)(2)进行但此后的最前位置或最进行但此后的最前位置或最后位置是在已排定位置的工件之后或之前如此继续下后位置是在已排定位置的工件之后或之前如此继续下去，直至把所有工件都排完为止去，直至把所有工件都排完为止 8 8本讲稿第八页，共二十页用上述算法步骤求解例4.1工件的加工顺序为:(，)工件工件加工时间加工时间设备设备 1 14 4A AB B 9 9本讲稿第九页，共二十页2.旅行商问题(TSP)TSP：一个商人从某一城市出发，访问n个城市各一次且仅一次，然后回到原出发城市问他应走什么样的路线才能使总行程最短？有许多重要的应用,如：集成电路板上插件的插接顺序问题；物流配送车辆的行车路线编排问题（在一辆送货车装载量能满足的前提下）求解难度还没有找到多项式算法已证明TSP属于NP-难问题只有对很小规模的问题才能求出最优解对于较大规模的TSP（n40）需用启发式算法求解 1010本讲稿第十页，共二十页1.Clarke-Wright节约算法节约算法 于1964年提出，是按“逐步构解策略”构造的 基本思想：设有设有n n个城市（点），取其中的一点，例如点个城市（点），取其中的一点，例如点1 1，作为起点先将每个，作为起点先将每个点与起点相连，构成线路点与起点相连，构成线路1 1j j1(1(j j=2,3,=2,3,n)n)，即即n n 1 1条仅含一条仅含一个访问点的线路总费用为个访问点的线路总费用为其中假设其中假设c c1 1j j=c cj j1 1然后，计算将然后，计算将i i和和j j（i i,j j 1 1）连接在一条线路上所引连接在一条线路上所引起的路程节约值起的路程节约值S S(i i,j j)）：）：S S(i i,j j)=2)=2c c1 1i i+2+2c c1 1j j(c c1 1i i+c cij ij+c c1 1j j)=)=c c1 1i i+c c1 1j jc cij ij S S(i i,j j)越大，说明把越大，说明把i i和和j j连接在一起使总费用减少越多若根据连接在一起使总费用减少越多若根据S S(i i,j j)的大小来构造线路，就有可能得到总费用较小的解的大小来构造线路，就有可能得到总费用较小的解 1111本讲稿第十一页，共二十页节约算法迭代步骤：1)选取起点，将起点与其它各点连接，得到n 1条线路1j1（j=2,3,n）2)对不违背限制条件的所有可连接点对(i,j)计算节约值S(i,j)=c1i+c1jcij3)将算出的S(i,j)0，按从大到小的顺序排列4)按S(i,j)的上述顺序，逐个考察其端点i和j，若满足以下条件，就将弧(i,j)插入到线路中，其条件是：点i和点j不在一条线路上，且均与点1相邻（不是线路的内点）5)返回步骤(4)，直至考察完所有可插入弧(i,j)为止1212本讲稿第十二页，共二十页例例4.24.2 用节约算法求下述的旅行商问题，其中点1为起（终）点，各点对间的距离由下表给出 ji123456781-859121312172-81517711143-78107124-31711165-1811156-887-51313本讲稿第十三页，共二十页(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 弧弧(i,j)(7,8)(6,8)(4,5)(6,7)(5,8)(2,6)(5,7)S(i,j)24221817141413弧弧(i,j)(2,8)(4,7)(4,8)(3,7)(3,8)(2,7)(3,5)S(i,j)111010101098弧弧(i,j)(3,6)(3,4)(5,6)(4,6)(2,3)(2,5)(2,4)S(i,j)87755321414本讲稿第十四页，共二十页2.最邻近法 步骤如下：1)任取一点作为线路的起点 2)寻找与上一次加进线路中的点距离最近的点，把此点加到线路中去 3)重复(2)，直到所有的点都已考虑，这就得到了一条线路 例例4.3 4.3 用最邻近法求解上例 1515本讲稿第十五页，共二十页 1 1 4 4 2 2 3 5 3 5 6 6 7 7 8 8j ji i2 23 34 45 56 67 78 81 18 85 59 91212 1313 1212 17172 2-8 81515 17177 71111 14143 3-7 78 810107 712124 4-3 31717 1111 16165 5-1818 1111 15156 6-8 88 87 7-5 51616本讲稿第十六页，共二十页k-交换(k-最优，k-opt)，一般取k=2,3,4 是用解改进策略构造的算法 基本原理是应用局部搜索的概念，通过对k条边(弧)进行交换，在初始解的邻域中对初始解进行调整，每次调整接受得到改进的可行解，直至解在其邻域内不能改进为止最终解就叫做k-最优解(k-opt)3.2-交换(2-opt)算法 1717本讲稿第十七页，共二十页4.3-交换(3-opt)算法 1818本讲稿第十八页，共二十页4.4 启发式方法的特点分析 是寻求解决问题的一种基本原理和策略建立在经验和直观推断的基础上.根据所采用的策略不同，算法一般终止于一个可行解（如逐步构解策略），或者是一个与初始解密切相关的局部最优解（如解改进策略）用启发式方法解决问题时强调“满意”，但不能保证得到最优解常常是得到“满意解”决策者就认为可以了，其原因主要是：有很多问题不存在严格（绝对）最优解有些问题，如NP难问题，要得到最优解需花费过大的代价，不合算从实际需求出发，有时不要求问题的解具有很高的精度 1919本讲稿第十九页，共二十页经典运筹学中的解析式求解算法，是以数学证明和已知的性质为根据，以演绎推理为基础的；而启发式算法是以归纳推理为基础的 好的启发式算法与精确算法相比有下述优点：(1)计算步骤简单，易于实现(2)通常不需要高深和复杂的理论知识(3)常可以减少大量的计算工作量.(4)易于将定量分析与定性分析相结合 主要缺点：担心出现所求出的最终解远离最优解能够较好地改善此不足之处的一个有效途径，就是运用将在后续各章中介绍的通用启发式算法（metaheuristics）来构造求解相关问题的算法 2020本讲稿第二十页，共二十页