極大代數(shù)線性離散事件動(dòng)態(tài)系統(tǒng)性能估計(jì)算法研究.pdf

1、離散事件動(dòng)態(tài)系統(tǒng)（DEDS）是上世紀(jì)80年代以來(lái)興起的一門學(xué)科。它淵源于排隊(duì)和網(wǎng)絡(luò)分析問(wèn)題，由于信息處理、計(jì)算機(jī)和機(jī)器人等技術(shù)的發(fā)展、完善和應(yīng)用的需要，出現(xiàn)了計(jì)算機(jī)集成制造、通訊網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)、交通調(diào)度和公共服務(wù)等一系列人造系統(tǒng)，這使得對(duì)于DEDS的研究更為迫切，并且極具實(shí)際的價(jià)值。越來(lái)越多的人進(jìn)入到DEDS這一極富挑戰(zhàn)性的研究領(lǐng)域，在建模、分析、控制、綜合等問(wèn)題作了很多研究。 本論文是在已有成果的基礎(chǔ)上，對(duì)極大代數(shù)線性DED

2、S的性能分析算法（即周時(shí)計(jì)算算法）進(jìn)行研究。Howard算法和CalcCycleTime算法是目前該類算法中效率最高的算法，本文重點(diǎn)對(duì)它們通過(guò)數(shù)值試驗(yàn)，進(jìn)行比較和研究，并對(duì)算法提出改進(jìn)。 本文首先深入研究了這兩個(gè)算法。Howard算法是策略迭代算法，首先進(jìn)行策略選擇并求出相應(yīng)的策略矩陣的廣義特征模式，然后檢測(cè)策略矩陣的廣義特征模式是否為最初矩陣的廣義特征模式。如果滿足，則極大代數(shù)矩陣的周時(shí)被求出，不滿足，進(jìn)行策略改進(jìn)。CalcC

3、ycleTime算法也是策略迭代算法，但與Howard算法相比采用了不同的思路。它首先利用CalcSpectralRadius計(jì)算譜半徑，其實(shí)質(zhì)也是通過(guò)策略迭代不斷地對(duì)策略進(jìn)行改進(jìn)，當(dāng)?shù)竭_(dá)最優(yōu)策略時(shí)，策略矩陣的最大特征值就是函數(shù)的譜半徑，然后將周時(shí)分量等于該譜半徑的節(jié)點(diǎn)從原系統(tǒng)中消去，最后遞歸調(diào)用CalcCycleTime算法計(jì)算簡(jiǎn)化函數(shù)的周時(shí)。 正是這兩個(gè)算法采用策略迭代這一思想。使得他們具有很高的計(jì)算效率。平均時(shí)間復(fù)雜度近似

4、線性，針對(duì)這兩個(gè)算法，論文做了如下主要工作： （1）在國(guó)內(nèi)首次對(duì)Howard算法進(jìn)行了詳細(xì)分析，寫出了詳細(xì)的Howard算法的中文文檔。對(duì)Howard算法編寫了大量數(shù)值實(shí)驗(yàn)程序，得到了關(guān)于其運(yùn)行效率的數(shù)據(jù)。 （2）將Howard算法與對(duì)偶CalcCycleTime算法進(jìn)行數(shù)值試驗(yàn)比較。首次得出了前者在總體上優(yōu)于后者的結(jié)論，并為后者的進(jìn)一步優(yōu)化指明了方向和思路。 （3）對(duì)Howard算法進(jìn)行了盡可能的優(yōu)化和改進(jìn)。H