- 上一篇：数学分析中不等式证明的常用方法
- 下一篇：线性无关的向量组正交化方法探讨
摘要:本文主要研究了利用分枝定界算法求解运筹学中的整数线性规划问题.首先对分枝定界算法相关知识进行了简要的叙述,并对该算法思想以及计算步骤进行了详细的说明;进而深入到分枝定界算法在运筹学中的应用,在此采用分枝定界算法解决了指派问题和投资问题;最后,又设计了分枝定界算法在 中解决整数线性规划问题的程序框架.42967
毕业论文关键词:分枝定界算法;整数线性规划;指派问题;投资问题
Application of the Branch and Bound Algorithm
in Operational Research
Abstract: This paper mainly studies which the branch and bound algorithm is used to solve the integer linear programming problems in operational research. First, the branch and bound algorithm is briefly introduced, its basic idea and steps are explained in detail. Then, application of the branch and bound algorithm in operatio-
nal research are explored in depth, for example, the assignment problem and the investment problem are solved. At last, the procedural framework of the branch and bound algorithm is designed in software to solve the integer linear programming problem.
Key words: The branch and bound algorithm; Integer linear programming; assign- ment problem ; investment problem
目 录
摘 要 1
引言 2
1.分枝定界算法 3
1.1分枝定界算法概述 3
1.2分枝定界算法的基本思想 3
1.3分枝定界算法的计算步骤 5
2.分枝定界算法在运筹学中的应用 6
2.1求解指派问题 6
2.2求解投资问题 9
3.分枝定界算法在MATLAB中的设计框架 13
4.结束语 14
参考文献 15
致谢 16
分枝定界算法在运筹学中的应用引言
整数线性规划是一种比较特殊的规划问题,并且整数规划凭借其算法简单和在理论上相对来说比较完善等优点,在生活中得到了广泛应用.50多年来,经过人们不懈的努力,建立出许多用来解决生活中的各类问题的整数规划模 .例如:在运输以及工业生产等方面的最优化模型中,整数线性规划都占有非常重要的地 ,而到目前为止,分枝定界算法以其独特的特征成为解决上述问题的首选方案.分枝定界算法不单能够解决 ,也能解决各种 .
文献[1][2][3]主要是针对 在生活中的作用的例子展开的,体现出 在生活中有非常重要的地位; 文献[4][5][6]主要讲解了分枝定界算法的思想和步骤,为下面的应用做准备; 文献[7][8][9][10]主要是解决分枝定界算法在指派问题求解过程中的一些细节问题; 文献[11][12][13]是用 算法解决投资问题中的相关参考; 文献[14]主要是关于 在 中的设计程序框架的相关知识．
当讨论组合最优化问题的全部可行解时,通过添加一些的约束条件以用来把一些最优解不存在的区域去掉.其基本思想是: 先把原ILP问题分解成为几个子问题,对每个子问题再继续分解,若对于每个子问题都不能再进行分解或者最优解不存在,则停止分解.在分枝,-751;文'论[文]网www.751com.cn定界的整个过程中,要是选取的分枝规则和定界方式不同,就得到同一问题的不同的 .本文从下面几部分进行展开,第一: 首先对分枝定界算法的定义进行了简要的叙述,并对其思想和步骤进行了详细的说明; 第二:在对分枝定界算法做了基本了解后,进而深入到分枝定界算法在运筹学中的应用,对此我利用分枝定界算法解决了指派问题和投资问题;第三: 最后又设计了其算法在 中求解 的程序框架.