数学建模-第一章组合优化模型与计算复杂性.ppt

第一章 组合优化模型与计算复杂性,组合优化理论,Combinatorial Optimization Theory,第一章 组合优化模型 与计算复杂性,1 组合优化模型与算法,2 计算复杂性问题,3 启发式算法,第一章 组合优化模型与计算复杂性,模型（model）是所研究的系统、过程、事物或概念的一种表达形式.,1 组合优化模型与算法,（一)模型的概念,模型不是研究对象本身，而是对研究对象的一种抽象，它反映现实中对象系统的主要特征，但它又高于现实，因而具有同类问题的共性.,由于研究目的的不同，对于同一个对象系统，可以建立完全不同的模型，分别反映该系统的不同侧面；出于相同的研究目的，对于同一个对象系统，也可能建立不同的模型，反映不同的研究角度、考察因素和价值取向.,一、关于模型,1 组合优化模型与算法,（二）模型的本质,从系统概念上看，模型是系统中各种关系的表达形式.因此，建立模型要从状态和过程两个方面去寻找、把握和描述各系统要素之间的相互关系.,状态：事物在某个时刻所处的状况或表现形态,过程：事物状态的变化在时间上的持续和空间上的延伸,过程和状态两者紧密联系、不可分割，状态决定和影响过程，过程又决定和影响新的状态.,状态和过程是相对的.,从认识论上看，模型是作为认识与实践活动的中介.,现实世界,认识（信息）,模 型,实践活动,概念化,用信息载体表达,决策（行动方案）,产品和服务,模型化过程示意图,模型既是认识的表达，又是实践活动的先导.,模型参与认识世界和改造世界的不断的循环往复过程，既是认识不断深化的体现，又是实践活动不断拓展的体现.,第一章 组合优化模型与计算复杂性,1 组合优化模型与算法,从信息论上看，模型和认识之间存在密切的反馈关系.从已知信息可以通过模型加工产生出新的信息，相关信息的积累可以从量变产生质变，形成新的概念，促使认识深化.,因此，模型的建立和完善不仅要注重对系统物质形态和能量形态的认识、把握和描述，而且也依赖于对系统相关信息不断的采集、积累和加工，这就是用模型研究问题的现实活动.,（三）模型的分类,1、原样模型,原样模型是在工程开发末期建立的一种具象实体，是具有实物形态的模型.,它与目的工程在结构和过程方面基本相同.,原样模型经过试验改进和完善后便是所要开发的目的工程.,新产品的样机、新著作的原稿,第一章 组合优化模型与计算复杂性,1 组合优化模型与算法,2、相似模型,相似模型是根据不同系统间的相似规律（包括几何相似、逻辑相似和过程相似等）而建立的用于研究的模型.,3、图形模型,地球仪、船体放样模型、飞机风洞实验模拟模型等等,图形模型可以表达非常丰富的内容，主要有：,图画 一种可以示形的图形；,草图 一种可以示意的图形；,框图 一种可以表示系统的部分之间或部分 与整体之间联系的图形；,称为不严格图（没有严格的规范）,系统分析和设计人员常常借助于这些图形模型来开发、构建一个新系统的想象力和创造力，逐步引申出与之有关的问题和需要进一步探索的问题，使所要开发的系统变得越来越清晰、越来越具体.,逻辑图 一种可以反映因素或对象间逻辑关系 的图形；,如：程序流程图、控制关系图 etc.,工程图 一种可以反映物体确定的结构和顺序 关系的图形；,如：建筑工程图、铁路站场配置图 etc.,图论图 包括图论所定义的无向图 G(V，E)、有向图 G(V，A)、加权有(无)向图G(V，A(E)，w).,关系,称为严格图（有严格确定的结构形式和规范）,4、数学模型,数学模型是指运用数学符号和公式来表达、研究对象系统的结构或过程的模型.,数学模型是用数学的语言、方法去近似地刻画实际,是由数字、字母或其他数学符号组成的，描述现实对象数量规律的数学公式、图形或算法.,是对现实对象本质属性的抽象而又简洁的刻画，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略.,Go back,第一章 组合优化模型与计算复杂性,二、数学模型,Example 1,七桥问题,18世纪的德国有个哥尼斯堡城，在流贯全城的普雷尔河两岸和河中两个岛之间架设了七座桥，把河的两岸和两岛连接起来，能否有这样一种走法，它通过每座桥一次且仅一次.,该问题由Euler在1736年解决,Solution:,1 组合优化模型与算法,A,B,C,D,显然，解决该问题时，两岸和岛的大小、形状以及桥的长短曲直都无关，重要的是什么？,每块陆地间有几座桥,对问题进行数学抽象：,把两岸和两岛都看做顶点，将连接这些顶点的桥当作边，于是得到一无向图.,则七桥问题就成为无向图中是否存在通过每一边一次且仅一次的路（即一笔画）问题.,第一章 组合优化模型与计算复杂性,1 组合优化模型与算法,A,B,C,D,Euler 在他的论文中证明：,一个图中存在一笔画的充要条件是同时满足：,1、图是连通的；,2、与图中每一顶点（可能有两点例外）相连的边（线度）必须是偶数条.,这是关于图论的第一篇论文,见图可知，与四个顶点相连的边都是奇数条，因而不可能存在通过每条边一次且仅一次的画法，即一笔画不存在.故七桥问题不可能有解.,问题原型七桥问题,数学模型一笔画问题,无 解(一次过七座桥不可能),无 解(一笔画不可能),数学抽象,逻辑推理,翻译回去,有无解？,这是利用数学模型分析和解决问题的一个成功范例,（一）数学模型的特点,1、高度的抽象性,数学方法不仅要抛开事物的次要属性，突出事物的本质属性，而且要舍弃事物的物质和能量方面的具体内容，只考虑其数量关系和空间形式，同时还要把这些数量关系和空间形式作进一步的抽象，加以形式化和符号化，以便能够进行逻辑推理和数值运算.,这种高度的抽象性，实质是对事物认识上的高度概括和深化，对同类问题包含更多的经验和理解.,第一章 组合优化模型与计算复杂性,1 组合优化模型与算法,2、高度的精确性,数学方法的高度精确性表现在三个方面：,一是表达各种因素、变量和它们之间的关系相当明确、清楚；二是逻辑推演和运算规则十分严密；三是结论非常确定.,数学方法可以处理多变量、关系复杂的问题，可在有意义的范围内获得令人满意的计算精度.,特别适合于揭示事物的量的规定性，成为定量研究的有力工具.,3、应用的普适性,数学方法的高度抽象和精确，使之比任何一种科学方法的应用范围都更为广泛.,只存在尚未运用数学方法的领域而不存在不能运用数学方法的领域.,许多相同形式的数学模型可用于不同的实际问题，具有重要类比和借鉴意义.数学方法的形式化和公理化，使模型本身、计算过程和计算结果都便于交流，数学模型易变动，便于修改和改变计算关系，分析和求解问题速度快，求解成本低.,数学模型缺乏直观性、形象性和实时感,第一章 组合优化模型与计算复杂性,1 组合优化模型与算法,（二）数学模型分类,数学模型分类的方法很多，如：,1、按所研究问题的性质分类,静态模型与动态模型,确定型模型与随机型模型,连续模型与离散模型,线性模型与非线性模型,宏观模型与微观模型,2、按模型的解的特征分类,解析模型与数值模型,3、按模型所用的数学方法分类,初等模型、微分方程模型、差分方程模型、优化模型等,4、按模型研究的实际范畴分类,人口模型、生态系统模型、交通流模型、经济模型、基因模型等,5、按对实际问题了解的程度分类,白箱模型、灰箱模型、黑箱模型,第一章 组合优化模型与计算复杂性,1 组合优化模型与算法,（三）数学建模的基本步骤,数学模型因问题不同而异，对同一问题，从不同角度、不同要求出发，甚至问题的解表示结构不同，都可以建立不同的数学模型.建立数学模型也没有固定的方法、标准.不同的实际问题，建模模式千差万别.,在此介绍通常的几个步骤：,数学建模问题直接来源各领域实际，往往含糊不清（目的、条件、类型 etc.）.首先，要对该问题进行全面的、深入细微的调查和研究.明确所解决问题的性质，着手收集数据；,1、明确问题,合理地、有目的地,注意精度,2、合理假设,现实问题错综复杂，涉及面非常之广.一个数学模型面面俱到、无所不包地反映一个现实是不可能的，即使可能，也因其过于复杂而很难求解，也是没有必要的.所以，要作合理的假设.,1、简化问题2、限定适用范围,但也不能忽略实质相关的因素,作假设的依据通常是出于对问题内在规律的认识,或来自对数据或现象的分析，也可以是二者的综合.善于辨别问题的主次，抓住主要因素，通过合理假设,使问题简化以便进行数学描述.,假设是在模型的建立、求解和分析过程中完善.,通常开始让问题尽可能简化,第一章 组合优化模型与计算复杂性,1 组合优化模型与算法,3、建立模型,建模时，要分清问题的类型恰当使用数学工具；抓住问题的本质简化变量之间的关系.,用什么样的方法建立数学模型，没有绝对的标准；数学模型的形式可以是多种多样，数学公式、表格、图形、算法.,模型的优劣在于是否采用了恰当的方法，合理地描述了实际问题，而不在于是否用到了高深的数学工具.,数学建模是一个过程.,4、模型求解,不同的模型要用到不同的数学工具求解.这就要求从事实际工作者对相应的数学分支知识有一定的了解.,可借助计算机，特别是利用数学工具软件.,5、模型分析,对模型求出的解进行数学上的分析，有助于对实际问题的解决.,如：,结果的误差分析,误差是否在允许的范围内,分析误差来源：,建模假设的误差；,数据测量的误差；,近似求解方法的误差；,计算工具的舍入误差.,结果的统计分析,结果是否符合特定的统计规律,模型对数据的灵敏度分析,模型的结果是否会因数据的微小改变而发生大的变化,对假设的鲁棒性分析,模型的结果是否对某一假设非常依赖,不同模型间的对比分析,robustness,第一章 组合优化模型与计算复杂性,1 组合优化模型与算法,6、模型检验,将求解结果和分析结果翻译回到实际问题之中，与实际现象、实际数据进行比较，检验是否与实际吻合.如果吻合较好，则模型及其结果可以应用于实际问题；如果吻合不好，则需要对模型进行修正.,7、改进模型,吻合不好，问题常常出现在模型假设上.可能由于假设了过于苛刻的条件，或者忽略了一些不该忽略的因素.所以,要对实际问题中的主次因素再次分析,对模型进行修改、补充、完善.需要多次反复才能达到比较满意的程度。,8、模型应用,数学建模最终的目的是为了解决问题.一方面可以解释以前的实践成果；另一方面可以为现在的实际问题提供解决方案，甚至可以对一些不确定的现象或规律作出预测.,现实问题,简化、假设,建立模型,求解模型,检验分析模型,模型应用,观察、分析,收集数据,确定主要因素,及相互关系,Go back,第一章 组合优化模型与计算复杂性,三、组合优化模型,Example 2,某商场根据客流量统计得出一周中每天所需要的营业员数如表：,营业员配置问题,如果规定每个营业员每周连续工作 5 天，休息 2 天，求总人数最少的营业员排班方案.,Solution:,设 xj 为从周 j 开始连续工作 5 天的营业员人数，j=1,7(其中 x7 为周日开始连续工作 5 天的营业员数)，则,可行解集是有限集,1 组合优化模型与算法,Example 3 旅行商问题,（Traveling Salesman Problem）,TSP:,有一位旅行售货员，欲到城市 v1，v2,，vn 进行商品销售，已知：的距离为 wij.(,).他从其中某个城市出发，需访问每一个城市一次而回到出发的城市.问应如何计划他的旅行路线，使他所走路线的总长度最短？,TSP可分为：对称（dij=dji)和非对称（dij dji）距离两种,第一章 组合优化模型与计算复杂性,1 组合优化模型与算法,Hamilton 回路：,不含平行边及自环,这是1856年，Hamilton 首先提出的所谓环球航行问题而得名。它的存在性远比 Eular 回路的存在性复杂得多。,最优 Hamilton 回路：,在赋权图中，权和最小的 Hamilton 回路.,过简单图 G 的每一个顶点一次且仅一次的回路.,最优旅行商问题与最优 Hamilton 回路一样吗？,如果不满足三角不等式，则可通过求最短路方法，构造新图，使之满足三角不等式.所以以下仅讨论最优的 Hamilton 回路.,2 5,2 3,Theorem 1 如果赋权图满足三角不等式（欧氏距离），则它的最优旅行商回路与最优 Hamilton 回路相同（Hamilton 回路存在时）.,第一章 组合优化模型与计算复杂性,1 组合优化模型与算法,TSP 问题的数学模型（非对称的）：,v6,v4,v5,v3,v2,v1,Note：条件(1)，(2)表示每个城市经过一次，但不能保证它可行.,要求局部不构成圈，条件(3)就是为了约束这一点.,共同特点：可行方案是有限的 组合优化问题,Definition 1 组合优化问题是一个极小化（或极大化）的问题，它是由以下三部分组成：,（1）实例集合；,（2）对每个实例 I，有一个有穷的可行解集合 S(I)；,（3）目标函数 f，它对于每个实例 I 和每个可行解 S(I)，赋以一个实数 f(I,).则实例I的最优解为这样一个可行解*S(I),它使得对于所有S(I)，都有(I,*)f(I,)（f(I,*)f(I,)）.,问题：一类实际问题的数学模型的总称，如TSP、LP etc；实例：（一个问题中总包含了若干个参数）对问题 给定一组参数所得到的例子.,第一章 组合优化模型与计算复杂性,1 组合优化模型与算法,组合优化的数学模型：,Min f(x)s.t.g(x)0 xD,其中x为决策变量,f(x)为目标函数,g(x)为约束函数,D为决策变量的定义域,F=x|x D,g(x)0可行域(有限集),很多组合优化问题都可以给出整数线性规划描述，甚至在一些时候还不得不利用整数线性规划的技巧来解.当然也可以用文字、网络等来叙述.,线性规划是连续模型，但由于它的解的特殊结构，也可以作为组合优化问题考虑.,四、关于算法,有两种思想，像珠宝商放在天鹅绒上的宝石一样熠熠生辉，一个是微积分，另一个就是算法，微积分以及在微积分基础上建立起来的数学分析体系造就了现代科学，而算法则造就了现代世界.,伯林斯基（D.Berlinski）,算法思想：指通过把数学问题的求解分解为简单的、刻板的、重复的机械动作，达到以数目较多的、简单的量的工作去实现较复杂的质的目的.,算法思想是数学发展的一个重要源泉,20 世纪中叶计算机的问世是人类智力最伟大的成就之一.算法是计算机的灵魂，随着计算机融入现代科学实践和社会生活的各个方面，算法思想的意义与作用日益为数学家所认识.是数学发展的机械化之路.,第一章 组合优化模型与计算复杂性,一个科学的计算过程，指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰描述.,算法是相对问题而言的，不单单是针对问题的某个实例.,算法：,Note：,假设你想把某个解决问题的方法传授给一台没有任何智能的机器，以便由它来帮你完成解决这类问题,机器会要求你怎么做？,(算法的能行性),你当然不能只告诉它一个大概或者模棱两可、含糊其辞，而应该明确无误地告诉它所有解决问题的细节，而且这些细节应详细到机器可以执行的程度（机械性）；你当然也不可能无休止地进行传授，而只能用到一些有限的符号，告诉它一些有限的规则（有限性）.,1 组合优化模型与算法,如果算法从前一步到后一步的运行是由当时状态唯一确定的.如：单纯形法，表上作业法.,遗传算法是随机性算法.,确定性算法：,数学上常常将算法分为数值算法和非数值算法.一般来说，数值算法用于科学计算，主要进行代数运算；而非数值算法则用于数据处理，主要进行比较和逻辑运算（也含代数运算）.,第一章 组合优化模型与计算复杂性,对于一个极小化（极大化）优化问题，如果给定任意一个实例I，算法A总能找到一个可行解*S（I）。使得 f(I,*)f(I,)（f(I,*)f(I,)）,启发式算法（近似算法，在4 中介绍）,组合优化总存在最优算法，仅讨论可计算问题,最优算法：,是否任何数学问题都有算法求解吗？,答案是否定的（不可计算）,停机问题：给定一个带输入的计算机程序，它会停机 吗？,英国数学家图灵(Turing)证明了不存在一个算法，它能对该问题的一切实例给出正确答案.,D.Hilbert 23个问题之10 Diophantus 方程的可解性.（求出一个整系数方程的整数根）,算法的正确性不蕴含算法的有效性,1 组合优化模型与算法,五、算法设计的基本方法,本节介绍算法设计的一些基本方法.在进行复杂的算法设计时，常常利用这些基本方法（思想），有必要熟练掌握.,（一）穷举法,穷举法：穷举所有可能的解并进行比较和选优的方法.,优点：获得最优解是确切无疑的（算法的正确性）,对于运算规模较小的、运算时间允许的优化问题，如无适合该问题的优化算法时，可采用穷举法.,缺点：需要大量的机时和内存空间（算法的有效性）,引言中对TSP问题已有说明，复杂性为O(n-1)!),采用穷举法的关键在于：1、能否在理论上确定所求解问题的全部可行解集；2、对所求解问题的全部可行解集进行比选是否可能.（计算时间复杂性）,第一章 组合优化模型与计算复杂性,（二）登山法（也称贪心法）,登山法：从对问题的某一初始推测或初始解出发，逐步逼近给定的目标，并尽可能快地逼近更好的解；当进行到某一步，不能再继续逼近时，算法便终止.,得到的是近似解或局部最优解,方法简单、适用面广,登山法是一个多步决策过程，每一步的选择都是为了能构成问题的一个可行解，同时使目标函数的值增加最大或最小.,选择过程是以某些最优化量度为依据.,最优化量度可以是目标函数，也可以是别的量度，它的选择是登山法的关键.,1 组合优化模型与算法,TSP 的距离矩阵,Example 2 用登山法求 TSP.,v5,v4,v3,v2,v1,4,1,4,3,2,3,5,7,2,1,Solution:,优化准则：最短距离.,从 v1 出发，有4 个选择，按优化准则：选 v2;,得：v1 v2 v5 v3 v4 v1,总距离为：14,复杂性为 O(n2).,记住：没有免费的午餐！,从选择 p 个不同的城市出发，分别用登山法得到 p 个结果.比较得距离和最短的路线.,复杂性为 O(pn2).,但求得的解更接近于最优解，如从 v2 出发，得：,v2 v1 v3 v4 v5 v2,总距离为：10,这是最优解（运气好）.,也可以从一个可行解出发，交换相邻两个城市位置,优化准则：总距离下降.,v1 v2 v5 v3 v4 v1,第一章 组合优化模型与计算复杂性,（三）分枝与定界法,分枝与定界法的基本思想是对有约束条件的最优化问题的所有可行解（其数目为有限集）空间适当地进行搜索.,具体执行时，把可行解空间不断分割为越来越小的子集（称为分枝），并确定每个分枝内的解值的下界或上界（称为定界）.在每次分枝后，对凡是界超出已知可行解值的子集被剪去，从而不断缩小搜索范围.,这个过程一直进行到找出最优解为止，该可行解的值不大于或不小于任何子集的界.,优点：1、适用面广 2、可检查较少的解（运气好）3、可获得最优解,缺点：本质是穷举，复杂性大于穷举法,给出一个重要思想:设门槛(称为隐枚举),1 组合优化模型与算法,设,如果 则称问题（2）是问题（1）的松弛问题.,Note:,1、松弛问题未必比原问题难解；,如：整数规划与线性规划；TSP 与指派问题 etc.,如：A：寻找全国18 岁百米最快的运动员.,B：寻找全国所有百米最快的运动员.,显然，B 问题是 A 问题的松弛问题，且B 问题更易解.,2、如果松弛问题易解，则先解松弛问题是有益的.,1）设 x0 是松弛问题的最优解，且 则原问题已解,2）即使 给出了原问题最优值的界 f(x0).,x0,B,A,B,A,x0,第一章 组合优化模型与计算复杂性,分枝与定界法为什么能少检查一些解？,B,10s,B1,B2,10.2s,*,10s,B3,B4,10.3s,*,几点注意：,确定问题（子问题）的最优值的界,通常是通过求解松弛问题，用松弛问题的解作为界，也可以用启发式算法得到.,Note:松弛问题选择的原则,1、松弛问题要与原问题的 最优值尽量接近；,2、松弛问题要尽量容易解.,这两个原则不易统一，所以可选择不同的松弛问题,1 组合优化模型与算法,划分方法的选择,原则是希望分出来的子问题容易被查清，可加快计算.,选哪个活问题先检查,1、先检查最大上界（极大化问题）的活问题,优点：检查子问题较其他规则为少；,缺点：计算机储存量较大.,2、先检查最新产生的最大上界的活问题,优点：计算机储存量较少；,缺点：需要更多的分支运算.,选择的不同，提供了发挥的余地,分枝与定界法的重要在于它提出了一类新的思路（隐枚举法），使得许多原来不好解决的问题有了解决的可能性.（具有普适性）,第一章 组合优化模型与计算复杂性,（四）分治法,分治法就是把原问题分成若干个规模较小的子问题，这些子问题互相独立且与原问题形式相同，对每个子问题分别求解，然后将各子问题的解合并得到原问题的解.,如果子问题仍较复杂，可递归使用上述方法.,Note：问题的类别在细分过程中不允许改变，改变的只是问题的尺度.,分治法的基本步骤：,分治法在每一层递归上都有三个步骤：,分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；,解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；,合并：将各个子问题的解合并为原问题的解.,1 组合优化模型与算法,整序问题的快速算法是典型的分治策略运用.,8 1 9 6 7 5 3 2,8,1,9,6,7,5,3,2,合并,合并,合并,合并,1 8,6 9,5 7,2 3,1 6 8 9,2 3 5 7,1 2 3 5 6 7 8 9,合并,合并,合并,第一章 组合优化模型与计算复杂性,分治法所能解决的问题一般具有以下几个特征：,1、该问题的规模缩小到一定的程度就可以容易地解决;,2、该问题可以分解为若干个规模较小的相同问题；,3、利用该问题分解出的子问题的解可以合并为该问 题的解；,4、该问题所分解出的各个子问题是相互独立的，即 子问题之间不包含公共的子子问题.,如何使用，因问题而异.,分治法的应用很广，如铁路运输技术计划中的空车调度计划等.,1 组合优化模型与算法,（五）递归方法,递归就是自己调用自己的过程.这里的“自己”可以是函数、过程、语言结构和解题方法等.,递归方法思路:第一步骤（递归步骤）：将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题。即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题.第二步骤：确定一个或多个无须分解、可直接求解的最小子问题（称为递归的终止条件）.,第一章 组合优化模型与计算复杂性,Example 4,斐波那契数定义为下列无穷整数的序列：,1,1,2,3,5,8,13,21,34,55,89，,第 n 个元素是紧接在它之前的两个元素之和，用FIB(n)表示第 n 个斐波那契数，则可用如下递归关系式定义：,FIB(n)=FIB(n-1)+FIB(n-2)FIB(1)=1 FIB(2)=1,为了计算 FIB(n)，要递归调用 FIB(n-1)、FIB(n-2),而为了计算 FIB(n-1)，除了利用已调用的 FIB(n-2)外，还要调用FIB(n-3)，因此，为了计算FIB(n)需作 n-1 次递归调用.,递归调用次数递归深度,分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法.,1 组合优化模型与算法,（六）动态规划法,Example 5,100多年前，有位美国推销员乘驿站马车向西旅行，从州A(state,状态)到州E 如图，需要4个驿程（stage，阶段）。问题为求从 State A到 State E 走哪条途径使他最安全？,原问题为求从 A 到 E 走哪条途径使保险单（policy，策略）的总费用达到最小？,6,4,第一章 组合优化模型与计算复杂性,6,4,Note:,作出各相继驿程上最佳决策。不一定产生总的最佳决策（即Greedy 算法未必取得最佳策略）.,如：A 2 B1 4 C2 3 D2 4 E,费用和为13,而 A 3 B3 1 C2,费用更低廉,穷举法：,即列出所有的可行路径，逐个路径进行比较，并从中选出最佳路径.,共有路径 18 条.,1 组合优化模型与算法,如果 s1s2sk sk+1 sn 是 s1 sn的最短路，则该路上任一点sksk+1sn 是sk sn的最短路.,结论：,设 Sk 表示在第k个驿程上出发州的集合（状态集合），S1=A，S2=B1，B2，B3，S3=C1，C2，C3，S4=D1，D2，,uk(sk)=sk+1 表示在第k个驿程从 sk 出发所作的决策,如：u2(B1)=C1 或 C2 或 C3(C1，C2，C3 表示第k 驿程从B1出发的允许决策集合).,第一章 组合优化模型与计算复杂性,6,4,fk(sk)表示从第 k 个驿程的出发州 sk E 的最短路的费用和，f1(s1)即为所求.,若已知 f2(B1)、f2(B2)、f2(B3)，则,当k=4时，,3,4,1 组合优化模型与算法,6,4,3,4,当k=3时，,5,7,6,第一章 组合优化模型与计算复杂性,6,4,3,4,5,7,6,当 k=2 时，,8,8,11,1 组合优化模型与算法,6,4,3,4,5,7,6,8,8,11,当 k=1 时，,11,u2(B3)=C2 u3(C2)=D2 u4(D2)=E 最安全道路为AB3C2D2E，最小费用为11.,Note 优点：减少计算量，（共 18 次加法，11次比较）；丰富了计算结果.,第一章 组合优化模型与计算复杂性,动态规划是解决多阶段决策过程最优化的数量化方法.,动态规划的成功之处在于，它可以把一个 n 维决策问题变换为 n 个一维最优化问题；,另外，动态规划能够得到全局最优解.,以空间换时间；,动态规划是求解某类问题的一种方法，是一种算法设计的策略，而不是一种特殊的算法（不像 LP 有统一的数学模型和算法）.,必须对具体问题进行具体分析：适用动态规划的问题必须满足最优化原理和无后效性；以丰富的想象力和灵活的技巧建立动态规划模型及求解.,动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解.,最优化原理（最优子结构性质）：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略.简言之,一个最优化策略的子策略总是最优的.,无后效性（马尔科夫性）是指：如果给定某一阶段的状态，则在这一阶段以后过程的发展，不受这阶段以前各阶段状态的影响，而只与当前的状态有关.换句话说，过程的过去历史只能通过当前的状态去影响未来的发展.每个状态都是过去历史的一个完整总结.,用到了递归，与贪心法、分治法、分枝与定界区别？,1 组合优化模型与算法,动态规划问题具有以下基本特征：1、问题具有多阶段决策的特征；2、每一阶段都有相应的“状态”与之对应；3、每一阶段都面临一个决策；4、每一阶段的最优解问题可以递归地归结为下一阶 段各个可能状态的最优解问题，各子问题与原问 题具有完全相同的结构.,动态规划的基本概念：,1、阶段（stage）是对整个过程的自然划分.用 k=1,2,n 表示阶段序号，把 k 称为阶段变量.,第一章 组合优化模型与计算复杂性,2、状态(state)状态表示每个阶段开始时所面临的自然状况或客观条件.既是该阶段某支路的始点，又是前一阶段某支路的终点.,描述状态的变量称为状态变量，记作sk，它表示第k 阶段所处的状态.状态变量取值的全体，称为允许状态集合，记作Sk.显然有 sk Sk,如前例 S1=A，S2=B1，B2，B3，etc.而 s2 可取B1，B2，B3.,3、决策(decision)当某阶段的状态确定后，可以作出各种不同的选择，从而确定下一阶段的状态，这种选择称为决策.,1 组合优化模型与算法,描述决策的变量称为决策变量，用 uk(sk)表示第 k 阶段当状态处于 sk 时的决策变量.,决策变量允许取值的范围称为允许决策集合，常用Dk(sk)表示第 k 阶段从状态 sk 出发的允许决策集合，显然有 uk(sk)Dk(sk).,在前例中，D1(A)=B1，B2，B3，D2(B1)=C1，C2，C3 etc.,4、策略(policy)是一个按顺序排列的决策组成的集合,由过程的第 k 阶段开始到终止状态为止的过程,称为问题的后部子过程.,第一章 组合优化模型与计算复杂性,由每阶段的决策按顺序排列组成的可行决策函数序列 uk(sk)，uk+1(sk+1),，un(sn)，称为 k 子过程策略，简称子策略.,记为 pk,n(sk)=uk(sk),uk+1(sk+1),un(sn).,当 k=1 时，此决策函数序列称为全过程的一个策略，简称策略，记 p1，n(s1).,可供选择的策略有一定的范围，称为允许策略集合，用 P1,n(s1)表示.从 P1,n(s1)中找出达到最优效果的策略称为最优策略，记 p1,n*=p1,n*(s1)=u1*(s1)，u2*(s2),，un*(sn).,1 组合优化模型与算法,5、状态转移方程(equation of state transition)反映 前后阶段状态之间的关系的方程 记为：sk+1=Tk(sk，uk).,体现了无后效性，正是能将多阶段化为单阶段决策的理论依据,（前例：sk+1=uk(sk)）,6、指标函数和最优值函数(objective function and optimal value function)阶段的指标函数是对应某一阶段状态和从该状态出发的一个决策的某种效益度量，用vk(sk，uk)表示.,过程指标函数（又称目标函数）是用来衡量所实现过程优劣的一种数量指标，它是定义在全过程和所有后部子过程上的数量函数，记作Vk,n=Vk,n(sk,uk,sk+1,uk+1,sn,un)(k=1,2,，n),当 k=1 时，就是全过程的指标函数.指标函数也是初始状态和策略的函数 即 Vk,n=Vk,n（sk，pk,n（sk）.,第一章 组合优化模型与计算复杂性,Note 指标函数应具有可分离性，即Vk,n可表示为：,Vk,n(sk,uk,sk+1,uk+1,sn,un)=,且 对于Vk+1,n 严格单调.,常见的指标函数的形式有：全过程和它的任一后部子过程的指标函数等于各 阶段指标函数之和，即：,Vk,n(sk,uk,sk+1,uk+1,sn,un)=,或,1 组合优化模型与算法,全过程和它的任一后部子过程的指标函数等于各阶 段指标函数之积，即：,指标函数的最优值，称为最优值函数，记 fk(sk),（opt 即 optimization,具体问题可取 min，max）,或,f1(s1)即为全过程的最优策略.,第一章 组合优化模型与计算复杂性,Note 当初始状态给定时，用逆序的方式比较好，当终止状态给定时，用顺序的方式比较好，通常初始状态给定的情况居多，所以用逆序的方式比较多.,对第一类指标函数其基本方程为：,1 组合优化模型与算法,Example 6,用动态规划法解 TSP,距离矩阵如右：,Solution:,不妨设从 v1 出发回 到 v1.,用 f(vi;V)表示从 vi 出发，经顶点集合 V 中的点各一次，回到 v1 点的最短路.,则动态规划函数方程为：,用 f(v1;v2,v3,v4)表示从 v1 出发经 v2,v3,v4 各一次最后返回 v1 的最短路长度.,第一章 组合优化模型与计算复杂性,TSP 的距离矩阵,由动态规划函数方程有：,为了计算，,必须先计算,而,1 组合优化模型与算法,计算顺序为：,第一章 组合优化模型与计算复杂性,TSP 的距离矩阵,TSP 的距离矩阵,最后计算：,通过下标，不难得最优回路为:v1v3v4v2v1,用动态规划算法求 TSP,其时间复杂性为 O(n 2n).,1 组合优化模型与算法,（七）探索法,探索法是一种对给定的问题能通过某种途径（容易得到、比求最优解的算法速度快）进行探索而找到一个较好的解（不一定是最优解，有时探索甚至失败）的算法.,设计探索法的一种常用方法是列出精确解的所有要求，并把这些要求分成两类：1、必须满足的要求；2、允许折衷的要求.探索算法的设计目标就是保证第一类要求得到满足，对第二类要求要尽量满足，但并不一定满足.,第一章 组合优化模型与计算复杂性,启发式算法,（八）倒推法,倒推法是从某个目标或某个解出发，倒推到这个问题的初始陈述.如果这个过程是可以逆转的，则从问题的陈述可以推得问题的解.,倒推法不是从某个解推导出什么新的结论，而是猜测能使结论成立的前提条件，然后再从这些前提条件出发，找出能导致它们成立的新的前提条件，如此继续寻找.,有可能在进行到某一步时新的前提条件会与已知条件（即问题的初始陈述）一致.这时，由于已知条件成立，所以在已知条件和解之间所有的前提条件都成立，从而解必定成立.,适用于倒推法的问题应满足以下两个条件：1、问题必须有唯一解；2、在问题中出现的函数是单值的，或者说对每一条输出信息都可以找到唯一的一条输入信息（又称 1 对 1 运算）.,1 组合优化模型与算法,Example 7,水罐问题,有两个水罐，它们的容积分别为 7L 和 3L，除此之外没有别的容器.水的供应是充分的.怎样用这两个水罐量出 5L 水？,Solution:,这个问题的解是在大罐里装有 5L 水.,从解往前倒推，有五种情况可能导致解的产生：,大罐里有 2L 水，再从小罐里倒入 3L 水；,大罐里装满水，小罐里有 1L 水，从大罐里倒出2L 水到小罐里，剩下 5L；,大罐里有 3L 水，再从小罐里倒入 2L；,大罐里有 4L 水，再从小罐里倒入 1L；,大罐里有 6L 水，小罐里有 2L，从大罐里往 小罐里倒入 1L 水，剩下 5L 水.,在这五种情况中，第一和第二两种情况的可能性大，下面从第二种情况出发再往前推.,先把大罐装满，再用小罐从大罐里量出两次共 6L 水，使之剩下 1L 水，把它倒入小罐，然后把大罐再装满.这就得到了上述第二种情况.这种情况发生后，从大罐往小罐到2L 水，剩下 5L 水，问题得到了解决.,第一章 组合优化模型与计算复杂性,（九）回溯法,回溯法是一种满足一定约束条件的穷举式搜索法，它的搜索方式与对树的深度优先搜索方式相似，但由于规定了问题的解必须满足一些约束条件，因此需要搜索的空间大大减少.,如果问题的解能表示为一个 n 元组(x1,x2,xn)则可采用回溯法求解.,回溯法求解的约束条件一般分为两类：,1、显约束，每个 xi 的取值范围；,2、隐约束，满足判定函数的关于解空间上的多元式.,1 组合优化模型与算法,Example 8,设有一 44 的棋盘（即每行每列都有 4 个正方格的棋盘），用 4 个棋子布到格子上，要求满足一下两个条件：,1、任意两个棋子不在同一行和同一列上；,2、任意两个棋子不在一对角线上.,试问有多少种的布局？,Solution:,如果采用穷举式搜索，先不考虑 1、2 两个条件，则布到每一行的棋子有 4 个选择，故共有 44=256种方案.,设 xi 表示放在第 i 行上的棋子的列数，,这是显约束,显然没有必要！,第一章 组合优化模型与计算复杂性,隐约束有：,不同列,不在一对角线上,搜索过程如下：,这种一旦发现前面已是“此路不通”，立即回头，改换路径，而不是一条道走到底的策略，就是回溯法的基本思想.,向前走，碰壁回头,1 组合优化模型与算法,（十）模拟法,在实际科研和生产中有许多大系统，要构造大系统的模型、对它们分析和求解都是相当困难的.变量之间的关系难以确定，随机变量的分布不得而知，甚至影响因素就找不全.利用计算机对大系统进行模拟是研究大系统的一种好方法.,模拟法有许多优点：1、它能按预定要求去研究系统的各个方面，借助计算 机的高速运算和逻辑判断能力，可以同时顾及系统各 个方面的结构，容易展现系统动态变化的具体细节；,第一章 组合优化模型与计算复杂性,直接解决问题的方法，是