幾個組合優(yōu)化問題的研究及應(yīng)用.pdf

1、山東大學(xué)博士學(xué)位論文幾個組合優(yōu)化問題的研究及應(yīng)用姓名：王新紅申請學(xué)位級別：博士專業(yè)：運籌學(xué)與控制論指導(dǎo)教師：劉家壯20030328山東大學(xué)博士學(xué)位論文圖G關(guān)于劃分(，％，，％)的緊縮圖的概念，并將圖G的L(2，1)一標號問題轉(zhuǎn)化為求圖的最優(yōu)獨立集劃分和最優(yōu)路劃分的問題第三節(jié)為圖的最優(yōu)獨立集劃分問題和圖的最優(yōu)路劃分問題設(shè)計了啟發(fā)式算法，進而設(shè)計了一個新的求解L(2，1)一標號問題的有效算法L21。第四節(jié)以山東省十七地市的頻率分配問題為實例

2、，給出L(2，1卜標號方案，并且驗證L2t算法的優(yōu)越性本文的創(chuàng)新點為：1提出強距離ro一控制集的概念，設(shè)計了求解最優(yōu)強距離ro一控制集問題的有效算法SDD，并應(yīng)用于求解濟南市警車設(shè)點問題2利用就近配對思想與分層分解技術(shù)設(shè)計了求解合理定向問題的近似算法RO，并應(yīng)用于求解濟南市道路定向問題。3提出k一穩(wěn)定集劃分的概念，設(shè)計了一個新的求解L(2，1)一標號問題的有效算法L21，并應(yīng)用于求解山東省十七地市的頻率分配問題。關(guān)鍵詞：強距離ro一控制