文献综述（或调研报告）：
1992年，Burton和Toint[1]在研究一个有趣的地质科学应用中提出了最短路径问题的逆问题。该问题要求在调整点权的情况下，使得一个给定的顶点v0成为调整点权后的重心，使得点权调整量在某种模的意义下尽可能的小。同年，Berman[2]等人提出通过改变弧长和引入新的弧的方法来解决这种逆问题，也就是现在的改变边权和引入新的边。Burkard[3]等人又提出了圈上的反向1-重心问题的解决方法，即通过预算来改变一些边的长度，使得到预定顶点的加权距离和尽可能小。后来，M.C. Cai, X.G. Yang, J.Z. Zhang[4]证实了逆重心选址问题是一个NP-hard问题。近年来，Burkard[5]等人认为，树上的逆-1重心问题可以通过一种贪心算法解决，即不从整体最优角度考虑该问题，而是找出局部最优。Heuberger[6]则对逆优化问题中的网络和选址模型进行了深入研究。J.Zhang, Z. Liu, Z. Ma[7]也提出过相似的问题，为了最小化一个给定设施到其他各节点的最远距离，他们提出了一种多项式算法用于缩短给定预算内的属性网络的长度。在求解逆问题的全局解时，我们运用Mefiddo[8]提出的线性时间算法知道，只有两个变量的线性规划问题的时间复杂度为O(n^3)。
对给定的一个连通无向图G，每条边都有一个权和价值系数，如何改变图的边权向量使得G的支撑树是在新的权向量下的最小支撑树，且在哈明距离下的费用总和最小，这一个求和型哈明距离下的赋权逆最小支撑树问题。而我们要研究的求和型哈明距离下的选址问题，可以类似地被描述为：对给定的一个连通无向图G，每条边都有一个权和价值系数，如何改变图的边权向量使得在新的边权向量下从给定顶点s到网络的其他丁点的距离不超过给定的上界，切在哈明距离下的总费用最小。
中国计量学院吴龙树和曹飞龙[9]提出，在网络中顶点的权值可以改变的情况下,对哈明距离下以及l1模下1-重心问题的反问题进行研究。通过将哈明距离下网络1-重心问题的反问题归约为0-1背包问题,证明即使是在链式网络中,在哈明距离下该问题仍是NP困难的,并给出l1模下在一般网络中求解1-重心反问题的多项式时间算法。吴龙树[10]等人还就哈明距离下网络中的1-重心问题的反问题进行了研究。他们指出，1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其他顶点的加权距离之和不超过一个给定的上界。证明了在哈明距离下该问题是NP困难的。并运用动态规划的思想,在考虑改变顶点的权的情况下,对一般网络进行了求解。
青岛大学段伟伟[11]等人在对于树上的具有非负权重的2-重心问题及其反问题的研究上，得出了下面的结论:若顶点子集a,b V是树的2-重心,在树上连接顶点a和顶点b有唯一的一条路,去掉路的中点所在的边,树分成两个子树,则a和b分别是所在子树的1-重心.根据这个结论,提出了具体的算法,即树上的具有非负权重的2-重心可以通过在其子树上求1-重心来得到。树上的具有非负权重的2-重心问题的反问题,可以转化为线性规划模型求解,存在有效算法。
参考文献：
[1] D. Burton, Ph.L. Toint, On an instance of the inverse shortest path problem, Mathematical Programming 53 (1992) 45–61.
[2] O.Berman,D.I.Ingco,A.R.Odoni,Improving the location of minisum facilities through network modification, Annals of Operations Research 40 (1992) 1–16.
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
