最优指派问题DNA算法  

Algorithm of DNA computing on optimal assignment problems

作　　者：周康[1] 同小军[1] 许进[2] 

机构地区：[1]武汉工业学院数理科学系,湖北武汉430023 [2]华中科技大学控制科学与工程系,湖北武汉430074

出　　处：《系统工程与电子技术》2007年第7期1183-1187,共5页Systems Engineering and Electronics

基　　金：国家自然科学基金资助课题(60403002)

摘　　要：对求最小值的最优指派数学模型,设计并实现了DNA计算算法。首先经过特殊的DNA编码将二维的决策变量和二维的效益值编入DNA序列中;然后通过杂交实验和分离实验得到指派问题的全部可行解;最后通过电泳实验和检测实验获得最优指派问题的最优解。证明了算法的复杂性并举例说明了算法的可行性。分别给出了求最大值的最优指派问题和人数与工作数不等的最优指派问题的处理方法。An algorithm of DNA computing is designed for minimum assignment problems, in which after planar decision-making variable and planar benefit value are compiled in DNA sequence through specific DNA encoding, all feasible solutions are gained with hybridization experiment and separating experiment, and then all optimization solutions are obtained with electrophoresis experiment and checking experiment. The complexity of the DNA algorithm is proved and its feasibility is explained by an example. Respective methods dealing with the maximal assignment problem and the people and worker＇s unequal number assignment problem are brought forward.

关 键 词：DNA计算 指派问题 分离实验 检测实验 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]