武大数学建模培训多目标决策模型层次分析法P代数模型离散
Document number：BGCG-0857-BTDO-0089-2022
层次分析法建模
层次分析法（AHP－Analytic Hierachy process）---- 多目标决策方法
70 年代由美国运筹学家T·L·Satty提出的，是一种定性与定量分析相结合的多目标决策分析方法论。吸收利用行为科学的特点，是将决策者的经验判断给予量化，对目标（因素）结构复杂而且缺乏必要的数据情况下，采用此方法较为实用，是一种系统科学中，常用的一种系统分析方法，因而成为系统分析的数学工具之一。
传统的常用的研究自然科学和社会科学的方法有：
机理分析方法：利用经典的数学工具分析观察的因果关系；
统计分析方法：利用大量观测数据寻求统计规律，用随机数学方法
描述（自然现象、社会现象）现象的规律。
基本内容：（1）多目标决策问题举例AHP建模方法
（2）AHP建模方法基本步骤
（3）AHP建模方法基本算法
（3）AHP建模方法理论算法应用的若干问题。
参考书： 1、姜启源，数学模型（第二版，第9章；第三版，第8章），高等教育出版社
2、程理民等，运筹学模型与方法教程，（第10章），清华大学出版社
3、《运筹学》编写组，运筹学（修订版），第11章，第7节，清华大学出版社
一、问题举例：
A．大学毕业生就业选择问题
获得大学毕业学位的毕业生，“双向选择”时，用人单位与毕业生都有各自的选择标准和要求。就毕业生来说选择单位的标准和要求是多方面的，例如：
①能发挥自己的才干为国家作出较好贡献（即工作岗位适合发挥专
长）；
②工作收入较好（待遇好）；
③生活环境好（大城市、气候等工作条件等）；
④单位名声好（声誉-Reputation）；
⑤工作环境好（人际关系和谐等）
⑥发展晋升（promote, promotion）机会多（如新单位或单位发展有后
劲）等。
问题：现在有多个用人单位可供他选择，因此，他面临多种选择和决策，问题是他将如何作出决策和选择——或者说他将用什么方法将可供选择的工作单位排序
Ｂ.假期旅游地点选择
暑假有3个旅游胜地可供选择。例如：1P ：苏州杭州，2P 北戴河，3P 桂林，到底到哪个地方去旅游最好要作出决策和选择。为此，要把三个旅游地的特点，例如：①景色；②费用；③居住；④环境；⑤旅途条件等作一些比较——建立一个决策的准则，最后综合评判确定出一个可选择的最优方案。
目标层
准则层
方案层
C ．资源开发的综合判断
7种金属可供开发，开发后对国家贡献可以通过两两比较得到，决定对哪种资源先开发，效用最用。
二、问题分析：
例如旅游地选择问题：一般说来，此决策问题可按如下步骤进行： （S1）将决策解分解为三个层次，即：
目标层：（选择旅游地）
准则层：（景色、费用、居住、饮食、旅途等5个准则） 方案层：（有1P ，2P ，3P 三个选择地点） 并用直线连接各层次。
（S2）互相比较各准则对目标的权重，各方案对每一个准则的权重。这些权
限重在人的思维过程中常是定性的。
例如：经济好，身体好的人：会将景色好作为第一选择；
中老年人：会将居住、饮食好作为第一选择； 经济不好的人：会把费用低作为第一选择。
而层次分析方法则应给出确定权重的定量分析方法。
（S3）将方案后对准则层的权重，及准则后对目标层的权重进行综合。 （S4）最终得出方案层对目标层的权重，从而作出决策。
以上步骤和方法即是AHP 的决策分析方法。
三、确定各层次互相比较的方法——成对比较矩阵和权向量
在确定各层次各因素之间的权重时，如果只是定性的结果，则常常不容
易被别人接受，因而Santy 等人提出：一致矩阵法．．．．．
即：1. 不把所有因素放在一起比较，而是两两相互比较
2. 对此时采用相对尺度，以尽可能减少性质不同的诸因素相互比较的困难，提高准确度。
因素比较方法 —— 成对比较矩阵法：
目的是，要比较某一层n 个因素n C C C , ,,21 对上一层因素O 的影响（例如：旅游决策解中，比较景色等5个准则在选择旅游地这个目标中的重要性）。
采用的方法是：每次取两个因素i C 和j C 比较其对目标因素O 的影响，并用ij a 表示，全部比较的结果用成对比较矩阵表示，即：
)1( 1
,0 ,)(=?=
>=ij ij ij
ji ij nxn ij a a a a a a A 或 （1）
由于上述成对比较矩阵有特点： ji
ij ij ij a a a a A 1 ,0 , )(=>= 故可称A 为正互反矩阵：显然，由 ji
ij a a 1
=
，即：1=?ji ij a a ，故有：1=ji a
例如：在旅游决策问题中：
2112=a =（费用）（景色）21C C 表示：???2O 1O 21的重要性为（费用）对目标
的重要性为景色）对目标（C C 故：），费用重要性为即景色重要性为21(2112=a
14413==a = （居住条件）（景色）3
1
C C 表示：??
?1O C 4O (31的重要性为（居住条件）对目标
的重要性为景色）对目标
C 即：景色为4，居住为1。
17723==a =（居住条件）（费用）3
2
C C 表示：??
?1O C 7O (32的重要性为（居住条件）对目标
的重要性为费用）对目标
C 即：费用重要性为7，居住重要性为1。
因此有成对比较矩阵：?
??
?????
?
??=113
5
13
1112513131211714
1
55337412121
A 问题：稍加分析就发现上述成对比较矩阵的问题：
① 即存在有各元素的不一致性，例如：
既然：4
1114a ;22113313113212112==?===?==
a a C C a C C a 所以应该有：188412
1
3
12
31213223======
C C C C a a C C a
而不应为矩阵A 中的1723=a
②成对比较矩阵比较的次数要求太 ，因：n 个元素比较次数为：
!
2)
1(2
-=
n n C n 次， 因此，问题是：如何改造成对比较矩阵，使由其能确定诸因素n
C C , ,1 对上层因素O 的权重
对此Saoty 提出了：在成对比较出现不一致情况下，计算各因素
n C C , ,1 对因素（上层因素）O 的权重方法，并确定了这种不一致的容许误
差范围。
为此，先看成对比较矩阵的完全一致性——成对比较完全一致性
四：一致性矩阵
Def ：设有正互反成对比较矩阵：
???
?
???
????
?
?
??======
========= 1 a , , 1 , , 1 1nn 221122222212211121121111n n n n n n j i ij n n n
n W W W W a W W a W W
a W W a W W a W W a W W a W W a W W a A
(4) 除满足：（i ）正互反性：即
)1 ( 1
0=?=
>ji ij ji
ij ij a a a a a 或 而且还满足：（ii ）一致性：即
i, j 1, 2, n i ik ij ik kj j j k
a a
a a a a a =
=?==
则称满足上述条件的正互反对称矩阵A 为一致性矩阵，简称一致阵。
一致性矩阵（一致阵）性质： 性质1：A 的秩 Rank(A)=1
A 有唯一的非0的最大特征根为n
性质2：A 的任一列（行）向量都是对应特征根n 的特征向量：
即有(特征向量、特征值)：
?????????? ??=n n n n n n W W W W W W W W W W W
W W W W W W W A
2
1
2221212111
，则向量???????
??=321W W W W
满足：n nW nW nW W W W W W W W W W W W W W W W A n n n n
n n n
=??
?
?
??? ??=??????? ?????????
? ??=
212121
1211
1 即： 0)(=-W nI A
启发与思考：既然一致矩阵有以上性质，即n 个元素W 1, W 2, W 3 , …W n 构成的
向量????
??
?
??=→
n W W W W 21
是一致矩阵A 的特征向量，则对一致矩阵A 来说，可以把一致矩阵A 的特征向量→
W 求出之后，再把一致矩阵A 的特征向量→
W 归一化后得到的向量→
ω，看成是诸元素W 1, W 2, W 3 , …W n
目标O 的权向量。因此，可以用求一致矩阵的特征根和特征向量的办法，求出元素W 1, W 2, W 3 , …W n 相对于目标O 的权向量。
解释：一致矩阵即：n 件物体n M M M , , ,21 ，它们重量分别为
n W W W , , ,21 ，将他们
两比较重量，其比值构成一致矩阵，若用重量向量????
??
? ??=n W W W W 21右乘A ，则
：()???????
?
?????
??∑???
?
? ??????
?
?? ??称特征根法，求权向量的方法量权向量，此种用特征向为即对上层因素O的权重，，C ，，C C ，就表示诸因素＝W＝则归一化后的特征向量，＝：重量向量 为特征根的特征向量为
以的特征根为n 21 1W W W W ,121 i n W W W n n A
分析：
若重量向量????
??
? ??=n W W W W 21未知时，则可由决策者对物体n M M M , , ,21 之间
两两相比关系，主观作出比值的判断，或用Delphi （调查法）来确定这些比值，使A 矩阵（不一定有一致性）为已知的，并记此主观判断作出的矩阵为（主观）判断矩阵A ，并且此A （不一致）在不一致的容许范围内，再依据：A 的特征根或和特征向量W 连续地依赖于矩阵的元素ij a ，即当ij a 离一致性的要求不太远时，A 的特征根i 和特征值（向量）W 与一致矩阵A 的特征根λ和特征向量W 也相差不大的道理：由特征向量W 求权向量W 的方法即为特征向量法，并由此引出一致性检查的方法。
问题：Remark
以上讨论的用求特征根来求权向量W 的方法和思路，在理论上应解决以下问题：
1．一致阵的性质1是说：一致阵的最大特征根为n （即必要条件），但用特
征根来求特征向量时，应回答充分条件：即正互反矩阵是否存在正的最大特征根和正的特征向量且如果正互反矩阵A 的最大特征根n =max λ时，
A 是否为一致阵
2．用主观判断矩阵A 的特征根λ和特征向量W 连续逼近一致阵A 的特征根λ
和特征向量W 时，即： 由λλ=→k k
k lim
得到：W W k k =∞
→lim
即： A A k k =∞
→lim
是否在理论上有依据。
3．一般情况下，主观判断矩阵A 在逼近于一致阵A 的过程中，用与A 接近的
*A 来代替A ，即有A A ≈*，这种近似的替代一致性矩阵A 的作法，就导致
了产生的偏差估计问题，即一致性检验问题，即要确定一种一致性检验判断指标，由此指标来确定在什么样的允许范围内，主观判断矩阵是可以接受的，否则，要重新两两比较构造主观判断矩阵。此问题即一致性检验问题的内容。
以上三个问题：前两个问题由数学严格比较可获得（见教材P325，定理1、定理2）。第3个问题：Satty 给出一致性指标（Th1,Th2介绍如下：） 附：
Th1：（教材P326，perronTh 比隆 1970 ）对于正矩阵A （A 的所有元素为正数）
（1）A 的最大特征根是正单根λ；
（2）λ对应正特征向量W （W 的所有分量为正数）
（3）W e A e e A k T k
k =∞→lim 其中：????
??
? ??=111
e 为半径向量，W 是对应λ的归一化特
征向量
证明：（3）可以通过将A 化为标准形证明
Th2：n 阶正互反阵A 的最大特征根n ≥λ；
当n =λ时，A 是一致阵
五、一致性检验——一致性指标：
1．一致性检验指标的定义和确定——I C ?的定义：
当人们对复杂事件的各因素，采用两两比较时，所得到的主观判断矩阵
A ，一般不可直接保证正互反矩阵A 就是一致正互反矩阵A ，因而存在误差
（及误差估计问题）。这种误差，必然导致特征值和特征向量之间的误差
()][W W )(－及λλ-。此时就导致问题W max
W A λ
＝与问题nW AW =之间的差
别。（上述问题中m ax λ是主观判断矩阵A 的特征值，W 是带有偏差的相对权向量）。这是由判断矩阵不一致性所引起的。
因此，为了避免误差太大，就要给出衡量主观判断矩阵A 的一致性的判别准则。
因为：
①当主观判断矩阵A 为一致阵A 时就有：
∑∑∑∑=======n
k n k kk n k n
n k
k
n a 1
1
1
1
1λ
λ＝ A 为一致阵时有：1=ii a
此时存在唯一的非O 特征根 n ==max λλ
（由一致阵性质1：Rark(4)=1，A 有唯一非O 最大特征根且n =max λ） ②当主观判断矩阵A 不是一致矩阵时，此时一般有：n ≥max λ （Th2） 此时，应有：
∑∑==+
≠
n a ii
k h
max
max λ
λλ
即： ∑≠-
=-max
max k k
n λ
λ
所以，可以取其平均值作为检验主观判断矩阵的准则，一致性的指标， 即： 1
1
max
max --=
--=
?∑≠n n n
I C k k
λ
λ
显然：
（1） 当n =max λ时，有：0=?I C ， A 为完全一致性
（2） I C ?值越大，主观判断矩阵A 的完全一致性越差，即：A 偏离A 越
远(用特征向量作为权向量引起的误差越大)
（3） 一般10?≤?I C ，认为主观判断矩阵A 的一致性可以接受，否则应
重新进行两两比较，构造主观判断矩阵。
2．随机一致性检验指标——I R ?
问题：实际操作时发现：主观判断矩阵A 的维数越大，判断的一致性越差，
故应放宽对高维矩阵的一致性要求。于是引入修正值I R ?来校正一致性检验指标：即定义I R ?的修正值表为：
并定义新的一致性检验指标为：I
R I
C R C ??=
? 随机一致性检验指标——I R ?的解释：
为确定A 的不一致程度的容许范围，需要确定衡量A 的一致性指示I C ?的标准。于是Satty 又引入所谓随机一致性指标I R ?，其定义和计算过程为：
① 对固定的n ，随机构造正互反阵A '，其元素)(j i a ij
<'从1～9和1～9
1中随机取值，且满足ij
a '与ji a '的互反性，即：ji
ij a a '='1，且1='ii a . ② 然后再计算A '的一致性指标I C ?，因此A '是非常不一致的，此时，
I C ?值相当大.
③ 如此构造相当多的A '，再用它们的I C ?平均值作为随机一致性指标。
④ Satty 对于不同的1(=n n ～11)，用100～500个样本A '计算出上表所列
出的随机一致性指标I R ?作为修正值表。
3．
一致性检验指标的定义——一致性比率R C ?。 由随机性检验指标R C ?可知：
当2 ,1=n 时，0=?I R ，这是因为1, 2阶正互反阵总是一致阵。 对于3≥n 的成对比较阵A ，将它的一致性指标I C ?与同阶（指n 相同）的随机一致性指标I R ?之比称为一致性比率——简称一致性指标， 即有： 一致性检验指标的定义——一致性比率 定义：I R I C R C ??=
?： I
R I
C R C ??=? 当：10?
R I
C R C 时，认为主观判断矩阵A 的不一致程度在
容许范围之内，可用其特征向量作为权向量。否则，对主观判断矩阵A 重新进行成对比较，构重新的主观判断矩阵A 。 注：上式10?
?I
R I
C R C 的选取是带有一定主观信度的。
六、标度——比较尺度解：
在构造正互反矩阵时，当比较两个可能是有不同性质的因素i C 和j
C 对于上层因素O 的影响时，采用什么样的相对刻度较好，即ij a 的元素的值在（1～9）或（1～91）或更多的数字，Satty 提出用1～9尺度最好，即ij a 取值为1～9或其互反数1～91，心理学家也提出：人们区分信息等级的极限解能力为7±2。可见对n n ?阶矩阵，只需作出2
)
1(-n n 个判断值即可
注：以上比较的标度Satty 曾用过多种标度比较层，得到的结论认为：1～9尺度不仅在较简单的尺度中最好，而且比较的结果并不劣于较为复杂的尺度。Satty 曾用的比较尺度为：
① 1～3, 1～5, 1～6，…, 1～11，以及 ② )1.0(+d ～)9.0(+d ，其中4 ,3 ,2 ,1=d ③ p 1～P 9，其中 5 ,4 ,3 ,2=P …
等共27种比较尺度，对放在不同距离处的光源亮度进行比较判断，并构造出成对比较矩阵，计算出权向量。同时把计算出来的这些权向量与按照物理学中光强度定律和其他物理知识得到的实际权向量进行对比。结果也发现1～9的比较标度不仅简单，而效果也较好（至少不比其他更复杂的尺度差） 因而用1～9的标度来构造成对比较矩阵的元素较合适。
七、组合权向量的计算——层次总排序的权向量的计算 层次分析法的基本思想：
（1） 计算出下一层每个元素对上一层每个元素的权向量W
def ：层次总排序，计算同一层次所有元素对最高层相对重要性的排序权值。
当然要先：①构造下一层每个元素对上一次每个元素的成对比较矩阵 ②计算出成对比较矩阵的特征向量（和法，根法，幂法） ③由特征向量求出最大特征根m ax λ（由和法，根法，幂法求得）
④用最大特征根m ax λ用方式 1
max --=
?n n
I C λ及I
R R
C R C ??=
?对成对比较矩阵进行一致性检，并通过。
（2） 并把下层每个元素对上层每个元素的权向量按列排成以下表格形
式：例，假定：上层A 有m 个元素，m A A A , , ,21 ，且其层次总排序权向量为m a a a , , ,21 ，下层B 有n 个元素n B B B , , ,21 ，则按
j B 对 i A 个元素的单排序权向量的列向量为ij b ，即有：
注：①若下层元素k B 与上层元素j A 无关系时，取0=kj b ②总排序权向量各分量的计算公式：),,1(1n i b a W ij m
j j i ==∑=
(3) 对层次总排序进行一致性检验：从高层到低层逐层进行，如果 如果B 层次某些元素对j A 单的排序的一致性指标为j CI ，相应的平均随机
一致性指标为j RI ，则B 层总排序随机一致性比率为：∑∑===
?m
j j
j
m
j j
j
RI a
CI
a R C 1
1
当10? 八、层次分析法的基本步骤： （S1）建立层次结构模型 将有关因素按照属性自上而下地分解成若干层次： 同一层各因素从属于上一层因素，或对上层因素有影响，同时又支配下一层的因素或受到下层因素的影响。 最上层为目标层（一般只有一个因素），最下层为方案层或对象层/决策层，中间可以有1个或几个层次，通常为准则层或指标层。 当准则层元素过多（例如多于9个）时，应进一步分解出子准则层。 （S2）构造成对比较矩阵，以层次结构模型的第2层开始，对于从属于（或影响及）上一层每个因素的同一层诸因素，用成对比较法和1～9比较尺度构造成对比较矩阵，直到最下层。 （S3）计算（每个成对比较矩阵的）权向量并作一致性检验 ① 对每一个成对比较矩阵计算最大特征根m ax λ及对应的特征向量（和 法、根法、幂法等）??? ? ? ??=n W W 1 ② 利用一致性指标I C ?，随机一致性指标R C ?和一致性比率作一致性检 验?? ? ????= I R I C CR ③ 若通过检验（即1.0 ? ? ? ??=n W W W 1归一化之后作为（j B 到j A ）的权向量（即单排序权向量） ④ 若1.0 （S4）计算组合权向量并作组合一致性检验——即层次总排序 ① 利用单层权向量的权值m j W W W n j , ,11 =??? ? ? ??=构组合权向量表：并计算 出特征根，组合特征向量，一致性 ② 若通过一致性检验，则可按照组合权向量??? ? ? ??=n W W W 1的表示结果进行决 策（???? ? ??=n W W 1中i W 中最大者的最优），即： (){} T n i W W W W W ,,:max *1 ∈= ③ 若未能通过检验，则需重新考虑模型或重新构造那些一致性比率，CR 较大的成对比较矩阵 九、特征根的近似求法（实用算法） 层次分析法的基本思路是计算上层每个元素对下一层次各元素的权向量 （即最大特征根m ax λ对应的特征向量??? ? ? ??=n W W 1），以及组合权向量及一致性 检验问题。 计算判断矩阵最大特征根和对应阵向量，并不需要追求较高的精确度，这是因为判断矩阵本身有相当的误差范围。而且优先排序的数值也是定性概念的表达，故从应用性来考虑也希望使用较为简单的近似算法。常用的有以下求特征根的近似求法：“和法”、“根法”、“幂法”，具体如下： 1．“和法”求最大特征根和对应特征向量（近似解） （S1）将矩阵nxm ij a A )(=的每一列向量的归一化得：∑== n i ij ij ij a a W 1 ~ （S2）对ij W ~ 按行求和得：∑==n j ij i W W 1 ~~ （S3）将i W ~ 归一化，即有：∑== n i i i i W W W 1 ~ ~，则有特征向量：???? ? ??=n W W W 1~ （S4）计算与特征向量???? ? ??=n W W 1对应的最大特征根m ax λ的近似值： ∑==n i i i W AW n 1max )(1λ 此方法：实际上是将A 的列向量归一化后取平均值作为A 的特征向量。 解释： 当A 为一致矩阵时，它的每一列向量都是特征向量W 离散模型 § 1 离散回归模型 一、离散变量 如果我们用0，1，2，3，4，?说明企业每年的专利申请数，申请数是一个离散的变量,但是它是间隔尺度变量，该变量类型不在本章的讨论的被解释变量中。但离散变量0和1可以用来说明企业每年是否申请专利的事项，类似表示状态的变量才在本章的讨论中。在专利申请数的问题中，离散变量0，1，2，3 和4 等数字具 有具体的经济含义，不能随意更改；而在是否申请专利的两个选择对象的选择问题中，数字0和1只是用于区别两种不同的选择，是表示一种状态。本专题讨论有序尺度变量和名义尺度变量的被解释变量。 、离散因变量 在讨论家庭是否购房的问题中，可将家庭购买住房的决策用数字1 表示，而将家庭不购买住房的决策用数字0 表示。 1 yes x 0 no 如果x 作为说明某种具体经济问题的自变量，则应用以前介绍虚拟变量知识就足够了。如果现在考虑某个家庭在一定的条件下是否购买住房问题时，则表示状态的虚拟变量就不再是自变量，而是作为一个被说明对象的因变量出现在经济模型中。因此，需要对以前讨论虚拟变量的分析方法进行扩展，以便使其能够适应分析类似家庭是否购房的问题。因为在家庭是否购房问题中,虚拟因变量的具体取值仅是为了区别不同的状态，所以将通过虚拟因变量讨论备择对象选择的回归模型称为离散选择模型。 三、线性概率模型 现在约定备择对象的0 和1 两项选择模型中，下标i 表示各不同的经济主体，取值 0或l的因变量 y i表示经济主体的具体选择结果，而影响经济主体进行选择的自变量 x i 。如果选择响应YES 的概率为 p(y i 1/ x i ) ，则经济主体选择响应NO 的概率为 1 p(y i 1/ x i)， 则E(y i /x i) 1 p(y i 1/x i) 0 p(y i 0/x i)＝ p(y i 1/x i)。根据经典线性回归，我们知道其总体回归方程是条件期望建立的，这使我们想象可以构造线性概率模型 p(y i 1/ x i) E(y i / x i) x iβ 0 1 x i1 L k x ik u i 描述两个响应水平的线性概率回归模型可推知，根据统计数据得到的回归结果并不一定能够保证回归模型的因变量拟合值界于[0，1]。如果通过回归模型式得到的因变量拟合值完全偏离0或l两个数值，则描述两项选择的回归模型的实际用途就受到很大的限制。为避免出现回归模型的因变量预测值偏离0或1的情形，需要限制因变量的取值范围并对回归模型式进行必要的修正。由于要对其进行修正，那么其模型就会改变，模型改变会导致似然函 离散数学在计算机科学中的应用 本学期我们开了一门新的课程——离散数学，这是一门艰深又充满挑战的课程，随着学习的深入，我逐步加深了对它的了解。 首先简单介绍一下离散数学的定义及其在各学科领域的重要作用。离散数学(Discrete mathe matics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。 由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。 由此可见，离散数学在计算机科学中具有广泛的应用，下面我将一一陈述。 1 离散数学在关系数据库中的应用 关系数据库中的数据管理系统向用户提供使用的数据库语言称为数据子语言，它是以关系代数或谓词逻辑中的方法表示。由于用这种数学的方法去表示，使得对这些语言的研究成为对关系代数或逻辑谓词的研究，优化语言的表示变成为对关系代数与谓词逻辑的化简问题。由于引入了数学表示方法，使得关系数据库具有比其它几种数据库较为优越的条件。正因为如此关系数据库迅速发展成为一种很有前途、很有希望的数据库。另外，离散数学中的笛卡儿积是一个纯数学理论，是研究关系数据库的一种重要方法，显示出不可替代的作用。不仅为其提供理论和方法上的支持，更重要的是推动了数据库技术的研究和发展。关系数据模型建立在严格的集合代数的基础上，其数据的逻辑结构是一个由行和列组成的二维表来描述关系数据模型。在研究实体集中的域和域之间的可能关系、表结构的确定与设计、关系操作的数据查询和维护功能的实现、关系分解的无损连接性分析、连接依赖等问题都用到二元关系理论。 2 离散数学在数据结构中的应用 计算机要解决一个具体问题，必须运用数据结构知识。对于问题中所处理的数据，必须首先从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调整直至得到问题的最终解答。而寻求数学模型就是数据结构研究的内容。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描 述。数据结构中将操作对象间的关系分为四类：集合、线性结构、树形结构、图状结构或网状结构。 二、模型的假设 1、假设我们所统计和分析的数据，都是客观真实的； 2、在考虑影响毕业生就业的因素时，假设我们所选取的样本为简单随机抽样，具有典型性和普遍性，基本上能够集中反映毕业生就业实际情况； 3、在数据计算过程中，假设误差在合理范围之内，对数据结果的影响可以忽略. 三、符号说明 四、模型的分析与建立 1、问题背景的理解 随着我国改革开放的不断深入，经济转轨加速，社会转型加剧，受高校毕业生总量的增加，劳动用工管理与社会保障制度，劳动力市场的不尽完善，以及高校的毕业生部分择业期望过高等因素的影响，如今的毕业生就业形势较为严峻.为了更好地解决广大学生就业中的问题，就需要客观地、全面地分析和评价毕业生就业的若干主要因素，并将它们从主到次依秩排序. 针对不同专业的毕业生评价其就业情况，并给出某一专业的毕业生具体的就业策略. 2、方法模型的建立 （1）层次分析法 层次分析法介绍：层次分析法是一种定性与定量相结合的、系统化、层次化的分析方法，它用来帮助我们处理决策问题.特别是考虑的因素较多的决策问题，而且各个因素的重要性、影响力、或者优先程度难以量化的时候，层次分析法为我们提供了一种科学的决策方法. 通过相互比较确定各准则对于目标的权重，及各方案对于每一准则的权重.这些权重在人的思维过程中通常是定性的，而在层次分析法中则要给出得到权重的定量方法. 我们现在主要对各个因素分配合理的权重，而权重的计算一般用美国运筹学 家T.L.Saaty 教授提出的AHP 法. （2）具体计算权重的AHP 法 AHP 法是将各要素配对比较，根据各要素的相对重要程度进行判断，再根据计算成对比较矩阵的特征值获得权重向量k W . Step1. 构造成对比较矩阵 假设比较某一层k 个因素12,,,k C C C 对上一层因素ο的影响，每次两个因素i C 和j C ，用ij C 表示i C 和j C 对ο的影响之比，全部比较结果构成成对比较矩阵C ，也叫正互反矩阵. *()k k ij C C =， 0ij C >，1 ij ji C C =， 1ii C =. 若正互反矩阵C 元素成立等式：* ij jk ik C C C = ，则称C 一致性矩阵. 标度ij C 含义 1 i C 与j C 的影响相同 3 i C 比j C 的影响稍强 5 i C 比j C 的影响强 7 i C 比j C 的影响明显地强 9 i C 比j C 的影响绝对地强 2,4,6,8 i C 与j C 的影响之比在上述两个相邻等级之间 11 ,,29 i C 与j C 影响之比为上面ij a 的互反数 Step2. 计算该矩阵的权重 通过解正互反矩阵的特征值，可求得相应的特征向量，经归一化后即为权重向量 12 = [ , ,..., ]T k k k kk Q q q q ，其中的ik q 就是i C 对ο的相对权重.由特征方程 A-I=0λ，利用Mathematica 软件包可以求出最大的特征值 max λ 和相应的特征向 量. Step3. 一致性检验 1）为了度量判断的可靠程度，可计算此时的一致性度量指标CI ： 数学建模中常见的十 大模型 精品文档 数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的 收集于网络，如有侵权请联系管理员删除 信息技术与课程整合本栏目责任编辑：贾薇薇离散数学在计算机学科中的应用 陈敏，李泽军 （湖南工学院计算机科学系，湖南衡阳421002） 摘要：离散数学作为有利的数学工具，对计算机的发展与计算机科学的研究起着重大的作用。阐述了离散数学在计算机科学的几个不同领域中的应用，分析了离散数学与计算机专业其他学科间的关系，指出了离散数学在从事计算机及相关科学工作中的重要性。关键词：离散数学；数据结构；编译原理；人工智能 中图分类号：O158,TP305文献标识码：A 文章编号：1009-3044(2009)01-0251-02 The Application of Discrete Mathematics in Computer Science CHEN Min,LI Ze-jun (Department of Computer Science and Technlology,Hunan Insititute of Technology,Hengyang 421002,China) Abstract:Being a helpful mathematical tool,discrete mathematics plays a significant role in the development and research of computer sci -ence.This paper introduces the application of discrete mathematics in different fields of computer science,analyzes the relationship between discrete mathematics and other subjects in computer specialty and points out the importance of discrete mathematics in computer science and related fields. Key words:discrete mathematics;data structure;decoding principles;artificial intelligence 1引言 离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。它是以研究离散性的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素。由于计算机科学的迅速发展，与其有关的领域中，提出了许多有关离散量的理论问题，需要用某些数学的工具做出描述和深化[1]。离散数学把计算机科学中所涉及到的研究离散量的数学综合在一起，进行较系统的、全面的论述，为研究计算机科学的相关问题提供了有力的工具。 离散数学课程所涉及的概念、方法和理论，大量地应用在数据结构、数据库系统、编译原理、人工智能、计算机体系结构、算法分析与设计、软件工程、多媒体技术、数字电路、计算机网络等专业课程以及信息管理、信号处理、模式识别、数据加密等相关课程中[2-4]。它所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。这些能力与态度是一切软、硬件计算机科学工作者所不可缺少的，为学习计算机科学的后续课程、从事科研或工程技术工作以及进一步提高科学技术水平奠定理论基础。离散数学提供的营养滋补了计算机科学的众多领域，学好了离散数学就等于掌握了一把开启计算机科学之门不可缺少的钥匙。 2离散数学在数据结构中的应用 计算机要解决一个具体问题，必须运用数据结构知识。对于问题中所处理的数据，必须首先从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调整直至得到问题的最终解答。而寻求数学模型就是数据结构研究的内容。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。数据结构中将操作对象间的关系分为四类：集合、线性结构、树形结构、图状结构或网状结构。数据结构研究的主要内容是数据的逻辑结构，物理存储结构以及基本运算操作。其中逻辑结构和基本运算操作来源于离散数学中的离散结构和算法思考。离散数学中的集合论、关系、图论、树四个章节就反映了数据结构中四大结构的知识。如集合由元素组成，元素可理解为世上的客观事物。关系是集合的元素之间都存在某种关系。例如雇员与其工资之间的关系。图论是有许多现代应用的古老题目。伟大的瑞士数学家列昂哈德·欧拉在18世纪引进了图论的基本思想，他利用图解决了有名的哥尼斯堡七桥问题。还可以用边上带权值的图来解决诸如寻找交通网络里两城市之间最短通路的问题[5]。而树反映对象之间的关系，如组织机构图、家族图、二进制编码都是以树作为模型来讨论。 3离散数学在数据库中的应用 数据库技术被广泛应用于社会各个领域，关系数据库已经成为数据库的主流，离散数学中的笛卡儿积是一个纯数学理论，是研究关系数据库的一种重要方法，显示出不可替代的作用。不仅为其提供理论和方法上的支持，更重要的是推动了数据库技术的研究和发展。关系数据模型建立在严格的集合代数的基础上，其数据的逻辑结构是一个由行和列组成的二维表来描述关系数据模型。在研究实体集中的域和域之间的可能关系、表结构的确定与设计、关系操作的数据查询和维护功能的实现、关系分解的无损连接性分析、连接依赖等问题都用到二元关系理论[6]。 4离散数学在编译原理中的应用 编译程序是计算机的一个十分复杂的系统程序。一个典型的编译程序一般都含有八个部分：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、错误检查和处理程序、各种信息表格的管理程序[7]。离散数学里的计算模型章节里就讲了三种类型的计算模型：文法、有限状态机和图灵机。具体知识有语言和文法、带输出的有限状态机、不带输出的有限状态机、语言的识别、图灵机等。短语结构文法根据产生式类型来分类：0型文法、1型文法、2型文法、3型文法。以上这些收稿日期：2008-12-10 基金项目：“湖南省教育厅教学改革研究项目（湘教通2008第263号） ISSN 1009-3044 Computer Knowledge and Technology 电脑知识与技术 Vol.5,No.1,January 2009,pp.251-252E-mail:kfyj@https://www.doczj.com/doc/2215592587.html, https://www.doczj.com/doc/2215592587.html, Tel:+86-551-56909635690964251 离散建模 专业计算机科学与技术 班级 姓名 学号 授课教师 二 O 一七年十二月 离散建模是离散数学与计算机科学技术及IT技术应用间的联系桥梁。也是学习离散数学的根本目的。 它有两部分内容组成: 1.离散建模概念与方法 2.离散建模应用实例 一.离散建模概念与方法 1.1离散建模概念 在客观世界中往往需要有许多问题等待人们去解决。而解决的方法很多，最为常见的方法是将客观世界中的问题域抽象成一种形式化的数学表示称数学模型，从而将对问题域的求解变成为对数学表示式的求解。而由于人们对数学的研究已有数千年历史，并已形成了一整套行之有效的对数学求解的理论与方法，因此用这种数学方法去解决实际问题可以取得事倍功半的作用。而采用这种方法的关键之处是数学模型的建立，它称为数学建模，而当这种数学模型是建立在有限集或可列集之上时，此种模型的建立称离散建模。 1.2.离散建模方法 （1）两个世界理论 在离散建模中有两个世界，一个是现实世界另一个是离散世界。现实世界是问题域产生的世界，离散世界则是一种数学世界，它有三个特性：离散世界采用离散数学语言，该语言具有简洁性且表达力丰富。 离散世界所表示的是一种抽象符号，它是一种形式化符号体系。 离散世界中的环境简单，它在离散建模时设立，可以屏蔽大量无关信息对问题求解的干扰。 为求解问题须将问题域转换成离散模型,然后对离散模型求解,再逆向转换成现实世界中的解. （2）两个世界的转换 在离散建模方法中需要构作两种转换，即由现实世界到离散世界的转换以及由离散世界到现实世界的逆转换，而其中第一种转换尤为重要，这种转换我们一般即称之为离散建模。 下面对两种转换作介绍： 现实世界到离散世界的转换 复杂系统决策模型与层次分析法 费用居住饮食交通例3?科研课题 科研课題 承徳 可行性 实用价值学 术 意 义 人 才 培 养 §3.4复杂系统决策模型与层次分析法 Analitic Hierachy Process （AHP） T. L. Saaty 1970* —种定性和定量相结合的、系统化、层次化的分析方法。—?问题举例 1.在海尔、新飞、容声和雪花四个牌号的电冰箱中选购一种。要考虑品牌的信誉、冰箱的功能、价格和耗电量。 2.在泰山、杭州和承德三处选择一个旅游点。要考虑景点的景色、居住的环境、饮食的特色、交通便利和旅游的费用。 3.在基础研究、应用研究和数学教育中选择一个领域申报科研课题。要考虑成果的贡献（实用价值、科学意义），可行性（难度、周期和经费）和人才培养。 -?模型和方法 1.层次结构模型的构造 步骤一：确定层次结构，将决策的目标、考虑的因素（决策准则）和决策对象按它们之间的相互关系分为最高层、中间层和最低层，绘出层次结构图。 最高层：决策的目的、要解决的问题。 最低层：决策时的备选方案。 中间层：考虑的因素、决策的准则。 对于相邻的两层，称高层为目标层，低层为因素层。 例1.选购冰箱迭购冰箱步骤二：通过相互比较，确定下一 层各因素对上一层目标的影响的权重，将定性的判断定量化，即构 造因素判断矩阵。 例2. 步骤三：由矩阵的特征值确定判别的一致性；由相应的特征向量表示各因素的影响 权重，计算权向量。 步骤四：通过综合计算给出最底层（各方案）对最高层（总目标）影响的权重， 权重最大的方案即为实现目标的最由选择。 2. 因素判断矩阵 比较n 个因素y 二（y“兀,…,yJ 对目标z 的影响. 采用两两成对比较，用弘表示因素y ：与因素力对目标z 的影响程度之比。 通常用数字r 9及其倒数作为程度比较的标度，即九级标度法 Xi/Xj 相当 较重要 重要 很重要绝对重要 Si ； 1 3 5 7 9 2, 4, 6, 8 居于上述两个相邻判断之间。 当弘＞ 1时，对目标Z 来说Xi 比X ：重要，其数值大小表示重要的程度。 同时必有3二1/氐＜1,对目标Z 来说X ：比血不重要，其数值大小表示不重 要的程度。 称矩阵A = （ aij ）为因素判断矩阵。 因为＞0且a.i =1/ 故称A 二（％ ）为正互反矩阵。 例.选择旅游景点Z ：目标，选择景点 y ：因素，决策准则 如果a ￡j a jk =a ik i, j, k=l, 2,n.则称正互反矩阵A 具有一致性.这表明对 各个因素所作的两两比较是可传递的。 —致性互正反矩阵A=（如）具有性质： A 的每一行例）均为任意指定行（列）的正数倍数，因此wnk （A ）二1. A 有特征值九二n,其余特征值均为零. 记A 的对应特征值九二n 的特征向量为w 二（w : w 2,…，wj 贝IJ a ￡j 二w, w ；1 如果在目标Z 中n 个因素y= (yi, y 2,…,yj 所占比重分别为w 二(w 】w?,…，wj, 则 =1,且因素判断矩阵为A=(w i w ；1) o 因此，称一致性正互反矩阵A 相应于特征值n 的归一化特征向量为因素 y= (yi> y?,…,yJ 对目标z 的权向量 4. 一致性检验与因素排序 定理1： n 阶正互反矩阵A 是一致性的当且仅当其最大特征值为n. 定理2：正互反矩阵具有模最大的正实数特征值九，其重数为1,且相应特征向量 为正向量. 为刻画n 阶正互反矩阵A=(如)与一致性接近的程度，定义一致性指标(Consensus index): 1 2 7 5 5 1/2 1 4 3 3 4 = 1/7 1/4 1 1/2 1/3 1/5 1/3 I 1 J/5 1/3 3 1 1 yi 费用, 景色, ys 居住, 3.—致性与权向量 yi 饮食，ys 交通 第四讲层次分析法 在现实世界中，往往会遇到决策的问题，比如如何选择旅游景点的问题，选择升学志愿的问题等等。在决策者作出最后的决定以前，他必须考虑很多方面的因素或者判断准则，最终通过这些准则作出选择。 比如选择一个旅游景点时，你可以从宁波、普陀山、浙西大峡谷、雁荡山和楠溪江中选择一个作为自己的旅游目的地，在进行选择时，你所考虑的因素有旅游的费用、旅游地的景色、景点的居住条件和饮食状况以及交通状况等等。这些因素是相互制约、相互影响的。我们将这样的复杂系统称为一个决策系统。这些决策系统中很多因素之间的比较往往无法用定量的方式描述，此时需要将半定性、半定量的问题转化为定量计算问题。层次分析法是解决这类问题的行之有效的方法。层次分析法将复杂的决策系统层次化，通过逐层比较各种关联因素的重要性来为分析、决策提供定量的依据。 一、建立系统的递阶层次结构 首先要把问题条理化、层次化，构造出一个有层次的结构模型。一个决策系统大体可以分成三个层次： （1） 最高层（目标层）：这一层次中只有一个元素，一般它是分析问题的预定目标或理想结果； （2） 中间层（准则层）：这一层次中包含了为实现目标所涉及的中间环节，它可以由若干个层次组成，包括所需考虑的准则、子准则； （3） 最低层（方案层）：这一层次包括了为实现目标可供选择的各种措施、决策方案等。 比如旅游景点问题，我们可以得到下面的决策系统： 目标层——选择一个旅游景点 准则层——旅游费用、景色、居住、饮食、交通 方案层——宁波、普陀山、浙西大峡谷、雁荡山、楠溪江 二、构造成对比较判断矩阵和正互反矩阵 在确定了比较准则以及备选的方案后，需要比较若干个因素对同一目标的影响，从额确定它们在目标中占的比重。如旅游问题中，五个准则对于不同决策者在进行决策是肯定会有不同的重要程度，而不同的方案在相同的准则上也有不同的适合程度表现。层次结构反映了因素之间的关系，但准则层中的各准则在目标衡量中所占的比重并不一定相同，在决策者的 数学建模中常见的十大 模型 Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】 数学建模常用的十大算法==转 (2011-07-24 16:13:14) 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 数学建模算法--复杂系统决策模型与层次分析法 §3.4 复杂系统决策模型与层次分析法 Analitic Hierachy Process (AHP) T.L.Saaty 1970’ 一种定性和定量相结合的、系统化、层次化的分析方法。 一. 问题举例 1. 在海尔、新飞、容声和雪花四个牌号的电冰箱中选购一种。要考虑品牌的信誉、冰箱的功能、价格和耗电量。 2. 在泰山、杭州和承德三处选择一个旅游点。要考虑景点的景色、居住的环境、饮食的特色、交通便利和旅游的费用。 3. 在基础研究、应用研究和数学教育中选择一个领域申报科研课题。要考虑成果的贡献（实用价值、科学意义），可行性（难度、周期和经费）和人才培养。 二. 模型和方法 1. 层次结构模型的构造 步骤一：确定层次结构，将决策的目标、考虑的因素（决策准则）和决策对象按它们之间的相互关系分为最高层、中间层和最低层，绘出层次结构图。 最高层：决策的目的、要解决的问题。 最低层：决策时的备选方案。 中间层：考虑的因素、决策的准则。 对于相邻的两层，称高层为目标层，低层为因素层。 例 1. 选购冰箱 例2. 旅游景点 例3. 选购冰箱 品牌 功能 价格 耗电 海尔 新飞 容声 雪花 旅游景点 居住 景色 费用 饮食 交通 泰山 杭州 承德 科研课题 贡献 可行性 实 用 价 值 学 术 意 义 人 才 培 养 难 度 周 期 经 费 基础 应用 教育 步骤二： 通过相互比较，确定下一层各因素对上一层目标的影响的权重，将定性的判断定量化，即构造因素判断矩阵。 步骤三：由矩阵的特征值确定判别的一致性；由相应的特征向量表示各因素的影响权重，计算权向量。 步骤四： 通过综合计算给出最底层（各方案）对最高层（总目标）影响的权重，权重最大的方案即为实现目标的最由选择。 2. 因素判断矩阵 比较n 个因素y=(y 1,y 2,…,y n )对目标 z 的影响. 采用两两成对比较，用a ij 表示因素 y i 与因素y j 对目标z 的影响程度之比。 通常用数字 1~ 9及其倒数作为程度比较的标度， 即九级标度法 x i /x j 相当 较重要 重要 很重要 绝对重要 a ij 1 3 5 7 9 2, 4, 6, 8 居于上述两个相邻判断之间。 当a ij > 1时，对目标 Z 来说 x i 比 x j 重要, 其数值大小表示重要的程度。 同时必有 a ji = 1/ a ij ≤1，对目标 Z 来说 x j 比 x i 不重要，其数值大小表示不重要的程度。 称矩阵 A = （ a ij ）为因素判断矩阵。 因为 a ij >0 且 a ji =1/ a ij 故称A = (a ij )为正互反矩阵。 例. 选择旅游景点 Z ：目标，选择景点 y ：因素，决策准则 y 1 费用，y 2 景色，y 3 居住，y 4 饮食，y 5 交通 3. 一致性与权向量 如果 a ij a jk =a ik i, j, k=1,2,…,n， 则称正互反矩阵A 具有一致性. 这表明对各个因素所作的两两比较是可传递的。 一致性互正反矩阵A=( a ij )具有性质: A 的每一行(列)均为任意指定行(列)的正数倍数,因此 rank(A)=1. A 有特征值λ=n, 其余特征值均为零. 记A 的对应特征值λ=n 的特征向量为w=(w 1 w 2 ,…, w n ) 则 a ij =w i w j -1 如果在目标z 中n 个因素y=(y 1,y 2,…,y n )所占比重分别为w=(w 1 w 2 ,…, w n ), 则 ∑i w i =1, 且因素判断矩阵为 A=(w i w j -1) 。 因此，称一致性正互反矩阵A 相应于特征值n 的归一化特征向量为因素y=(y 1,y 2,…,y n )对目标z 的权向量 4. 一致性检验与因素排序 定理1: n 阶正互反矩阵A 是一致性的当且仅当其最大特征值为 n. 定理2: 正互反矩阵具有模最大的正实数特征值λ1, 其重数为1, 且相应特征向量为正向量. 为刻画n 阶正互反矩阵A=( a ij )与一致性接近的程度, 定义一致性指标(Consensus index) : CI=(λ1-n)/(n-1) CI = 0, A 有完全的一致性。CI 接近于 0, A 有满意的一致性 。 Saaty 又引入平均随机一致性指标RT n 1 2 3 4 5 6 7 8 9 RI 0 0 0.58 0.90 1.12 1.24 1.32 1.41 1.45 当CR = CI / RI < 0.1 时, 认为A 有满意的一致性。 ????????????????=1133/15/11123 /15/13/12/114/17/133412/155 721A 二、模型的假设 1、假设我们所统计与分析的数据,都就是客观真实的; 2、在考虑影响毕业生就业的因素时,假设我们所选取的样本为简单随机抽样,具有典型性与普遍性,基本上能够集中反映毕业生就业实际情况; 3、在数据计算过程中,假设误差在合理范围之内,对数据结果的影响可以忽略、 三、符号说明 四、模型的分析与建立 1、问题背景的理解 随着我国改革开放的不断深入,经济转轨加速,社会转型加剧,受高校毕业生总量的增加,劳动用工管理与社会保障制度,劳动力市场的不尽完善,以及高校的毕业生部分择业期望过高等因素的影响,如今的毕业生就业形势较为严峻、为了更好地解决广大学生就业中的问题,就需要客观地、全面地分析与评价毕业生就业的若干主要因素,并将它们从主到次依秩排序、 针对不同专业的毕业生评价其就业情况,并给出某一专业的毕业生具体的就业策略、 2、方法模型的建立 (1)层次分析法 层次分析法介绍:层次分析法就是一种定性与定量相结合的、系统化、层次化的分析方法,它用来帮助我们处理决策问题、特别就是考虑的因素较多的决策问题,而且各个因素的重要性、影响力、或者优先程度难以量化的时候,层次分析法为我们提供了一种科学的决策方法、 通过相互比较确定各准则对于目标的权重,及各方案对于每一准则的权重、这些权重在人的思维过程中通常就是定性的,而在层次分析法中则要给出得到权重的定量方法、 我们现在主要对各个因素分配合理的权重,而权重的计算一般用美国运筹学家T、L、Saaty教授提出的AHP法、 (2)具体计算权重的AHP 法 AHP法就是将各要素配对比较,根据各要素的相对重要程度进行判断,再根据 W、 计算成对比较矩阵的特征值获得权重向量 k 2016江西财经大学数学建模竞赛 A题 城市交通模型分析 参赛队员: 黄汉秦、乐晨阳、金霞 参赛队编号：2016018 2016年5月20日~5月25日 承诺书 我们仔细阅读了江西财经大学数学建模竞赛的竞赛章程。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C中选择一项填写）： A 我们的参赛队编号为2016018 参赛队员(打印并签名) ： 队员1. 姓名专业班级计算机141 队员2. 姓名专业班级计算机141 队员3. 姓名专业班级计算机141 日期： 2016 年 5 月 25 日 编号和阅卷专用页 江西财经大学数学建模竞赛组委会 2016年5月15日制定 城市交通模型分析 摘要 随着国民经济的高速发展和城市化进程的加快，我国机动车保有量及道路交通流量急剧增加，交通出行结构发生了根本变化，城市道路交通拥挤堵塞问题已成为制约经济发展、降低人民生活质量、削弱经济活力的瓶颈之一。本篇论文针对道路拥挤的问题采用层次分析法进行数学建模分析，讨论拥堵的深层次问题及解决方案。 首先建立绩效评价指标的层次结构模型，确定了目标层，准则层（一级指标），子准则层（二级指标）。 其次，建立评价集V=(优，良，中，差)。对于目标层下每个一级评价指标下相对于第m 个评价等级的隶属程度由专家的百分数u 评判给出，即U ＝[0,100]应用模糊统计建立它们的隶属函数A(u)， B(u)， C(u) ，D(u)，最后得出目标层的评价矩阵Ri ，（i=1,2,3,4,5）。利用A,B 两城相互比较法，根据实际数据建立二级指标对于相应一级指标的模糊判断矩阵P i （i=1,2,3,4,5） 然后，我们经过N 次试验调查，明确了各层元素相对于上层指标的重要性排序，构造模糊判断矩阵P ，利用公式 1 ,ij ij n kj k u u u == ∑ 1 ,n i ij j w u ==∑ 1 ,i i n j j w w w == ∑ []R W R W R W R W R W W R W O 5 5 4 4 3 3 2 2 1 1 ,,,,==计算出权重值，经过一致性检验公式 RI CI CR = 检验后，均有0.1CR <，由此得出各层次的权向量()12,,T n W W W W =K 。然后后， 给出建立绩效评价模型（其中O 是评价结果向量），应用模糊数学中最大隶属度原则，对被评价城市交通的绩效进行分级评价。 接着在改进方案中，我们具体以交叉口为中心建立模型，其中包括道路长度、宽度、车辆平均长度、车速等等考虑因素。通过车辆排队长度可以间接判断交通拥堵情况，不需要测量车速、时间等因素而浪费的人力物力和财力，有效的提高了工作成本和效率。为管理城市交通要道提供了良好的模型和依据。 【关键字】交通拥堵 层次分析法 模糊综合评判 绩效评价 隶属度 数学模型的分类 按模型的数学方法分： 几何模型、图论模型、微分方程模型、概率模型、最优控制模型、规划论模型、马氏链模型等 按模型的特征分： 静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型等 按模型的应用领域分： 人口模型、交通模型、经济模型、生态模型、资源模型、环境模型等。 按建模的目的分： 预测模型、优化模型、决策模型、控制模型等 一般研究数学建模论文的时候，是按照建模的目的去分类的，并且是算法往往也和建模的目的对应 按对模型结构的了解程度分： 有白箱模型、灰箱模型、黑箱模型等 比赛尽量避免使用，黑箱模型、灰箱模型，以及一些主观性模型。 按比赛命题方向分： 国赛一般是离散模型和连续模型各一个，2016美赛六个题目（离散、连续、运筹学/复杂网络、大数据、环境科学、政策） 数学建模十大算法 1、蒙特卡罗算法 （该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法） 2、数据拟合、参数估计、插值等数据处理算法 （比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题 （建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法 （这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法 （这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法 （这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法 （当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法 （很多问题都是从实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法 （如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法 （赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的这些图形如何展示，以及如何处理就是需要解决的问题，通常使用Matlab进行处理） 算法简介 1、灰色预测模型（必掌握） 解决预测类型题目。由于属于灰箱模型，一般比赛期间不优先使用。 满足两个条件可用： ①数据样本点个数少，6-15个 ②数据呈现指数或曲线的形式 2、微分方程预测（高大上、备用） 微分方程预测是方程类模型中最常见的一种算法。近几年比赛都有体现，但其中的要求，不言而喻。学习过程中 无法直接找到原始数据之间的关系，但可以找到原始数据变化速度之间的关系，通过公式推导转化为原始数据的关系。 3、回归分析预测（必掌握） 求一个因变量与若干自变量之间的关系，若自变量变化后，求因变量如何变化； 样本点的个数有要求： ①自变量之间协方差比较小，最好趋近于0，自变量间的相关性小； ②样本点的个数n＞3k+1，k为自变量的个数； 8.3.2 层次分析法的计算步骤 一、建立层次结构模型 运用AHP进行系统分析，首先要将所包含的因素分组，每一组作为一个层次，把问题条理化、层次化，构造层次分析的结构模型。这些层次大体上可分为3类 1、最高层：在这一层次中只有一个元素，一般是分析问题的预定目标或理想结果，因此又称目标层； 2、中间层：这一层次包括了为实现目标所涉及的中间环节，它可由若干个层次组成，包括所需要考虑的准则，子准则，因此又称为准则层； 3、最底层：表示为实现目标可供选择的各种措施、决策、方案等，因此又称为措施层或方案层。 层次分析结构中各项称为此结构模型中的元素，这里要注意，层次之间的支配关系不一定是完全的，即可以有元素（非底层元素）并不支配下一层次的所有元素而只支配其中部分元素。这种自上而下的支配关系所形成的层次结构，我们称之为递阶层次结构。 递阶层次结构中的层次数与问题的复杂程度及分析的详尽程度有关，一般可不受限制。为了避免由于支配的元素过多而给两两比较判断带来困难，每层次中各元素所支配的元素一般地不要超过9个，若多于9个时，可将该层次再划分为若干子层。 例如，大学毕业的选择问题，毕业生需要从收入、社会地位及发展机会方面考虑是否留校工作、读研究生、到某公司或当公务员，这些关系可以将其划分为如图8.1所示的层次结构模型。 图8.1 再如，国家综合实力比较的层次结构模型如图6 .2： 图6 .2 图中，最高层表示解决问题的目的，即应用AHP所要达到的目标；中间层表示采用某种措施和政策来实现预定目标所涉及的中间环节，一般又分为策略层、约束层、准则层等；最低层表示解决问题的措施或政策（即方案）。 然后，用连线表明上一层因素与下一层的联系。如果某个因素与下一层所有因素均有联系，那么称这个因素与下一层存在完全层次关系。有时存在不完全层次关系，即某个因素只与下一层次的部分因素有联系。层次之间可以建立子层次。子层次从属于主层次的某个因素。它的因素与下一层次的因素有联系，但不形成独立层次，层次结构模型往往有结构模型表示。 二、构造判断矩阵 任何系统分析都以一定的信息为基础。AHP的信息基础主要是人们对每一层次各因素的相对重要性给出的判断，这些判断用数值表示出来，写成矩阵形式就是判断矩阵。判断矩阵是AHP工作的出发点，构造判断矩阵是AHP的关键一步。 当上、下层之间关系被确定之后，需确定与上层某元素（目标A或某个准则Z）相联系的下层各元素在上层元素Z之中所占的比重。 假定A层中因素Ak与下一层次中因素B1，B2，…，Bn有联系，则我们构造的判断矩阵如表8.16所示。 表8.16 判断距阵 Ak B1 B2 …Bn数学建模专题汇总-离散模型
离散数学在计算机科学中的应用
层次分析法模型
数学建模中常见的十大模型讲课稿
离散数学在计算机学科中的应用
(完整word版)离散数学建模
最新复杂系统决策模型与层次分析法
数学建模之层次分析法
数学建模中常见的十大模型
数学建模算法--复杂系统决策模型与层次分析法
层次分析法模型
(完整版)基于层次分析法的模糊综合评价模型
数学建模常用算法模型
层次分析法的计算步骤
相关主题
文本预览