首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 122 毫秒
1.
可满足合取范式(CNF)公式F到极小不可满足公式MU(1)的扩张是,对给定的CNF公式F,是否存在一个公式G满足条件var(G)包含var(F)并使得F+G∈MU(1)。Horn公式到MU(1)公式的扩张问题可在多项式时间内解决,但对一般CNF公式F的扩张问题,至今尚未解决。这里我们将给出一个多项式时间的算法解决这一问题。  相似文献   

2.
给定一个结合A,A可嵌入一个有单位元的环(即Dorroh扩张),本文将Dorroh扩张进行了推广,给出它的应用和根的刻划。  相似文献   

3.
讨论了运输网络的一类最优扩张问题,在有限的投资条件下,最有效地扩充容量,使运输网络达到一个预期的流值。  相似文献   

4.
主要研究网络优化领域中一种具有动态特征的最短路问题,给出了离散时间模型下关于时间和费用的动态最短路问题的描述,通过引入时间扩张图概念,将动态最短路问题转化为对应的静态网络中的最短路问题,讨论了两类动态最短路问题的复杂性并给出算法。  相似文献   

5.
考虑到时间对最小费用流问题中各个参数的影响,首先通过对动态最小费用流问题的各参数的定义建立了动态最小费用流问题的数学模型,在这样的有向网络里,流可以在中间点上停留一段时间,弧的容量以及中间点的容量随时间变化,流经过弧时所需的费用也随时间变化;在此模型基础上给出了动态最小费用增广链的定义并证明了与其相关的定理,并在最后给出求解动态最小费用流问题的一个算法。  相似文献   

6.
给定一个连通网络,找两点之间的最短路,作为两点之间的流量路径。每条路径都有一定的需求,网络中每条边的容量至少为经过该边的所有路径的需求之和,若某条边的容量小于经过该边的所有路径的需求之和,则需要对其容量进行扩充。每种扩充方案的扩充费用是关于扩充容量的函数。本文给出解决该问题的一个多项式时间算法,使得各边容量达到需求,且总的扩充费用最小。  相似文献   

7.
本文研究的是一类特殊的极大+和支撑树在调整和权值下的逆问题.给定一个边赋权连通网络G=(VE,c,w),对于每一条边e∈E,已知一个费用c(e)和一个权值叫(e),极大+和支撑树问题是指寻找一棵支撑树T*,使得其是权值marxw(e)+∑c(e)最小的一棵支撑树.而在极大+和支撑树的逆问题中,给定一棵支撑树%,eET它不是已知网络中最优的极大+和支撑树,要求调整网络中各边的费用c(e),使死变成调整后网络中最优的极大+和支撑树,目标函数是使得在l1模意义下的边权调整费用尽可能的小.本文针对已知网络中各边费用都相等这一特殊情况,给出了求解该逆问题的列生成算法,每次迭代时入基向量的选择可以转化为一个新参数下的极大+和支撑树问题,从而可在多项式时间内确定入基向量的选择.本文最后给出了一个实例说明算法的有效性.  相似文献   

8.
对多收点容量网络最小费用流问题,证明了当收点处的净流入量增加时,其总的最小费用沿着该收点的方向的增长速率也相应增加  相似文献   

9.
针对将网络最小费用最大流问题转化为单目标优化问题进行求解的缺陷,提出网络最小费用最大流的双目标优化模型,并引入多目标遗传算法.对最小支撑树对应的余树弦流量初始值进行编码,通过解码和回路矩阵计算流量网络树枝的流量.在网络最小费用、最大流量双目标函数和网络结点容量、网络分支容量约束条件基础上,按照多目标优化理论构建增广最小...  相似文献   

10.
本文讨论了σ有限测度μ从(X,A)到(X,σ(A∪{C}))上的扩张测度的唯一性问题给出了这种扩张唯一性的四个充分条件。  相似文献   

11.
认知无线电是解决频谱资源紧张,提高频谱利用率的有效方式之一。在保护授权用户不受过度干扰的前提下,为了充分利用基于OFDM的认知无线网络频谱资源,在分别考虑频谱检测可靠性和互干扰对资源分配影响的基础上,构建了一个联合功率控制和子载波分配的最优化目标。考虑算法实际可行性,提出了3个次优的基于最小资源代价增量的算法,即最小功率代价增量算法、最小干扰代价增量算法以及最小功率干扰加权和代价增量算法。数值仿真表明,相比于现有的静态等功率资源分配,所提算法的吞吐量性能均有明显提升,其中,最小功率干扰加权和代价增量算法整体性能最好。  相似文献   

12.
The paper points out the relationship between the bottleneck and the minimum cutset of the network, and presents a capacity expansion algorithm of network optimization to solve the network bottleneck problem. The complexity of the algorithm is also analyzed. As required by the algorithm, some virtual sources are imported through the whole positive direction subsection in the network, in which a certain capacity value is given. Simultaneously, a corresponding capacity-expanded network is constructed to search all minimum cutsets. For a given maximum flow value of the network, the authors found an adjustment value of each minimum cutset are‘s group with gradually reverse calculation and marked out the feasible flow on the capacity-extended networks again with the adjustment value increasing. All this has been done repeatedly until the original topology structure is resumed. So the algorithm can increase the capacity of networks effectively and solve the bottleneck problem of networks.  相似文献   

13.
构造指派问题的最小费用最大流模型,并将基于对偶原理的允许边算法用于该模型,提出了求解指派问题的一种新算法。该算法按照互补松驰条件,通过修改已标号节点的势,在容量-费用网络中逐步扩大允许网络,并在其中增广流量,直至求得容量-费用网络的最小费用最大流,此最大流中的非0流边即对应于指派问题的最优指派。在迭代过程中,后续迭代充分利用了上一迭代的信息,有效节省了计算量。对于非标准指派问题,可以直接求解,而不需要先将其转化为标准形式。  相似文献   

14.
容量制约下的交通网络流模型是一个非线性规划问题,表现为在路段容量约束条件下的用户均衡网络的优化,这个模型能够描述交通网络的拥挤特征.容量制约下的交通网络流模型可以转换成传统的用户均衡模型的形式,为此对于任意一个给定的结点对,定义了一个新梯度,这个新梯度等于所有使用路径的费用的均值.利用新梯度的特征,并结合惩罚函数方法,可以获得容量制约下的交通网络流的解.数值实验表明所提出的方法表现出优良的收敛性能.  相似文献   

15.
为了在网络中更好地部署对等网络(P2P)流量缓存,从而优化网络的性能,提出了一个评价方法量化在不同链路上部署P2P缓存的收益。基于该方法建立了最优化模型:在给定部署开销的约束下最大化收益。分析了问题复杂度,提出了优先选择收益开销比的链路进行部署的启发式算法求解。对实际校园网络的仿真结果表明:在10%的链路上部署P2P流量缓存,能够降低30%的平均链路利用率。该文提出的P2P流量缓存部署模型和算法可以有效地指导P2P缓存的部署,优化网络性能。  相似文献   

16.
分析交通网络系统的特点,研究混合交通OD结构的关联性,在定量分析路网交通流受交通容量、交通安全及交通服务能力等条件限制的基础上,研究路网利用效益最大化及路网交通流量最大化问题,构建一种路网交通流的二层平衡规划模型。利用先验分布理论和极大熵原理,给出模型的极大熵函数解,进一步证明解的存在与唯一性。模型一方面描述了管理部门对路网交通的优化配置,一方面描述了出行者充分利用路网资源的最优选择。最后通过一个实例,分析模型计算的相关结论。  相似文献   

17.
为了在网络中更好地部署对等网络(P2P)流量缓存,从而优化网络的性能,提出了一个评价方法量化在不同链路上部署P2P缓存的收益。基于该方法建立了最优化模型:在给定部署开销的约束下最大化收益。分析了问题复杂度,提出了优先选择收益开销比的链路进行部署的启发式算法求解。对实际校园网络的仿真结果表明:在10%的链路上部署P2P流量缓存,能够降低30%的平均链路利用率。该文提出的P2P流量缓存部署模型和算法可以有效的指导P2P缓存的部署,优化网络性能。  相似文献   

18.
讨论一类在交通网络中设立服务站的最优选址问题。在给定的网络G(V,A)中有r对O-D用户流。在总建站费用最小的目标下考虑3个因素:每对用户流都能得到服务;每对用户流的时间满意度不低于某一给定值;每个服务站的服务能力是有限制的。通过分析这类问题的特征后,形成一个线性混合整数规划模型,并给出了求解实例。  相似文献   

19.
多目标优化量子免疫算法求解基站选址问题   总被引:3,自引:1,他引:2  
为了解决带容量约束WCDMA网络的基站选址问题,提出了一个基于多目标优化量子免疫算法的基站选址优化方案.设计了基站选址问题的数学模型,给出了多目标优化量子免疫算法框架,并进行了实验验证.实验结果表明:算法方案能以较小的基站建设代价满足覆盖要求,具有较好应用价值.  相似文献   

20.
基于复杂网络理论,从网络拓扑结构角度对配电网网架结构的脆弱性进行评估。建立了以配电网投资及运行费用最小、结构脆弱性指标最优为目标的配电网网架多目标优化规划模型。采用改进最小生成树算法,并将经济性指标的减少率和结构脆弱性指标的增长率之和作为迭代过程中的目标函数,将多目标问题转化为单目标进行求解,通过16节点算例验证了该方法在求解多目标配网优化规划问题中的可行性。算例结果表明,所建立的优化规划模型能够有效地评估配电网的结构脆弱性,并能求得结构稳定、经济性好的规划方案。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号