圖論與網(wǎng)絡(luò)模型(四)

圖論與網(wǎng)絡(luò)模型

及其應(yīng)用(五)——沖量模型本節(jié)我們用一個(gè)能源利用系統(tǒng)的例子說(shuō)明沖量過(guò)程的建模方法.我們考察某地區(qū)的能源利用狀況.先界定系統(tǒng)的范圍,比如只考慮能源利用量、價(jià)格、生產(chǎn)率、環(huán)境質(zhì)量、工業(yè)產(chǎn)值、就業(yè)機(jī)會(huì)及人口總數(shù)等7個(gè)因素，它們之間相互復(fù)雜的關(guān)系可以簡(jiǎn)化為一個(gè)因素對(duì)另外因素直接的促進(jìn)(正面)或促退(負(fù)面)作用。要研究的問(wèn)題是,當(dāng)其中某個(gè)因素突然發(fā)生改變時(shí),預(yù)測(cè)系統(tǒng)各因素的演變過(guò)程和趨勢(shì).定性模型V1---能源利用量V2---能源價(jià)格V3---能源生產(chǎn)率V4---環(huán)境質(zhì)量V5---工業(yè)產(chǎn)值V6---就業(yè)機(jī)會(huì)V7---人口總數(shù)v3???????v2v5v6v7v4v1++++++-+---G1我們將能源利用系統(tǒng)的每個(gè)因素用圖的一個(gè)頂點(diǎn)來(lái)表示,因素間的直接影響用帶方向的邊表示.為了表示因素間的影響是促進(jìn)還是促退,我們?cè)诩^旁邊分別標(biāo)示“+”或“-”.這樣,我們便得到了一個(gè)帶符號(hào)的有向圖G1.需說(shuō)明的是:第一,兩頂點(diǎn)之間的有向邊表示兩因素間的直接影響,如v1v3帶正號(hào)表示某時(shí)段能源利用量v1的增加導(dǎo)致下一時(shí)段能源生產(chǎn)率的增長(zhǎng),v1v4帶符號(hào)則表示v1的增加導(dǎo)致下一時(shí)段環(huán)境質(zhì)量的下降.至于因素間的間接影響是由幾條相連的同向邊反映出來(lái).

第二,像能源利用這樣的社會(huì)經(jīng)濟(jì)系統(tǒng),因素間的影響關(guān)系十分復(fù)雜,應(yīng)該合理、簡(jiǎn)化地確定哪些因素間有直接影響,這里除了主要根據(jù)客觀規(guī)律作出決定外,方針政策有時(shí)也是判斷的依據(jù).如能源利用量增加時(shí)能源價(jià)格是降低還是升高,是由政府鼓勵(lì)利用能源還是限制能源利用的價(jià)格政策決定的.定義鄰接矩陣A=(aij)如下:于是v3???????v2v5v6v7v4v1++++++-+---定量模型v3???????v2v5v6v7v4v111-2-0.51.21.50.30.81.5-0.7-1.2G2這里能源利用量v1和生產(chǎn)率v3均以變化10%為一個(gè)單位,如圖,v1增加1個(gè)單位將引起v30.8個(gè)單位的增長(zhǎng).邊上的權(quán)我們用wij表示.剛才的有向圖G1以及矩陣A是定性模型,如果將系統(tǒng)各因素加以量化,那么我們便得到定量模型,我們用加權(quán)的有向圖表示.如:這樣我們便得到圖G2的鄰接矩陣為v3???????v2v5v6v7v4v111-2-0.51.21.50.30.81.5-0.7-1.2V1出發(fā)的邊沖量過(guò)程為了研究系統(tǒng)的某個(gè)因素一個(gè)突然變化所引起的整個(gè)系統(tǒng)在其后各時(shí)段的演變過(guò)程,用vi(t)表示因素vi在時(shí)段t的值(我們這里實(shí)際上是將時(shí)間離散化處理),pi(t)表示在時(shí)段t的改變量(沖量).設(shè)系統(tǒng)共有n個(gè)因素,根據(jù)wij的含義,對(duì)t=0,1,2,…,有如果只考慮系統(tǒng)在初始狀態(tài)基礎(chǔ)上的變化,不妨設(shè)V(0)=P(0)于是我們便可以計(jì)算出P(t)和V(t)(以A為例):tp1p2p3p4p5p6p7v1v2v3v4v5v6v701000000100000010-11-10001-11-100021-10010-12-21-110031-11-10103-32-211-1……………這種由某些因素在初始時(shí)段的變化(沖量)引起的系統(tǒng)的演變過(guò)程成為沖量過(guò)程.當(dāng)初始沖量P(0)中只有一個(gè)分量是1,其余為0時(shí),成為簡(jiǎn)單沖量過(guò)程,記為S.一般的沖量過(guò)程可以看成若干個(gè)簡(jiǎn)單沖量過(guò)程的疊加.簡(jiǎn)單沖量過(guò)程的穩(wěn)定性如果系統(tǒng)的任一因素在t=0的變化,引起的各因素在任意時(shí)段的沖量和值都不會(huì)無(wú)限增長(zhǎng)或無(wú)限減少,那么這個(gè)系統(tǒng)的沖量過(guò)程S是穩(wěn)定的.對(duì)于所有的i和任意的t,若|Pi(t)|有界,稱S是沖量穩(wěn)定的;若|vi(t)|有界,稱S是值穩(wěn)定的.若S是值穩(wěn)定的,則必然是沖量穩(wěn)定的.反之不然.定理1S是沖量穩(wěn)定的必要條件是|λ|≤1.這里λ是W的非零特征值.下同.特別,當(dāng)只取數(shù)值0,1,-1時(shí),條件化為|λ|=1.必要條件不滿足時(shí)必然有某個(gè)簡(jiǎn)單沖量過(guò)程,其沖量不穩(wěn)定.定理2S是沖量穩(wěn)定的充分條件是|λ|≤1且均為單根.定理3S是值穩(wěn)定的充要條件S是沖量穩(wěn)定且λ≠1.我們用上述定理檢查有向圖G1表示的能源利用系統(tǒng).矩陣A的特征多項(xiàng)式為因?yàn)閒(1)=-2,f(2)=76,所以f(λ)在(1,2)內(nèi)有根.由定理1,必有某個(gè)簡(jiǎn)單沖量過(guò)程是不穩(wěn)定的.不穩(wěn)定過(guò)程的調(diào)節(jié)方法我們改變W或A的值,使得其特征值滿足定理2,3的要求.不過(guò),沒(méi)有統(tǒng)一的方法.如果一個(gè)帶符號(hào)的有向圖是雙向連通的(即任何兩個(gè)頂點(diǎn)間存在兩條有向路徑,使得此兩頂點(diǎn)可以互相連通),并存在一個(gè)位于所有閉路的中心頂點(diǎn),那么稱它是改進(jìn)的玫瑰圖.所謂閉路,是指從某頂點(diǎn)出發(fā),沿有向邊前進(jìn)回到該頂點(diǎn),且途中不經(jīng)過(guò)重復(fù)頂點(diǎn)的路徑.以圖G1為例,它就滿足這個(gè)要求,v1是中心頂點(diǎn).由v1v3,

v3v5,

v5v1構(gòu)成的閉路記做v1v3v5v1.閉路有v1v2v1,v1v3v2v1,v1v3v5v1,v1v4v7v1,

v1v3v5v6v7v1.構(gòu)成閉路的有向邊的數(shù)目稱為閉路的長(zhǎng)度.當(dāng)閉路包含奇數(shù)個(gè)帶-的有向邊時(shí),定義該閉路的符號(hào)為-1,否則為+1.用ak記長(zhǎng)度為k的閉路的符號(hào)和(不存在長(zhǎng)度為k的閉路時(shí)ak為0),設(shè)r是使得ar≠0的最大整數(shù).我們記用改進(jìn)的玫瑰圖描述的沖量過(guò)程為S*.于是,存在一個(gè)序列{a1,

a2,…,

ar},S*的穩(wěn)定性完全由這個(gè)序列決定.定理4S*沖量穩(wěn)定的必要條件是ar

=1或-1且

ak

=

-ar

ar-k,k=1,2,…,r-1.定理5若S*沖量穩(wěn)定的,則S*是值穩(wěn)定的充要條件是下面我們根據(jù)定理4,5來(lái)調(diào)整鄰接矩陣A的某些元素.先檢查定理4的必要條件.在圖G1中,沒(méi)有長(zhǎng)度為1的閉路,于是a1=0;再看有v1v2v1,由于兩邊都是符號(hào),故a2=1;有三條長(zhǎng)度為3的閉路,v1v3v2v1,v1v3v5v1,v1v4v7v1,

符號(hào)分別是+1,+1,-1,故a3=1;a4=0;只有一條長(zhǎng)度為5的閉路v1v3v5v6v7v1,其符號(hào)為+1,故a5=1;ak=0,k>5.故r=5.這樣我們得到序列{a1,a2,a3,a4,a5}={0,1,1,0,1}.用定理4的必要條件檢查發(fā)現(xiàn),條件a2=-a5a3以及a3=-a5a2不成立.由此可見(jiàn),為了滿足沖量穩(wěn)定的必要條件,需將中的一個(gè)從1改成-1.由圖可知,我們將v1v2的符號(hào)從-改成+時(shí),a2=1,而a3,a5不變.此時(shí){a1,a2,a3,a4,a5}={0,-1,1,0,1}.還有其他調(diào)整方法.這個(gè)改動(dòng)的實(shí)際含義是,將原來(lái)的“能源利用量的增加引起價(jià)格下降”,調(diào)整為“能源利用量的增加導(dǎo)致價(jià)格上升”,即從鼓勵(lì)能源的利用調(diào)整為限制利用.這種價(jià)格政策的變得一般屬于人們可以控制的范圍.當(dāng)v1v2的符號(hào)從-改成+后,新的鄰接矩陣為由定理2,此時(shí)S*是沖量穩(wěn)定的.即能源利用系統(tǒng)的任何一個(gè)因素突然變化時(shí),各因素在以后各個(gè)時(shí)段的改變量時(shí)有限的.若進(jìn)一步判斷S*是否值穩(wěn)定.由于此時(shí)a1+a2+a3+a4+a5=1,不滿足定理5的充要條件.要想定理4成立的情況下定理5也成立,需將a3,a5改成1.這要求將長(zhǎng)度為3的一條閉路和長(zhǎng)度為5的閉路的公共邊改變符號(hào).只能將v3v5由+改成-(將v7v1由+改成-會(huì)導(dǎo)致a3=3).而這兩種情形都是不可能實(shí)現(xiàn)的,前者原意為“能源生產(chǎn)率的增加導(dǎo)致工業(yè)產(chǎn)值增加”,后