賦權哈明距離下若干網絡逆問題的研究.pdf

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

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

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

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

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