-
整數規劃
(數學名詞)
鎖定
- 中文名
- 整數規劃
- 外文名
- integer programming
- 所屬領域
- 數學、運籌學
- 定 義
- 線性模型中,變量限制為整數
- 應用舉例
- 0-1規劃
- 分類舉例
- 二次、非線性、線形
整數規劃定義
在線性規劃問題中,有些最優解可能是分數或小數,但對於某些具體問題,常要求某些變量的解必須是整數。例如,當變量代表的是機器的台數,工作的人數或裝貨的車數等。為了滿足整數的要求,初看起來似乎只要把已得的非整數解舍入化整就可以了。實際上化整後的數不見得是可行解和最優解,所以應該有特殊的方法來求解整數規劃。在整數規劃中,如果所有變量都限制為整數,則稱為純整數規劃;如果僅一部分變量限制為整數,則稱為混合整數規劃。整數規劃的一種特殊情形是01規劃,它的變數僅限於0或1。不同於線性規劃問題,整數和01規劃問題至今尚未找到一般的多項式解法。
整數規劃發展歷程
整數規劃是從1958年由R.E.戈莫里提出割平面法之後形成獨立分支的 ,30多年來發展出很多方法解決各種問題。解整數規劃最典型的做法是逐步生成一個相關的問題,稱它是原問題的衍生問題。對每個衍生問題又伴隨一個比它更易於求解的鬆弛問題(衍生問題稱為鬆弛問題的源問題)。通過鬆弛問題的解來確定它的源問題的歸宿,即源問題應被捨棄,還是再生成一個或多個它本身的衍生問題來替代它。隨即 ,再選擇一個尚未被捨棄的或替代的原問題的衍生問題,重複以上步驟直至不再剩有未解決的衍生問題為止。現今比較成功又流行的方法是分支定界法和割平面法,它們都是在上述框架下形成的。
[1]
整數規劃分類
整數規劃又分為:
1、純整數規劃:所有決策變量均要求為整數的整數規劃
2、混合整數規劃:部分決策變量均要求為整數的整數規劃
3、純0-1整數規劃:所有決策變量均要求為0-1的整數規劃
4、混合0-1規劃:部分決策變量均要求為0-1的整數規劃
整數規劃常用算法
單純形算法利用多面體的頂點構造一個可能的解,然後沿着多面體的邊走到目標函數值更高的另一個頂點,直至到達最優解為止。雖然這個算法在實際上很有效率,在小心處理可能出現的“循環”的情況下,可以保證找到最優解,但它的最壞情況可以很壞:可以構築一個線性規劃問題,單純形算法需要問題大小的指數倍的運行時間才能將之解出。事實上,有一段時期內人們曾不能確定線性規劃問題是NP完全問題還是可以在多項式時間裏解出的問題。
第一個在最壞情況具有多項式時間複雜度的線性規劃算法在1979年由前蘇聯數學家Leonid Khachiyan提出。這個算法建基於非線性規劃中Naum Shor發明的橢球法(ellip-soid method),該法又是Arkadi Nemirovski(2003年馮‧諾伊曼運籌學理論獎得主)和D. Yudin的凸集最優化橢球法的一般化。
理論上,“橢球法”在最惡劣的情況下所需要的計算量要比“單形法”增長的緩慢,有希望用之解決超大型線性規劃問題。但在實際應用上,Khachiyan的算法令人失望:一般來説,單純形算法比它更有效率。它的重要性在於鼓勵了對內點算法的研究。內點算法是針對單形法的“邊界趨近”觀念而改採“內部逼近”的路線,相對於只沿着可行域的邊沿進行移動的單純形算法,內點算法能夠在可行域內移動。
1984年,貝爾實驗室印度裔數學家卡馬卡(Narendra Karmarkar)提出了投影尺度法(又名Karmarkar's algorithm)。這是第一個在理論上和實際上都表現良好的算法:它的最壞情況僅為多項式時間,且在實際問題中它比單純形算法有顯著的效率提升。自此之後,很多內點算法被提出來並進行分析。一個常見的內點算法為Mehrotra predictor-corrector method。儘管在理論上對它所知甚少,在實際應用中它卻表現出色。
單形法沿着邊界由一個頂點移動到“相鄰”的頂點,內點算法每一步的移動考量較周詳,“跨過可行解集合的內部”去逼近最佳解。當今的觀點是:對於線性規劃的日常應用問題而言,如果算法的實現良好,基於單純形法和內點法的算法之間的效率沒有太大差別,只有在超大型線性規劃中,頂點幾成天文數字,內點法有機會領先單形法。
整數規劃應用舉例
整數規劃組合最優化
組合最優化通常都可表述為整數規劃問題。兩者都是在有限個可供選擇的方案中,尋找滿足一定約束的最好方案。有許多典型的問題反映整數規劃的廣泛背景。例如,背袋(或裝載)問題、固定費用問題、和睦探險隊問題(組合學的對集問題)、有效探險隊問題(組合學的覆蓋問題)、旅行推銷員問題, 車輛路徑問題等。因此整數規劃的應用範圍也是極其廣泛的。它不僅在工業和工程設計和科學研究方面有許多應用,而且在計算機設計、系統可靠性、編碼和經濟分析等方面也有新的應用。