单位无穷范数下边权有界的最小支撑树逆最优值问题  

The bounded inverse optimal value problem on minimum spanning tree under unit infinity norm

作　　者：张斌武 关秀翠 ZHANG Binwu;GUAN Xiucui(College of Science,Hohai University,Nanjing 210098,Jiangsu,China;School of Mathematics,Southeast University,Nanjing 210096,Jiangsu,China)

机构地区：[1]河海大学理学院,江苏南京210098 [2]东南大学数学学院,江苏南京210096

出　　处：《运筹学学报》2022年第3期44-56,共13页Operations Research Transactions

基　　金：国家自然科学基金(No.11471073)。

摘　　要：研究了单位l范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络G=(V,E,w),支撑树T^(0),下界向量l,上界向量u及数值K,寻求一个新的边权向量w满足上下界约束l≤w≤u,且T^(0)是在向量w下权值为K的一个最小支撑树,目标是在单位l范数下使得修改成本‖w-w‖最小。本文给出了该问题的数学模型,分析了其最优性条件,设计了求解该问题的时间复杂度为O(|V||E|)的强多项式时间算法。We consider the bounded inverse optimal value problem on minimum spanning tree under unit lnorm.Given an edge weighted connected undirected network G=(V,E,w),a spanning tree T^(0),a lower bound vector l,an upper bound vector u and a value K,we aim to obtain a new weight vector w satisfying the lower and upper bounds such that T^(0)is a minimum spanning tree under the vector w with weight K.The objective is to minimize the modification cost under unit lnorm.We present a mathematical model of the problem.After analyzing optimality conditions of the problem,we develop an O(|V||E|)strongly polynomial time algorithm.

关 键 词：最小支撑树 l_(∞)范数 逆最优值问题 强多项式时间算法 

分 类 号：O221.2[理学—运筹学与控制论]