混合整數(shù)規(guī)劃中的幾個啟發(fā)式方法的研究.pdf

1、混合整數(shù)規(guī)劃在運輸業(yè)、電力調(diào)度、天然氣分配、石油混流等各個方面有著廣泛的應(yīng)用.研究表明，80％的工業(yè)問題都是混合整數(shù)規(guī)劃問題，因此求解混合整數(shù)規(guī)劃問題具有非常高的學(xué)術(shù)研究價值和實際應(yīng)用價值.然而，混合整數(shù)規(guī)劃是NP-hard問題，但線性規(guī)劃可以在多項式時間內(nèi)求解，因此在實際中通過求解混合整數(shù)規(guī)劃的線性松弛問題來求解混合整數(shù)規(guī)劃.隨著計算機技術(shù)的發(fā)展，以線性規(guī)劃求解器為工具，基于分支定界算法和割平面算法的混合整數(shù)規(guī)劃求解器也隨之出現(xiàn)，混合

2、整數(shù)規(guī)劃求解器包括預(yù)處理、節(jié)點選擇、線性規(guī)劃求解、啟發(fā)式方法等模塊.在求解混合整數(shù)規(guī)劃問題中，啟發(fā)式方法能夠快速有效地根據(jù)問題本身提供的信息找到問題的可行解.本文主要研究混合整數(shù)規(guī)劃中的幾種啟發(fā)式方法，首先介紹了幾種常用的啟發(fā)式方法，包括圓整啟發(fā)式方法、潛水啟發(fā)式方法和OCTANE啟發(fā)式方法;之后通過數(shù)值實驗來分析啟發(fā)式方法找到解的效率.實驗表明，不同的啟發(fā)式方法找到解的效率不同，且同時調(diào)用多種啟發(fā)式方法找到解的效率與單獨調(diào)用一種啟發(fā)式