对货郎担问题指派解法的一点探讨  

作　　者：马晓娜[1] 

机构地区：[1]宿州学院数学与统计学院,安徽宿州234000

出　　处：《赤峰学院学报（自然科学版）》2012年第10期4-6,共3页Journal of Chifeng University(Natural Science Edition)

基　　金：安徽省优秀青年人才基金项目(2011SQRL154)

摘　　要：货郎担问题是组合优化中的著名问题,到目前为止它还没有一个有效算法,本文把它转化为增加限制条件的指派问题,利用指派问题的差额法的变形算法来进行计算,此法适合于求解对称形式的距离矩阵,对于非对称形式的距离矩阵我们也找出了算法,以后再作探讨.此法解得的初始解一般为最优解或接近最优解,当解得的初始解不是最优解时,也给出了改进方法,以及合并两个以上回路的方法.该算法优于传统算法,而且具有一定的实用性.

关 键 词：指派问题 差额法 TSP问题 

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