下载文档原格式
离散模型的原理和应用原理离散模型是指在数学和计算机科学中，将连续对象或现象进行离散化处理的模型和方法。
它涉及到对连续数据进行离散化表示和处理的技术，广泛应用于各个领域。
离散模型的原理主要涉及以下几个方面：离散化表示离散化表示是将连续数据转化为离散数据的过程。
在离散化表示中，连续数据被划分为若干个不相交的区间，每个区间用一个离散值来表示。
离散化表示可以通过等宽法、等频法、聚类法等多种方法来完成。
状态空间离散模型中的状态空间是指系统在不同时刻可能处于的不同状态的集合。
状态空间可以用有限状态机、马尔科夫链等形式来表示。
状态空间的大小和粒度直接影响了离散模型的复杂度和效果。
离散模型的转移规则离散模型中的转移规则描述了系统在不同状态之间的转移概率或条件。
转移规则可以通过概率矩阵、转移图等方式来表示。
转移规则的设计和优化对于离散模型的准确性和效率都有很大影响。
离散模型的推理和学习算法离散模型的推理和学习算法用于对离散模型进行推理和学习。
推理算法可以用于根据给定的观测数据来推断系统的状态，学习算法则可以用于从数据中学习转移规则和状态空间。
常用的离散模型推理和学习算法包括贝叶斯网络、隐马尔可夫模型等。
应用离散模型在各个领域中都有广泛应用。
以下是几个典型的应用领域：自然语言处理在自然语言处理领域，离散模型被用于词义消歧、句法分析、机器翻译等任务。
通过将单词或句子的表示离散化，可以方便地进行语义匹配和推理。
图像处理在图像处理领域，离散模型被用于图像分割、目标检测、图像生成等任务。
通过将像素或图像的表示离散化，可以方便地进行图像的分析和处理。
机器学习在机器学习领域，离散模型被用于分类、聚类、回归等任务。
通过将输入特征和输出标签的表示离散化，可以方便地进行模型的训练和预测。
强化学习在强化学习领域，离散模型被用于描述智能体和环境之间的交互。
通过将状态、动作和奖励的表示离散化，可以方便地进行智能体的决策和优化。
社交网络分析在社交网络分析领域，离散模型被用于描述人与人之间的联系和行为。
实验09 离散模型（2学时）（第8章离散模型）1. 层次分析模型1.1（验证，编程）正互反阵最大特征根和特征向量的实用算法p263~264已知正互反阵261????1/21A?4????1/461/1??注：[263]定理2 n阶正互反阵A的最大特征根≥n。
★(1) 用MATLAB函数求A的最大特征根和特征向量。
调用及运行结果（见[264]）：1 3.0092k =1>> w=V(:,k)/sum(V(:,k))w =0.58760.32340.0890[263]）(2) 幂法（见n正互反矩阵，算法步骤如下：A为n×(0)w 1）；a. 任取n 维非负归一化初始列向量（分量之和为)k?1)((k2,0,1,?Aww,k?；计算b.1)?(k w1)k?(?w1)k?(w归一化，即令c. ；n?1)?(k w i1i?)(1)k(k?1)k?(?)n|?|w,(i?w?1,2,w即，当d. 对于预先给定的精度ε时，iib；为所求的特征向量；否则返回到步骤1)?(kn w1??i?。
e. 计算最大特征根)(k wn1i?i 注：)k(k?1)(((k)k)???wAw??ww?1)(k? w?i n,i?1,2,??)k(w i文件如下：函数式m [lambda w]=p263MI(A,d)function——求正互反阵最大特征根和特征向量%幂法% A 正互反方阵% d 精度 2 % lambda 最大特征根归一化特征列向量% w0.000001，则d取if(nargin==1) %若只输入一个变量（即A）d=1e-6;end的阶数取方阵A n=length(A); %任取归一化初始列向量w0=w0/sum(w0);%w0=rand(n,1);1while ww=A*w0;%归一化w=ww/sum(ww);all(abs(w-w0)<d) if; breakendw0=w;endlambda=sum(ww./w0)/n;的最大特征根和特征向量。
实验09离散模型（2学时）（第8章离散模型）1. 层次分析模型（验证，编程）正互反阵最大特征根和特征向量的实用算法p263~264已知正互反阵注：[263]定理2 n阶正互反阵A的最大特征根≥n。
★(1) 用MATLAB函数求A的最大特征根和特征向量。
A为n×n正互反矩阵，算法步骤如下：a. 任取n 维非负归一化初始列向量（分量之和为1）(0)w ；b. 计算(1)(),0,1,2,k k wAw k +==%L ； c. (1)k w +%归一化，即令(1)(1)(1)1k k n k ii ww w+++==∑%%； d. 对于预先给定的精度ε，当(1)()||(1,2,,)k k i i w w i n ε+-<=L 时，(1)k w +即为所求的特征向量；否则返回到步骤b ；e. 计算最大特征根(1)()11k n i k i i w n w λ+==∑%。
注：☆(2) 用幂法函数求A 的最大特征根和特征向量。
A 为n×n 正互反矩阵，算法步骤如下：a. 将A 的每一列向量归一化得∑==n i ijij ij a a w 1~；b. 对ijw ~按行求和得∑==nj ij i w w 1~~； c. 将i w ~归一化T n n i i i i w w w w ww w ),,,(,~~211Λ==∑=即为近似特征向量；d. 计算∑==n i ii w Aw n 1)(1λ，作为最大特征根的近似值。
☆(3) 用和法函数求A 的最大特征根和特征向量。
根法（见[264]）A 为n×n 正互反矩阵，算法步骤如下：a. 将A 的每一列向量归一化得∑==n i ijij ij a a w 1~； b. 对ijw ~按行求积并开n 次方得∏==n j nij i w w 11)~(~； c. 将i w ~归一化T n n i ii i w w w w w w w ),,,(,~~211Λ==∑=即为近似特征向量；d. 计算∑==n i ii w Aw n 1)(1λ，作为最大特征根的近似值。
第8章 习题参考答案1. 在一次10周年同学聚会上，想统计所有人握手的次数之和，应该如何建立该问题的图论模型？解：将每个同学分别作为一个节点，如果两个人握过一次手就在相应的两个节点之间画一条无向边，于是得到一个无向图。
一个人握手的次数就是这个节点与其他节点所连接的边的条数，进而可得出所有人握手的次数之和。
2. 在一个地方有3户人家，并且有3口井供他们使用。
由于土质和气候的关系，有些井中的水常常干枯，因此各户人家要到有水的井去打水。
不久，这3户人家成了冤家，于是决定各自修一条路通往水井，打算使得他们在去水井的路上不会相遇。
试建立解决此问题的图论模型。
解：将3户人家分别看做3个节点且将3口井分别看做另外3个节点，若1户人家与1口井之间有一条路，则在该户人家与该口井对应的节点之间连一条无向边，这样就得到一个无向图。
3. 某人挑一担菜并带一条狼和一只羊要从河的一岸到对岸去。
由于船太小，只能带狼、菜、羊中的一种过河。
由于明显的原因，当人不在场时，狼要吃羊，羊要吃菜。
通过建立图论模型给出问题答案。
解：不妨认为从北岸到南岸，则在北岸可能出现的状态为24=16种，其中安全状态有下面10种：（人，狼，羊，菜），（人，狼，羊），（人，狼，菜），（人，羊，菜），（Φ），（人，羊），（菜），（羊），（狼），（狼，菜）；不安全的状态有下面6种：（人）（人，菜）（人，狼）（狼，羊，菜）（狼，羊）（羊，菜）。
线将北岸的10种安全状态看做10个节点，而渡河的过程则是状态之间的转移，这样就得到一个无向图，如图8-1所示。
图8-1从上述无向图可以得出安全的渡河方案有两种：第1种：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（狼）→（人，狼，羊）→（羊）→（人，羊）→（Φ）。
(人，狼，羊，菜)(人，狼，羊)(人，狼，菜)(人，羊，菜)(人，羊) (狼，菜) (羊) (狼) (菜) (Φ)第2中：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（菜）→（人，羊，菜）→（羊）→（人，羊）→（Φ）。
第八章离散模型一般地说，确定性离散模型包括的范围很广，除第7章的差分方程模型外，用整体规划、图论、对策论、网络流等数学工具都可以建立离散模型。
本章选择了几个在实际应用较广、涉及的数学模型又不太深的模型。
“层次分析模型”和“冲量过程模型”是对社会经济体系进行系统分配的有力工具，“循环比赛的名次”讨论了排序问题，“马氏链模型”主要解决随机转移过程的问题。
从应用的角度看，这些模型只是用到基本的代数、集合，及一点点图论的知识。
8.1层次分析模型人们从日常生活中常常碰到许多决策问题：买一件衬衫，你要在棉的、丝的、涤纶的……及花的、白的、方格的……之中做出抉择；请朋友吃饭，要筹划师办家宴或去饭店，是吃中餐、西餐还是自助餐；假期旅游，是去风光绮丽的苏杭，还是去迷人的北戴河海滨，或是山水甲天下的桂林。
如果以为这些小事不必作为决策认真对待的话，那么当你面临报考学校、挑选专业，或者选择工作岗位的时候，就要慎重考虑、反复比较，尽可能做出满意的决策了。
从事决策的人也经常面对决策：一个厂长要决定购买哪种设备，上马什么产品；科技人员要选择研究课题；医生要为疑难病症确定治疗方案；经理要从若干应试者中挑选秘书；各地区各部门的官员要对人口、交通、经济、环境等领域的发展规划做出决策。
人们在处理上面这些决策问题的时候，要考虑的因素有多有少，有大有小，但是一个共同的特点是他们通常要涉及到经济、社会、人文等方面的因素。
在做比较、判断、评价、决策时，这些因素的重要性、影响力或者优先程度往往难以量化，人们的主观选择（当然要根据客观实际）会起到相当主要的作用，这就给用一般的数学方法解决问题带来本质上的困难。
T.L.Saaty等人在20世纪70年代提出一种能有效地处理这类问题的实际方法，称为层次分析法（Analystic Hierarchy Process,简记AHP），这是一种定性与定量相结合的、系统化、层次化的分析方法。
8.1.1层次分析方法的基本步骤层次分析法的基本思路与人对一个复杂的决策问题的思维、判断过程大体上是一样的。
数学建模案例分析第八章离散模型第八章"离散模型"主要介绍了离散数学在数学建模中的应用。
离散数学是指研究离散对象和离散结构的数学学科，与连续数学相对应。
在数学建模中，离散模型常用于描述离散化的问题，如网络优化、排队论、图论等。
本章讨论了三个离散模型的案例分析。
第一个案例是关于动态规划的问题。
动态规划是一种解决优化问题的动态模型，通过将问题划分为多个阶段，每个阶段可存在多个状态，根据转移方程进行状态转移和决策，最终得到最优解。
本案例中，讨论了一个旅行商问题（Traveling Salesman Problem，TSP），即如何找到一条路径，使得旅行商能够访问给定的一组城市且总路径最短。
通过动态规划的方法，可以列出状态转移方程，并利用递推关系计算最优解。
第二个案例是关于网络优化的问题。
网络优化是指在给定的网络结构上，通过合理的设计和调整网络的参数、算法等，以提高网络的性能和效率。
本案例中，以网络中的流最大问题（Maximum Flow Problem）为例，介绍了如何通过建立网络模型、定义网络容量等参数，以及应用最小割定理和残余网络的概念来解决流最大问题。
第三个案例是关于排队论的问题。
排队论是研究排队系统中等待时间、服务时间等性能指标的数学理论。
本案例中，以排队模型中的M/M/1排队系统为例，介绍了如何通过排队模型来估计顾客等待时间、系统繁忙程度等指标，并通过参数调整和优化来改善排队系统的性能。
以上三个案例分析都是基于离散模型的，通过合理的数学建模和求解方法，解决了实际问题中的离散化问题。
通过学习这些案例，我们可以更好地理解离散模型的应用和原理，并将其运用到实际问题中，提高问题求解的效率和准确性。
总结起来，离散模型在数学建模中扮演着重要的角色。
通过离散化的方式，将实际问题抽象成离散对象和结构，可以更好地进行问题求解和优化。
离散模型的应用领域广泛，涉及到网络优化、排队论、图论等多个领域，因此在实际问题中，我们需要根据具体情况选择合适的离散模型，并运用适当的数学建模和求解方法来解决问题。
第8章 离散模型
8.1 设n 阶矩阵A 为一致阵，证明A 具有下列性质： （1）A 的秩为1，唯一的非零特征根为n ；
（2）A 的任一列向量都是对应于n 的特征向量。
解：
（1） 由一致阵的定义，
ik
ij jk
a a a =，1,2,k n =，所以A 的任意两行成比例，对A 进行
初等行变换得B
B=111210000
0n a a a ⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦
，所以A 的秩为1。
由初等变换及初等矩阵的关系得，存在可逆阵P ，使得PA=B ，所以
11PAP BP --==1112100
000
0n c c c ⎡⎤⎢⎥⎢
⎥⎢⎥⎢
⎥⎣⎦
=C ，则A 与C 相似，便有相同的特征根。
易知C 的特征根为11c （一次根），0；由于对任意矩阵A 有12()n tr A λλλ+++=，
于是11c =n ，
所以A 的唯一非零特征值为n 。
（2） 对于A 的任一列向量[]12,,,T
k k nk a a a ，有：
[]12,,
,T k k nk A a a a =12111,,
,T
n n
n
j jk j jk nj jk j j j a a a a a a ===⎡
⎤⎢⎥⎣⎦∑∑∑=12111,,,T
n
n n
k k nk j j j a a a ===⎡⎤
⎢⎥⎣⎦
∑∑∑ =[]12,,,T
k k nk n a a a
所以，每一列均为对应于n 的特征向量。
8.2 若发现一成对比较矩阵A 的非一致性较为严重，应如何寻找引起非一致性的元素？例如，设已构造了成对比较矩阵
⎥⎥
⎥⎦
⎤
⎢⎢⎢⎣⎡=161316153511A
（1）对A 作一致性检验；
（2）若A 的非一致性较严重，应如何作修正。
解：（1）
对A 作一致性检验，算出A 的最大特征值，
A=[1 1/5 3;5 1 6;1/3 1/6 1]; a=max(eig(A)); CI=(a-3)/(3-1); RI=0.58; CR=CI/IR
解得CR=0.0810<0.1 （2）
根据一致阵的定义，一致阵满足ik kj ij a a a =，所以，应该对不满足这个条件的元素进行修正。
8.3 你已经去过几家主要的摩托车商店，基本确定将从三种车型中选购一种。
你选择的标准主要有：价格、耗油量大小、舒适程度和外表美观情况。
经反复思考比较，构造了它们之间的成对比较矩阵
⎥⎥⎥⎥⎦
⎤⎢⎢⎢
⎢⎣⎡=1315181315171551318731
A 三种车型（记为a ，b ，c ）关于价格、耗油量、舒适程度及你对它们表观喜欢程度的
成对比较矩阵为
（价格） （耗油量）
c b a c b
a
c b a ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡12112121321 c b a ⎥⎥⎥⎦
⎤
⎢⎢⎢⎣⎡17127152111
（舒适程度） （外表）
c b a c b a
c b a ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡141514131531 c b a ⎥⎥⎥⎦
⎤
⎢⎢⎢⎣⎡171317153511
（1）根据上述矩阵可以看出四项标准在你心目中的比重是不同的，请按由重到轻的顺
序将它们排出。
（2）哪辆车最便宜、哪辆车最省油、哪辆车最舒适，你认为哪辆车最漂亮？ （3）用层次分析法确定你对这三种车型的喜欢程度（用百分比表示）。
解：
(1) 根据矩阵A 的最大特征值对应的特征向量即为四项标准的比重。
Matlab 程序：
A=[1 3 7 8;1/3 1 5 5;1/7 1/5 1 3;1/8 1/5 1/3 1]; a=max(eig(A));
v=null(A-a*eye(size(A))); c=abs(v./norm(v,1))
解得c=[0.5820，0.2786，0.0899，0.0495]
所以，四项标准按由轻到重的顺序为价格、耗油量、舒适程度、外观 （2）根据价格、耗油量、舒适程度、外观的四个矩阵很容易得到结论。
显然,c 车最便宜，a 车最省油，a 车最舒适，b 车最漂亮
（3）先求出a,b,c 三车的各个标准之比，再根据各标准的比重算出三种车的比重，即为对三种车的喜欢程度之比。
Matlab 程序：
A1=[1 2 3;1/2 1 2;1/3 1/2 1]; A2=[1 1/5 1/2;5 1 7;2 1/7 1]; A3=[1 3 5;1/3 1 4;1/5 1/4 1]; A4=[1 1/5 3;5 1 7;1/3 1/7 1]; a1=max(eig(A1));
v1=null(A1-a1*eye(size(A1))); c1=abs(v1./norm(v1,1)); a2=max(eig(A2));
v2=null(A2-a2*eye(size(A2))); c2=abs(v2./norm(v2,1)); a3=max(eig(A3));
v3=null(A3-a3*eye(size(A3))); c3=abs(v3./norm(v3,1)); a4=max(eig(A4));
v4=null(A4-a4*eye(size(A4))); c4=abs(v4./norm(v4,1)); c=[c1 c2 c3 c4];
m=[0.5820,0.2786,0.0899,0.0495]'; t=c*m
解得t=[ 0.4092，0.4415，0.1493]
所以，对三种车的喜欢程度分别为40.92%，44.15%，14.93% 8.4 外出旅游选择交通工具（包括飞机、火车、汽车），由于不同人外出的目的不同，经济条件不同，体制、心理、经历、兴趣都不同，考虑到安全、舒适、快速、经济、游览等因素，问应如何选择交通工具。
解：
建立层次分析模型，用12345c c c c c ，，，，依次表示舒适、快速、安全、经济、游览
5个准则，构造成对比较矩阵
1
1/243
3217551/4
1/711/21/31/31/52111/3
1/5311A ⎡⎤
⎢⎥⎢⎥⎢⎥=⎢⎥
⎢⎥⎢⎥⎣⎦
由给出的成对比较矩阵可以算出，特征值=5.073λ，归一化特征向量
=.2.4T
ω（063,075,0.055,0.099,0.110）。
由 5.07350.018151
n CI n λ--===--，
查表可知 1.12RI =。
0.0180.0160.11.12
CI CR RI =
==<，一致性检验通过，上述ω可作为权向量。
用同样的方法构造第三层（方案层）对第二层的每一个准则的成对比较阵如下：
11251/2121/51/21B ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦ 21571/5121/71/21B ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦ 311/51/351231/21B ⎡⎤
⎢⎥=⎢⎥⎢⎥⎣⎦
41551/5111/511B ⎡⎤⎢⎥=⎢⎥
⎢⎥⎣⎦
511/21/5211/2521B ⎡⎤
⎢⎥=⎢⎥⎢⎥⎣⎦
由第三层的成对比较矩阵k B 计算出权向量(3)
k ω，最大特征根k λ和一致性指标k CI ，
结果列表如下：
从上表可以看出，上面的k CI 均可通过一致性检验。
故三种方案在目标层中的权重为T
)
2063.0,2604.0,553.50(=ω,由此看出，选择飞机比较理想。
8.6 右图是5位网球 选手循环赛的结果。
作为 竞赛图，它是双向连通的 吗？找出几条完全路径， 用适当方法排出5位选手 的名次。
解：
（1）对图中的任意两点，都存在两条路径，使得这两点可以相互连通，所以此图为双向连通的。
（2）完全路径：53124→→→→，51243→→→→,54312→→→→,52431→→→→等
（3）此竞赛图的邻接矩阵为：A=010********
0000001001
1110⎡⎤
⎢⎥⎢
⎥⎢⎥⎢⎥
⎢⎥⎢⎥⎣⎦
令[]1,1,1,1,1T
e =，各级得分向量为：
[]12,2,1,1,4T S Ae ==，[]213,2,2,1,6T S A S =⨯=，[]323,3,3,2,8T
S A S =⨯= []435,5,3,3,11T
S A S =⨯=，[]548,6,5,3,16T
S A S =⨯=
所以五位选手的名次为5，1，2，3，4。
