信息系統(tǒng)中的組合優(yōu)化問題研究.pdf

1、在實際應用領域產(chǎn)生的許多組合優(yōu)化問題,如工件的排序加工問題、旅行售貨員問題、裝箱問題和頻道分配問題都是NP困難問題.對于這類問題,從數(shù)學的角度出發(fā),需要考慮問題的模型,求解此問題.在P≠NP的假設被人們廣泛地認可下,在多項式時間內(nèi)尋找此類問題的精確解是不可行的.因此,設計這類問題的近似算法,已成為計算機科學和數(shù)學中學術探討的一個無法抗拒的主題.該文研究了從實際應用中產(chǎn)生的兩個組合優(yōu)化問題:帶頻道負荷的頻道分配問題和帶拒絕的裝箱問題.第二

2、章討論了一般網(wǎng)絡的帶頻道負荷經(jīng)束的頻道分配問題.概括地說,該文的主要創(chuàng)新點有1.推廣了頂點染色的概念.在給出的圖模型基礎上,定義并討論了k-m限制多重染色.當其中的參數(shù)取不同的特定值時,k-m限制多重染色分別對應于圖的頂點染色和頂點多重染色.并利用序列算法得到該染色的一些理論結果與相應的頂點染色和多重染色的有關結論.2.給出了求星圖和樹圖的μ-定向最優(yōu)解的多項式時間算法.首先找到星圖的μ-定向最優(yōu)解,而后利用動態(tài)規(guī)劃思想,從樹的最底層葉