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