带有模糊约束最短路问题的数学模型及算法

吉林大学学报(理学版)

带有模糊约束最短路问题的数学模型及算法

孙小军

宝鸡文理学院数学与信息科学学院, 陕西宝鸡 721013

收稿日期:2014-06-30 出版日期:2015-05-26 发布日期:2015-05-21
通讯作者: 孙小军 E-mail:bwlsxj@163.com

Mathematical Model and Algorithm for the ShortestPath Problem with Fuzzy Constraints

SUN Xiaojun

College of Mathematics and Information, Baoji University of Arts and Sciences, Baoji 721013, Shaanxi Province, China

Received:2014-06-30 Online:2015-05-26 Published:2015-05-21
Contact: SUN Xiaojun E-mail:bwlsxj@163.com

摘要/Abstract

摘要：

针对带有模糊约束的最短路问题, 在其模糊线性规划模型的基础上, 利用容差法和罚函数法对该模型进行转化, 得到了与原模型具有相同最优解与最优值的转化模型, 并提出一种修正的萤火虫算法求解转化模型. 数值算例结果表明, 该模型与算法对求解带有模糊约束的最短路问题有效.

关键词: 模糊约束, 最短路问题, 萤火虫算法, 修正算法

Abstract:

In order to solve the shortest path problem with fuzzy constraint, based on the fuzzy linear programming model, tolerance method and penalty function method were adopted to convert the original model to obtain a transformed model with the same optimal solution and optimal value as those of the original model. Then, a modified firefly algorithm was proposed to solve the transformed model. In addition, the computational complexities of the modified algorithm as well as the firefly algorithm were analyzed and compared. Finally, numerical example was given to illustrate the efficiency of the new model and algorithm to solve the shortest path problem with fuzzy constraint.

Key words: fuzzy constraints, shortest path problem, firefly algorithm, modified algorithm

中图分类号:

TP301.6

孙小军. 带有模糊约束最短路问题的数学模型及算法[J]. 吉林大学学报(理学版), 2015, 53(03): 478-482.

SUN Xiaojun. Mathematical Model and Algorithm for the ShortestPath Problem with Fuzzy Constraints[J]. Journal of Jilin University Science Edition, 2015, 53(03): 478-482.