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

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

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

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

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

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