共查询到10条相似文献，搜索用时 31 毫秒
1.
《厦门大学学报(自然科学版)》2017,(6)
针对容量型最小费用流逆问题的可行性及相关优化进行研究,证明了判断容量型最小费用流逆问题是否可行可以在多项式时间内完成.如果容量型最小费用流逆问题不可行,即无论怎样修改容量的上界u和下界l,初始流f0都不能变为新网络的最小费用流.给出了两种调整初始流f0的算法,证明了通过最少修改初始流f0,可以使最小费用流逆问题变为可行. 相似文献
2.
构造指派问题的最小费用最大流模型,并将基于对偶原理的允许边算法用于该模型,提出了求解指派问题的一种新算法。该算法按照互补松驰条件,通过修改已标号节点的势,在容量-费用网络中逐步扩大允许网络,并在其中增广流量,直至求得容量-费用网络的最小费用最大流,此最大流中的非0流边即对应于指派问题的最优指派。在迭代过程中,后续迭代充分利用了上一迭代的信息,有效节省了计算量。对于非标准指派问题,可以直接求解,而不需要先将其转化为标准形式。 相似文献
3.
讨论在总流量可变动的情况下，网络最小费用流问题的解法。分别就单源单汇和多源多汇情况构造不同的辅助网络，将原网络中的最小费用流问题转化为辅助网络中的最小费用循环流问题，然后用瑕疵算法求最小费用循环流问题的最优解，这样在求出原网络中最小费用流的同时，也获得了总流量的最优取值。 相似文献
4.
为计算矿井最大通风量,针对最短增广链算法随机选取增广链,造成增广链缺失和极值流偏小的问题,提出一种基于最小分支剩余容量的矿井通风网络极值流算法。该算法在选取增广链时,选择中间分支剩余容量最小的增广链进行增广;每次增广完毕后,优先选择与增广完毕的增广链包含相同分支的增广链进行下一次增广。利用Excel Solver解算模型与BA无标度随机网络进行仿真实验,结果表明该算法比最短增广链算法解算时间短,且避免了增广链缺失。研究结论为矿井最大通风量的计算提供理论参考。 相似文献
5.
6.
厍向阳 《江苏大学学报(自然科学版)》2011,32(3):341-345,358
针对将网络最小费用最大流问题转化为单目标优化问题进行求解的缺陷,提出网络最小费用最大流的双目标优化模型,并引入多目标遗传算法.对最小支撑树对应的余树弦流量初始值进行编码,通过解码和回路矩阵计算流量网络树枝的流量.在网络最小费用、最大流量双目标函数和网络结点容量、网络分支容量约束条件基础上,按照多目标优化理论构建增广最小... 相似文献
7.
针对网络最大流的计算问题,提出了一种网络最大流计算模型的实现方法,具体作法是灵活运用栈和结构数组以实现算法功能．首先创建邻接表,其结构包含边的方向、容量、流量等信息.然后根据邻接表采用标号法寻找增广链,在寻找过程中采用深度优先遍历和广度优先遍历的方法把点存入栈中,并用一数组保存所经过的路径．直至找出最大流及各边的流量. 相似文献
8.
用对偶原理求解最小费用流的一种新算法 总被引：1，自引：1，他引：0
基于对偶原理提出了求解最小费用流的一种新算法,该算法不需要传统方法中的构造剩余网络以及求最短路等步骤,而是保持互补松弛条件不变,通过在原网络中修改节点的势,给节点标号寻求目标流。并给出了新算法正确性的证明。算例表明该算法可明显减少迭代步骤。 相似文献
9.
针对传统优化算法在处理具有一定非线性功能函数的结构可靠性分析问题时出现迭代次数较多或精确度不够的问题,提出了一种基于人群搜索算法和增广乘子法的混合可靠性分析方法.该算法以可靠指标最小为目标函数,以影响结构可靠指标的随机变量构成的极限状态方程为约束条件建立结构可靠性优化数学模型,并使用增广乘子法将有约束优化问题转换为无约... 相似文献
10.
建立了连续时间网络上的最小费用流问题的数学模型；证明了连续时间网络中的增广流的存在性定理和最优性定理；最后给出求最小费用流的算法． 相似文献
