賦權(quán)哈明距離下若干網(wǎng)絡(luò)逆問題的研究.pdf

1、網(wǎng)絡(luò)優(yōu)化問題是一類重要的組合優(yōu)化問題，它要求找到給定問題的最優(yōu)解．隨著社會生產(chǎn)的發(fā)展，又產(chǎn)生一些所謂的網(wǎng)絡(luò)優(yōu)化逆問題，在這些問題中，先給定一個可行解，但就目前的參數(shù)而言，它并不是最優(yōu)解，我們需要通過盡可能少的修改相應(yīng)的參數(shù)從而使得所給的可行解成為最優(yōu)解．隨著計算機(jī)科學(xué)、管理科學(xué)和現(xiàn)代化生產(chǎn)技術(shù)等的日益發(fā)展，這類問題與日俱增，越來越受到運籌學(xué)、應(yīng)用數(shù)學(xué)、計算機(jī)科學(xué)及管理科學(xué)等諸多學(xué)科的高度重視．本文就是針對這些新問題，主要對哈明距離下的若

2、干網(wǎng)絡(luò)逆問題進(jìn)行了研究．全文共分為四章，第一章主要介紹與組合優(yōu)化問題及逆問題相關(guān)的一些概念和預(yù)備知識．接著我們分別研究了不同問題的若干模型．
　　 第二章研究的是賦權(quán)哈明距離下最大流逆問題：對給定的連通有向網(wǎng)絡(luò)N(V，A，C)，每條弧都有一個容量改造費用，令f0是網(wǎng)絡(luò)N的一個可行流，如何改變網(wǎng)絡(luò)弧上的容量使得f0成為新容量下的最大流，且在哈明距離下產(chǎn)生的改造費用最?。覀兛偣惭芯苛怂姆N模型；對于總和型，我們把問題轉(zhuǎn)化為求解剩余網(wǎng)

3、絡(luò)的一個受限制割，從而給出了時間復(fù)雜性為O(n3)的多項式時間算法．對于瓶頸型，我們通過把問題轉(zhuǎn)化為求解剩余網(wǎng)絡(luò)的一個受限制瓶頸割問題，從而給出了時間復(fù)雜性為O(m+n·logn)的多項式時間算法．對于兩種混合型，我們利用二分法思想，結(jié)合前面的算法，分別給出了時間復(fù)雜性為O(n3·logm)和O(n3)的多項式時間算法．
　　 第三章研究的是賦權(quán)哈明距離下最小一最大支撐樹逆問題：對給定的連通圖G=(V，E，c)，每條邊都有一個長

4、度改造費用，令T0是圖G的一個支撐樹，如何改變圖上邊的長度使得T0成為新長度下的最小一最大支撐樹，且在哈明距離下產(chǎn)生的改造費用最?。覀兛偣惭芯苛怂姆N模型：對于總和型，我們先給出了最優(yōu)解的可能取值，然后通過求解圖的受限最小割問題給出了時間復(fù)雜性為O(n4)的多項式時間算法．對于瓶頸型，我們通過求解圖的受限最小瓶頸割問題給出了時間復(fù)雜性為O(n5)的多項式時間算法．對于兩種混合型，我們利用二分法的思想，結(jié)合前面的算法，分別給出了時間復(fù)雜性

5、為O(n5)和O(n4)的多項式時間算法．
　　 第四章研究的是賦權(quán)哈明距離下最小割逆問題：對給定的連通有向網(wǎng)絡(luò)N(V，A，c)，每條弧都有一個容量改造費用，令{X0，X0}是網(wǎng)絡(luò)N的一個s—t割，如何改變網(wǎng)絡(luò)弧上的容量使得{X0，X0}成為新容量下的最小割，且在哈明距離下產(chǎn)生的改造費用最?。覀冄芯苛藘煞N模型：對于總和型，我們利用背包問題的實例的多項式歸約，證明了該問題是NP—難的．對于瓶頸型，通過利用最大流—最小割和哈明距離