本文研究的是l_∞模下調(diào)整最大權(quán)重w的極大加和支撐樹逆問題.極大加和支撐樹問題是在一個邊賦權(quán)無向連通圖G（V,E,c,w）中,找一棵最優(yōu)的支撐樹T*,使得目標(biāo)函數(shù)max_e∈Tw（e）+∑_e∈T c（e）最小,該問題的時間復(fù)雜度為O（m log n）,其中m:= |E|,n:= |V|.它的逆問題描述為:給定網(wǎng)絡(luò)G的一棵非最優(yōu)的支撐樹T₀,調(diào)整網(wǎng)絡(luò)各邊的權(quán)重w到（?）,使得T₀成為新網(wǎng)絡(luò)G（V,E,c,（?））下的最優(yōu)極大加和支撐樹,其中w-l≤（?）≤w+u,l≥0,u≥0.目標(biāo)函數(shù)是使得maxe∈Eq（e）|w（e）-（?）（e）|最小,其中q（e）是調(diào)整1單位w（e）所需的費用.本文首先分析了該逆問題的可行解和最優(yōu)解所具有的性質(zhì),其次得到了如何通過給定的可行目標(biāo)函數(shù)值構(gòu)造可行解這個重要結(jié)論.最后我們分別討論了三種情況.首先在無界的單位無窮模情況下,我們根據(jù)最優(yōu)值的性質(zhì)設(shè)計了二分法確定最優(yōu)值的下界,進一步根據(jù)最優(yōu)解的性質(zhì)確定了最優(yōu)值,并證明了該算法的迭代次數(shù)不超過O（m）,算法... 

【文章來源】：東南大學(xué)江蘇省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：65 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究背景及意義
    1.2 支撐樹的基礎(chǔ)知識
    1.3 向量的模
    1.4 本文主要研究工作
∞模下調(diào)整w的極大加和支撐樹逆問題">第二章 l_∞模下調(diào)整w的極大加和支撐樹逆問題
∞
b的可行解及最優(yōu)解的性質(zhì)">    2.1 IM SST_{∞
b的可行解及最優(yōu)解的性質(zhì)
∞}模下的逆問題">    2.2 無界時單位l_∞模下的逆問題
∞模下的逆問題">    2.3 無界時賦權(quán)l(xiāng)_∞模下的逆問題
∞模下的逆問題">    2.4 有界時賦權(quán)l(xiāng)_∞模下的逆問題
    2.5 數(shù)值實驗
第三章 總結(jié)與展望
致謝
參考文獻


【參考文獻】：
碩士論文
[1]調(diào)整和權(quán)值下一類極大加和支撐樹逆問題[D]. 何新燕.東南大學(xué) 2015



本文編號：3083714