本文選題：混合整數(shù)規(guī)劃　切入點(diǎn)：圓整啟發(fā)式方法　出處：《北京交通大學(xué)》2017年碩士論文

【摘要】：混合整數(shù)規(guī)劃在運(yùn)輸業(yè)、電力調(diào)度、天然氣分配、石油混流等各個方面有著廣泛的應(yīng)用.研究表明,80%的工業(yè)問題都是混合整數(shù)規(guī)劃問題,因此求解混合整數(shù)規(guī)劃問題具有非常高的學(xué)術(shù)研究價值和實(shí)際應(yīng)用價值.然而,混合整數(shù)規(guī)劃是NP-hard問題,但線性規(guī)劃可以在多項(xiàng)式時間內(nèi)求解,因此在實(shí)際中通過求解混合整數(shù)規(guī)劃的線性松弛問題來求解混合整數(shù)規(guī)劃.隨著計算機(jī)技術(shù)的發(fā)展,以線性規(guī)劃求解器為工具,基于分支定界算法和割平面算法的混合整數(shù)規(guī)劃求解器也隨之出現(xiàn),混合整數(shù)規(guī)劃求解器包括預(yù)處理、節(jié)點(diǎn)選擇、線性規(guī)劃求解、啟發(fā)式方法等模塊.在求解混合整數(shù)規(guī)劃問題中,啟發(fā)式方法能夠快速有效地根據(jù)問題本身提供的信息找到問題的可行解.本文主要研究混合整數(shù)規(guī)劃中的幾種啟發(fā)式方法,首先介紹了幾種常用的啟發(fā)式方法,包括圓整啟發(fā)式方法、潛水啟發(fā)式方法和OCTANE啟發(fā)式方法;之后通過數(shù)值實(shí)驗(yàn)來分析啟發(fā)式方法找到解的效率.實(shí)驗(yàn)表明,不同的啟發(fā)式方法找到解的效率不同,且同時調(diào)用多種啟發(fā)式方法找到解的效率與單獨(dú)調(diào)用一種啟發(fā)式方法找到解的效率也有所不同,合理設(shè)置啟發(fā)式方法的調(diào)用位置和調(diào)用頻率才能更快更有效地找到混合整數(shù)規(guī)劃的可行解.
[Abstract]:Mixed integer programming is widely used in transportation, electric power dispatching, natural gas distribution, oil mixed flow, etc. The research shows that 80% of industrial problems are mixed integer programming problems. Therefore, solving mixed integer programming problems has high academic value and practical application value. However, mixed integer programming is a NP-hard problem, but linear programming can be solved in polynomial time. Therefore, in practice, the mixed integer programming is solved by solving the linear relaxation problem of mixed integer programming. With the development of computer technology, the linear programming solver is used as a tool. The mixed integer programming solver based on branch and bound algorithm and cut plane algorithm also appears. The mixed integer programming solver includes preprocessing, node selection and linear programming solution. In solving mixed integer programming problems, the heuristic method can quickly and effectively find the feasible solution of the problem according to the information provided by the problem itself. In this paper, several heuristic methods in mixed integer programming are studied. This paper first introduces several common heuristic methods, including round heuristic method, diving heuristic method and OCTANE heuristic method, then analyzes the efficiency of the heuristic method by numerical experiments. The efficiency of different heuristic methods in finding solutions is different, and the efficiency of finding solutions by calling multiple heuristic methods at the same time is different from that of using one heuristic method alone. In order to find the feasible solution of mixed integer programming more quickly and more effectively, we can set the call position and frequency of heuristic method reasonably.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O221.4

【相似文獻(xiàn)】

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

1 黃海軍;朱宏;;公路干線網(wǎng)絡(luò)發(fā)展規(guī)劃的啟發(fā)式方法模型[J];軟科學(xué);1988年03期

2 王強(qiáng);乞建勛;郭新志;;資源約束項(xiàng)目調(diào)度中重心啟發(fā)式方法研究[J];運(yùn)籌與管理;2008年05期

3 白思俊;資源有限網(wǎng)絡(luò)計劃啟發(fā)式方法的評價(中)——啟發(fā)式方法的綜合比較和評價[J];運(yùn)籌與管理;1999年03期

4 張尚書;一種簡便有效的系統(tǒng)優(yōu)化方法——啟發(fā)式方法[J];中國計量學(xué)院學(xué)報;1996年02期

5 胡麗榮;吳樹華;;統(tǒng)計教學(xué)中啟發(fā)式方法的具體應(yīng)用[J];職業(yè)技術(shù);2006年16期

6 白思俊;資源有限網(wǎng)絡(luò)計劃啟發(fā)式方法的評價(下)——啟發(fā)式方法與網(wǎng)絡(luò)特征的相關(guān)性分析[J];運(yùn)籌與管理;1999年04期

7 白思俊;;資源有限的網(wǎng)絡(luò)計劃與啟發(fā)式優(yōu)化方法及其評價與選擇——啟發(fā)式優(yōu)化方法綜述[J];中國管理科學(xué);1993年02期

8 阮曉芳;張瑞生;胡榮靜;袁永娜;劉滿倉;范波濤;;基于啟發(fā)式方法和支持向量機(jī)定量研究藥物的血腦屏障通透性[J];蘭州大學(xué)學(xué)報(自然科學(xué)版);2007年05期

9 楊立君;對Flowshop排序問題啟發(fā)式方法的評價與改進(jìn)[J];湖北汽車工業(yè)學(xué)院學(xué)報;1997年02期

10 楊立君;對Flowshop排序問題啟發(fā)式方法的評價與改進(jìn)[J];工業(yè)工程與管理;1998年01期

相關(guān)會議論文 前1條

1 葛晨暉;柏寧豐;樊鶴紅;韋樸;趙俊;孫小菡;張明德;;WDM網(wǎng)絡(luò)通道保護(hù)P圈啟發(fā)式設(shè)計方法[A];全國第十三次光纖通信暨第十四屆集成光學(xué)學(xué)術(shù)會議論文集[C];2007年

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

1 柳一君;基于單值變量的求解啟發(fā)式方法研究[D];吉林大學(xué);2017年

2 洪星;混合整數(shù)規(guī)劃中的幾個啟發(fā)式方法的研究[D];北京交通大學(xué);2017年

3 邱俊熒;基于帶Path-Relinking的GRASP的超啟發(fā)式方法[D];大連理工大學(xué);2011年

4 張良;基于沖突的求解啟發(fā)式優(yōu)化策略研究[D];吉林大學(xué);2014年

5 馬咪咪;基于用戶測試的啟發(fā)式評估研究[D];山東大學(xué);2013年

，

本文編號：1670891