算法设计问题

1、 当你的模型求解用已知的求解方法效果不好当你的模型求解用已知的求解方法效果不好或没有现成的求解方法时，尝试针对要求解的数或没有现成的求解方法时，尝试针对要求解的数学问题自己设计一个专用的算法将是完成数学建学问题自己设计一个专用的算法将是完成数学建模任务的关键。模任务的关键。 本章通过几个典型的算法设计案例介绍这方本章通过几个典型的算法设计案例介绍这方面的做法，以达到读者了解和学习这方面技能的面的做法，以达到读者了解和学习这方面技能的目的。目的。 8.1 离散点集拐点的快速查找算法离散点集拐点的快速查找算法 平面波形曲线一般是由一系列较短时间间隔采集数据点获得的平面波形曲线一般是由一系列较短时间

2、间隔采集数据点获得的平面离散点集，再经过分段线性插值的方法画出的。平面离散点集，再经过分段线性插值的方法画出的。 波形特怔（如波形曲线的极值点和拐点）的计算机自动识别在波形特怔（如波形曲线的极值点和拐点）的计算机自动识别在各种探伤和检测的计算机信息处理中占有重要的地位。如何快速确各种探伤和检测的计算机信息处理中占有重要的地位。如何快速确定构成波形的这些离散点集中的拐点在平面曲线波形的计算机自动定构成波形的这些离散点集中的拐点在平面曲线波形的计算机自动识别中是经常要考虑的问题之一。识别中是经常要考虑的问题之一。 目前确定平面离散点集中的拐点方法还没有较好的算法，请尝目前确定平面离散点集中的拐点方

3、法还没有较好的算法，请尝试给出一个求离散点集中拐点的快速查找算法。试给出一个求离散点集中拐点的快速查找算法。 问题的提出问题的提出问题的分析与算法构造问题的分析与算法构造 拐点是曲线凹凸交界点，注意到不在同一拐点是曲线凹凸交界点，注意到不在同一直线上的三点可以确定此段曲线的凹凸性。直线上的三点可以确定此段曲线的凹凸性。 因此，要获得曲线拐点信息至少需要四个点。因此，要获得曲线拐点信息至少需要四个点。 观察由平面散点集画出的散点图，发现散观察由平面散点集画出的散点图，发现散点图中的某点如果是拐点，要由该点左边的点图中的某点如果是拐点，要由该点左边的2个个点和右边的一个点共四个点来确定，逐次连接点

4、和右边的一个点共四个点来确定，逐次连接顺序两点连线更易看出是否拐点（图顺序两点连线更易看出是否拐点（图8-1） 定义定义1. 设平面上两点的坐标分别为设平面上两点的坐标分别为 P1(x1 ,y1) 和和 P2(x2 ,y2), P1 P2，称具有方向，称具有方向 P1P2 且过此两点的且过此两点的有向直线为正向直线，而称对应的直线方程有向直线为正向直线，而称对应的直线方程为关于点为关于点P1 ，P2的正向直线方程。的正向直线方程。 211121:0Lxxyyyyxx定义定义2. 给定平面上一条正向直线给定平面上一条正向直线L后，平面上不在后，平面上不在L上的点分为两类：上的点分为两类： 处于处

5、于L顺时针一侧的点称为关于正向直线顺时针一侧的点称为关于正向直线L的内点的内点, 处于处于L逆时针一侧的点称为关于正向直线逆时针一侧的点称为关于正向直线L的外点。的外点。定理定理1.记关于平面上两点记关于平面上两点 P1(x1 ,y1)和和 P2(x2 ,y2)的的正向直线方程正向直线方程L的左端表达式为函数的左端表达式为函数对于不在直线对于不在直线L上的任何一点上的任何一点 ，有，有 12211211,Sx yxxyyyyxx000,P xy1) 如果如果 , 则则 是正向直线是正向直线L的内点的内点.2) 如果如果 , 则则 是正向直线是正向直线L的外点。的外点。 1200,0Sxy000

6、,P xy1200,0Sxy000,P xy证明：证明： 关于正向直线关于正向直线L的内点有如下四种情况的内点有如下四种情况 取与点取与点 有同一横坐标且在有同一横坐标且在 L上的参考点上的参考点 ， 则有则有 将将 代入函数代入函数 ,有有 000,P xy*0,Q xy*1202111201,0Sxyxxyyyyxx000,P xy12,Sx y 120021011201*21011201*2102111201*210,Sxyxxyyyyxxxxyyyyyyxxxxyyxxyyyyxxxxyy 拐点的确定及算法拐点的确定及算法（1 1）计算）计算 并将其存储在变量并将其存储在变量S1S1中

7、中（2 2）对）对 1 1） 2 2）如果）如果 ，则，则 是拐点，是拐点， 保存或打印保存或打印 3 3）替换）替换S1S1的值，进行下个点的判别：的值，进行下个点的判别：S2 = S1S2 = S1（3 3）停止）停止1233,Sxy3,4,1kn111,2kkkkSxyS120SS,kkkPxy,kkkPxy算例算例考虑在考虑在-3，3上的函数上的函数 y=x*sin x2，它在，它在-3，3上的有上的有7个拐个拐点，分别为：点，分别为： x1= -2.5514, x2=-1.88206, x3= -0.994103, x4=0. , x5=0.994103, x6=1.88206, x

8、7=2.5514.现在从该曲线上取现在从该曲线上取400个等距点获得该曲线图形的离散点集。个等距点获得该曲线图形的离散点集。用本算法快速准确的求出了该离散点集的拐点，分别为：用本算法快速准确的求出了该离散点集的拐点，分别为： 第第31点点 -2.55, -0.55478；第；第76个点个点 -1.875, 0.685072；第第135个点个点 -0.99, -0.822248，第，第201个点个点 2.42861 10-15 , 1.43243 10-44 ；第第268个点个点 1.005, 0.851079，第，第327个点个点 1.89, -0.788757； 第第372个点个点 2.56

9、5, 0.748299。计算结果是非常令人满意的。计算结果是非常令人满意的。 它的散点图与求出的拐点在同一坐标系中的图形见图它的散点图与求出的拐点在同一坐标系中的图形见图 人们在进行社会的、经济的以及科人们在进行社会的、经济的以及科学管理领域问题的系统分析中，面临的学管理领域问题的系统分析中，面临的常常是一个由相互关联、相互制约的众常常是一个由相互关联、相互制约的众多因素构成的复杂而往往缺少定量数据多因素构成的复杂而往往缺少定量数据的系统。的系统。 层次分析法为这类问题的决策和排序层次分析法为这类问题的决策和排序提供了一种简洁而实用的建模方法。提供了一种简洁而实用的建模方法。 层次分析法（层次

10、分析法（Analytic Hierarchy Process，简称简称AHP）是一种定性和定量相结合的层次化）是一种定性和定量相结合的层次化分析方法，由美国运筹学家分析方法，由美国运筹学家T. L. Saaty 教授于教授于70年代初期提出。年代初期提出。 它较好地把它较好地把半定性和半定量问题半定性和半定量问题转化为转化为定定量量问题来处理，特别适用于那些难于完全定量问题来处理，特别适用于那些难于完全定量分析的问题。分析的问题。 节层次分析法中的节层次分析法中的比较尺度的定义比较尺度的定义、比较比较矩阵构矩阵构的造构和的造构和一致性检验一致性检验等都是数学建模中等都是数学建模中把定性问题变为

11、定量问题常见方法。把定性问题变为定量问题常见方法。 问题的提出问题的提出 “五一五一”假期快到了，张勇决定假期假期快到了，张勇决定假期去踏青。他想去杭州、黄山和庐山三个踏去踏青。他想去杭州、黄山和庐山三个踏青地点，但由于时间的原因，他只能在这青地点，但由于时间的原因，他只能在这3 3个地点中选一个来作为踏青目的地。请个地点中选一个来作为踏青目的地。请用数学建模的方式帮他选择这个踏青地。用数学建模的方式帮他选择这个踏青地。问题的分析问题的分析 本题是决策问题。要做的是从多个选择中选择最好的一个。本题是决策问题。要做的是从多个选择中选择最好的一个。选择依据：选择依据： 在多个对象中选择其中一个，人

12、们往往要根据自己的目标和在多个对象中选择其中一个，人们往往要根据自己的目标和有利于目标实现的多种因素的考量来做出最后选择。有利于目标实现的多种因素的考量来做出最后选择。但但： 目标和要考量的因素往往是不能用数量描述的定性概念。目标和要考量的因素往往是不能用数量描述的定性概念。如问题中张勇的目标是选择一个踏青地点，而选择踏青地他如问题中张勇的目标是选择一个踏青地点，而选择踏青地他要考虑踏青地的景色、费用、居住、饮食和旅途等因素，这要考虑踏青地的景色、费用、居住、饮食和旅途等因素，这些因素显然都是定性的概念。些因素显然都是定性的概念。要做的事情要做的事情 如何把定性的内容变为定量的内容，还要考虑有

13、什么样的如何把定性的内容变为定量的内容，还要考虑有什么样的结构描述这类决策问题。结构描述这类决策问题。层次分析法的递阶层次结构层次分析法的递阶层次结构 目标层：目标层： 层次中只有一个因素，一般它是决策问题的预定目标层次中只有一个因素，一般它是决策问题的预定目标或理想结果，处于层次结构的第一层。或理想结果，处于层次结构的第一层。 准则层准则层： 层次中包含了为实现目标所涉及的中间环节，它可以层次中包含了为实现目标所涉及的中间环节，它可以由若干个层次组成，包括所需考虑的准则、子准则，处于由若干个层次组成，包括所需考虑的准则、子准则，处于层次结构的中间层。层次结构的中间层。 方案层方案层： 层次包

14、括了为实现目标可供选择的各种措施、决策方层次包括了为实现目标可供选择的各种措施、决策方案等，因此也称为措施层，处于层次结构的最底层。案等，因此也称为措施层，处于层次结构的最底层。最佳旅游地最佳旅游地景色费用居住饮食旅游杭洲黄山庐山目标层目标层准则层准则层踏青问题的踏青问题的3 3层的递阶层次结构层的递阶层次结构方案层方案层构造判断矩阵构造判断矩阵问题问题 1.1.层次结构虽反映了因素之间的关系，但准则层中的各准则因素在目层次结构虽反映了因素之间的关系，但准则层中的各准则因素在目标衡量中所占的比重在决策者的心目中各占有的比例不同。标衡量中所占的比重在决策者的心目中各占有的比例不同。 2. 2.在

15、确定影响某因素的诸因子在该因素中所占的比重时，主要困难是在确定影响某因素的诸因子在该因素中所占的比重时，主要困难是这些比重常常不易定量化。这些比重常常不易定量化。 3. 3.当影响某因素的因子较多时，直接考虑各因子对该因素有多大程度当影响某因素的因子较多时，直接考虑各因子对该因素有多大程度的影响时，常常会因考虑不周全、顾此失彼甚至有可能提出一组隐含的影响时，常常会因考虑不周全、顾此失彼甚至有可能提出一组隐含矛盾的数据。矛盾的数据。解决方法解决方法 两个因子通过比较容易知道它们所影响的因素的大小。两个因子通过比较容易知道它们所影响的因素的大小。 根据这个特点，根据这个特点，SaatySaaty等

16、人提出先采取对因子进行两两比较建立成对等人提出先采取对因子进行两两比较建立成对比较矩阵的办法来描述各因素两两比较后对所影响因素的数据，然后比较矩阵的办法来描述各因素两两比较后对所影响因素的数据，然后再用代数方法确定影响该因素的诸因子在该因素中所占的比重。再用代数方法确定影响该因素的诸因子在该因素中所占的比重。成对比较矩阵的构造方法成对比较矩阵的构造方法 假设要比较假设要比较n个因子个因子 对某因素对某因素Z的影响大小：的影响大小： 每次取其中的两个因子每次取其中的两个因子 和和 ，以，以 表示这两个因表示这两个因子对子对Z 的影响大小之比，全部比较结果用矩阵表示的影响大小之比，全部比较结果用矩

17、阵表示 称称A为为Z - C之间的成对比较判断矩阵（简称判断矩阵）。之间的成对比较判断矩阵（简称判断矩阵）。 容易看出容易看出12,nC CCiCjCijannijaA)(ijjiaa1Saaty 标度标度 标度 aij含义1Ci与与Cj的影响相同的影响相同 3Ci与与Cj的影响稍强的影响稍强 5Ci与与Cj的影响强的影响强 7Ci与与Cj的影响明显的强的影响明显的强 9Ci与与Cj的影响绝对的强的影响绝对的强2,4,6,8Ci与与Cj的影响之比在上述相邻等级之间的影响之比在上述相邻等级之间 1/2,1/3,1/9Ci与与Cj的影响之比为的影响之比为aij 的倒数的倒数 本例的一个判断矩阵本例

18、的一个判断矩阵 定义：若矩阵 满足 nnijaA)(11.0;2.ijjiijaaa则称之为正互反矩阵。则称之为正互反矩阵。一致性条件：一致性条件： , , ,1,2,ijjkika aai j kn构造判断矩阵构造判断矩阵问题问题 1.1.层次结构虽反映了因素之间的关系，但准则层中的各准则因素在目层次结构虽反映了因素之间的关系，但准则层中的各准则因素在目标衡量中所占的比重在决策者的心目中各占有的比例不同。标衡量中所占的比重在决策者的心目中各占有的比例不同。 2. 2.在确定影响某因素的诸因子在该因素中所占的比重时，主要困难是在确定影响某因素的诸因子在该因素中所占的比重时，主要困难是这些比重常

19、常不易定量化。这些比重常常不易定量化。 3. 3.当影响某因素的因子较多时，直接考虑各因子对该因素有多大程度当影响某因素的因子较多时，直接考虑各因子对该因素有多大程度的影响时，常常会因考虑不周全、顾此失彼甚至有可能提出一组隐含的影响时，常常会因考虑不周全、顾此失彼甚至有可能提出一组隐含矛盾的数据。矛盾的数据。解决方法解决方法 两个因子通过比较容易知道它们所影响的因素的大小。两个因子通过比较容易知道它们所影响的因素的大小。 根据这个特点，根据这个特点，SaatySaaty等人提出先采取对因子进行两两比较建立成对等人提出先采取对因子进行两两比较建立成对比较矩阵的办法来描述各因素两两比较后对所影响因

20、素的数据，然后比较矩阵的办法来描述各因素两两比较后对所影响因素的数据，然后再用代数方法确定影响该因素的诸因子在该因素中所占的比重。再用代数方法确定影响该因素的诸因子在该因素中所占的比重。成对比较矩阵的构造方法成对比较矩阵的构造方法 假设要比较假设要比较n个因子个因子 对某因素对某因素Z的影响大小：的影响大小： 每次取其中的两个因子每次取其中的两个因子 和和 ，以，以 表示这两个因表示这两个因子对子对Z 的影响大小之比，全部比较结果用矩阵表示的影响大小之比，全部比较结果用矩阵表示 称称A为为Z - C之间的成对比较判断矩阵（简称判断矩阵）。之间的成对比较判断矩阵（简称判断矩阵）。 容易看出容易看

21、出12,nC CCiCjCijannijaA)(ijjiaa1假设因子假设因子12,nC CC对对Z Z的权为的权为,1,2,jwjn则有则有11221,0,1nnniiiZw CwCwCww, ,1,2,iijjwai jnw11112122221212,nnnnnnnwwwwwwwwwwwwwwAwwwwwwww记Awnw说明权向量可以通过求矩阵的特征值对应的特征向量得到说明权向量可以通过求矩阵的特征值对应的特征向量得到 ！一致性检验处理一致性检验处理定理定理:n 阶正互反矩阵阶正互反矩阵A为一致矩阵当且仅当其最大为一致矩阵当且仅当其最大特征值特征值 .且当正互反矩阵非一致时，必有且当正互

22、反矩阵非一致时，必有 .maxnmaxn一致性指标一致性指标CI计算公式计算公式 1maxnnCI随机一致性指标随机一致性指标RI的值的值 n12345678910RI000.58 0.90 1.12 1.24 1.32 1.41 1.45 1.49一致性比例一致性比例CRCR的计算公式为的计算公式为RICICR 10. 0CR通过一致性检验的条件：若没有通过一致性检验，要对比较矩阵作适当修正。组合权向量的计算组合权向量的计算 上面的做法得到的是一组元素对其上一层中某元素的上面的做法得到的是一组元素对其上一层中某元素的权重向量。权重向量。 如果该组元素还有下一层的一组元素与其相连，则如果该组元

23、素还有下一层的一组元素与其相连，则有下层的元素通过该层建立了与上层元素的权重集合，这有下层的元素通过该层建立了与上层元素的权重集合，这种权重集合称为组合权向量。种权重集合称为组合权向量。 用层次分析法解决决策问题，我们最终要得到最底层用层次分析法解决决策问题，我们最终要得到最底层中各方案对于目标的排序权重，从而可以进行方案选择。中各方案对于目标的排序权重，从而可以进行方案选择。 组合权向量之间的公式组合权向量之间的公式 设目标层只有一个因素设目标层只有一个因素O，第二层包含，第二层包含n n个因素个因素B B， 其关于其关于O的权重记为的权重记为第三层次包含第三层次包含m个因素个因素C.第三层对第二层的每个因素的权重为第三层对第二层的每个因素的权重为 212,Tnww ww12,nBB BB 31,1,2,Tjjmjwww