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

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

【文章頁數】：65 頁

【學位級別】：碩士

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


【參考文獻】：
碩士論文
[1]調整和權值下一類極大加和支撐樹逆問題[D]. 何新燕.東南大學 2015



本文編號：3083714