共查询到17条相似文献,搜索用时 109 毫秒
1.
带有模糊容量限制的网络中的最佳最小费用最大流 总被引:2,自引:0,他引:2
本文主要讨论当网络中的弧容量限制和最大流目标要求带有模糊性时的最小费用最大流问题,通过构造带费用的增量网络并设法寻找其中的最佳最小费用路,给出了求解这类模糊网络流问题的算法。 相似文献
2.
遗传算法求解带容量限制的最小费用流问题 总被引:1,自引:0,他引:1
研究了带容量限制的带固定费用和可变费用的最小费用流问题,发现该问题是混合0-1整数规划问题,不存在多项式算法.在研究了最优解的结构后,结合最优解的结构特点为之设计了遗传算法,然后构造了一个100个节点的特殊网络,用计算机做了100例计算,验证了该算法具有很好的近似比和很快的收敛速度. 相似文献
3.
分配网络流广泛应用于解决水源、电力的调度及工厂的产品运输、分配、合成等问题.本文提出一个分配网络流的最小费用流算法. 相似文献
4.
《数学的实践与认识》2017,(18)
构造(m,n,k)指派问题的最小费用流模型,并将基于对偶原理的最小费用流的允许边算法求解该模型,提出求解(m,n,k)指派问题的一种算法.算法直接在其对应的网络中保持互补松弛条件不变,通过调整节点势以扩大允许网络从而寻求增广链并进行流量增广,直至在网络中得到流量为k的最小费用流,此时非O流边对应(m,n,k)指派问题的最优解.给出了(m,n,k)指派问题的最优解及多重最优解的重要性质,数值试验表明算法有效可行. 相似文献
5.
带有模糊容量限制的网络中的最佳最小费用量大流 总被引:2,自引:2,他引:0
本文主要讨论当网络中弧容量限制和最大流目标要求带有模糊性时的最小费最大流问题,通过构造带费用的增量网络并设法寻找其中的最佳最小费用路,给出了求解这类模糊网络流问题的算法。 相似文献
6.
研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性. 相似文献
7.
8.
9.
10.
本文提出并讨论了最小费用流的反问题:如何在有限的投资条件下,最有效地扩充容量参数,达到一个予定的流值。建立了反问题的数学模型,给出了最优参数配置的算法。 相似文献
11.
《European Journal of Operational Research》2005,164(1):89-103
We address the two-commodity minimum cost flow problem considering two objectives. We show that the biobjective undirected two-commodity minimum cost flow problem can be split into two standard biobjective minimum cost flow problems using the change of variables approach. This technique allows us to develop a method that finds all the efficient extreme points in the objective space for the two-commodity problem solving two biobjective minimum cost flow problems. In other words, we generalize the Hu's theorem for the biobjective undirected two-commodity minimum cost flow problem. In addition, we develop a parametric network simplex method to solve the biobjective problem. 相似文献
12.
We present algorithms for the single-source uncapacitated version of the minimum concave cost network flow problem. Each algorithm exploits the fact that an extreme feasible solution corresponds to a sub-tree of the original network. A global search heuristic based on random extreme feasible initial solutions and local search is developed. The algorithm is used to evaluate the complexity of the randomly generated test problems. An exact global search algorithm is developed, based on enumerative search of rooted subtrees. This exact technique is extended to bound the search based on cost properties and linear underestimation. The technique is accelerated by exploiting the network structure. 相似文献
13.
Jiang et al. proposed an algorithm to solve the inverse minimum cost flow problems under the bottleneck-type weighted Hamming distance [Y. Jiang, L. Liu, B. Wuc, E. Yao, Inverse minimum cost flow problems under the weighted Hamming distance, European Journal of Operational Research 207 (2010) 50–54]. In this note, it is shown that their proposed algorithm does not solve correctly the inverse problem in the general case due to some incorrect results in that article. Then, a new algorithm is proposed to solve the inverse problem in strongly polynomial time. The algorithm uses the linear search technique and solves a shortest path problem in each iteration. 相似文献
14.
Rainer E. Burkard Helidon Dollani Phan Thien Thach 《Journal of Global Optimization》2001,19(2):121-139
We consider minimum concave cost flow problems in acyclic, uncapacitated networks with a single source. For these problems a dynamic programming scheme is developed. It is shown that the concave cost functions on the arcs can be approximated by linear functions. Thus the considered problem can be solved by a series of linear programs. This approximation method, whose convergence is shown, works particularly well, if the nodes of the network have small degrees. Computational results on several classes of networks are reported. 相似文献
15.
M. Sakarovitch 《Mathematical Programming》1973,4(1):1-20
This paper shows that the linear programming formulation of the two-commodity network flow problem leads to a direct derivation of the known results concerning this problem. An algorithm for solving the problem is given which essentially consists of two applications of the Ford—Fulkerson max flow computation. Moreover, the algorithm provides constructive proofs for the results. Some new facts concerning feasible integer flows are also given. 相似文献
16.
A. Sedeño-Noda C. González-Martín S. Alonso-Rodríguez 《Computational Optimization and Applications》2010,47(2):289-305
We address the two-commodity maximum flow problem on undirected networks. As a result of a change of variables, we introduce
a new formulation that solves the problem through classical maximum flow techniques with only one-commodity. Therefore, a
general strategy, based on this change of variables, is defined to deal with other undirected multi-commodity problems. Finally,
we extend the single objective problem to a bicriteria environment. We show that the set of efficient solutions of the biobjective
undirected two-commodity maximum flow problem is the set of alternative optimum solutions of the undirected two-commodity
maximum flow problem. In addition, we prove that the set of efficient extreme points in the objective space has, at most,
cardinality two. 相似文献
17.
Antoon Kolen 《European Journal of Operational Research》1983,12(3):266-278
Given a tree network on n vertices, a neighborhood subtree is defined as the set of all points on the tree within a certain radius of a given point, called the center. It is shown that for any two neighborhood subtrees containing the same endpoint of a longest path in the tree one is contained in the other. This result is then used to obtain O(n2) algorithms for the minimum cost covering problem and the minimum cost operating problem as well as an O(n3) algorithm for the uncapacitated plant location problem on the tree. 相似文献