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

《数学建模组合优化模型与计算复杂性学习教案》由会员分享，可在线阅读，更多相关《数学建模组合优化模型与计算复杂性学习教案（117页珍藏版）》请在装配图网上搜索。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、 （f (I, *) f( I, )）.问题：一类实际问题的数学模型的总称，如TSP、 LP etc ；实例：（一个问题中总包含了若干个参数）对问题 给定一组参数所得到的例子.第一章 组合优化模型与计算复杂性第28页/共117页第二十九页，共117页。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页第三十页，共117页。31 有两种思想，像珠宝商放在天鹅绒上的宝石(bosh)一样熠熠生辉，一个是微积分，另一个就是算法，微积分以及在微积分基础上建立起来的数学分析体系造就了现代科学，而算法则造就了现代世界 .伯林斯基（D. Berlinski ）算法思想：指通过把数学问题的求解(qi ji)分解为简单的、刻板的、重复的机械动作，达到以数目较多的、简单的量的工作去实现较复杂的质的目的 .算法思想是数学发展的一个重要源泉 20 世纪中叶计算机的问世是人类智力最伟大的成就之一 . 算法是计算机的灵魂，随着计算

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

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

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

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

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

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

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

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

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

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

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

36、7页第四十二页，共117页。43 整序问题的快速算法是典型(dinxng)的分治策略运用.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页第四十三页，共117页。44分治法所能解决(jiju)的问题一般具有以下几个特征：1、该问题的规模缩小到一定的程度(chngd)就可以容易地解决;2、该问题可以分解(fnji)为若干个规模较小的相同问题；3、利用该问题分解出的子问题的解可以合并为该问 题的解； 4、该问题所分解

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

38、的终止条件）.第一章 组合优化模型与计算复杂性第44页/共117页第四十五页，共117页。46Example 4斐波那契数定义为下列(xili)无穷整数的序列： 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89， 第 n 个元素是紧接在它之前的两个元素之和，用FIB(n) 表示(biosh)第 n 个斐波那契数，则可用如下递归关系式定义：FIB(n) = FIB(n-1) + FIB(n-2) FIB(1) = 1 FIB(2) = 1 为了计算 FIB(n) ，要递归调用(dioyng) FIB(n-1) 、FIB(n-2) ,而为了计算 FIB(n-1) ，除了利用

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

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

41、短路 .结论(jiln)： 设 Sk 表示在第k个驿程上出发州的集合(jh)（状态集合）， 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页第四十九页，共117页。5026AB2B1B3C1C2C3D1D2E243743241543333464 fk(sk) 表示(biosh)从第 k 个驿程的出发州

42、 sk E 的最短路的费用和，f1(s1) 即为所求.若已知 f2(B1)、f2(B2)、f2(B3)，则21122232()( )min 4()3()fBf AfBfB当k = 4时，4141()3,()fDuDE4242()4,()fDuDE34第49页/共117页第五十页，共117页。5126AB2B1B3C1C2C3D1D2E24374324154333346434当k = 3时， 4131311422()()min54()fDf Cu CDfD， （ ）4132322426()()min73()fDf Cu CDfD， （）4133331423()()min63()f Df Cu C

43、Df D，（ ）576第一章 组合优化模型(mxng)与计算复杂性第50页/共117页第五十一页，共117页。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页第五十二页，共117页。5326AB2B1B3C1C2C3D1D2E243743241

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

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

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

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

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

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

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

51、前后阶段状态之间的关系的方程 记为：sk+1=Tk(sk，uk) .体现了无后效性，正是(zhn sh)能将多阶段化为单阶段决策的理论依据（前例(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 ,

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

53、：( ,)njjjj kv s u,1,11( ,)(,.,)k nkkkknkknnVv s uVsus u Vk,n(sk , uk , sk+1 , uk+1 , , sn , un) = 或第59页/共117页第六十页，共117页。61 全过程(guchng)和它的任一后部子过程(guchng)的指标函数等于各阶 段指标函数之积，即：,1,(,)(,)nk njjjkkkknj kVv s uv s u V,(.)()(,.,)knkkk nkknnuufsopt Vs us u指标指标(zhbio)函数的最优值，称为最优值函数，记函数的最优值，称为最优值函数，记 fk(sk)（opt

54、 即 optimization, 具体问题(wnt)可取 min，max）,()()(,)k nk nkkkk nkk npPsfsoptVsp或f1(s1) 即为全过程的最优策略.第一章 组合优化模型与计算复杂性第60页/共117页第六十一页，共117页。62Note 当初始状态给定(i dn)时，用逆序的方式比较好，当终止状态给定(i dn)时，用顺序的方式比较好，通常初始状态给定(i dn)的情况居多，所以用逆序的方式比较多 .对第一类指标函数其基本(jbn)方程为：11()111()(,)()()0(,)kkkkkkkkkuDsnnkkkkfsoptv s ufsfssT s u第61

55、页/共117页第六十二页，共117页。63Example 6用动态(dngti)规划法解 TSP距离(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 的距离矩阵

56、第62页/共117页第六十三页，共117页。64由动态规划(guhu)函数方程有：1234122341332414423( ;,)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

57、第63页/共117页第六十四页，共117页。65441(;)9f vd 331( ;)8f vd 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

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

59、234( ; , , )f v v v v234(;,)f v v v324( ;,)f v 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页第六十六页，共117页。67（七） 探索(tn su)法探索法是一种对给定的问题能通过(tnggu)某种途径（容易得到、比求最优解的算法速度快）进行探索而找到一个较

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

61、前提条件出发，找出能导致它们成立的新的前提条件，如此继续寻找 . 有可能在进行到某一步时新的前提(qint)条件会与已知条件（即问题的初始陈述）一致 . 这时，由于已知条件成立，所以在已知条件和解之间所有的前提(qint)条件都成立，从而解必定成立 .适用于倒推法的问题应满足以下两个条件：1、问题必须有唯一解；2、在问题中出现的函数是单值的，或者说对每一条输出信息都可以找到唯一的一条输入信息（又称 1 对 1 运算）.第67页/共117页第六十八页，共117页。69Example 7水罐问题(wnt) 有两个水罐，它们的容积分别为 7L 和 3L，除此之外没有别的容器 . 水的供应是充分(ch

62、ngfn)的 . 怎样用这两个水罐量出 5L 水？Solution :这个(zh ge)问题的解是在大罐里装有 5L 水 .从解往前倒推，有五种情况可能导致解的产生： 大罐里有 2L 水，再从小罐里倒入 3L 水； 大罐里装满水，小罐里有 1L 水，从大罐里倒出2L 水到小罐里，剩下 5L； 大罐里有 3L 水，再从小罐里倒入 2L ； 大罐里有 4L 水，再从小罐里倒入 1L ； 大罐里有 6L 水，小罐里有 2L ，从大罐里往 小罐里倒入 1L 水，剩下 5L 水 . 在这五种情况中，第一和第二两种情况的可能性大，下面从第二种情况出发再往前推 . 先把大罐装满，再用小罐从大罐里量出两次共

63、6L 水，使之剩下 1L 水，把它倒入小罐，然后把大罐再装满 . 这就得到了上述第二种情况 . 这种情况发生后，从大罐往小罐到2L 水，剩下 5L 水，问题得到了解决 .第一章 组合优化模型与计算复杂性第68页/共117页第六十九页，共117页。70（九） 回溯(hu s)法回溯法是一种满足(mnz)一定约束条件的穷举式搜索法，它的搜索方式与对树的深度优先搜索方式相似，但由于规定了问题的解必须满足(mnz)一些约束条件，因此需要搜索的空间大大减少 . 如果问题的解能表示(biosh)为一个 n 元组 (x1, x2, , xn) 则可采用回溯法求解 .iixS回溯法求解的约束条件一般分为两类：

64、1、显约束，每个 xi 的取值范围；2、隐约束，满足判定函数的关于解空间上的多元式 .第69页/共117页第七十页，共117页。71Example 8 设有一 44 的棋盘（即每行每列都有 4 个正方格(fn )的棋盘），用 4 个棋子布到格子上，要求满足一下两个条件：1、任意两个(lin )棋子不在同一行和同一列上；2、任意(rny)两个棋子不在一对角线上 .试问有多少种的布局 ？Solution : 如果采用穷举式搜索，先不考虑 1、2 两个条件，则布到每一行的棋子有 4 个选择，故共有 44 = 256种方案 . 设 xi 表示放在第 i 行上的棋子的列数，1,2,3,4ix 这是显约束

65、 显然没有必要！第一章 组合优化模型与计算复杂性第70页/共117页第七十一页，共117页。72隐约束(yush)有：( ,1,2,3,4)ijxxi jij1( ,1,2,3,4)ijiji jijxx 不同(b tn)列不在一对角线上搜索过程(guchng)如下： 这种一旦发现前面已是“此路不通”，立即回头，改换路径，而不是一条道走到底的策略，就是回溯法的基本思想 .向前走，碰壁回头第71页/共117页第七十二页，共117页。73（十） 模拟法 在实际科研和生产中有许多大系统，要构造大系统的模型、对它们分析和求解都是相当困难的 . 变量之间的关系难以确定，随机变量的分布不得而知(b d r

66、 zh)，甚至影响因素就找不全 . 利用计算机对大系统进行模拟是研究大系统的一种好方法 . 模拟法有许多优点：1、它能按预定要求去研究系统的各个方面，借助计算 机的高速运算和逻辑判断能力，可以同时顾及系统各 个方面的结构，容易(rngy)展现系统动态变化的具体细节 ；第一章 组合优化模型(mxng)与计算复杂性 直接解决问题的方法，是一种建模方法.第72页/共117页第七十三页，共117页。742、模拟的方法比将系统置于实际环境直接进行试验的方法要节省很多时间和经费；3、模拟可用不同的时间比例尺进行, 可放慢时间，在微观上认真(rn zhn)考察系统的性态；也可加快时间，在宏观和大范围上观察系统的行为；还可以使时间暂停、返回和重置，以便反复、详尽地研究系统在任意时段的各种反常的或重要的性态及行为，这些都是在实际系统中很难或根本不可能实现的 . 模拟是一项实验技术，其实验结果取决于所采用(ciyng)的模型和数据 .其他需要应用模拟的情况：1、有危险性或代价过高的事情；2、一旦实施，无法复原或产生严重后果的事情；3、某种理论(lln)研究的结果需要验证 . etc . 以上介绍了十种基本