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

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

【共引文獻(xiàn)】

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1623182