数学建模组合优化模型与计算复杂性学习教案

1、会计学1数学建模组合优化模型数学建模组合优化模型(mxng)与计算复杂与计算复杂性性第一页，共118页。21 组合优化模型(mxng)与算法2 计算(j sun)复杂性问题3 启发式算法第1页/共117页第二页，共118页。3第一章 组合(zh)优化模型与计算复杂性 模型（model ）是所研究的系统、过程、事物或概念(ginin)的一种表达形式 . （一) 模型的概念 模型不是研究对象本身，而是对研究对象的一种抽象，它反映现实中对象系统的主要特征，但它又高于现实，因而具有同类问题的共性 . 由于研究目的的不同，对于同一个对象系统，可以建立完全不同的模型，分别反映该系统的不同侧面；出于相同的研

2、究目的，对于同一个对象系统，也可能建立不同的模型，反映不同的研究角度、考察因素和价值取向 .一、关于模型第2页/共117页第三页，共118页。4（二） 模型(mxng)的本质 从系统概念上看，模型是系统中各种关系的表达形式 . 因此，建立模型要从状态(zhungti)和过程两个方面去寻找、把握和描述各系统要素之间的相互关系 .状态：事物在某个时刻所处的状况或表现形态 过程：事物状态的变化在时间上的持续和空间上的延伸 过程和状态两者紧密联系、不可分割，状态决定和影响过程，过程又决定和影响新的状态 . 状态和过程是相对的 .第3页/共117页第四页，共118页。5 从认识论上看，模型是作为(zuw

3、i)认识与实践活动的中介 .现实(xinsh)世界认识(rn shi)（信息） 模 型实践活动概念化用信息载体表达决策（行动方案）产品和服务模型化过程示意图模型既是认识的表达，又是实践活动的先导 . 模型参与认识世界和改造世界的不断的循环往复过程，既是认识不断深化的体现，又是实践活动不断拓展的体现 .第一章 组合优化模型与计算复杂性第4页/共117页第五页，共118页。6 从信息论上看，模型和认识之间存在密切的反馈关系 . 从已知信息可以通过模型加工(ji gng)产生出新的信息，相关信息的积累可以从量变产生质变，形成新的概念，促使认识深化 . 因此，模型的建立和完善不仅要注重对系统物质形态和

4、能量形态的认识、把握和描述，而且也依赖于对系统相关信息不断的采集、积累和加工，这就是(jish)用模型研究问题的现实活动 .第5页/共117页第六页，共118页。7（三） 模型(mxng)的分类1、原样(yun yn)模型 原样模型是在工程开发末期建立的一种(y zhn)具象实体，是具有实物形态的模型 .它与目的工程在结构和过程方面基本相同 . 原样模型经过试验改进和完善后便是所要开发的目的工程 .新产品的样机、新著作的原稿 第一章 组合优化模型与计算复杂性第6页/共117页第七页，共118页。82、相似(xin s)模型 相似模型是根据不同(b tn)系统间的相似规律（包括几何相似、逻辑相似

5、和过程相似等）而建立的用于研究的模型 .3、图形模型 地球仪、船体放样模型、飞机风洞实验模拟模型等等图形模型可以表达非常丰富的内容，主要有： 图画 一种可以示形的图形； 草图 一种可以示意的图形； 框图 一种可以表示系统的部分之间或部分 与整体之间联系的图形； 称为不严格图（没有严格的规范） 系统分析和设计人员常常借助于这些图形模型来开发、构建一个新系统的想象力和创造力，逐步引申出与之有关的问题和需要进一步探索的问题，使所要开发的系统变得越来越清晰、越来越具体 .第7页/共117页第八页，共118页。9 逻辑图 一种可以反映因素或对象(duxing)间逻辑关系 的图形； 如：程序(chngx)

6、流程图、控制关系图 etc. 工程图 一种可以反映物体确定的结构和顺序 关系(gun x)的图形； 如：建筑工程图、铁路站场配置图 etc. 图论图 包括图论所定义的无向图 G(V，E) 、 有向图 G(V，A)、加权有(无)向图G(V，A(E)，w).关系 称为严格图（有严格确定的结构形式和规范）4、数学模型 数学模型是指运用数学符号和公式来表达、研究对象系统的结构或过程的模型 .数学模型是用数学的语言、方法去近似地刻画实际 ,是由数字、字母或其他数学符号组成的，描述现实对象数量规律的数学公式、图形或算法 . 是对现实对象本质属性的抽象而又简洁的刻画，它或能解释某些客观现象，或能预测未来的发

7、展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略 .Go back第一章 组合优化模型与计算复杂性第8页/共117页第九页，共118页。10Example 1七桥问题(wnt) 18世纪(shj)的德国有个哥尼斯堡城，在流贯全城的普雷尔河两岸和河中两个岛之间架设了七座桥，把河的两岸和两岛连接起来，能否有这样一种走法，它通过每座桥一次且仅一次 .该问题(wnt)由Euler在1736年解决Solution :第9页/共117页第十页，共118页。11ABCD 显然，解决该问题时，两岸和岛的大小、形状(xngzhun)以及桥的长短曲直都无关，重要的是什么？每块陆地(ld)间有几座

8、桥对问题进行数学(shxu)抽象： 把两岸和两岛都看做顶点，将连接这些顶点的桥当作边，于是得到一无向图 . 则七桥问题就成为无向图中是否存在通过每一边一次且仅一次的路（即一笔画）问题 .第一章 组合优化模型与计算复杂性第10页/共117页第十一页，共118页。12ABCDEuler 在他的论文(lnwn)中证明： 一个图中存在一笔画的充要条件是同时(tngsh)满足：1、图是连通的；2、与图中每一顶点（可能有两点例外）相连的边 （线度）必须是偶数条 .这是关于图论的第一篇论文 见图可知，与四个顶点相连的边都是奇数条，因而不可能存在通过每条边一次且仅一次的画法，即一笔画不存在 . 故七桥问题不可

9、能有解 .问题原型七桥问题数学模型一笔画问题无 解(一次过七座桥不可能)无 解(一笔画不可能)数学抽象逻辑推理翻译回去有无解？这是利用数学模型分析和解决问题的一个成功范例第11页/共117页第十二页，共118页。13（一） 数学模型的特点(tdin)1、高度(god)的抽象性 数学方法不仅要抛开事物的次要属性，突出事物的本质属性，而且要舍弃事物的物质和能量方面的具体内容，只考虑其数量关系(gun x)和空间形式，同时还要把这些数量关系(gun x)和空间形式作进一步的抽象，加以形式化和符号化，以便能够进行逻辑推理和数值运算 . 这种高度的抽象性，实质是对事物认识上的高度概括和深化，对同类问题包

10、含更多的经验和理解 .第一章 组合优化模型与计算复杂性第12页/共117页第十三页，共118页。142、高度(god)的精确性数学方法的高度精确性表现(bioxin)在三个方面： 一是表达各种因素、变量和它们之间的关系相当明确、清楚；二是逻辑推演和运算规则十分严密；三是结论非常确定 . 数学方法可以处理多变量、关系复杂的问题，可在有意义的范围内获得令人满意的计算精度 . 特别适合于揭示事物的量的规定性，成为定量研究的有力工具 .第13页/共117页第十四页，共118页。153、应用(yngyng)的普适性 数学方法的高度抽象和精确，使之比任何一种科学方法的应用(yngyng)范围都更为广泛 .

11、 只存在(cnzi)尚未运用数学方法的领域而不存在(cnzi)不能运用数学方法的领域 . 许多相同形式的数学模型可用于不同的实际问题，具有重要类比和借鉴意义 .数学方法的形式化和公理化，使模型本身、计算过程和计算结果都便于交流，数学模型易变动，便于修改和改变计算关系，分析和求解问题速度快，求解成本低 .数学模型缺乏直观性、形象性和实时感第一章 组合优化模型与计算复杂性第14页/共117页第十五页，共118页。16（二） 数学模型分类(fn li)数学模型分类(fn li)的方法很多，如：1、按所研究问题的性质分类 静态模型与动态模型 确定型模型与随机型模型 连续模型与离散模型 线性模型与非线性

12、模型 宏观模型与微观模型第15页/共117页第十六页，共118页。172、按模型(mxng)的解的特征分类解析(ji x)模型与数值模型3、按模型所用(su yn)的数学方法分类初等模型、微分方程模型、差分方程模型、优化模型等4、按模型研究的实际范畴分类人口模型、生态系统模型 、交通流模型、经济模型、 基因模型等5、按对实际问题了解的程度分类 白箱模型、灰箱模型、黑箱模型第一章 组合优化模型与计算复杂性第16页/共117页第十七页，共118页。18（三） 数学(shxu)建模的基本步骤 数学模型因问题不同而异，对同一问题，从不同角度、不同要求出发，甚至问题的解表示(biosh)结构不同，都可以

13、建立不同的数学模型. 建立数学模型也没有固定的方法、标准 . 不同的实际问题，建模模式千差万别. 在此介绍通常的几个步骤： 数学建模问题直接来源各领域实际，往往含糊不清（目的、条件、类型 etc.）. 首先，要对该问题进行全面的、深入细微的调查和研究. 明确所解决问题的性质，着手收集数据 ；1、明确问题合理地、有目的地注意精度第17页/共117页第十八页，共118页。192、合理(hl)假设 现实问题错综复杂，涉及面非常之广. 一个数学模型(mxng)面面俱到、无所不包地反映一个现实是不可能的，即使可能，也因其过于复杂而很难求解，也是没有必要的 . 所以，要作合理的假设 .1、简化问题(wnt

14、)2、限定适用范围但也不能忽略实质相关的因素 作假设的依据通常是出于对问题内在规律的认识,或来自对数据或现象的分析，也可以是二者的综合. 善于辨别问题的主次，抓住主要因素，通过合理假设,使问题简化以便进行数学描述 . 假设是在模型的建立、求解和分析过程中完善 .通常开始让问题尽可能简化第一章 组合优化模型与计算复杂性第18页/共117页第十九页，共118页。203、建立(jinl)模型 建模时，要分清问题的类型恰当使用数学工具(gngj)；抓住问题的本质简化变量之间的关系 . 用什么样的方法建立数学模型，没有绝对的标准；数学模型的形式可以是多种多样，数学公式、表格、图形、算法 . 模型的优劣在

15、于是否采用了恰当的方法，合理地描述了实际问题，而不在于是否用到了高深的数学工具 .数学建模是一个过程 .第19页/共117页第二十页，共118页。214、模型(mxng)求解 不同的模型要用到不同的数学工具求解 . 这就要(ji yo)求从事实际工作者对相应的数学分支知识有一定的了解 .可借助计算机，特别是利用(lyng)数学工具软件 .5、模型分析 对模型求出的解进行数学上的分析，有助于对实际问题的解决 .如： 结果的误差分析误差是否在允许的范围内分析误差来源：建模假设的误差；数据测量的误差；近似求解方法的误差；计算工具的舍入误差 . 结果的统计分析结果是否符合特定的统计规律 模型对数据的灵

16、敏度分析模型的结果是否会因数据的微小改变而发生大的变化 对假设的鲁棒性分析模型的结果是否对某一假设非常依赖 不同模型间的对比分析robustness第一章 组合优化模型与计算复杂性第20页/共117页第二十一页，共118页。226、模型(mxng)检验 将求解结果和分析结果翻译回到实际问题之中，与实际现象(xinxing)、实际数据进行比较，检验是否与实际吻合 . 如果吻合较好，则模型及其结果可以应用于实际问题；如果吻合不好，则需要对模型进行修正 .7、改进模型 吻合不好，问题常常出现在模型假设上 . 可能由于假设了过于苛刻的条件，或者忽略了一些不该忽略的因素. 所以, 要对实际问题中的主次因

17、素再次分析,对模型进行修改、补充、完善 . 需要多次反复才能达到比较满意的程度 。第21页/共117页第二十二页，共118页。238、模型(mxng)应用 数学建模最终的目的是为了解决问题 . 一方面可以解释(jish)以前的实践成果；另一方面可以为现在的实际问题提供解决方案，甚至可以对一些不确定的现象或规律作出预测 .现实(xinsh)问题简化、假设建立模型求解模型检验分析模型模型应用观察、分析收集数据确定主要因素及相互关系Go back第一章 组合优化模型与计算复杂性第22页/共117页第二十三页，共118页。24Example 2 某商场(shngchng)根据客流量统计得出一周中每天所

18、需要的营业员数如表：营业员配置(pizh)问题时间时间周一周一周二周二周三周三周四周四周五周五周六周六周日周日所需营业员数所需营业员数677278768510698 如果规定每个营业员每周连续工作 5 天，休息 2 天，求总人数最少的营业员排班方案 .Solution : 设 xj 为从周 j 开始连续工作 5 天的营业员人数，j = 1,7 (其中 x7 为周日开始连续工作 5 天的营业员数)，则71minjjzx14567. .67stxxxxx71minjjzx14567. .67stxxxxx1256772xxxxx1236778xxxxx1234776xxxxx1234585xxxx

19、x23456106xxxxx3456798xxxxx0,1,.,106 ,1,.,7jxj可行解集是有限集第23页/共117页第二十四页，共118页。25Example 3 旅行(lxng)商问题（Traveling Salesman Problem）TSP : 有一位旅行售货员，欲到城市 v1，v2,，vn 进行商品销售，已知： 的距离为 wij.( , ).他从其中某个城市出发，需访问每一个城市一次而回到出发的城市.问应如何计划他的旅行路线，使他所走路线的总长度最短？ijvvij,1i jnTSP可分为：对称(duchn)（dij = dji)和非对称(duchn)（dij dji）距离两

20、种第一章 组合(zh)优化模型与计算复杂性第24页/共117页第二十五页，共118页。26不含平行(pngxng)边及自环 这是1856年，Hamilton 首先提出的所谓环球航行问题而得名。它的存在性远比 Eular 回路的存在性复杂得多。最优 Hamilton 回路：在赋权图中，权和最小的 Hamilton 回路 .过简单图 G 的每一个顶点一次且仅一次的回路 .第25页/共117页第二十六页，共118页。27最优旅行(lxng)商问题与最优 Hamilton 回路一样吗？ 如果不满足三角(snjio)不等式，则可通过求最短路方法，构造新图，使之满足三角(snjio)不等式 . 所以以下仅

21、讨论最优的 Hamilton 回路 . 2 5 2 3Theorem 1 如果赋权图满足三角不等式（欧氏距离），则它的最优旅行商回路与最优 Hamilton 回路相同(xin tn) （Hamilton 回路存在时）.第一章 组合优化模型与计算复杂性第26页/共117页第二十七页，共118页。28minijijijd xTSP 问题(wnt)的数学模型（非对称的）：1. .11(1)nijjstxin111(2)nijixjn,1221,2,(3)iji j sxssnsn,110iji jnijxij表示回路通过第 个城市到第 个城市的边否则 1iji Sj Sx或v6v4v5v3v2v1N

22、ote：条件(1)，(2)表示每个城市经过(jnggu)一次，但不能保证它可行. 要求局部不构成圈，条件(3)就是为了约束这一点 .第27页/共117页第二十八页，共118页。29 Definition 1 组合(zh)优化问题是一个极小化（或极大化）的问题，它是由以下三部分组成：（1）实例(shl)集合 ；（2）对每个实例 I，有一个有穷的可行解集合 S(I)；（3）目标函数 f ，它对于每个实例 I 和每个可行解 S(I)，赋以一个实数 f (I, ). 则实例I的最优解为这样一个可行解 * S(I) ,它使得对于所有S(I)，都有 (I, *) f (I, ) （f (I, *) f(

23、I, )）.问题：一类实际问题的数学模型的总称，如TSP、 LP etc ；实例：（一个问题中总包含了若干个参数）对问题 给定一组参数所得到的例子.第一章 组合优化模型与计算复杂性第28页/共117页第二十九页，共118页。30组合(zh)优化的数学模型： Min f(x)s.t. g(x) 0 xD其中x为决策(juc)变量 f(x)为目标函数g(x)为约束函数D为决策变量的定义域F=x|x D, g(x) 0可行域(有限集) 很多组合优化问题都可以给出整数线性规划描述，甚至在一些时候还不得不利用整数线性规划的技巧来解 . 当然也可以用文字、网络等来叙述 . 线性规划是连续模型，但由于它的解

24、的特殊结构，也可以作为组合优化问题考虑 .第29页/共117页第三十页，共118页。31 有两种思想，像珠宝商放在天鹅绒上的宝石一样熠熠生辉，一个是微积分，另一个就是算法，微积分以及在微积分基础上建立起来(q li)的数学分析体系造就了现代科学，而算法则造就了现代世界 .伯林斯基（D. Berlinski ）算法思想：指通过把数学问题的求解分解为简单的、刻板的、重复的机械动作，达到以数目较多的、简单的量的工作去实现较复杂(fz)的质的目的 .算法思想是数学发展的一个重要源泉 20 世纪中叶计算机的问世是人类智力最伟大的成就之一 . 算法是计算机的灵魂，随着计算机融入现代科学实践和社会生活的各个

25、方面，算法思想的意义与作用日益为数学家所认识 . 是数学发展的机械化之路.第一章 组合优化模型与计算复杂性第30页/共117页第三十一页，共118页。32 一个科学的计算过程，指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰(qngx)描述 .算法是相对(xingdu)问题而言的，不单单是针对问题的某个实例 .算法(sun f)：Note： 假设你想把某个解决问题的方法传授给一台没有任何智能的机器，以便由它来帮你完成解决这类问题,机器会要求你怎么做？( 算法的能行性 ) 你当然不能只告诉它一个大概或者模棱两可、含糊其辞，而应该明确无误地告诉它所有解决问题的细节，而且这些细节应详细到

26、机器可以执行的程度（机械性）；你当然也不可能无休止地进行传授，而只能用到一些有限的符号，告诉它一些有限的规则（有限性） .第31页/共117页第三十二页，共118页。33如果算法(sun f)从前一步到后一步的运行是由当时状态唯一确定的. 如：单纯形法，表上作业法 . 遗传算法(sun f)是随机性算法(sun f) .确定性算法(sun f)： 数学上常常将算法分为数值算法和非数值算法 . 一般来说，数值算法用于科学计算，主要进行代数运算；而非数值算法则用于数据处理，主要进行比较和逻辑运算（也含代数运算） .第一章 组合优化模型与计算复杂性第32页/共117页第三十三页，共118页。34 对

27、于一个极小化（极大化）优化问题，如果给定任意(rny)一个实例I，算法A总能找到一个可行解* S（I）。 使得 f(I, *) f(I, )（f(I, *) f(I, )）启发式算法(sun f)（近似算法(sun f)，在4 中介绍） 组合优化总存在最优算法，仅讨论可计算(j sun)问题最优算法：是否任何数学问题都有算法求解吗？答案是否定的 （不可计算）停机问题：给定一个带输入的计算机程序，它会停机 吗？ 英国数学家图灵 (Turing) 证明了不存在一个算法，它能对该问题的一切实例给出正确答案 . 23个问题之10 Diophantus 方程的可解性 . （求出一个整系数方程的整数根）算

28、法的正确性不蕴含算法的有效性第33页/共117页第三十四页，共118页。35 本节介绍算法(sun f)设计的一些基本方法 . 在进行复杂的算法(sun f)设计时，常常利用这些基本方法（思想），有必要熟练掌握 .（一） 穷举法穷举法：穷举所有(suyu)可能的解并进行比较和选优的方法 .优点：获得最优解是确切无疑的（算法的正确性） 对于运算规模较小的、运算时间允许的优化问题，如无适合该问题的优化算法时，可采用穷举法 .缺点：需要大量的机时和内存空间（算法的有效性）引言中对TSP问题已有说明，复杂性为O(n-1)!) 采用穷举法的关键在于：1、能否在理论上确定所求解问题的全部可行解集；2、对所

29、求解问题的全部可行解集进行比选是否可能. （计算时间复杂性）第一章 组合优化模型与计算复杂性第34页/共117页第三十五页，共118页。36（二） 登山(dn shn)法 （也称贪心法）登山法：从对问题(wnt)的某一初始推测或初始解出发，逐步逼近给定的目标，并尽可能快地逼近更好的解；当进行到某一步，不能再继续逼近时，算法便终止 .得到(d do)的是近似解或局部最优解 方法简单、适用面广 登山法是一个多步决策过程，每一步的选择都是为了能构成问题的一个可行解，同时使目标函数的值增加最大或最小 .选择过程是以某些最优化量度为依据 . 最优化量度可以是目标函数，也可以是别的量度，它的选择是登山法的

30、关键 .第35页/共117页第三十六页，共118页。371275144324127413532312345vvvvv12345vvvvvTSP 的距离(jl)矩阵Example 2 用登山(dn shn)法求 TSP .v5v4v3v2olution :优化准则(zhnz)：最短距离. 从 v1 出发，有4 个选择，按优化准则：选 v2 ;得： v1 v2 v5 v3 v4 v1总距离为：14 复杂性为 O(n2) .记住：没有免费的午餐！ 从选择 p 个不同的城市出发，分别用登山法得到 p 个结果 . 比较得距离和最短的路线 . n复杂性为 O(pn2) .但求得的

31、解更接近于最优解，如从 v2 出发，得： v2 v1 v3 v4 v5 v2总距离为：10 这是最优解（运气好）. 也可以从一个可行解出发，交换相邻两个城市位置,优化准则：总距离下降. v1 v2 v5 v3 v4 v1第一章 组合优化模型与计算复杂性第36页/共117页第三十七页，共118页。38（三） 分枝(fn zh)与定界法分枝与定界(dn ji)法的基本思想是对有约束条件的最优化问题的所有可行解（其数目为有限集）空间适当地进行搜索 . 具体(jt)执行时，把可行解空间不断分割为越来越小的子集（称为分枝），并确定每个分枝内的解值的下界或上界（称为定界）. 在每次分枝后，对凡是界超出已知

32、可行解值的子集被剪去，从而不断缩小搜索范围. 这个过程一直进行到找出最优解为止，该可行解的值不大于或不小于任何子集的界 .优点：1、适用面广 2、可检查较少的解（运气好）3、可获得最优解缺点：本质是穷举，复杂性大于穷举法给出一个重要思想:设门槛 (称为隐枚举)第37页/共117页第三十八页，共118页。39设min( )(1)x Af xmin( )(2)x Bf xAB如果 则称问题(wnt)（2）是问题(wnt)（1）的松弛问题(wnt).Note :1、松弛(sn ch)问题未必比原问题难解；如：整数规划(guhu)与线性规划(guhu)；TSP 与指派问题 etc. 如： A：寻找全国

33、18 岁百米最快的运动员.B：寻找全国所有百米最快的运动员.显然，B 问题是 A 问题的松弛问题，且B 问题更易解 .2、如果松弛问题易解，则先解松弛问题是有益的 .1）设 x0 是松弛问题的最优解，且 则原问题已解0 xA0 xA2）即使 给出了原问题最优值的界 f(x0) .x0BABAx0第一章 组合优化模型与计算复杂性第38页/共117页第三十九页，共118页。40分枝(fn zh)与定界法为什么能少检查一些解？B10sB1B2*10sB3B4*几点注意(zh y)： 通常是通过求解松弛问题，用松弛问题的解作为界，也可以用启发式算法得到 .Note 松弛问题选择的原则、松弛问题要与原问

34、题的 最优值尽量接近；松弛问题要尽量容易解 .这两个原则不易统一，所以可选择不同的松弛问题第39页/共117页第四十页，共118页。41原则是希望分出来(ch li)的子问题容易被查清，可加快计算.先检查最大上界（极大化问题）的活问题优点：检查子问题较其他规则为少；缺点：计算机储存量较大先检查最新产生的最大上界的活问题优点：计算机储存量较少 ；缺点：需要更多的分支运算选择的不同，提供了发挥的余地 分枝与定界法的重要在于它提出了一类新的思路（隐枚举法），使得许多原来不好解决的问题有了解决的可能性. （具有普适性）第一章 组合优化模型与计算复杂性第40页/共117页第四十一页，共118页。42（四

35、） 分治(fn zh)法分治(fn zh)法就是把原问题分成若干个规模较小的子问题，这些子问题互相独立且与原问题形式相同，对每个子问题分别求解，然后将各子问题的解合并得到原问题的解 . 如果子问题仍较复杂(fz)，可递归使用上述方法 .Note：问题的类别在细分过程中不允许改变，改变的只是问题的尺度 .分治法的基本步骤：分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解.第41页/共117页第四十二页，共118页。43 整序问题的快速

36、(kui s)算法是典型的分治策略运用.8 1 9 6 7 5 3 281967532合并(hbng)合并(hbng)合并合并1 86 95 72 31 6 8 92 3 5 71 2 3 5 6 7 8 9合并合并合并第一章 组合优化模型与计算复杂性第42页/共117页第四十三页，共118页。44分治法所能解决的问题(wnt)一般具有以下几个特征：1、该问题的规模缩小到一定(ydng)的程度就可以容易地解决;2、该问题(wnt)可以分解为若干个规模较小的相同问题(wnt)；3、利用该问题分解出的子问题的解可以合并为该问 题的解； 4、该问题所分解出的各个子问题是相互独立的，即 子问题之间不包

37、含公共的子子问题 . 如何使用，因问题而异. 分治法的应用很广，如铁路运输技术计划中的空车调度计划等.第43页/共117页第四十四页，共118页。45（五） 递归方法(fngf)递归就是自己调用自己的过程 . 这里(zhl)的“自己”可以是函数、过程、语言结构和解题方法等 .递归方法思路: 第一步骤（递归步骤）：将规模较大的原问题分解为一个或多个(du )规模更小、但具有类似于原问题特性的子问题。即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题. 第二步骤：确定一个或多个(du )无须分解、可直接求解的最小子问题（称为递归的终止条件）.第一章 组合优化模型与计算复杂

38、性第44页/共117页第四十五页，共118页。46Example 4斐波那契数定义(dngy)为下列无穷整数的序列： 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89， 第 n 个元素是紧接在它之前的两个元素之和，用FIB(n) 表示第 n 个斐波那契数，则可用如下递归关系(gun x)式定义：FIB(n) = FIB(n-1) + FIB(n-2) FIB(1) = 1 FIB(2) = 1 为了(wi le)计算 FIB(n) ，要递归调用 FIB(n-1) 、FIB(n-2) ,而为了(wi le)计算 FIB(n-1) ，除了利用已调用的 FIB(n-2) 外，

39、还要调用FIB(n-3)，因此，为了(wi le)计算FIB(n)需作 n-1 次递归调用 . 递归调用次数递归深度 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法.第45页/共117页第四十六页，共118页。47（六） 动态(dngti)规划法Example 5 原问题(wnt)为求从 A 到 E 走哪条途径使保险单（policy，策略）的总费用达到最小？26AB2B1B3C1C2C3D1D2E243743241543333464第一章 组合优化模型与计算复杂性第46页/共117页第四十七页，共118页。4826AB2B1B3C1C2C3D1D2E2437432

40、41543333464Note : 作出各相继驿程上最佳决策。不一定产生(chnshng)总的最佳决策（即Greedy 算法未必取得最佳策略）.如： A 2 B1 4 C2 3 D2 4 E费用(fi yong)和为13而 A 3 B3 1 C2费用(fi yong)更低廉穷举法： 即列出所有的可行路径，逐个路径进行比较，并从中选出最佳路径.共有路径 18 条 .第47页/共117页第四十八页，共118页。49 如果 s1s2sk sk+1 sn 是 s1 sn的最短路(dunl)， 则该路上任一点sksk+1sn 是sk sn的最短路(dunl) .结论(jiln)： 设 Sk 表示在第k个

41、驿程上出发(chf)州的集合（状态集合）， 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出发的允许决策集合) .第一章 组合优化模型与计算复杂性第48页/共117页第四十九页，共118页。5026AB2B1B3C1C2C3D1D2E243743241543333464 fk(sk) 表示从第 k 个驿程的出发(chf)州 sk E 的最短路的费用和，f1(s1) 即为所求

42、.若已知 f2(B1)、f2(B2)、f2(B3)，则21122232()( )min 4()3()fBf AfBfB当k = 4时，4141()3,()fDuDE4242()4,()fDuDE34第49页/共117页第五十页，共118页。5126AB2B1B3C1C2C3D1D2E24374324154333346434当k = 3时， 4131311422()()min54()fDf Cu CDfD， （ ）4132322426()()min73()fDf Cu CDfD， （）4133331423()()min63()f Df Cu CDf D，（ ）576第一章 组合(zh)优化模型与

43、计算复杂性第50页/共117页第五十一页，共118页。5226AB2B1B3C1C2C3D1D2E24374324154333346434576当 k = 2 时，312132212337()7 5min 4()min 4 7116()6 6f Cf Bf Cu BCf C（ ），（ ）312232221333()()min2()84()fCfBfCuBCfC， （）312332232334min185fCfBfCuBCfC，8811第51页/共117页第五十二页，共118页。5326AB2B1B3C1C2C3D1D2E2437432415433334643457688112112213232

44、()2 11min 4()min48113()38fBf AfBu ABfB（ ），（ ）当 k = 1 时，11u2( B3 ) = C2 u3( C2 ) = D2 u4( D2 ) = E 最安全(nqun)道路为AB3C2D2E，最小费用为11 .Note 优点： 减少计算(j sun)量，（共 18 次加法，11次比较）； 丰富了计算(j sun)结果 .第一章 组合优化模型(mxng)与计算复杂性第52页/共117页第五十三页，共118页。54动态规划是解决(jiju)多阶段决策过程最优化的数量化方法. 动态规划的成功之处在于(ziy)，它可以把一个 n 维决策问题变换为 n 个一

45、维最优化问题 ；另外，动态规划能够得到(d do)全局最优解 .以空间换时间； 动态规划是求解某类问题的一种方法，是一种算法设计的策略，而不是一种特殊的算法（不像 LP 有统一的数学模型和算法）. 必须对具体问题进行具体分析：适用动态规划的问题必须满足最优化原理和无后效性；以丰富的想象力和灵活的技巧建立动态规划模型及求解 . 动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解.最优化原理（最优子结构性质）：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略.

46、 简言之, 一个最优化策略的子策略总是最优的.无后效性（马尔科夫性）是指：如果给定某一阶段的状态，则在这一阶段以后过程的发展，不受这阶段以前各阶段状态的影响，而只与当前的状态有关. 换句话说，过程的过去历史只能通过当前的状态去影响未来的发展 . 每个状态都是过去历史的一个完整总结. 用到了递归，与贪心法、分治法、分枝与定界区别？第53页/共117页第五十四页，共118页。55动态规划问题具有以下基本特征：1、问题具有多阶段决策的特征；2、每一阶段都有相应的“状态”与之对应； 3、每一阶段都面临一个决策；4、每一阶段的最优解问题可以(ky)递归地归结为下一阶 段各个可能状态的最优解问题，各子问题

47、与原问 题具有完全相同的结构 . 动态(dngti)规划的基本概念：1、阶段（stage） 是对整个过程的自然划分(hu fn). 用 k = 1,2, n 表示阶段序号，把 k 称为阶段变量 .第一章 组合优化模型与计算复杂性第54页/共117页第五十五页，共118页。562、状态 (state) 状态表示每个阶段开始时所面临的自然状况(zhungkung)或客观条件. 既是该阶段某支路的始点，又是前一阶段某支路的终点. 描述状态的变量称为状态变量，记作描述状态的变量称为状态变量，记作sk，它表示第它表示第k 阶段所处的状态阶段所处的状态. 状态变量取值的全体，状态变量取值的全体，称为允许称

48、为允许状态集合，记作状态集合，记作Sk . 显然有显然有 sk Sk 如前例如前例(qinl) S1= A ，S2= B1，B2，B3 ，etc. 而而 s2 可取可取B1，B2，B3 .3、决策(juc) (decision) 当某阶段的状态确定后，可以作出各种不同的选择，从而确定下一阶段的状态，这种选择称为决策(juc).第55页/共117页第五十六页，共118页。57 描述决策的变量称为决策变量，用 uk(sk) 表示(biosh)第 k 阶段当状态处于 sk 时的决策变量. 决策变量允许取值的范围称为允许决策集合(jh)，常用Dk(sk) 表示第 k 阶段从状态 sk 出发的允许决策集

49、合， 显然有 uk(sk) Dk(sk) . 在前例(qinl)中，D1(A) = B1，B2，B3 ， D2(B1) = C1，C2，C3 etc .4、策略 (policy) 是一个按顺序排列的决策组成的集合 由过程的第 k 阶段开始到终止状态为止的过程, 称为问题的后部子过程 .第一章 组合优化模型与计算复杂性第56页/共117页第五十七页，共118页。58 由每阶段的决策按顺序排列组成的可行决策函数序列 uk(sk) ，uk+1(sk+1) , ，un(sn) ，称为(chn wi) k 子过程策略，简称子策略. 记为 pk , n(sk)= uk(sk) , uk+1(sk+1) ,

50、 , un(sn) . 当 k = 1 时，此决策函数序列称为全过程的一个(y )策略，简称策略，记 p1，n(s1) . 可供选择的策略有一定的范围，称为允许(ynx)策略集合，用 P1, n(s1) 表示 . 从 P1, n(s1) 中找出达到最优效果的策略称为最优策略，记 p1,n*= p1,n*(s1)= u1*(s1) ，u2*(s2),，un*(sn) .第57页/共117页第五十八页，共118页。595、状态转移方程 (equation of state transition) 反映(fnyng) 前后阶段状态之间的关系的方程 记为：sk+1=Tk(sk，uk) .体现(txin

51、)了无后效性，正是能将多阶段化为单阶段决策的理论依据（前例(qinl)： 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 时，就是全过程的指

52、标函数 . 指标函数也是初始状态和策略的函数 即 Vk,n = Vk,n（sk，pk,n（sk）. 第一章 组合优化模型与计算复杂性第58页/共117页第五十九页，共118页。60Note 指标函数(hnsh)应具有可分离性，即Vk,n可表示为：1,1,.kkknknsuVsu， Vk,n(sk , uk , sk+1 , uk+1 , , sn , un) = 且 对于(duy)Vk+1 , n 严格单调.常见的指标函数的形式有： 全过程和它的任一后部子过程的指标函数等于(dngy)各 阶段指标函数之和，即：( ,)njjjj kv s u,1,11( ,)(,.,)k nkkkknkknn

53、Vv s uVsus u Vk,n(sk , uk , sk+1 , uk+1 , , sn , un) = 或第59页/共117页第六十页，共118页。61 全过程和它的任一后部子过程的指标函数(hnsh)等于各阶 段指标函数(hnsh)之积，即：,1,(,)(,)nk njjjkkkknj kVv s uvs u V,(.)()(,.,)knkkk nkknnuufsopt Vs us u指标指标(zhbio)函数的最优值，称为最优值函数，函数的最优值，称为最优值函数，记记 fk(sk)（opt 即 optimization, 具体问题(wnt)可取 min，max）,()()(,)k n

54、k nkkkk nkk npPsfsoptVsp或f1(s1) 即为全过程的最优策略.第一章 组合优化模型与计算复杂性第60页/共117页第六十一页，共118页。62Note 当初始状态给定时(dn sh)，用逆序的方式比较好，当终止状态给定时(dn sh)，用顺序的方式比较好，通常初始状态给定的情况居多，所以用逆序的方式比较多 .对第一类指标函数(hnsh)其基本方程为：11()111()(,)()()0(,)kkkkkkkkkuDsnnkkkkfsoptv s ufsfssT s u第61页/共117页第六十二页，共118页。63Example 6用动态(dngti)规划法解 TSP距离(

55、jl)矩阵如右：Solution : 不妨(bfng)设从 v1 出发回 到 v1 . 用 f( vi; V) 表示从 vi 出发，经顶点集合 V 中的点各一次，回到 v1 点的最短路 . 则动态规划函数方程为： ( ; )min(;)jiijjjvVf v Vdf v Vv 用 f(v1; v2,v3,v4) 表示从 v1 出发经 v2,v3,v4 各一次最后返回 v1 的最短路长度 .第一章 组合优化模型与计算复杂性2584768569581234vvvv1234vvvvTSP 的距离矩阵第62页/共117页第六十三页，共118页。64由动态规划(guhu)函数方程有：1234122341

56、332414423( ;,)min(;,),( ;,),(;,)f v v v vdf v v vdf v v vdf v v v1234( ;,)f v v v v234(;,)f v v v为了(wi le)计算 ，324( ;,)f v v v423(;,)f v v v必须(bx)先计算23423342443( ;,)min( ;),( ;)f v v vdf v vdf v v而34344( ;)(;)f v vdf v441(;)f vd 331( ;)f vd 221(;)f vd 第63页/共117页第六十四页，共118页。65441(;)9f vd 331( ;)8f vd

57、221(;)4f vd 计算(j sun)顺序为：23233(;)( ;)15f v vdf v 24244(;)(;)15f v vdf v 23423342443(;,)min( ;),(;)22f v v vdf v vdf v v42422(;)(;)9f v vdf v 34344( ;)(;)15f v vdf v 43433(;)( ;)16f v vdf v 32322( ;)(;)9f v vdf v 32432243442( ;,)min(;),(;)15f v v vdf v vdf v v42342234332(;,)min(;),( ;)17f v v vdf v v

58、df v v第一章 组合(zh)优化模型与计算复杂性258476856958TSP 的距离(jl)矩阵1234vvvv1234vvvv第64页/共117页第六十五页，共118页。662584768569581234vvvv1234vvvvTSP 的距离(jl)矩阵最后(zuhu)计算：1234122341332414423( ;,)min(;,),( ;,),(;,)20f v v v vdf v v vdf v v vdf v v v通过(tnggu)下标，不难得最优回路为: v1v3v4v2v11234( ; , , )f v v v v234(;,)f v v v324( ;,)f v

59、v v423(;,)f v v v23(;)f v v24(;)f v v42(;)f v v34( ;)f v v43(;)f v v32( ;)f v v4(;)f v 3( ;)f v 2(;)f v 4(;)f v 3( ;)f v 2(;)f v 用动态规划算法求 TSP , 其时间复杂性为 O(n 2n) .第65页/共117页第六十六页，共118页。67（七） 探索(tn su)法探索法是一种对给定的问题能通过某种途径(tjng)（容易得到、比求最优解的算法速度快）进行探索而找到一个较好的解（不一定是最优解，有时探索甚至失败）的算法 . 设计探索法的一种常用(chn yn)方法是

60、列出精确解的所有要求，并把这些要求分成两类：1、必须满足的要求；2、允许折衷的要求 . 探索算法的设计目标就是保证第一类要求得到满足，对第二类要求要尽量满足，但并不一定满足 .第一章 组合优化模型与计算复杂性启发式算法 第66页/共117页第六十七页，共118页。68（八） 倒推法倒推法是从某个目标或某个解出发，倒推到这个问题的初始(ch sh)陈述 . 如果这个过程是可以逆转的，则从问题的陈述可以推得问题的解 . 倒推法不是从某个解推导出什么新的结论，而是猜测能使结论成立的前提(qint)条件，然后再从这些前提(qint)条件出发，找出能导致它们成立的新的前提(qint)条件，如此继续寻找