文档介绍：摘要和启发式规则提出了组合优化问题的精确求解方法,用于快速求解余下的子问题。三机床加工调度问题、痶背包问题、旅行推销员问题和坦克战中武器一目标分配问题。解同顺序加工调度问题的启发式双侧广度优先搜索方法。实验结果表明:当加工工序数目较少时,利用这种精确求解方法求解需要搜索的次数很少。种结构较好的最小卜树的基础上可以产生质量较好的近似解。论文构造了边对权值用于更得它的最优解。为了解决大规模组合优化问题,人们一直在探索不同的搜索策略,希望能够提高搜索效率,但是求取最优解十分困难,实际应用中常常以近似解代替最优解。已有方法主要采用启发式策略避免陷入局部极值,没有充分利用问题的相关信息,无法避免大量的重复搜索。为了缩小搜索范围,减少重复搜索量,在较短时间内得到质量更高的近似解甚至精确解,论文提出了基于状态转移的组合优化方法,并使用这种方法求解具体问题。论文提出了基于状态转移的组合优化方法,利用问题的领域知识,对问题进行分类,问题的上界陆、近似解以及其他相关信息降低问题的维数,晟后用精确求解方法求基础还提出了利用元素间关系降维的方法、基于特征值的降维方法、把问题分解成多个子问题的降维方法、基于推理的降维方法和基于评价函数的降维方法。论文提出了一些基本的改进近似解的方法,与定界算法一起用于简化问题。论文结合动态规划方法、定界算法利用基于状态转移的组合优化方法研究了四个组合优化问题的求解方法,包括同顺序针对同顺序三机床加工调度问题,提出了一种下界算法用于选择问题的第一个加工工接近问题的下界,绝大部分是问题的最优解。论文还提出了一种较好的近似方法求解一般针对疘背包问题,物品的重量与价值不相关或者线性相关时已有相应的快速精确求解方法;但物品的重量与价值非线性相关时该问题尚无快速精确求解方法。基于此,论文提出了这种情况下背包问题的上界算法、降维方法简化问题,改进近似解,最后利用精确求解方法求解余下的子问题,实现了背包问题的快速求解。针对旅行推销员问题,提出了一种在最小皇鞯幕∩系蠼獾南陆缢惴ê徒魄加有效地简化问题,提出了简化旅行推销员问题的四种降维方法。最后综合近似方法、下界算法、降维方法和精确求解方法构成基于状态转移的组合优化方法用于求取问题的精确针对坦克战中的武器一目标分配问题,研究时把它分解成三个子问题:确定对不同毁损程度的目标攻击的武器数最、具体目标选择和弹药选择。分别建立了各个子问题的模型,由于组合优化问题的解空间十分庞大,使用精确求解方法无法在确定多项式时间内求主要工作如下:对不同类别的问题寻求不同的近似方法,并且在迭代求解过程中,逐步改进近似解,利用解余下的子问题。论文提出了利用当前最优解与上界陆相比较的降维方法,以它为件,提出了一种评价函数用于求解时选择后续工件。改变第一个加工工件或者评价函数中的参数可能得到更好的解。实验结果表明:使用这种方法求得的解对应的总加工时间非常的同顺序加工调度问题。最后综合动态规划方法、下界算法和近似方法提出了一种精确求解方法,这种下界算法不仅可以得到问题的下界,还可以得到结构较好的最小卜树,在这解。国防科学技术大学研究生院学位论文
关键词:状态转移,组合优化,非多项式确定问题,降维方法,定界算法,启发式提出了坦克战中确定对不同毁损程度的目标攻击的武器数量的算法、标选择方法和弹药选择方法,提出了目标选择问题的上界算法。坦克战中武器~目标问题求解方法可以有效利用基于状态转移的组合优化方法快速精确求解组合优化问题的关键是获取较好的定界算法和问题的近似求解方法。文中提出的降维方法,从一定程度上弥补了近似求解方法、地提高坦克部队的战斗力。实验结果表明:基于状态转移的组合优化方法是一种有效的组合优化问题求解方法。定界算法存在的不足。旅行推销员问题,琹背包问题,同顺序加工调度问题,
.施/,琩...—瓸甀,··.甀
:——————型些兰堕些些璧些圣——:;———一甈每.:琖甅琩痩.,.:,甌,,,琀,.。
基王挞查整整的塑叠选丝左洼盈壅——日期:埘年争月日日期:捌年以月日作者指导教师签名:忝阚学位论文作者签名:之童型学位论文作者签名:曼延型独创性声明学位论文版权使用授权书羹王迭查整壁鲍塑佥值氆左选堡嚣本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的通方外,论文中不包含其他人已经发表和撰写过的研究成果,也不包含为获得国防科学技术大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国防科学技术大学可以保留并向国家有关部门或机构