最小费用流逆问题的可行性研究

来源 :厦门大学 | 被引量 : 0次 | 上传用户:luwei2431231
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
给定网络N(V,A,u,l,c,s,t),所谓的最小费用流问题就是求一个达到给定流量(一般就是网络的最大流)而费用达到最小的可行流。而最小费用流逆问题则是,给定初始网络N(V,A,u,l,c,s,t)和初始可行流f0,在当前参数下,f0不是网络N的最小费用流,我们要通过最少的改变某些参数,使得f0在新的参数下是最小费用流。本文考虑的最小费用流逆问题改变的参数是容量的上界u和下界l,我们称之为容量型最小费用流逆问题。  本文主要针对容量型最小费用流逆问题的可行性及相关优化问题展开研究。所谓的可行性,就是给定网络N(V,A,u,l,c,s,t)和可行流f0,在当前参数下,f0不是网络N的最小费用流,我们是否可以通过改变容量的上界u和下界l,从而使得f0在新的参数下是最小费用流。首先我们证明了判断容量型最小费用流逆问题是否可行可以在多项式时间内完成。其次如果容量型最小费用流逆问题不可行,即无论如何修改容量的上界u和下界l,f0都不能成为N的最小费用流,则我们希望通过最少改变f0来使得最小费用流逆问题变得可行。这里我给出了两个算法来调整流f0。最后,我们给出了例子来进一步展示我们的算法。
其他文献
本文研究了几类竞争Lotka-Volterra系统的动力学性态:如平衡点的存在性和稳定性,周期轨的存在性以及不变环面的存在性等;并讨论了各类分岔现象:如Hopf分岔,同宿分岔,倍周期分
学位
本文针对一类具有HollingⅣ功能性反应函数的捕食系统,应用微分方程稳定性和定性理论、重合度理论,证明了系统正平衡点全局稳定性,极限环的存在唯一性和周期解的存在性。主要内
非线性发展方程,就是以时间t为其一个独立变量的非线性偏微分方程。从数学以及物理,生物,力学,化学,材料科学等自然科学分支中提出的许多问题,最后都归结为一个非线性发展方
笛卡尔乘积是大规模网络拓扑结构设计的一种重要方法,它能够从较小的模块结构开始,逐级扩展为大型结构并继承了原始结构许多好的拓扑性质。完全图是图论中最基本的图,也是网络设
作为我国高等学校的主体,地方高等院校实行校院二级管理是对建设现代大学制度的积极回应.然后,由于权力不明、职责不清、管理乏术、发展乏力等因素制约,地方高等院校二级学院
非线性约束广泛存在于控制系统中,其中饱和非线性就是一类较常见的非线性约束。在控制系统中加入饱和非线性因素会对系统的性能产生严重影响,甚至会导致系统不稳定。因此对饱
本文主要考虑了二维不可压缩微极性流体方程的柯西问题.我们利用关于角粘性系数的一致估计,证明了当角粘性趋于零(即γ→0)时的极限过程,并得到了收敛速度.  
不确定性与时滞是实际系统中普遍存在的现象。在实际系统中,由于测量误差、输入条件的变化、传感器等部件非正常工作及来自外界的干扰均会引起不确定性的出现。由于不确定性
近些年,顺序统计量的随机比较问题受到广泛关注。本文考虑非齐次相依样本的顺序统计量的随机比较问题,我们用copula,其中包括极值copula、阿基米德copula,刻画相依性,在比例反失效
在工程实际问题中针对具有病态数值特性的研究对象进行分析和建模时,奇异系统理论是一种有效的工具。奇异系统又被称为描述系统、微分代数系统、广义状态空间系统或半状态系