清华大学：《数学建模》课程教学资源（讲义）离散模型（冲量过程建模，姜启源）

离散模型之三——冲量过程建模 例能源利用系统的预测 v1能源利用量;2能源价格; 3能源生产率;4环境质量;v v—工业产值;6就业机会; —人口总数。 系统的元素图的顶点 带符号的有向图 元素间的影响带方向的弧 影响的正反面弧旁的+、一号 影响直接影响符号客观规律;方针政策 V顶点集 带符号有向图G1=(V,E)的邻接矩阵A 1,若vv为+ 弧集 a,={-1,若vv为 0,若vv,∈E 0-11-1000 -1000000 0-100100 带符号的有向图G1 A=0000001 1000010 0000001 某时段v的增加导致 1000000下时段y的增加减少 定性模型 1

      

           x         

     
L M L M L M LM 

               
           

   
      

 
 
      


               x            L M L M  

加权有向图G,及其邻接矩阵W wii. 某时段v的增加1单位导致 下时段v的增加w:单位 0-0.50.8-1.2000 07000000加权有向图G 0 20 0 0000.3 1.2 001.50 0 00000 1.5 定量模型 冲量过程( Pulse Process) 研究由某元素ν变化引起的系统的演变过程 ()~v在时段的值;p()~v在时段的改变量(冲量) v(t+1)=v()+P(+1),i=1,2,…,n,t=0,2, p,(t+1) ∑ P(),j=12,…,n,t=0,1,2, P(+1)=2aP( +1)=v(t)+p(t+1) v()=(v(),2(),…,v(O),p(t+1)=p(t)W p(O)=(P(),P2(,…P(O)A视为W的特例

     
            

    
           
           
      




      x         
  L M LM L  
  L  L  
  
 
   
 
     Q L M LM L       
  
 
  
 
                               Q Q

   
     
             
        Q L M LM L    
  

能源利用系统的预测 v(+1)=w()+p(+1) 简单冲量过程初始冲量0中p(+1)=p()4 1个分量为1,其余为0的冲量过程设v(0)=p(0) 若开始时能源利用量有突然增加,预测系统的演变 能源利用系统的p()和v(,t=0,1, tP:P2P3P4P,P。P,‖vv2vV.v,VV 1000000 0-11-1000‖1 1000 1-10010-1 1110-1 3111-10103-3 211-1 简单冲量过程S的稳定性 任意时段S的各元素的值和冲量是否为有限(稳定) S不稳定时如何改变可以控制的关系使之变为稳定」 P(t+1=p(t)w +1)=()+p(t+1) S冲量稳定对任意t1|pO)界值稳定 S值稳定~对任意,,v(1)有界冲量稳定 ()=p(0)′口S的稳定性取决于W的特征根 记矿的非零特征根为入

    

              
 
     
      


  



  

 
 



 





   










     
     
  
                       
    
   
 W       

简单冲量过程S的稳定性 ·S冲量稳定→1|≤1 s冲量稳定分|≤1且均为单根 ·s值稳定S冲量稳定且λ1 对于能源利用系统的邻接矩阵A」特征多项式 0-11 f(入)=2(3-2-2 -000.0|f()=-2/(2)=76日3∈0L 能源利用系统存在冲量 000000 不稳定的简单冲量过程 简单冲量过程的稳定性 改进的玫瑰形图S*~带符号的 有向图双向连通,且存在一个 : 位于所有回路上的中心顶点。 回路长度~构成回路的边数 回路符号~构成回路的有向边符号(+1,-1)之积 ac长度为的回路符号和]r使90的最大整数 S冲量稳定→an=±1,a=(k=12…+-1) 若S冲量稳定,则S值稳定∑a4≠1

  
            
» » » » » » » » » ¼ º « « « « « « « « « ¬ ª                                                      $    
              
        

              x          

   
  
   
  
 U  
 N U UN
     
U N  N

简单冲量过程S的稳定性 a1=0,a2=(-1)12×(-1)21=1 a3=(+1)135y1+(-1)141 +(+1)y132v1=1,a4=0,a5=1,=5 s冲量稳定→an=±1,a=-·a(k=12…y-1 a3≠-a,·a2口s冲量不稳定=能量 (1)12→(+1)12(由鼓励利用变为限制利用)→a2=1 日A的特征多项式f(4)=2(2+x2-2-1) A=0,01,+;(-1√3)/2s冲量稳定 11且为单根·s冲量稳定心风|≤1且均为单根 S冲量稳定→a=±1,a1=a·a(k=12…y-1) 若S冲量稳定,则S值稳定台∑a4≠ {a1,a2,a3,a4,a53}={0,-1,1,0,1} 口s值不稳定 S*值 l2, 稳定 35 中(+1)3s-(1)3s y能源生产率口(1)3违反客观规律 能源利用系统的值不应稳定?

            x        
 

 


 









 
   
   
  
 U  
 N U UN
      



  
  !  
     






 
  "      

                     x             
U N  N $     # $


#         
   
  
 U  
 N U UN
  

        
   



离散模型之四——循环赛排名 n支球队循环赛,每场比 赛只计胜负,没有平局。6 根据全部比赛结果排出 各队名次 依箭头方向通过全部顶点的路径6支球队循环赛结果 312456146325无法排名 计算得分:1队胜4场,2,3队各胜2,3队,4,5 3场,4,5队各胜2场,6队胜1场 队无法排名 循环比赛的结果——竞赛图 每对顶点间都有边相连的有向图 3个顶点 的竞赛图 名次{1,2,3 (1,2,3)} 4个顶点 的竞赛图 人A△ 名次{1,2,4)已2(134)134,2)[(1234



 % 
    

 
    
  
 
 
  
  
  
  

 $
# $
 # $
 # $ 
# $
 #  $
 #

·具有唯一的完全路径,如(1) 竞赛图.双向连通图任一对顶点存在两条有 的3种 形式 向路径相互连通,如(4); 其他,如(2),(3)。 竞赛图 必存在完全路径 的性质·若存在唯一的完全路径,则由它确定的顶 点顺序与按得分排列的顺序一致,如(1)。 双向连通竞赛图G=(V,E)的名次排序 1.yw.∈E 邻接矩阵a 0 EE 得分向量s=(s1,s2,…,s) 11 S=Ae,e=(1,1,…,1) A 00 0 s"=Ae=(2,2,1)~1级得分向量1000 s2)=As"=(3,2,2)~2级得分向量 s3)=(3,3,2,3),s=(5,5,3,3), Ask-=Ak s”=(8,6,3,5),s(=(9,8,5,8) s=(13389),(3=(2.179,13),k→∞,s→?


 
 
    
     
         
 7       



   

 
 7





   7


      
               
  
       L M L M LM   
 
 7 Q    
 
  
         
              7 7 7 7 7 7







N N N

         N 

双向连通竞赛图的名次排序s=As=Ae 对于n(>3)个顶点的双向连通竞赛图,存在 正整数r,使邻接矩阵A满足A∞>0,A称素阵 素阵A的最大特征根为正单 e lin 根λ,对应正特征向量s,且02 k→∞,“(一化局→S日用排非序 λ=1.4, s=(0.323,0.280,0.167,0.230) 0001 名次排序为{1,2,4,3} 6支球队循环赛结果 010111 000111 010100 A 000011 001001 00 000 s=(4,3,3,2,2,1),s2)=(8,5,9,3,4,3) s3)=(15,10,16,7,12,9),s+=(38,28,32,21,25,16) A=2.232,S=(0.238,0.164,0.231,0.113,0.150,0.104) 名次排序为{,3,2,5,4,6}

 



N N N
o f
 
 

N N N

          
               
      N   7 


  


          
                                   
7 7 7 7  
  



  

              




   7






 
      

离散模型之五——合作对策 例甲乙丙三人合作经商,若甲乙合作获利7元, 甲丙合作获利5元,乙丙合作获利4元, 三人合作获利11元。又知每人单干获利1元。 问三人合作时如何分配获利? 记甲乙丙三人分配为x=(x,x,x) x+x2+x3=11 解不唯 x1+x3≥5 (4,4,3) x+x≥4 x,x2,x3≥1 1) Shapley合作对策 集合1=1,2,…,n}好子集s∈,彐实函数vs)满足 v(s1∪s2)≥v(s1)+v(s2),s1∪s2= v(s)~子集 [,v~n人合作对策,v特征函数 s的获利 x=(x1,x2,…,xn)n人从得到的分配,满足 ∑x=v(1) x1≥v(i),i=1,2,…,n

     
                             
     
     Q L  L
L   


   

                


                  Q

  

l) Shapley合作对策 公理化方法 Shapley值 t ∑v(s)v(s)-v(sii=1 (n-s)(s-1)! n! s-子集s中的元素数目,S~包含的所有子集 v(s)-vs\i)对合作s的“贡献”」 v(s)~由s决定的“贡献”的权重 三人(=(123)经商中甲的分配x1的计算 1∪3 I v(s) 11 v(s\1) 0 4 v(s)-w(s1) 2 1/3 1/6 1/6 /3 (v(s)-v(s1)1/3 2/3 7/3 x1=13/3 x2=23/6,x2=17/6

          
      6L V L
       


                   
              
      

 
 !
!
 !