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

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

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

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

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