一类特殊的极大+和支撑树在调整和权值下的逆问题

摘要：

本文研究的是一类特殊的极大+和支撑树在调整和权值下的逆问题.给定一个边赋权连通网络G=(V E,c,w),对于每一条边e∈E,已知一个费用c(e)和一个权值w(e),极大+和支撑树问题是指寻找一棵支撑树T*,使得其是权值max/e∈T w(e)+∑e∈Tc(e)最小的一棵支撑树.而在极大+和支撑树的逆问题中,给定一棵支撑树T0,它不是已知网络中最优的极大+和支撑树,要求调整网络中各边的费用c(e),使T0变成调整后网络中最优的极大+和支撑树,目标函数是使得在l1模意义下的边权调整费用尽可能的小.本文针对已知网络中各边费用都相等这一特殊情况,给出了求解该逆问题的列生成算法,每次迭代时入基向量的选择可以转化为一个新参数下的极大+和支撑树问题,从而可在多项式时间内确定入基向量的选择.本文最后给出了一个实例说明算法的有效性.

关键词：极大+和支撑树问题、逆优化问题、线性规划问题、对偶问题、列生成算法

所属期刊栏目：30

分类号：O22(运筹学)

资助基金：国家自然科学基金10801031资助

在线出版日期：2014-04-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：205-214