松约束运输问题的三角形回路算法  

Triangle-loop Algorithm for Loose-constrained Transportation Problem

作　　者：卢厚清[1] 杜婕[1] 刘建永[1] 余勤[1] 

机构地区：[1]解放军理工大学工程兵工程学院,南京210007

出　　处：《计算机工程与应用》2004年第30期74-75,106,共3页Computer Engineering and Applications

摘　　要：运输问题存在“多反而少”现象,这是由于在松约束模型中放宽了约束条件,使得可行域变大,产生了新的最优解。传统的松约束模型的解法,是在表上作业法的基础上,先求得对应紧约束模型的最优解,再进行调整。论文介绍了一种完全独立于紧约束模型的算法,并分析了该算法的正确性,最后对相同参数的紧约束和松约束模型的最优解进行比较,从而验证了算法的潜在实用价值。The Transportation Problem exists'more-for-less'paradox,which because the loose-constrained model has broadened the restriction,enlarged the feasible area,and bring new optimal solution.Traditional method based on diagram programming is to adjust the corresponding solution of strict-constrained model.This paper introduces a method completely independent of strict-constrained model,analyzes the correctness of this algorithm,then compares the solution of strict-constrained and loose-constrained model,which demonstrate that the approach proposed is adaptive to practical use.

关 键 词：松约束 紧约束“多反而少”悖论 时间复杂度 

分 类 号：O22[理学—运筹学与控制论]