基本介紹
- 中文名：整數規劃
- 外文名：integer programming
- 所屬領域：數學、運籌學
- 定義：線性模型中，變數限制為整數
- 套用舉例：0-1規劃
- 分類舉例：二次、非線性、線形
定義,發展歷程,分類,常用算法,套用舉例,組合最最佳化,0—1規劃,
定義
線上性規劃問題中，有些最優解可能是分數或小數，但對於某些具體問題，常要求某些變數的解必須是整數。例如，當變數代表的是機器的台數，工作的人數或裝貨的車數等。為了滿足整數的要求，初看起來似乎只要把已得的非整數解捨入化整就可以了。實際上化整後的數不見得是可行解和最優解，所以應該有特殊的方法來求解整數規劃。在整數規劃中，如果所有變數都限制為整數，則稱為純整數規劃；如果僅一部分變數限制為整數，則稱為混合整數規劃。整數規劃的一種特殊情形是01規劃，它的變數僅限於0或1。不同於線性規劃問題，整數和01規劃問題至今尚未找到一般的多項式解法。
發展歷程
整數規劃是從1958年由R.E.戈莫里提出割平面法之後形成獨立分支的 ，30多年來發展出很多方法解決各種問題。解整數規劃最典型的做法是逐步生成一個相關的問題，稱它是原問題的衍生問題。對每個衍生問題又伴隨一個比它更易於求解的鬆弛問題（衍生問題稱為鬆弛問題的源問題）。通過鬆弛問題的解來確定它的源問題的歸宿，即源問題應被捨棄，還是再生成一個或多個它本身的衍生問題來替代它。隨即 ，再選擇一個尚未被捨棄的或替代的原問題的衍生問題，重複以上步驟直至不再剩有未解決的衍生問題為止。現今比較成功又流行的方法是分支定界法和割平面法，它們都是在上述框架下形成的。
分類
整數規劃又分為：
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。儘管在理論上對它所知甚少，在實際套用中它卻表現出色。
單形法沿著邊界由一個頂點移動到“相鄰”的頂點，內點算法每一步的移動考量較周詳，“跨過可行解集合的內部”去逼近最佳解。當今的觀點是：對於線性規劃的日常套用問題而言，如果算法的實現良好，基於單純形法和內點法的算法之間的效率沒有太大差別，只有在超大型線性規劃中，頂點幾成天文數字，內點法有機會領先單形法。
線性規劃的求解程式在各種各樣的工業最最佳化問題里被廣泛使用，例如運輸網路的流量的最最佳化問題，其中很多都可以不太困難地被轉換成線性規劃問題。
套用舉例
組合最最佳化
組合最最佳化通常都可表述為整數規劃問題。兩者都是在有限個可供選擇的方案中，尋找滿足一定約束的最好方案。有許多典型的問題反映整數規劃的廣泛背景。例如，背袋（或裝載）問題、固定費用問題、和睦探險隊問題（組合學的對集問題）、有效探險隊問題（組合學的覆蓋問題）、旅行推銷員問題, 車輛路徑問題等。因此整數規劃的套用範圍也是極其廣泛的。它不僅在工業和工程設計和科學研究方面有許多套用，而且在計算機設計、系統可靠性、編碼和經濟分析等方面也有新的套用。
