混合整数规划中伪费用分枝策略的改进

发布时间：2018-03-17 04:28

本文选题：整数规划　切入点：分枝定界　出处：《北京交通大学》2015年硕士论文　论文类型：学位论文

【摘要】：摘要：目前,整数规划已经成为最优化方法中求解经管类问题最有效的方法之一.而且在这类问题中,混合整数规划问题(MIP)变得越来越常见,求解MIP问题的方法主要有分枝定界算法和割平面法.其中,使用分枝定界算法和松弛方法的算法来优化模型、求解问题更加有效.由于这种方法的高效性,MIP在学术上和工业上得到了普遍的应用.它是在二十世纪六十年代初由Land Doig和Dakin等人提出的.分枝定界算法主要分为两个步骤：一是节点选择策略,二是分枝变量选择策略.这两种策略又分别有许多不同的实现方法,本篇文章的重点在于分枝策略中伪费用(Pscudo-cost)分枝策略.使用伪费用方法来选择较好的变量进行分枝来产生子问题,可以更加快速的找到最优解.但是伪费用又有不同的定义,在文章中主要提到了两种伪费用的定义,论文中提到了四种改进方法,但本文主要的创新之处就在于分别将这两种伪费用根据两者乘积和两者权重之和来产生新的伪费用定义.在Matlab数值实验中,对这两种方法进行了数值实验,结果显示改进的伪费用效果较好,说明了这两种改进方法的有效性.
[Abstract]:Absrtact: at present, integer programming has become one of the most effective methods for solving economic management class problems in optimization methods. In this kind of problems, the mixed integer programming problem (MIPP) has become more and more common. The main methods for solving MIP problem are branch-and-bound algorithm and cut plane method, in which the branch and bound algorithm and relaxation method are used to optimize the model. It is more effective to solve the problem. Because of the high efficiency of this method, it has been widely applied in the academic and industrial fields. It was put forward by Land Doig and Dakin in early 1960s. The branch and bound algorithm is mainly divided into. Two steps: one is the node selection strategy, The second is the branch variable selection strategy, which has many different implementation methods. The emphasis of this paper is on the branching strategy of Pscudo-Cost.Using the pseudo-cost method to select better variables for branching to generate subproblems, we can find the optimal solution more quickly. However, there are different definitions of pseudo-cost. In this paper, two definitions of pseudo-cost are mainly mentioned, and four improved methods are mentioned in this paper. However, the main innovation of this paper is to produce a new definition of pseudo-cost according to the sum of the product and weight of the two kinds of pseudo-cost respectively. In the Matlab numerical experiment, the two methods are numerically tested. The results show that the improved pseudo-cost effect is better, which shows the effectiveness of the two improved methods.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O224

【共引文献】