组合优化和整数规划应用研究与软件实现关于分支定界法的思考 (2)
use branch and bound algorithm to solve them.At last,we analyze the result
of this kind of problem.
Keywords Combinatorial Optimization ,Integer Programming ,Branch and
Bound Algorithm ,Genetic Algorithm ,c++
目录
第 1章 绪论 . 1
1.1组合优化问题简介 1
1.2整数规划问题 1
1.2.1整数规划问题的背景与历史 1
1.2.2整数规划问题的挑战性 2
1.2.3完备性理论 2
第 2章 对于分支定界法的研究 . 4
2.1分支定界法的背景与思想 4
2.1.1分支定界法概述 4
2.1.2分支定界法的思想 4
2.2 分支定界法的过程 5
2.2.1 分支规则 5
2.2.2 定界规则 6
2.2.3 选择规则 7
2.2.4 消除规则 7
2.2.5 分支变量的选取 7
2.3 分支定界算法的程序实现及收敛性分析 8
2.4分支定界法的不足与改进 9
2.4.1线性整数规划问题中分支定界法的缺陷 9
2.4.2遗传算法简介 . 10
2.4.3遗传算法在分支定界法中的应用 . 11
第 3章 分支定界法的应用 14
3.1 问题的提出与描述 . 14
3.1.1 模型的建立 . 14
3.1.2 数据量增大时模型的修改 . 16
3.2 问题的计算及对结果的分析 . 16
3.2.1 程序实现过程中的问题 . 16
3.2.2 对结果的分析 . 17
结论 . 19
致谢 . 20
参考文献 . 21
附录 . 22
第 1 章 绪论
1.1 组合优化问题简介[7]
组合优化问题又称离散优化问题，是一类重要的优化问题。在信息的采集、
传递、加工过程中这类问题与日俱增，越来越受到运筹学、应用数学、计算机科
学及管理科学等诸多学科的高度重视。组合优化是近几十年发展起来的一门新兴
的交叉学科分支。在计算机科学、计算生物学、物流和供应链管理等新兴领域有
大量的应用。
组合优化（Combinatorial Optimization）问题的目标是从组合问题的可行解集
中求出最优解，通常可描述为：令Ω＝{s1，s2，…，sn}为所有状态构成的解空间，
C(si)为状态si对应的目标函数值，要求寻找最优解 s*，使得对于所有的si ∈ Ω，有
C(s∗
)＝minC(si)。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一
个重要分支。
典型的组合优化问题有旅行商问题（Traveling Salesman Problem－TSP）、加工
调度问题（Scheduling Problem，如Flow-Shop，Job-Shop）、0-1背包问题（Knapsack
Problem）、装箱问题（Bin Packing Problem）、图着色问题（Graph Coloring Problem）、
聚类问题（Clustering Problem）等。这些问题描述非常简单，并且有很强的工程代
表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行
时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合
爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究
兴趣。
1.2 整数规划问题
1.2.1整数规划问题的背景与历史
整数规划与组合最优化从广泛的意义上说，两者的领域是一致的，都是在有
限个可供选择的方案中，寻找满足一定标准的最好方案。整数规划是带整数变量
的最优化问题，即最大化或最小化一个全部或部分变量为整数的多元函数受约束