第八章离散模型解答.doc

萧澜 1 . 循环赛模型一、 问题：下图是5位网球选手循环赛的结果。作为竞赛图，它是双向连通的吗？找出几条完全路径，用适当的方法排出5位选手的名次。二、模型分析与建立：这是一个关于竞赛图排列名次的问题，我们可以利用双向连通竞赛的名次排序方法来处理这一问题。根据图形建立竞赛图的邻接矩阵A=（）如下： 由此得到邻接矩阵A=三、模型求解：各级分量为S=S(1)=(2,2,1,2,3),S(2)=(4,3,2,4,5),S(3)=(7,6,4,7,9),S(4)=(13,11,7,13,17).由此可以知道名次为：5，1（4），2，3（选手1和4名次相同）。另外此结果也可以根据Perron-Frobenius定理，由我们只需算出矩阵A的最大特征根和对应特征向量S得到大小排处名次。我们可以用Matlab求解，程序如下：A=0,1,0,1,0 0,0,1,1,0 1,0,0,0,0 1,1,1,0,0;eig(A) X,D=eig(A)从结果中可以看到A的最大特征根，所对应的特征向量为：由此得到排名顺序也是：5，1（4），2，3（选手1和4名次相同）。2投票权重 理事会有五个常任理事和十个非常任的理事，提案仅当全部的常任理事和至少非四个常任理事赞成时方可通过，求每位常任理事和每位非常任理事在投票中的权重？模型分析：由题意可知题中涉及到了利益的分配问题，那么此题可以应用Shapley值法进行求解Shapley值法所需要的知识：设集合I=1,2,n,如果对于I的任意一个子集s都对应着一个实值函数v(s),满足 v()=0; v()v()+v(), =称I,v为n人合作对策，v为对策的特征函数Shapley值由特征函数v来确定记为对于任意的子集s,记x(s)=,即s中成员的权重,对于一切s满足x(s)v(s)的x组成的集合称I,v的核心,当核心存在时,即所有s的分配都不小于s的效益,可以将Shapley值作为一种特定的分配,即;Shapley值为,i=1,2,n 其中是中包含的所有子集,s是子集s中的元素的数目(人数),是加权因子, s i表示s去掉i后的集合.模型建立:集合I=1,2,5,6,15,其中i=1,2,5表示常人理事会员,i=6,15为非常任理事会员,将集合s=()中任意的k个元素的集合,k=4,5,10的特征函数定义为1,I中的其他集合的特征函数的定义为0,因为这样的集合有个,且(k=4,5,10),所以任意一个常任理事的Shapley值为(即投票时占的比重)为代入数据可的=0.916,(i=1,2,5)而任意的非常任理事的权重为=(1-5*0.196)=0.002(i=6,15).Matlab语言程序:循环赛模型另解下图是5位网球选手循环赛的结果。作为竞赛图，它是双向连通的吗？找出几条完全路径，用适当的方法排出5位选手的名次。二、模型分析与建立：这是一个关于竞赛图排列名次的问题，我们可以利用双向连通竞赛的名次排序方法来处理这一问题。根据图形建立竞赛图的邻接矩阵A=（）如下： 由此得到邻接矩阵A=三、模型求解：各级分量为S=S(1)=(2,2,1,2,3),S(2)=(4,3,2,4,5),S(3)=(7,6,4,7,9),S(4)=(13,11,7,13,17).由此可以知道名次为：5，1（4），2，3（选手1和4名次相同）。另外此结果也可以根据Perron-Frobenius定理，由我们只需算出矩阵A的最大特征根和对应特征向量S得到大小排处名次。我们可以用Matlab求解，程序如下：A=0,1,0,1,0 0,0,1,1,0 1,0,0,0,0 1,1,1,0,0eig(A) X,D=eig(A)所得结果为:A = 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 1 1 0 0ans = 1.8393 -0.5000 + 1.3229i -0.5000 - 1.3229i -0.4196 + 0.6063i -0.4196 - 0.6063iX = Columns 1 through 3 0.4623 -0.4009 - 0.3536i -0.4009 + 0.3536i 0.3880 0.1336 - 0.3536i 0.1336 + 0.3536i 0.2514 -0.1336 + 0.3536i -0.1336 - 0.3536i 0.4623 0.5345 0.5345 0.5990 -0.1336 + 0.3536i -0.1336 - 0.3536i Columns 4 through 5 0.0657 - 0.3211i 0.0657 + 0.3211i 0.1014 + 0.4957i 0.1014 - 0.4957i -0.4088 + 0.1746i -0.4088 - 0.1746i 0.0657 - 0.3211i 0.0657 + 0.3211i 0.5759 0.5759 D = Columns 1 through 3 1.8393 0 0 0 -0.5000 + 1.3229i 0 0 0 -0.5000 - 1.3229i 0 0 0 0 0 0 Columns 4 through 5 0 0 0 0 0 0 -0.4196 + 0.6063i 0 0 -0.4196 - 0.6063i从结果中可以看到A的最大特征根，所对应的特征向量为：由此得到排名顺序也是：5，1（4），2，3（选手1和4名次相同）。 4题目： 某甲（农民）有一块土地，若从事农业生产可收入1万元；若将土地租给某乙（企业家）用与工业生产，可收入2万元；肉租给某丙（旅店老板）开发旅游也，可收入4万元；为促成最高收入的实现，试用Shapley值法分配个人的所得。2.基本假定和符号规定：设甲乙丙三人为，表示合作的最大效益，表示方程的收入，表示第方所作出的贡献，表示集合中任一中合作。3.问题分析与建立模型： 根据已知条件我们可以知道： ， 经过验证可以得到， 我们可以用Shspley值法来计算最大效益。Shspley值有特征函数确定，记做： ， 其中 ， ； 其中是中包含的所有子集，是子集中的元素数目（人数），是加权因子，表示去掉后的集合。4.模型求解： 首先计算：可知中包含1的子集为：1，1，2，1，3，1，2，3。 我们依次求出接着我们来求：可知中包含2的子集为：21，2、 1，2，3；21，21，2，30240130111231/31/61/301/61/3在将上述表格中的最后以行相加,得： 。最后在计算： 可知中包含3的子集为：3、1，3、1，2，3；31，31，2，30340120221231/31/61/301/32/3 由上述表格中可得： 。5.结果分析： 由上面的一系列表格我们知道, , , . 即： 为实现最大效益，甲应分得2.5万元、乙应分得0.5万元、丙应分得1万元。Shapley值法以严格的公理为基础，在处理合作对策的分配问题时具有公证、合理、等优点，但是它需要知道所有合作的获利，即要定义的所有子集（共个）的特征函数，这个实际上常常做不到。因此，在效益分配问题上，我们还有协商解、均衡解、最小距离解、满意解、Raiffa解。6题目：问题的提出：考察由野兔R和狐狸F组成的生态系统，在野兔的食物资源充足的情况下，其带符号的有向图如右所示。（1） 解释图中+,-号的意义。（2） 若初始时段野兔有一增量，且设V(0)=(10,10),计算V(1)和V(2).（3） 证明该系统对所有简单冲量过程都是冲量和值稳定的，从生态意义上进行解释。（4） 说明若用权描述二者的相互作用，则在某中加权的情况下系统不再稳定，并从生态意义上进行解释。答案如下：（1） 图中+号表示某时段野兔增加时，导致下一段它自身的增加和狐狸的增加（提供了事物）-号表示某个时段狐狸增加时，导致下一段它自身的减少和野兔的减少（被吃掉）。（2） 记R为V1,F为V2,则有向图的邻接矩阵为A=已知V(0)=(10,10) P(0)=(1,0),可以算出P(1)=(1,1),V(1)=(11,11),P(2)=(0,0),V(2)=(11,11).(3) A的特征根为0，所以冲量和值稳定，因为野兔（或狐狸）的增加导致双方的增加（或减少），而双方的增加（或减少）导致二者都不再变化。(4) 若二者的相互作用远大于内部作用，设加权有向图的邻接矩阵为W=,其中K1,K21,则W特征根的模大于系统不再稳定。较大的相互作用导致双方数量越来越大的变化。7题目：食肉动物、食草动物和草组成生态系统，因为草地有限，草过密会使草的生长减慢。用带符号的有向图建立这个系统的冲量过程模型，并证明冲量过程是不稳定的。建立模型与求解 如图所示， 邻接矩阵为 的特征多项式为 因为，所以有一根 ；又因为。故必存在模大于1的特征根，冲量过程不稳定。10.题目： 森林了在一定的时期会出现两种或两种以上的动物相互的吃对方的食物，这样就形成拉生态系统问题，现在有野兔R和狐狸F组成的生态系统，在野兔的食物充足的情况下，有下面的图表表示，生态系统的一些关系， + + FFFF R F （1）. 请你解释图中+，号的意义？(2). 如果在开始时段里野兔有增量，且设V（0）=（10，10），计算V（1），V（2）；(3). 证明该系统对所有简单冲量过程都是冲量和值稳定的，从生态意义上进行解释。（4） 说明如果用权来描述二者的相互作用，则在一种加权的情况下系统不再稳定，并从生态意义上进行解释；解:一 问题分析： 我们可以在图中看到有+，号的现象，从我们的日常中可以猜测是两种动物之间的数量的增加或减少，我们还看到有箭头的执行问题，那么这就应该是二者之间的影响，那么到底又是如何来影响的呢/。下面我们进一步的说明：（1） 在上面的图中我们看到的+号是代表野兔在这个生态系统中的数量是在增加的，同样号是代表狐狸在这个生态系统中的减少情况。（2） 如果在题目的假设我们知道，在这个生态的开始时期，野兔是有 所增加的，并且设他的初始值是V（0）=（10，10）；对应的建立模型来求解问题；（3） 在前两个的基础上，进行比较检验冲量和值的稳定性，通过达尔文的优胜劣汰的原则。我们知道在两个动物之间的竞争中有一部分比较优秀的动物就会留下来，而那些身体素质不好，就会是其他动物的捕捉对象，在这个生态系统中就是说野兔的实物和它本身都可能是狐狸 的食物，当有的野兔的能力不够时，跑得不够快，长得不够强壮时 他会是被淘汰的对象，这是合乎生态原则的。（4） 如果用权来描述这个问题时，就会是一个的权在增加的同时其它的就会下降，使得整体的权是一致的。从生态的角度我们知道这也是把一群动物的简单集合，组成拉一个整体，同时又把一个整体分成一个个的小的部分的组合，每个小的部分都在这整体中有一定的比例，但是由于这是一个动态的组合，在一定的短时期里就会出现系统的不稳定，当时经过一定的时间后又会恢复稳定的状态的。二 模型假设与求解： 对于第二个问题我们知道假设给它一个初始值V（0）=（10，10），接下来在求得V（1），V（2）；同样我们知道P（0）=（1，0），再计算出P（1），P（2）；：由题目我们可以做出有邻接矩正，得到V（0）=（10。10），P（0）=（1。0）时的结果是：V（1）=（11，11）。V（2）=（11，11）。P（1）=（1，1）。P（2）=（0，0） 。三 结果分析： 在上面的图中我们看到的+号是代表野兔在这个生态系统中的数量是在增加的号是代表狐狸在这个生态系统中的减少情况。如果在题目的假设我们知道，在这个生态的开始时期，野兔是有 所增加的，并且设他的初始值是V（0）=（10，10）；对应的建立模型来求解问题；在前两个的基础上，进行比较检验冲量和值的稳定性，通过达尔文的优胜劣汰的原则。我们知道在两个动物之间的竞争中有一部分比较优秀的动物就会留下来，而那些身体素质不好，就会是其他动物的捕捉对象，在这个生态系统中就是说野兔的实物和它本身都可能是狐狸 的食物，当有的野兔的能力不够时，跑得不够快，长得不够强壮时 他会是被淘汰的对象，这是合乎生态原则的。如果用权来描述这个问题时，就会是一个的权在增加的同时其它的就会下降，使得整体的权是一致的。从生态的角度我们知道这也是把一群动物的简单集合，组成拉一个整体，同时又把一个整体分成一个个的小的部分的组合，每个小的部分都在这整体中有一定的比例，但是由于这是一个动态的组合，在一定的短时期里就会出现系统的不稳定，当时经过一定的时间后又会恢复稳定的状态的。15题目 ：常任理事权重模型的数学解理事会有五个常任理事和十个非常任的理事，提案仅当全部的常任理事和至少非四个常任理事赞成时方可通过，求每位常任理事和每位非常任理事在投票中的权重？模型分析：由题意可知题中涉及到了利益的分配问题，那么此题可以应用Shapley值法进行求解Shapley值法所需要的知识：设集合I=1,2,n,如果对于I的任意一个子集s都对应着一个实值函数v(s),满足 v()=0; v()v()+v(), =称I,v为n人合作对策，v为对策的特征函数Shapley值由特征函数v来确定记为对于任意的子集s,记x(s)=,即s中成员的权重,对于一切s满足x(s)v(s)的x组成的集合称I,v的核心,当核心存在时,即所有s的分配都不小于s的效益,可以将Shapley值作为一种特定的分配,即;Shapley值为,i=1,2,n 其中是中包含的所有子集,s是子集s中的元素的数目(人数),是加权因子, s i表示s去掉i后的集合.模型建立:集合I=1,2,5,6,15,其中i=1,2,5表示常人理事会员,i=6,15为非常任理事会员,将集合s=()中任意的k个元素的集合,k=4,5,10的特征函数定义为1,I中的其他集合的特征函数的定义为0,因为这样的集合有个,且(k=4,5,10),所以任意一个常任理事的Shapley值为(即投票时占的比重)为代入数据可的=0.916,(i=1,2,5)而任意的非常任理事的权重为=(1-5*0.196)=0.002(i=6,15).16题目：排名次的另一方法是考察“失分向量”以代替得分向量（选手输掉场次的数目为他的失分），按失分由小到大排列名次，用失分向量方法对竞赛图排列名次，结果与用得分方法排列相同吗？一、 模型准备：1. 失分方法相当于把竞赛图中各有向边反向，按得分向量排列名次，再把名次倒过来。2. 得分方法的邻接矩阵为 其中A=(a)如下 ：当a=1，存在从顶点到的有向边，当a=0，不存在从顶点到的有向边。 得其最大特征根为1.4,其对应特征向量为P=(0.323,0.280,0.167,0.230)二、 模型建立与求解：将图的有向边反向后得其邻接矩阵如下：若记顶点的失分向量为P=(p1,p2,p3,p4),其中pi是顶点i的失分，则P=BII=(1,1,1,1).记P=P,称为一级失分向量，进一步计算的得到失分向量:P=(1,1,2,2) P=(2,1,2,3) P=(3,2,3,3)P=(3,3,5,5) P=(5,3,6,8) 按失分由小到大排列名次为：2,1,3,4B的最大特征值为：=1.4,