图论与网络模型及其应用 (五 )
—— 冲量模型本节我们用一个能源利用系统的例子说明 冲量过程 的建模方法,
我们考察某地区的能源利用状况,先界定系统的范围,比如只考虑能源利用量、价格、生产率、环境质量、工业产值、就业机会及人口总数等 7个因素，它们之间相互复杂的关系可以简化为一个因素对另外因素直接的促进 (正面 )或促退 (负面 )作用。要研究的问题是,当其中某个因素突然发生改变时,预测系统各因素的演变过程和趋势,
定性模型
V1---能源利用量
V2---能源价格
V3---能源生产率
V4---环境质量
V5---工业产值
V6---就业机会
V7---人口总数
v3
v2
v5 v6
v7
v4
v1
+
+
++
+
+-
+
- --
G1
我们将能源利用系统的 每个因素用图的一个顶点来表示,因素间的直接影响用带方向的边表示,为了表示因素间的影响是促进还是促退,我们在箭头旁边分别标示,+”或,-”.这样,我们便得到了一个带符号的有向图 G1.
需说明的是,第一,两顶点之间的有向边表示两因素间的直接影响,如 v1v3带正号表示某时段能源利用量 v1的增加导致下一时段能源生产率的增长,v1v4带符号则表示 v1的增加导致下一时段环境质量的下降,至于因素间的间接影响是由几条相连的同向边反映出来,
第二,像能源利用这样的社会经济系统,
因素间的影响关系十分复杂,应该合理、简化地确定哪些因素间有直接影响,这里除了主要根据客观规律作出决定外,方针政策有时也是判断的依据,如能源利用量增加时能源价格是降低还是升高,是由政府鼓励利用能源还是限制能源利用的价格政策决定的,
定义邻接矩阵 A=(aij)如下,
vv
vv
vv
a
ji
ji
ji
ij
若不存在边为负若为正若
0,
1,-
,1
于是
0000001
1000000
0100001
1000000
0010010
0000001
0001110
A
v3
v2
v5 v6
v7
v4
v1
+
+
++
+
+-
+
- --
定量模型
v3
v2
v5 v6
v7
v4
v1
1 1
-2
-0.5
1.2
1.5
0.3
0.8 1.5
-0.7
-1.2
G2
这里能源利用量 v1
和生产率 v3均以变化 10%为一个单位,
如图,v1增加 1个单位将引起 v30.8个单位的增长,边上的权我们用 wij表示,
刚才的有向图 G1以及矩阵 A是定性模型,如果将系统各因素加以量化,那么我们便得到定量模型,我们用加权的有向图表示,如,
这样我们便得到图 G2的邻接矩阵为
0000005.1
1000000
05.100002.1
3.0000000
0010020
0000007.0
0002.18.05.00
W
v3
v2
v5 v6
v7
v4
v1
1 1
-2
-0.5
1.2
1.5
0.3
0.8 1.5
-0.7
-1.2
V1出发的边冲量过程为了研究系统的某个因素一个突然变化所引起的整个系统在其后各时段的演变过程,用 vi(t)表示因素 vi在时段 t的值 (我们这里实际上是将时间离散化处理 ),pi(t)
表示在时段 t的改变量 (冲量 ).设系统共有 n个因素,根据
wij的含义,对 t=0,1,2,…,有
,,,2,1),()1(
,,,2,1),1()()1(
1
njtpwtp
nitptvtv
n
i
iijj
iii
.W)0(P)(P,.,2,1,0,W)t(P)1t(P
),1t(P)(V)1(V
)),(,),(()()),(,),(()(V
11
t
tt
tt
tptptPtvtvt
nn
由此为上面两式可用矩阵表示则我们记
如果只考虑系统在初始状态基础上的变化,不妨设
V(0)=P(0)
于是我们便可以计算出 P(t)和 V(t)(以 A为例 ):
t p1 p2 p3 p4 p5 p6 p7 v1 v2 v3 v4 v5 v6 v7
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
1 0 -1 1 -1 0 0 0 1 -1 1 -1 0 0 0
2 1 -1 0 0 1 0 -1 2 -2 1 -1 1 0 0
3 1 -1 1 -1 0 1 0 3 -3 2 -2 1 1 -1
… … … … …
这种由某些因素在初始时段的变化 (冲量 )引起的系统的演变过程成为冲量过程,当初始冲量 P(0)中只有一个分量是 1,其余为 0时,成为简单冲量过程,记为 S.一般的冲量过程可以看成若干个简单冲量过程的叠加,
简单冲量过程的稳定性如果系统的任一因素在 t=0的变化,引起的各因素在任意时段的冲量和值都不会无限增长或无限减少,那么这个系统的冲量过程
S是稳定的,
对于所有的 i和任意的 t,若 |Pi(t)|有界,称 S是冲量稳定的 ;若 |vi(t)|有界,称 S是值稳定的,
若 S是值稳定的,则必然是冲量稳定的,反之不然,
定理 1 S是冲量稳定的必要条件是 |λ|≤1.
这里 λ是 W的非零特征值,下同,
特别,当只取数值 0,1,-1时,条件化为 |λ|=1.必要条件不满足时必然有某个简单冲量过程,其冲量不稳定,
定理 2 S是冲量稳定的充分条件是 |λ|≤1且均为单根,
定理 3 S是值稳定的充要条件 S是冲量稳定且 λ≠1.
我们用上述定理检查有向图 G1表示的能源利用系统,矩阵 A的特征多项式为
).1()( 352f
因为 f(1)=-2,f(2)=76,所以 f(λ)在 (1,2)内有根,由定理 1,必有某个简单冲量过程是不稳定的,
不稳定过程的调节方法我们改变 W或 A的值,使得其特征值满足定理
2,3的要求,不过,没有统一的方法,
如果一个带符号的有向图是双向连通的 (即任何两个顶点间存在两条有向路径,使得此两顶点可以互相连通 ),并存在一个位于所有闭路的 中心顶点,那么称它是 改进的玫瑰图,所谓 闭路,是指从某顶点出发,沿有向边前进回到该顶点,且途中不经过重复顶点的路径,以图 G1为例,它就满足这个要求,v1是中心顶点,由
v1 v3,v3 v5,v5v1构成的闭路记做 v1 v3 v5v1.闭路有 v1
v2v1,v1 v3 v2v1,v1 v3 v5v1,v1 v4 v7v1,v1 v3 v5 v6 v7v1,
构成闭路的有向边的数目称为闭路的长度,
当闭路包含奇数个带 -的有向边时,定义该 闭路的符号 为 -1,否则为 +1.
用 ak记长度为 k的闭路的符号和 (不存在长度为
k的闭路时 ak为 0),设 r是使得 ar≠0的最大整数,
我们记 用改进的玫瑰图描述的冲量过程为 S*.
于是,存在一个序列 {a1,a2,…,ar},S*的稳定性完全由这个序列决定,
定理 4 S*冲量稳定的必要条件是 ar =1或 -1 且
ak = -ar ar-k,k=1,2,…,r-1.
定理 5 若 S*冲量稳定的,则 S*是值稳定的充要条件是
.1
1
r
k
ka
下面我们根据定理 4,5来调整邻接矩阵 A的某些元素,
先检查定理 4的必要条件,在图 G1中,没有长度为 1
的闭路,于是 a1=0;再看有 v1 v2v1,由于两边都是符号,故 a2=1;有三条长度为 3的闭路,v1 v3 v2v1,v1 v3
v5v1,v1 v4 v7v1,符号分别是 +1,+1,-1,故 a3=1; a4=0;
只有一条长度为 5的闭路 v1 v3 v5 v6 v7v1,其符号为
+1,故 a5=1; ak=0,k>5.故 r=5.
这样我们得到序列 {a1,a2,a3,a4,a5}={0,1,1,0,1}.
用定理 4的必要条件检查发现,条件 a2=- a5 a3
以及 a3=- a5 a2不成立,
由此可见,为了满足冲量稳定的必要条件,需将中的一个从 1改成 -1.由图可知,我们将 v1 v2的符号从 -改成 +时,a2=1,而 a3,a5不变,此时 {a1,a2,
a3,a4,a5}={0,-1,1,0,1}.还有其他调整方法,
这个改动的实际含义是,将原来的“能源利用量的增加引起价格下降”,调整为“能源利用量的增加导致价格上升”,即从鼓励能源的利用调整为限制利用,这种价格政策的变得一般属于人们可以控制的范围,
当 v1 v2的符号从 -改成 +后,新的邻接矩阵为
).1)(1)(1(
)1()(
222
352
f
由定理 2,此时 S*是冲量稳定的,即能源利用系统的任何一个因素突然变化时,各因素在以后各个时段的改变量时有限的,
若进一步判断 S*是否值稳定,由于此时 a1+a2+
a3+ a4 +a5 =1,不满足定理 5的充要条件,要想定理 4成立的情况下定理 5也成立,需将 a3,a5改成 1.
这要求将长度为 3的一条闭路和长度为 5的闭路
.2/)3i(1,2/)3i( - 1i,- i,0,0,1,于是特征值为的公共边改变符号,只能将 v3 v5由 +改成 -(将
v7v1由 +改成 -会导致 a3=3).而这两种情形都是不可能实现的,前者原意为“能源生产率的增加导致工业产值增加”,后者原意为“人口总数的增加会引起能源利用量的增加”,
如果不要求改公共边,比如将 v5v1由 +改成 -或将 v3v2由 -改成 +,同时将 v5v6或 v6v7由 +改成 -.
这些变动都似乎不可能,
需注意的是,我们在此讨论这个问题时,是事先界定了系统的范围,即不考虑系统外的因素的影响,另外,各个因素间的关系也往往很复杂,在研究问题时必要的简化也是必须的,
—— 冲量模型本节我们用一个能源利用系统的例子说明 冲量过程 的建模方法,
我们考察某地区的能源利用状况,先界定系统的范围,比如只考虑能源利用量、价格、生产率、环境质量、工业产值、就业机会及人口总数等 7个因素，它们之间相互复杂的关系可以简化为一个因素对另外因素直接的促进 (正面 )或促退 (负面 )作用。要研究的问题是,当其中某个因素突然发生改变时,预测系统各因素的演变过程和趋势,
定性模型
V1---能源利用量
V2---能源价格
V3---能源生产率
V4---环境质量
V5---工业产值
V6---就业机会
V7---人口总数
v3
v2
v5 v6
v7
v4
v1
+
+
++
+
+-
+
- --
G1
我们将能源利用系统的 每个因素用图的一个顶点来表示,因素间的直接影响用带方向的边表示,为了表示因素间的影响是促进还是促退,我们在箭头旁边分别标示,+”或,-”.这样,我们便得到了一个带符号的有向图 G1.
需说明的是,第一,两顶点之间的有向边表示两因素间的直接影响,如 v1v3带正号表示某时段能源利用量 v1的增加导致下一时段能源生产率的增长,v1v4带符号则表示 v1的增加导致下一时段环境质量的下降,至于因素间的间接影响是由几条相连的同向边反映出来,
第二,像能源利用这样的社会经济系统,
因素间的影响关系十分复杂,应该合理、简化地确定哪些因素间有直接影响,这里除了主要根据客观规律作出决定外,方针政策有时也是判断的依据,如能源利用量增加时能源价格是降低还是升高,是由政府鼓励利用能源还是限制能源利用的价格政策决定的,
定义邻接矩阵 A=(aij)如下,
vv
vv
vv
a
ji
ji
ji
ij
若不存在边为负若为正若
0,
1,-
,1
于是
0000001
1000000
0100001
1000000
0010010
0000001
0001110
A
v3
v2
v5 v6
v7
v4
v1
+
+
++
+
+-
+
- --
定量模型
v3
v2
v5 v6
v7
v4
v1
1 1
-2
-0.5
1.2
1.5
0.3
0.8 1.5
-0.7
-1.2
G2
这里能源利用量 v1
和生产率 v3均以变化 10%为一个单位,
如图,v1增加 1个单位将引起 v30.8个单位的增长,边上的权我们用 wij表示,
刚才的有向图 G1以及矩阵 A是定性模型,如果将系统各因素加以量化,那么我们便得到定量模型,我们用加权的有向图表示,如,
这样我们便得到图 G2的邻接矩阵为
0000005.1
1000000
05.100002.1
3.0000000
0010020
0000007.0
0002.18.05.00
W
v3
v2
v5 v6
v7
v4
v1
1 1
-2
-0.5
1.2
1.5
0.3
0.8 1.5
-0.7
-1.2
V1出发的边冲量过程为了研究系统的某个因素一个突然变化所引起的整个系统在其后各时段的演变过程,用 vi(t)表示因素 vi在时段 t的值 (我们这里实际上是将时间离散化处理 ),pi(t)
表示在时段 t的改变量 (冲量 ).设系统共有 n个因素,根据
wij的含义,对 t=0,1,2,…,有
,,,2,1),()1(
,,,2,1),1()()1(
1
njtpwtp
nitptvtv
n
i
iijj
iii
.W)0(P)(P,.,2,1,0,W)t(P)1t(P
),1t(P)(V)1(V
)),(,),(()()),(,),(()(V
11
t
tt
tt
tptptPtvtvt
nn
由此为上面两式可用矩阵表示则我们记
如果只考虑系统在初始状态基础上的变化,不妨设
V(0)=P(0)
于是我们便可以计算出 P(t)和 V(t)(以 A为例 ):
t p1 p2 p3 p4 p5 p6 p7 v1 v2 v3 v4 v5 v6 v7
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
1 0 -1 1 -1 0 0 0 1 -1 1 -1 0 0 0
2 1 -1 0 0 1 0 -1 2 -2 1 -1 1 0 0
3 1 -1 1 -1 0 1 0 3 -3 2 -2 1 1 -1
… … … … …
这种由某些因素在初始时段的变化 (冲量 )引起的系统的演变过程成为冲量过程,当初始冲量 P(0)中只有一个分量是 1,其余为 0时,成为简单冲量过程,记为 S.一般的冲量过程可以看成若干个简单冲量过程的叠加,
简单冲量过程的稳定性如果系统的任一因素在 t=0的变化,引起的各因素在任意时段的冲量和值都不会无限增长或无限减少,那么这个系统的冲量过程
S是稳定的,
对于所有的 i和任意的 t,若 |Pi(t)|有界,称 S是冲量稳定的 ;若 |vi(t)|有界,称 S是值稳定的,
若 S是值稳定的,则必然是冲量稳定的,反之不然,
定理 1 S是冲量稳定的必要条件是 |λ|≤1.
这里 λ是 W的非零特征值,下同,
特别,当只取数值 0,1,-1时,条件化为 |λ|=1.必要条件不满足时必然有某个简单冲量过程,其冲量不稳定,
定理 2 S是冲量稳定的充分条件是 |λ|≤1且均为单根,
定理 3 S是值稳定的充要条件 S是冲量稳定且 λ≠1.
我们用上述定理检查有向图 G1表示的能源利用系统,矩阵 A的特征多项式为
).1()( 352f
因为 f(1)=-2,f(2)=76,所以 f(λ)在 (1,2)内有根,由定理 1,必有某个简单冲量过程是不稳定的,
不稳定过程的调节方法我们改变 W或 A的值,使得其特征值满足定理
2,3的要求,不过,没有统一的方法,
如果一个带符号的有向图是双向连通的 (即任何两个顶点间存在两条有向路径,使得此两顶点可以互相连通 ),并存在一个位于所有闭路的 中心顶点,那么称它是 改进的玫瑰图,所谓 闭路,是指从某顶点出发,沿有向边前进回到该顶点,且途中不经过重复顶点的路径,以图 G1为例,它就满足这个要求,v1是中心顶点,由
v1 v3,v3 v5,v5v1构成的闭路记做 v1 v3 v5v1.闭路有 v1
v2v1,v1 v3 v2v1,v1 v3 v5v1,v1 v4 v7v1,v1 v3 v5 v6 v7v1,
构成闭路的有向边的数目称为闭路的长度,
当闭路包含奇数个带 -的有向边时,定义该 闭路的符号 为 -1,否则为 +1.
用 ak记长度为 k的闭路的符号和 (不存在长度为
k的闭路时 ak为 0),设 r是使得 ar≠0的最大整数,
我们记 用改进的玫瑰图描述的冲量过程为 S*.
于是,存在一个序列 {a1,a2,…,ar},S*的稳定性完全由这个序列决定,
定理 4 S*冲量稳定的必要条件是 ar =1或 -1 且
ak = -ar ar-k,k=1,2,…,r-1.
定理 5 若 S*冲量稳定的,则 S*是值稳定的充要条件是
.1
1
r
k
ka
下面我们根据定理 4,5来调整邻接矩阵 A的某些元素,
先检查定理 4的必要条件,在图 G1中,没有长度为 1
的闭路,于是 a1=0;再看有 v1 v2v1,由于两边都是符号,故 a2=1;有三条长度为 3的闭路,v1 v3 v2v1,v1 v3
v5v1,v1 v4 v7v1,符号分别是 +1,+1,-1,故 a3=1; a4=0;
只有一条长度为 5的闭路 v1 v3 v5 v6 v7v1,其符号为
+1,故 a5=1; ak=0,k>5.故 r=5.
这样我们得到序列 {a1,a2,a3,a4,a5}={0,1,1,0,1}.
用定理 4的必要条件检查发现,条件 a2=- a5 a3
以及 a3=- a5 a2不成立,
由此可见,为了满足冲量稳定的必要条件,需将中的一个从 1改成 -1.由图可知,我们将 v1 v2的符号从 -改成 +时,a2=1,而 a3,a5不变,此时 {a1,a2,
a3,a4,a5}={0,-1,1,0,1}.还有其他调整方法,
这个改动的实际含义是,将原来的“能源利用量的增加引起价格下降”,调整为“能源利用量的增加导致价格上升”,即从鼓励能源的利用调整为限制利用,这种价格政策的变得一般属于人们可以控制的范围,
当 v1 v2的符号从 -改成 +后,新的邻接矩阵为
).1)(1)(1(
)1()(
222
352
f
由定理 2,此时 S*是冲量稳定的,即能源利用系统的任何一个因素突然变化时,各因素在以后各个时段的改变量时有限的,
若进一步判断 S*是否值稳定,由于此时 a1+a2+
a3+ a4 +a5 =1,不满足定理 5的充要条件,要想定理 4成立的情况下定理 5也成立,需将 a3,a5改成 1.
这要求将长度为 3的一条闭路和长度为 5的闭路
.2/)3i(1,2/)3i( - 1i,- i,0,0,1,于是特征值为的公共边改变符号,只能将 v3 v5由 +改成 -(将
v7v1由 +改成 -会导致 a3=3).而这两种情形都是不可能实现的,前者原意为“能源生产率的增加导致工业产值增加”,后者原意为“人口总数的增加会引起能源利用量的增加”,
如果不要求改公共边,比如将 v5v1由 +改成 -或将 v3v2由 -改成 +,同时将 v5v6或 v6v7由 +改成 -.
这些变动都似乎不可能,
需注意的是,我们在此讨论这个问题时,是事先界定了系统的范围,即不考虑系统外的因素的影响,另外,各个因素间的关系也往往很复杂,在研究问题时必要的简化也是必须的,
