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

南京大学学报数学半年刊 第30卷第2期 JOURNALOFNANJING UNIVERSITY Vo1．30，No．2 2013年l1月 MATHEMATICALBIQUARTERLY Nov．，2013 DOh10．3969／j．issn．0469—5097．2013．02．008 一 类特殊的极大 +和 支撑树在调整和权值下的逆问题 左 霞 (建东职业技术学院，常州 213022) 关秀翠 (东南大学数学系，南京 210096) 摘要 本文研究的是一类特殊的极大 +和支撑树在调整和权值下的逆问题．给定一 个边赋权连通网络 G=(E，c，)，对于每一条边 e∈E，已知一个费用 c(e)和一个 权值 叫(e)，极大 +和支撑树问题是指寻找一棵支撑树 ，使得其是权值marxw(e)+ ∑c(e)最小的一棵支撑树．而在极大 +和支撑树的逆问题中，给定一棵支撑树 ， eET 它不是已知网络中最优的极大 +和支撑树，要求调整网络中各边的费用 c(e)，使 变成调整后网络中最优的极大+和支撑树，目标函数是使得在c-模意义下的边权调 整费用尽可能的小．本文针对已知网络中各边费用都相等这一特殊情况，给出了求解 该逆问题的列生成算法，每次迭代时入基向量的选择可以转化为一个新参数下的极 大 +和支撑树问题，从而可在多项式时间内确定入基向量的选择．本文最后给出了 一 个实例说明算法的有效性． 关键词 极大 +和支撑树问题，逆优化问题，线性规划问题，对偶问题，列生成算法 中图法分类号 022 1 研究的背景和意义 组合优化研究的对象是具有离散结构的最优化问题，极大+和支撑树的问题是赋权图上 国家自然科学基金助． 收稿 日期：2012—06-04． Correspondenceauthor：zuozuoxia2OO8@qq．com；xcguan~(163．corn 南京大学学报数学半年刊 2013年 l1月 的最优化问题之一，其 目标函数是用两种常用的优化函数来综合度量的，一个是赋权和，一个 是瓶颈权，该问题在工程领域、卫星通讯、指派问题等方面都有广泛的应用 IsJ。 在一个边赋权连通网络 G=(E，C，W)中，对于每一条边e∈E，给定一个费用c(e)和一 个权值叫(e)，极大+和支撑树问题是指寻找一棵支撑树 ，使其在权值m2~w(e)+∑c(e) c eET 下最小的一棵支撑树．Punnen和Nair[]给出了求解极大 +和支撑树问题的一个时间复杂性 为o(mlog佗)的算法，其中JV}= ，lEj=m．本文要研究的是一类特殊的极大 +和支撑树在 调整和权值下的逆问题，给定一棵支撑树 ，它不是已知权值下最优的极大+和支撑树，该逆 问题要求调整网络中各边的费用c(e)，以使 变成调整后网络中最优的极大 +和支撑树，目 标函数是使得在 l模意义下的各边费用调整量尽可能的小． 极大 +和支撑树的逆问题从属于组合优化逆问题的研究领域，这是近二十年来最优化领 域中一个较新的研究方向，它包括最短路的逆问题、最大流的逆问题、最小支撑树的逆问题 f2，5，61等．Heuberger在其综述文章 3【】中对于组合优化逆问题的一般理论和各种逆问题的研 究结果进行了详细介绍． 最小支撑树逆问题是指调整各边的权值使得给定的支撑树成为调整后网络的最小支撑树． Sokkalingam等 0(j研究了三类最小支撑树逆 问题．首先将 11模下的逆问题转化为一类非平 衡指派问题，并用序列最短路算法在 O(n。)时间内求解；然后将赋权 f模下的逆问题转化为 一 类运输问题的对偶