l ∞ 模下调整最大权值的极大加和支撑树逆问题

发布时间：2021-03-15 06:25

　　本文研究的是l_∞模下调整最大权重w的极大加和支撑树逆问题.极大加和支撑树问题是在一个边赋权无向连通图G（V,E,c,w）中,找一棵最优的支撑树T*,使得目标函数max_e∈Tw（e）+∑_e∈T c（e）最小,该问题的时间复杂度为O（m log n）,其中m:= |E|,n:= |V|.它的逆问题描述为:给定网络G的一棵非最优的支撑树T₀,调整网络各边的权重w到（?）,使得T₀成为新网络G（V,E,c,（?））下的最优极大加和支撑树,其中w-l≤（?）≤w+u,l≥0,u≥0.目标函数是使得maxe∈Eq（e）|w（e）-（?）（e）|最小,其中q（e）是调整1单位w（e）所需的费用.本文首先分析了该逆问题的可行解和最优解所具有的性质,其次得到了如何通过给定的可行目标函数值构造可行解这个重要结论.最后我们分别讨论了三种情况.首先在无界的单位无穷模情况下,我们根据最优值的性质设计了二分法确定最优值的下界,进一步根据最优解的性质确定了最优值,并证明了该算法的迭代次数不超过O（m）,算法... 

【文章来源】：东南大学江苏省 211工程院校 985工程院校 教育部直属院校

【文章页数】：65 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景及意义
    1.2 支撑树的基础知识
    1.3 向量的模
    1.4 本文主要研究工作
∞模下调整w的极大加和支撑树逆问题">第二章 l_∞模下调整w的极大加和支撑树逆问题
∞
b的可行解及最优解的性质">    2.1 IM SST_{∞
b的可行解及最优解的性质
∞}模下的逆问题">    2.2 无界时单位l_∞模下的逆问题
∞模下的逆问题">    2.3 无界时赋权l_∞模下的逆问题
∞模下的逆问题">    2.4 有界时赋权l_∞模下的逆问题
    2.5 数值实验
第三章 总结与展望
致谢
参考文献


【参考文献】：
硕士论文
[1]调整和权值下一类极大加和支撑树逆问题[D]. 何新燕.东南大学 2015



本文编号：3083714