整數規劃-百科詞條

　　一類要求變數取整數值的數學規劃。若要求全部變數取整數值，則稱為純整數規劃，簡稱為整數規劃。若隻要求部分變數取整數值，則稱為混合整數規劃。特別地，當在線性規劃中要求變數取整數時，就是線性整數規劃。若要求變數為0，1變數，即其值隻取0或1時，則稱為0-1規劃。由於實際問題中有許多量具有不可分割的性質，如人數、機器數、元件數等；還有一些邏輯現象如開與關，取與舍，有與無等可利用0、1變數作數量化描述，因此，在線路設計、工廠選址、人員安排、代碼選取以及其他領域中，常常常出現整數規劃問題。1958年，R.E.戈莫裡提出解線性整數規劃的割平面法後，整數規劃逐步形成一個獨立的分支。

　　形式最簡單的整數規劃問題是背包問題，也就是求 max

，滿足

（ x _j取0或1）的解的問題。假如將 V解釋為背包的容積， v _j為物體 j的體積， w _j為物體 j的重量，而變量 x _j取1時表示物體 j裝入背包， x _j取0時表示物體 j不裝入背包，那麼背包問題就是要尋求一種既不超過背包容積，又能使總重量最大的裝法。背包問題的一種特殊解法是動態規劃的方法，這種方法所需的計算時間與所給問題中的參數 n， V有關，大致與 n V成正比例增長。

　　設所給的整數規劃問題(p)為求極小值問題。在整數規劃的一般性解法中，有三個基本概念。①分解，以F(p)表示問題(p)的約束集。所謂問題(p)分解為子問題(p₁)，(p₂)，…，(p_q)之和，是指滿足條件(S1)和(S2)，(S1)：問題(p)的任何一個可行解，恰好是(p₁)，(p₂)，…，(p_q)中某一個問題的可行解;(S2)：任何子問題(p_i)的可行解也是(p)的可行解，即

，1≤ i≠ j≤ q。最通常的分解方式是“二分法”，例如，若 x _j是( p)的0，1變量，把條件“ x _j=0”和“ x _j=1”分別添進問題( p)的約束條件中，則問題( p)分解為兩個子問題之和。②松弛，凡是放棄問題( p)的某些約束條件後所得到的問題( P̃)，都稱為問題( p)的松弛問題。任何松弛問題( P̃)都具有以下三個明顯的性質：(R1)若( P̃)沒有可行解，則( p)也沒有可行解；(R2)對同樣的目標函數而言，( p)的最小值不小於( p)的最小值;(R3)若( P̃)的一個最優解是( p)的可行解，則它也是( p)的一個最優解。最通常的松弛方式是放棄變量的整數性要求。③探測假設按某種規則，已將問題( p)分解為子問題( p ₁)，( p ₂)，…，( p _q)之和，並且各( p _j)已有對應的松弛問題( P̃ _j)。若( P̃ _j)沒有可行解，則探明瞭( p _j)沒有可行解，因此，可從( p)的分解表上把它刪去。此種情形記為(F1)。假若當時已掌握瞭( p)的一個可行解 x ^*，與之相應的目標函數值為 z ^*，如果松弛問題( P̃ _j)的最小值不比 z ^*小，那麼就探明瞭( p _j)中沒有比 x ^*更好的可行解，因此已無須再考慮子問題( p _j)，就可從分解表上把它刪去。此種情形記為(F2)。若( P̃ _j)的最優解是（ p _j）的可行解，則已求得瞭( p _j)的一個最優解。因此也無須再考慮它瞭，可以從分解表上把( p _j)刪去，這時若( p _j)的最優解比 x ^*好，則替換掉 x ^*，同時刷新 z ^*的值。此種情形記為(F3)。假如各個( P̃ _j)的目標函數最小值都不比 z ^*小，則 x ^*便是原問題( p)的最優解。此種情形記為(F4)。情形(F1)通常稱為可行性探測。情形(F2)至(F4)通常稱為最優性探測。

　　概括地說，求解一個整數規劃問題(p)，有以下幾個步驟。首先，選定一種松弛方式，將(p)松弛為問題(P̃)，使得比較容易求解。若(P̃)沒有可行解，則(p)也沒有可行解。若(P̃)的最優解是(p)的可行解，則已求得(p)的最優解。若(P̃)的最優解不是(p)的可行解，則有兩條不同的途徑，一是設法改進松弛問題(P̃)，繼續探測問題(P̃)；一是選定一種分解方式，把(p)分解成兩個或幾個子問題之和，將其列表記錄，並且賦予各子問題盡可能好的目標函數值的下界。然後，按一定的次序，逐個進行探測。當某個子問題已經被探明時，就從表中刪去，否則，繼續對子問題進行分解。

　　對線性整數規劃問題，不用分解的算法有割平面法，它以線性規劃問題作為松弛問題，利用生成割平面來不斷改進松弛問題，使最終求得的松弛問題的最優解也是整數解；還有一種是群論方法，它用有限阿貝爾群上的一個背包問題作為松弛問題，是放棄一部分變量的非負性要求後得到的。利用分解的算法有隱數法和分枝定界法兩類。它們通常都是以線性規劃問題作為松弛問題，不同之處僅在於探測子問題的先後次序。隱數法是按照子問題表中“先入後出”的原則來確定探測次序，即後出現的子問題先探測。分枝定界法是按照所賦予的下界大小來確定探測的先後順序，即下界小的子問題優先探測。前者計算程序比較簡單，在計算過程中所需要保存的信息較少，而後者在選取子問題時有靈活性，因為往往下界數值小的子問題中存在最優解的可能性較大。

　　對線性混合整數規劃問題，J.F.本德爾斯提出瞭一種分解算法。它的求解過程可以分為兩部分，一部分是解一個線性整數規劃問題，另一部分是解一個線性規劃問題。

　　割平面法　例如，考慮整數規劃問題：求

　　　(1)

滿足條件

　　　(2)

　　　(3)

　　　(4)

　　　(5)

x₁、x₂取整數值。　　　(6)

　　取它的松弛問題為線性規劃(1)～(5)，約束集為圖1

中的多邊形 A B C D。整數規劃的可行解是此多邊形內的整點（即座標為整數的點）。松弛問題的基本最優解為

即圖1中的點 C。目標函數的最優值

設

　　　(7)

　　　(8)

從(7)和(8)中解出 x ₁、 x ₂，得

　　　(9)

　　　(10)

因 x ₁、 x ₂、 y、 z都必須取整數值，故由(9)和(10)可得同餘方程

　　　(11)

　　　(12)

利用方程(11)或(12)中 y和 z的系數，可以導出整數規劃的一個新的約束條件，例如，用

乘條件(2)的兩邊，用

乘(4)的兩邊，然後將(2)和(4)的兩邊分別相加，可得

。由於 x ₁必須取整數值，就可推得一個新的約束條件： x ₁≤1。這就是整數規劃的一個割平面。類似地，由

可推得另一個割平面：3 x ₁- x ₂≤4。增加割平面 x ₁≤1後，新的松弛問題的約束集如圖 2

所示。它的基本最優解為： x ₁=1，

，是圖2中的點 Q。

再由條件 x ₁≤1和

可導出一個新的割平面： x ₁+ x ₂≥3。增加此割平面後，松弛問題的約束集如圖3所示。它的基本最優解為： x ₁=1即圖3中的點 R。由於它已是整數解，故必為整數規劃(1)～(6)的最優解。目標函數的最大值 x ₀=1。

　　分枝定界法　例如，整數規劃問題(p)：求

　　　　　(13)

滿足條件

(14)

(15)

(16)

x₁、x₂、x₃取整數值。 (17)

　　取松弛問題(P̃)為線性規劃(13)～(16)。(P̃)的最優解為x₁=0.4，x₂=3.8，x₃=0；x₀=14.2。按條件x₂≤3和x₂≥4將(p)分解為子問題(p₁)與(p₂)之和。解(p₁)的松弛問題(P̃₁)，得x¹：x₁¹=0.5，x₂¹=3，x

=0.5； x ₀ ¹=14.5。再按條件 x ₁＝0和 x ₁≥1將( p ₁)分解為( p ₃)與( p ₄)之和。這時子問題表為{( p ₃，( p ₄)，( p ₂)}。這些子問題的 x ₀的下界，暫時都可以取為15。按表中“先入後出”原則，解( p ₃)的松弛問題( P̃ ₃)，得 x ³： x ₁ ³=0， x ₂ ³=3， x ₃ ³=2； x ₀ ³=17。由於 x ³是整數解，故必為( p ₃)的最優解。因此，( p ₃)已被探明，就可從表中刪去，記 x ^*= x ³， z ^*=17，這是被找到的第一個整數解。解( P̃ ₄)，得