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

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

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