共查询到20条相似文献,搜索用时 125 毫秒
1.
《数学的实践与认识》2020,(13)
根据模糊数学原理,定义了一个三角模糊数的排序函数,并利用可能度研究三角模糊数的排序方法.对一组待排序的三角模糊数,根据不同情况,分别给出了相应的可能度计算公式,其结果反映的是一个三角模糊数大于另一个三角模糊数的可能程度,该公式具有计算方便等特点.最后,由两两比较的结果建立一个可能度矩阵,并给出了一种基于可能度矩阵的三角模糊数排序算法.应用实例表明,这种算法具有一定的合理性. 相似文献
2.
运用结构元理论来求解具有风险偏好的、带有模糊权值的网络最短路问题.首先,简要介绍模糊结构元及相关定理.之后,提出了组合序,证明组合序是全序.组合序含有参数θ,随着θ的取值范围不同,序反映风险偏好的类型不同.在组合序和相关定理的基础上,证明了模糊网络最短路的判定定理,定理表明:求模糊网络最短路等价求一经典网络最短路,且风险偏好大小由θ的取值来确定.最后,通过一个例子来说明求解过程. 相似文献
3.
4.
带有模糊约束的最优路 总被引:1,自引:0,他引:1
到目前为止,最短路问题已有很多好的算法,但这些算法都是假定所有弧的长度均为确定的数值;而在实际中,常会遇到一些网络,其所有弧的长度具有不确定性.本文将这种不确定性以模糊数的形式给定,然后提出了模糊最优路的概念,并针对L-R型模糊数给出了具体的算法. 相似文献
5.
6.
基于广义判断形式的模糊排序方法 总被引:7,自引:1,他引:7
广义判断下的AHP(GJAHP)是一种广义AHP。它是在研究不完全信息下的决策排序问题时,通过构造广义判断矩阵的数学模型而建立的一种广义AHP。本文应用集值统计的方法,在区间判断标度基础上确定模糊判断矩阵元素的正模糊数表示。给出了基于模糊区间数排序权值向量的特征根算法。讨论了Fuzzy环境下求解各种判断形式的模糊排序权值向量的方法。 相似文献
7.
8.
9.
由两个模糊数的隶属函数确定三个面积,据此建立一个对模糊数进行大小比较的可能度计算公式.公式表达式非常简洁,同时还具有传递性、互补性等诸多良好的性质,因而具有很强的实用性和可操作性.对给定的一组模糊数,先利用两两比较的结果建立一个可能度矩阵,同时给出基于可能度矩阵的模糊数排序算法.最后给出一个排序算法的实例. 相似文献
10.
讨论了如何利用结构元理论来解决模糊数的排序问题.首先,给出了四种经典的模糊数排序方法,并证明了这四种方法都可以利用结构元理记来表述;进而,提出了一种基于结构元理论的排序方法,给出了该方法的性质,并同传统方法进行了比较. 相似文献
11.
A network with its arc lengths as imprecise number, instead of a real number, namely, interval number and triangular fuzzy
number is considered here. Existing ideas on addition and comparison between two imprecise numbers of same type are introduced.
To obtain a fuzzy shortest path from a source vertex to all other vertices, a common algorithm is developed which works well
on both types of imprecise numbers under consideration. In the proposed algorithm, a decision-maker is to negotiate with the
obtained fuzzy shortest paths according to his/her view only when the means are same but the widths are different of the obtained
paths. Otherwise, a fuzzy optimal path is obtained to which the decision-maker always satisfies with different grades of satisfaction.
All pairs fuzzy shortest paths can be found by repeated use of the proposed algorithm. 相似文献
12.
This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm. 相似文献
13.
The shortest path problem in a network G is to find shortest paths between some specified source vertices and terminal vertices when the lengths of edges are given. The structure of the optimal solutions set on the shortest paths is studied in this paper. First,the conditions of having unique shortest path between two distinguished vertices s and t in a network G are discussed;Second,the structural properties of 2-transformation graph (?) on the shortest-paths for G are presented heavily. 相似文献
14.
New models for shortest path problem with fuzzy arc lengths 总被引:1,自引:0,他引:1
This paper considers the shortest path problem with fuzzy arc lengths. According to different decision criteria, the concepts of expected shortest path, α-shortest path and the most shortest path in fuzzy environment are originally proposed, and three types of models are formulated. In order to solve these models, a hybrid intelligent algorithm integrating simulation and genetic algorithm is provided and some numerous examples are given to illustrate its effectiveness. 相似文献
15.
Xiaoge Zhang Qing Wang Andrew Adamatzky Felix T. S. Chan Sankaran Mahadevan Yong Deng 《Journal of Optimization Theory and Applications》2014,163(3):1049-1056
The shortest path problem is among fundamental problems of network optimization. Majority of the optimization algorithms assume that weights of data graph’s edges are pre-determined real numbers. However, in real-world situations, the parameters (costs, capacities, demands, time) are not well defined. The fuzzy set has been widely used as it is very flexible and cost less time when compared with the stochastic approaches. We design a bio-inspired algorithm for computing a shortest path in a network with various types of fuzzy arc lengths by defining a distance function for fuzzy edge weights using \(\alpha \) cuts. We illustrate effectiveness and adaptability of the proposed method with numerical examples, and compare our algorithm with existing approaches. 相似文献
16.
In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible. 相似文献
17.
A. M. Frieze 《Mathematical Programming》1976,11(1):150-157
The group knapsack and knapsack problems are generalised to shortest path problems in a class of graphs called knapsack graphs. An efficient algorithm is described for finding shortest paths provided that arc lengths are non-negative. A more efficient algorithm is described for the acyclic case which includes the knapsack problem. In this latter case the algorithm reduces to a known algorithm. 相似文献
18.
Fred Glover Darwin Klingman Nancy Phillips 《European Journal of Operational Research》1984,17(1):123-124
In this paper an algorithm is presented for determining the K best paths that may contain cycles in a directed network.The basic idea behind the algorithm is quite simple. Once the best path has been determined it is excluded from the network in such a way that no new path is formed and no more paths are excluded. This step leads to an enlarged network where all the paths, but the best one, can be determined. The method is repeated until the desired paths have been computed.The proposed algorithm can be used not only for the classical K shortest paths problem but also for ranking paths under a nonlinear objective function, provided that an algorithm to determine the best path exists.Computational results are presented and comparisons with other approaches for the classical problem are made. 相似文献
19.
The time-constrained shortest path problem is an important generalisation of the classical shortest path problem and in recent years has attracted much research interest. We consider a time-schedule network, where every node in the network has a list of pre-specified departure times and departure from a node may take place only at one of these departure times. The objective of this paper is to find the first K minimum cost simple paths subject to a total time constraint. An efficient polynomial time algorithm is developed. It is also demonstrated that the algorithm can be modified for finding the first K paths for all possible values of total time. 相似文献
20.
针对道路堵塞如节假日导致的临时最短配送路径失效的问题,提出配送网络最优路径选择模型,并设计了求解快递配送网络关键边和最优路径的算法。首先,计算出整个网络的关键边,掌握配送网络特征;其次,考虑顾客时间要求,研究不完全信息(中断无法提前预知,只有到达中断边的起点处才可知)下的最优路径,根据最短路径上各边新的特点,计算出每条边中断后对应的一组备用路径,再选择运输时间小于或等于顾客可等待时间的路径为有效路径,考虑道路堵塞情况,从有效路径中选择最优路径;最后,结合配送网络的实际情况对最优路径进行了算例分析。 相似文献