毕业论文移动版

摘要：本文主要提出了一种关于资源分配的分支定界法。分支定界法是一种很常用的求解整数规划问题的方法。由于分支定界法可以进行计算机编程，所以利用分支定界法解决整数规划问题会比较便捷，给人们带来很大的便利，这样可以节省很多解决问题的时间。历来都有人使用这种算法解决过很多生活实际问题，也有很多人钻研这种算法。众所周知，资源分配是现实日常生活中比较常见的问题，一直以来也备受人们关注，如何能使得资源分配最优化也是讨论这个问题的意义所在。本文提出的算法能优化资源分配问题，并且还使得人们能考虑问题的每个资源的性能评级，完美解决这方面的问题。除此之外，文中还给出了一个样本不大的问题，并通过求解来验证这种算法的有效性。最后，本文还将用MATLAB来对分支定界问题进行仿真，计算并验证分支定界算法。

关键词：分支定界法；整数规划；资源分配；MATLAB仿真

Abstract：This paper mainly proposes a branch and bound method for resource allocation. Branch and bound method is a very common method of solving integer programming problem. The algorithm used to solve the integer programming is very convenient and saves a lot of time to solve the problem of integer programming, because the algorithm of branch and bound method can be simulated by computers. Such problems of resource allocation has been occurred in daily life and there are a lot of people studying the algorithm of branch and bound method to solve the problem of integer problem. As we all know, resource allocation is a very common problem in everyday life. It has always been a matter of concern. How can we optimize the allocation of resources also belongs to this problem. It is the significance of discussing this problem. This paper proposes that the algorithm can optimize the problem of resource  allocation.  The  algorithm  allows  people  to  consider  the  performance  of    each

resource performance rating，and provide a perfect solution to this problem. Additionally, the

paper gives a problem with small sample to verify the effectiveness of this algorithm. Finally, we will use MATLAB to simulate the algorithm branch and bound problem to calculate and verify the branch and bound algorithm.

Keywords: Branch and bound method; Integer programming; Resource allocation; MATLAB simulation

目录

第一章绪论1

第二章整数规划及分支定界法介绍-2

2.1整数规划2

2.2分支定界法4

第三章分支定界法的应用及MATLAB仿真-11结论16

致谢17

参考文献18

第一章绪论

分支定界法是由理查德·卡普教授（RichardKarp）和他的同事海尔特（M.Held）在20世纪60年代提出的，这种算法经过了他们反复研究。该算法的提出给人们计算线性规划问题带来了极大的便利，为科学发展贡献了一份力量。

一直以来，整数规划都与线性规划关系密切，是不可分割的，它其中的一些基本的设计与算法的出发点都是相应的线性规划的最优解。分支定界法与割平面发是解决整数规划的最为常见的两种算法，由于分支定界法便于利用计算机实现，这里主要介绍的是分支定界法。整数规划问题与我们的实际生活紧密相连，例如工业生产顺序问题、整数背包问题、旅行路线及售货员问题、集成电路的分布问题、投资决策问题等都是求整数的数学模型中比较著名的“困难”问题。因此，想要掌握这些生活中的问题的解决方法，必然的路径就是研究整数规划，要想研究好一个问题，就要找到它的最优路径，必然要会使用计算手段。所以本文所讲述的整数规划中的分支定界算法对我们的生活和今后的研究都有着极其重要的意义。为了使其数学研究的更全面、深入、细致，有必要对其综合起来呈现出了，以节约时间解决问题。 (责任编辑：qin)