组合优化和整数规划应用研究与软件实现关于分支定界法的思考

摘要组合优化在科学，经济和工程领域中有着广泛应用，包括：经济建模、固定费用、金融、网络和运输、数据库和芯片设计、图象处理、核能和机械设计、化学工程设计和控制、分子生物学以及环境工程。同时，由于在一个组合优化问题里可能存在多个局部最优解，且局部最优解不同于全局最优解，这使得组合优化的研究极具挑战性。分支定界算法是全局优化主要算法之一，被广泛地应用于整数规划和非线性规划等优化模型中，近年来一直是最优化领域的研究热点。在过去的几年里，人们一直在寻找求解效率高，迭代次数少，运行时间短的新方法，以便求解实际生产中大规模优化问题。本文是在已有理论的基础上，针对大规模线性整数规划问题，提出一种新的有效方法——基于遗传算法的分支定界算法。第一章，本文对组合优化以及整数规划问题的发展现状作出了概括。同时，文章还证明了整数规划问题是 NP完备的，说明了整数规划问题是一个难以解决的问题，并为后文提供理论基础。
第二章，本文对分支定界法进行了详细地叙述，并对其不足进行了思考。接下来，文章针对传统分支定界法的不足，在遗传算法的基础上提出了一种解决大规模线性整数规划问题的方法。
第三章，首先对实际问题建立了模型，再将分支定界法运用到具体的模型中，最后针对该问题的结果进行了分析。7081
关键词组合优化，整数规划，分支定界法，遗传算法，c++ Title The Applied Research And Software Implementation Of
Combinatorial Optimization And Integer Programming
——Thoughts On Branch And Bound Algorithm
Abstract
Combinatorial optimization problems have been widely applied to science、
economics and engineering and they include economic modeling，fixed
charges， finance， networks and transportation.Alongwith databases and chip
design ， image processing ， nuclear and mechanical design ， chemical
engineering design and control,molecular biology,and environmental
engineering. However,since there exists multiple local optima that differs
from the global solution, studying optimal combinatorial solution is
extremely challenging.
The branch and bound algorithm is one of the main global optimization
methods，has been wildly applied in integer programming and non-linear
programming,and has been the hot topic of research in the optimization
fields in recent years.During the past decades,in order to solve the large
scale optimization problems in practical production， people have been
looking for the new algorithm： computational efficiency of the algorithm
is higher，some methods may provide an feasible solution，the CPU time is
shorter，and the number of the node is smaller.In this paper,we propose
a new effective method(branch and bound algorithm based on genetic
algorithm) based on known theory and algorithms for large scale integer
programming problems．
In Chapter 1,this paper summarizes the development of combinatorial
optimization and integer programming problems.Meanwhile,it also proves that integer programming problem is NP perfect,this means that integer
programming problem is hardly to be solved,and that provides theoretical
basis to later paragraphs.
In Chapter 2,this paper introduces branch and bound algorithm in
detail,and ponders over its drawbacks.After that,aiming at the drawbacks
of traditional branch and bound algorithm,this paper propose a new method
which is based on genetic algorithm to solve large scale linear integer
programming problems.
In Chapter 3,firstly,we establish models of a practical issue,and then 组合优化和整数规划应用研究与软件实现关于分支定界法的思考 :http://www.751com.cn/shuxue/lunwen_4846.html