本文選題：整數(shù)規(guī)劃　切入點：分枝定界　出處：《北京交通大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

【摘要】：摘要：目前,整數(shù)規(guī)劃已經(jīng)成為最優(yōu)化方法中求解經(jīng)管類問題最有效的方法之一.而且在這類問題中,混合整數(shù)規(guī)劃問題(MIP)變得越來越常見,求解MIP問題的方法主要有分枝定界算法和割平面法.其中,使用分枝定界算法和松弛方法的算法來優(yōu)化模型、求解問題更加有效.由于這種方法的高效性,MIP在學(xué)術(shù)上和工業(yè)上得到了普遍的應(yīng)用.它是在二十世紀六十年代初由Land Doig和Dakin等人提出的.分枝定界算法主要分為兩個步驟：一是節(jié)點選擇策略,二是分枝變量選擇策略.這兩種策略又分別有許多不同的實現(xiàn)方法,本篇文章的重點在于分枝策略中偽費用(Pscudo-cost)分枝策略.使用偽費用方法來選擇較好的變量進行分枝來產(chǎn)生子問題,可以更加快速的找到最優(yōu)解.但是偽費用又有不同的定義,在文章中主要提到了兩種偽費用的定義,論文中提到了四種改進方法,但本文主要的創(chuàng)新之處就在于分別將這兩種偽費用根據(jù)兩者乘積和兩者權(quán)重之和來產(chǎn)生新的偽費用定義.在Matlab數(shù)值實驗中,對這兩種方法進行了數(shù)值實驗,結(jié)果顯示改進的偽費用效果較好,說明了這兩種改進方法的有效性.
[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.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O224

【共引文獻】

相關(guān)期刊論文 前1條

1 陳紹寬;王秀丹;柏峗;劉海東;毛保華;;基于費用最小的鐵路牽引接觸網(wǎng)維修計劃優(yōu)化模型[J];鐵道學(xué)報;2013年12期

相關(guān)博士學(xué)位論文 前4條

1 王沛;基于分支定價的多星多站集成調(diào)度方法研究[D];國防科學(xué)技術(shù)大學(xué);2011年

2 達林;切平面在混合整數(shù)非線性規(guī)劃中的應(yīng)用[D];北京交通大學(xué);2009年

3 霍兆義;基于分級超結(jié)構(gòu)的換熱網(wǎng)絡(luò)同步綜合與改造方法研究[D];大連理工大學(xué);2012年

4 谷培培;面向E-learning的學(xué)生評價關(guān)鍵技術(shù)研究[D];北京理工大學(xué);2014年

相關(guān)碩士學(xué)位論文 前1條

1 譚思捷;單行布局問題的變鄰域算法研究及其應(yīng)用[D];西南交通大學(xué);2013年

，

本文編號：1623182