网络改进问题是最优化领域的一个热门课题,近年来受到人们的广泛关注。网络改进问题是一种广义的逆最优化问题。逆最优化问题主要研究如何改变原问题中的参数,使得给定的可行解在新的参数下成为最优解,且总的改造费用尽可能少。人们根据不同的应用背景,分别研究了最短路的改进问题、逆最小费用流问题、逆最大流问题等,并在网络选址、运输流量均衡等众多领域取得了一些重要的理论和应用成果。网络选址问题是最优化领域的一类经典问题。网络选址问题主要研究如何在网络中将设施安排在最优的位置。但在实际网络中,公共设施可能已经存在,但由于区域环境的发展变化,未必仍满足位置最优的要求,而公共设施不能迁移或公共设施的迁移费用可能远远大于网络连接的改进费用,这时需要对网络进行改进,这就出现了网络选址问题的逆问题。本文从以下几个方面分别对l1模下和Hamming距离下特殊圈上的1-maxian逆问题以及只允许权重减小或权重增加的逆最小支撑树问题等进行了研究:第一,研究了l1模下特殊圈上的1-maxian逆问题。该问题主要研究如何在一定的预算下修改网络中边的长度,使得其他所有顶点到预先给定顶点的距离之和尽可能的大。首先我们对费用一致且边长及边长增量的上界均为1的特殊4-圈进行了研究,得到了该问题在任意预算下的最优解。然后将问题推广到特殊n-圈的情形,并得到其最优解的一般形式。第二,研究了Hamming距离下特殊圈上的1-maxian逆问题。首先,我们研究了费用一致且边长及边长增量的上界均为1时Hamming距离下4-圈的情形,得到了任意预算和距离之间关系的分段函数。然后将问题推广到特殊n-圈的情形,并得到其最优解的一般形式。第三,研究了只允许权重减小的逆最小支撑树问题。该问题研究如何尽可能少的减小图G中边的权重,使得在新的权重下预先给定的支撑树T成为图G的最小支撑树并且T中边的权重不能超过给定的界。我们得到了求解该问题的多项式时间算法,并通过实例验证了该算法的有效性。同时对只允许权重增加的逆最小支撑树问题也进行了研究,并得到了该问题的多项式时间算法。