【作者】 刘龙城；

【导师】 姚恩瑜； 何勇；

【作者基本信息】 浙江大学 ， 运筹学与控制论， 2009， 博士

【摘要】 网络优化问题是一类重要的组合优化问题,它要求找到给定问题的最优解。随着社会生产的发展,又产生一些所谓的网络优化逆问题,在这些问题中,先给定一个可行解,但就目前的参数而言,它并不是最优解,我们需要通过尽可能少的修改相应的参数从而使得所给的可行解成为最优解。随着计算机科学、管理科学和现代化生产技术等的日益发展,这类问题与日俱增,越来越受到运筹学、应用数学、计算机科学及管理科学等诸多学科的高度重视。本文就是针对这些新问题,主要对哈明距离下的若干网络逆问题进行了研究。全文共分为四章,第一章主要介绍与组合优化问题及逆问题相关的一些概念和预备知识。接着我们分别研究了不同问题的若干模型。第二章研究的是赋权哈明距离下最大流逆问题:对给定的连通有向网络N(V,A,c),每条弧都有一个容量改造费用,令f~0是网络N的一个可行流,如何改变网络弧上的容量使得f~0成为新容量下的最大流,且在哈明距离下产生的改造费用最小。我们总共研究了四种模型:对于总和型,我们把问题转化为求解剩余网络的一个受限制割,从而给出了时间复杂性为O(n~3)的多项式时间算法。对于瓶颈型,我们通过把问题转化为求解剩余网络的一个受限制瓶颈割问题,从而给出了时间复杂性为O(m+n·logn)的多项式时间算法。对于两种混合型,我们利用二分法思想,结合前面的算法,分别给出了时间复杂性为O(n~3·logm)和O(n~3)的多项式时间算法。第三章研究的是赋权哈明距离下最小—最大支撑树逆问题:对给定的连通图G=(V,E,c),每条边都有一个长度改造费用,令T~0是图G的一个支撑树,如何改变图上边的长度使得T~0成为新长度下的最小—最大支撑树,且在哈明距离下产生的改造费用最小。我们总共研究了四种模型:对于总和型,我们先给出了最优解的可能取值,然后通过求解图的受限最小割问题给出了时间复杂性为O(n~4)的多项式时间算法。对于瓶颈型,我们通过求解图的受限最小瓶颈割问题给出了时间复杂性为O(n~5)的多项式时间算法。对于两种混合型,我们利用二分法的思想,结合前面的算法,分别给出了时间复杂性为O(n~5)和O(n~4)的多项式时间算法。第四章研究的是赋权哈明距离下最小割逆问题:对给定的连通有向网络N(V,A,c),每条弧都有一个容量改造费用,令{X~0,(?)~0}是网络N的一个s-t割,如何改变网络弧上的容量使得{X~0,(?)~0}成为新容量下的最小割,且在哈明距离下产生的改造费用最小。我们研究了两种模型:对于总和型,我们利用背包问题的实例的多项式归约,证明了该问题是NP-难的,对于瓶颈型,通过利用最大流—最小割和哈明距离的性质,我们给出了时间复杂性为O(m·n~3)的多项式时间算法。更多还原

【Abstract】 Network optimization is one important branch of the combinatorial optimization, the goal is to find an optimal solution of the given problem. As the society advances, the inverse problems of network optimization arise. In these problems, a feasible solution is given which is not optimal under the current parameter values. And it is required to modify some parameters with minimum modification cost such that the given feasible solution forms an optimal solution. This inverse problem becomes increasingly conspicuous, attracting more and more attention from many disciplines, such as operations research, applied mathematics, computer science, management science and so on, as the computer science, the management science and the modem production technology develop. This thesis is organized into four chapters, and mainly deals with the inverse network problems under the weighted Hamming distance. In Chapter 1, we introduce some related basic concepts and knowledge. And then we discuss different models for the different problems.In Chapter 2, the inverse maximum flow problems under the weighted Hamming distance are discussed. In a given connected and directed network N(V,A,c), each arc has a specific modification cost. Let f~0 be a feasible flow of N. We are asked to modify the arc capacities such that f~0 forms a maximum flow of N and the modification cost of modified arcs is minimized under the weighted Hamming distance. Four models are studied. In the sum-type model, we resort to the method of the minimum cut of the residual network, to produce a polynomial algorithm which runs in O(n~3) time. In the bottleneck-type model, the method of the bottleneck minimum cut of the residual network is used to present a polynomial algorithm which runs in O(m + n·log n) time. And as for the model of two mixed types, using the bisection method and the algorithms given before, we present their polynomial algorithms that run in O(n~3·log m) time and O(n~3) time, respectively.In Chapter 3, we consider the following inverse min-max spanning tree problems under the weighted Hamming distance. In a given connected graph G(V. E. c), each arc has a specific modification cost. Let T~0 be a spanning tree of G. We are asked to modify the edge lengths such that T~0 forms a min-max spanning tree of G and the modification cost of modified edges is minimized under the weighted Hamming distance. Four models are studied. In the sum-type model, we are first given the range of the value, and use the method of the restricted minimum weight edge cut problem to produce a polynomial algorithm which runs in O(n~4) time. In the bottleneck-type model, the method for the restricted minimum bottleneck-type weight edge cut problem is adopted to present a polynomial algorithm which runs in O(n~5) time. And as for the model of two mixed types, using the bisection method and the algorithms given before, we present their polynomial algorithms that run in O(n~5) time and O(n~4) time, respectively.In Chapter 4, we consider the following inverse minimum cut problems under the weighted Hamming distance. In a given connected and directed network N(V, A, c), each arc has a specific modification cost. Let {X~0,(X|-)~0 } be an s - t cut of N. We are asked to modify the arc capacities such that {X~0, (X|-)~0 } forms a minimum cut of N and the modification cost of modified arcs is minimized under the weighted Hamming distance. Two models are studied. The first is a sum-type model, in which we show the problem is NP-hard by using the reduction from an instance of Knapsack Problem to an instance of the problem in polynomial time. In the latter bottleneck-type model, in terms of the properties of the maximum flow and minimum cut theory and the Hamming distance, we present a polynomial algorithm which runs in O(m·n~3) time.更多还原