图论与网络模型(四)

图论与网络模型

及其应用(五)——冲量模型本节我们用一个能源利用系统的例子说明冲量过程的建模方法.我们考察某地区的能源利用状况.先界定系统的范围,比如只考虑能源利用量、价格、生产率、环境质量、工业产值、就业机会及人口总数等7个因素，它们之间相互复杂的关系可以简化为一个因素对另外因素直接的促进(正面)或促退(负面)作用。要研究的问题是,当其中某个因素突然发生改变时,预测系统各因素的演变过程和趋势.定性模型V1---能源利用量V2---能源价格V3---能源生产率V4---环境质量V5---工业产值V6---就业机会V7---人口总数v3•••••••v2v5v6v7v4v1++++++-+---G1我们将能源利用系统的每个因素用图的一个顶点来表示,因素间的直接影响用带方向的边表示.为了表示因素间的影响是促进还是促退,我们在箭头旁边分别标示“+”或“-”.这样,我们便得到了一个带符号的有向图G1.需说明的是:第一,两顶点之间的有向边表示两因素间的直接影响,如v1v3带正号表示某时段能源利用量v1的增加导致下一时段能源生产率的增长,v1v4带符号则表示v1的增加导致下一时段环境质量的下降.至于因素间的间接影响是由几条相连的同向边反映出来.

第二,像能源利用这样的社会经济系统,因素间的影响关系十分复杂,应该合理、简化地确定哪些因素间有直接影响,这里除了主要根据客观规律作出决定外,方针政策有时也是判断的依据.如能源利用量增加时能源价格是降低还是升高,是由政府鼓励利用能源还是限制能源利用的价格政策决定的.定义邻接矩阵A=(aij)如下:于是v3•••••••v2v5v6v7v4v1++++++-+---定量模型v3•••••••v2v5v6v7v4v111-2-0.51.21.50.30.81.5-0.7-1.2G2这里能源利用量v1和生产率v3均以变化10%为一个单位,如图,v1增加1个单位将引起v30.8个单位的增长.边上的权我们用wij表示.刚才的有向图G1以及矩阵A是定性模型,如果将系统各因素加以量化,那么我们便得到定量模型,我们用加权的有向图表示.如:这样我们便得到图G2的邻接矩阵为v3•••••••v2v5v6v7v4v111-2-0.51.21.50.30.81.5-0.7-1.2V1出发的边冲量过程为了研究系统的某个因素一个突然变化所引起的整个系统在其后各时段的演变过程,用vi(t)表示因素vi在时段t的值(我们这里实际上是将时间离散化处理),pi(t)表示在时段t的改变量(冲量).设系统共有n个因素,根据wij的含义,对t=0,1,2,…,有如果只考虑系统在初始状态基础上的变化,不妨设V(0)=P(0)于是我们便可以计算出P(t)和V(t)(以A为例):tp1p2p3p4p5p6p7v1v2v3v4v5v6v701000000100000010-11-10001-11-100021-10010-12-21-110031-11-10103-32-211-1……………这种由某些因素在初始时段的变化(冲量)引起的系统的演变过程成为冲量过程.当初始冲量P(0)中只有一个分量是1,其余为0时,成为简单冲量过程,记为S.一般的冲量过程可以看成若干个简单冲量过程的叠加.简单冲量过程的稳定性如果系统的任一因素在t=0的变化,引起的各因素在任意时段的冲量和值都不会无限增长或无限减少,那么这个系统的冲量过程S是稳定的.对于所有的i和任意的t,若|Pi(t)|有界,称S是冲量稳定的;若|vi(t)|有界,称S是值稳定的.若S是值稳定的,则必然是冲量稳定的.反之不然.定理1S是冲量稳定的必要条件是|λ|≤1.这里λ是W的非零特征值.下同.特别,当只取数值0,1,-1时,条件化为|λ|=1.必要条件不满足时必然有某个简单冲量过程,其冲量不稳定.定理2S是冲量稳定的充分条件是|λ|≤1且均为单根.定理3S是值稳定的充要条件S是冲量稳定且λ≠1.我们用上述定理检查有向图G1表示的能源利用系统.矩阵A的特征多项式为因为f(1)=-2,f(2)=76,所以f(λ)在(1,2)内有根.由定理1,必有某个简单冲量过程是不稳定的.不稳定过程的调节方法我们改变W或A的值,使得其特征值满足定理2,3的要求.不过,没有统一的方法.如果一个带符号的有向图是双向连通的(即任何两个顶点间存在两条有向路径,使得此两顶点可以互相连通),并存在一个位于所有闭路的中心顶点,那么称它是改进的玫瑰图.所谓闭路,是指从某顶点出发,沿有向边前进回到该顶点,且途中不经过重复顶点的路径.以图G1为例,它就满足这个要求,v1是中心顶点.由v1v3,

v3v5,

v5v1构成的闭路记做v1v3v5v1.闭路有v1v2v1,v1v3v2v1,v1v3v5v1,v1v4v7v1,

v1v3v5v6v7v1.构成闭路的有向边的数目称为闭路的长度.当闭路包含奇数个带-的有向边时,定义该闭路的符号为-1,否则为+1.用ak记长度为k的闭路的符号和(不存在长度为k的闭路时ak为0),设r是使得ar≠0的最大整数.我们记用改进的玫瑰图描述的冲量过程为S*.于是,存在一个序列{a1,

a2,…,

ar},S*的稳定性完全由这个序列决定.定理4S*冲量稳定的必要条件是ar

=1或-1且

ak

=

-ar

ar-k,k=1,2,…,r-1.定理5若S*冲量稳定的,则S*是值稳定的充要条件是下面我们根据定理4,5来调整邻接矩阵A的某些元素.先检查定理4的必要条件.在图G1中,没有长度为1的闭路,于是a1=0;再看有v1v2v1,由于两边都是符号,故a2=1;有三条长度为3的闭路,v1v3v2v1,v1v3v5v1,v1v4v7v1,

符号分别是+1,+1,-1,故a3=1;a4=0;只有一条长度为5的闭路v1v3v5v6v7v1,其符号为+1,故a5=1;ak=0,k>5.故r=5.这样我们得到序列{a1,a2,a3,a4,a5}={0,1,1,0,1}.用定理4的必要条件检查发现,条件a2=-a5a3以及a3=-a5a2不成立.由此可见,为了满足冲量稳定的必要条件,需将中的一个从1改成-1.由图可知,我们将v1v2的符号从-改成+时,a2=1,而a3,a5不变.此时{a1,a2,a3,a4,a5}={0,-1,1,0,1}.还有其他调整方法.这个改动的实际含义是,将原来的“能源利用量的增加引起价格下降”,调整为“能源利用量的增加导致价格上升”,即从鼓励能源的利用调整为限制利用.这种价格政策的变得一般属于人们可以控制的范围.当v1v2的符号从-改成+后,新的邻接矩阵为由定理2,此时S*是冲量稳定的.即能源利用系统的任何一个因素突然变化时,各因素在以后各个时段的改变量时有限的.若进一步判断S*是否值稳定.由于此时a1+a2+a3+a4+a5=1,不满足定理5的充要条件.要想定理4成立的情况下定理5也成立,需将a3,a5改成1.这要求将长度为3的一条闭路和长度为5的闭路的公共边改变符号.只能将v3v5由+改成-(将v7v1由+改成-会导致a3=3).而这两种情形都是不可能实现的,前者原意为“能源生产率的增加导致工业产值增加”,后