徐曉輝

[摘? ? ? ? ? ?要]? 在數學建模應用中，整數線性規(guī)劃問題是一種常見的運籌學問題，其常用的解法有分支定界法、割平面法、蒙特卡羅法等。試圖從數學建模實踐的角度，淡化理論證明，僅對這幾種典型方法的原理、優(yōu)缺點、應用范圍等作一個簡要的分析比較，以供讀者在實際的數學建模過程中靈活應用。

[關? ? 鍵? ?詞]? 整數線性規(guī)劃;分支定界法;割平面法;蒙特卡羅法

[中圖分類號]? O151.2? ? ? ? ? ? ? ? ?[文獻標志碼]? A? ? ? ? ? ? ? ?[文章編號]? 2096-0603（2021）07-0178-02

一、整數線性規(guī)劃問題

規(guī)劃問題是運籌學的一個重要分支，從表達形式上看，可以分為線性規(guī)劃（linear programming，LP）和非線性規(guī)劃（non-linear programming，NLP）;從變量的可行域要求來看，也可以分為整數規(guī)劃（integer programming，IP）和非整數規(guī)劃（non-integer

programming，NIP），若既有表達式上的線性特征，又有變量的取整要求，這樣的規(guī)劃問題我們一般稱之為整數線性規(guī)劃（integer linear programming，ILP）問題[1]。

整數線性規(guī)劃問題的傳統(tǒng)解法是先求解與之對應的松弛問題（即先不考慮變量的整數約束而形成的新的線性規(guī)劃問題），若剛好得到整數解，則求解過程結束;否則，再通過適當方法（切割平面或分支定界）生成一個或多個新的松弛問題（最初松弛問題加上新的切割或分支條件），重復以上步驟直至求得最優(yōu)解。

一般而言，整數線性規(guī)劃問題的求解難度要比普通線性規(guī)劃問題大，其根本原因在于自變量取值增加了離散特性，但在工程上，離散特性恰好可以被計算機利用。蒙特卡羅算法是一類隨機方法的統(tǒng)稱。這類方法的基本思路是，可以通過隨機采樣進行計算而得到近似結果，隨著采樣的增多，得到正確結果的概率將逐漸加大，經過一定的步驟之后，就會盡可能趨近最佳結果。

二、割平面法

1958年，美國應用數學家R.E.戈莫里（Ralph Edward Gomory）首先提出了用割平面法求解整數線性規(guī)劃問題的經典思路：先求解相對應的松弛問題，若該松弛問題的最優(yōu)解就是整數解，則求解過程結束，否則通過適當的變形增加一個新的線性約束條件，再重復上述過程，直到最終求出原問題的最優(yōu)解[2]。新增的約束條件實際上縮小了變量的可行域，因此稱為“割平面”，割平面法的基本操作步驟如下：

事實上，由（3）式決定的割平面方程可能有一個或多個，這一方面提高了問題的難度，但是另一方面，增加割平面約束之后得到的新問題LP2在求解的時候也可以借助對偶單純形法原理得到一定程度的簡化。

從上述過程可以看出，基于嚴謹的理論推導的割平面法，比較適用于求解規(guī)模較小的整數線性規(guī)劃問題，但該方法收斂的速度比較慢，而且割平面的選取不唯一，這些都增加了其使用的復雜性。

三、分支定界法

20世紀60年代，美國計算機科學家、圖靈獎獲得者理查德·卡普（Richard M.Karp）提出了求解整數線性規(guī)劃問題的另一個經典思路[3]：同樣是先求解相對應的松弛問題，若該松弛問題的最優(yōu)解就是整數解，則求解過程結束，否則用與這個非整數解最接近的兩個整數來約束這個變量，并作為新的約束條件加入原問題中，形成兩個子問題，這稱為分支;重新求得兩個子問題的目標函數值確定了原問題目標函數值的上限（上界）或下限（下界），這稱為定界;若某個分支的最優(yōu)目標值超出了上一步的最優(yōu)目標值，則直接舍棄這個分支，是為“剪枝”，該過程縮小了原問題的搜索范圍，保證了算法的收斂性。重復上述分支、定界與剪枝過程，經若干步之后一般能找到原問題的最優(yōu)解。上述方法稱為分支定界法（branch and bound），其操作步驟如下：

Step 1：求解相應的線性規(guī)劃模型，確定目標值的初始上、下界：記原整數規(guī)劃問題為IP，先求解其對應的松弛問題為LP，若LP有整數解，即為IP的解，若LP的解中有非整數分量，則其目標值為IP的初始上界z1，進入下一步。

Step 2：分支。找出Step 1中解出的某個非整數分量，記為xj=bj，構造兩個新的約束條件xj≤[bj]和xj≥[bj]+1（其中[bj]表示不大于bj的最大整數）并分別加到原LP中，構成兩個子問題并求解它們。

Step 3：定界。以每個后繼問題為一個分支，并將所求得的最優(yōu)值與其他分支進行比較，找出其中最大者更新IP的上界z1;若有新的分支求得了整數解，則找出這些分支中目標函數最大者跟新IP的下界z2（最初的下界可以看作是z2=0）。

Step 4：剪枝。對任意一個分支，若本身無可行解，或是已經得到了不大于z2的非整數最優(yōu)解，則可以直接“剪除”這個分支，不再往下考慮了。

Step 5：若z1>z2，則找出z1多對應的分支，繼續(xù)返回Step 2，并重復上述過程，直至z1=z2z*，則z*就是此IP問題的解。

在實踐中，用分支定界算法求解整數線性規(guī)劃問題時，其平均收斂速度往往比用割平面法快，但新增的分支顯然也增加了計算的復雜度。

四、蒙特卡羅及其他方法

蒙特卡羅法一般認為是起源于法國數學家布豐（Buffon）的投針實驗，并由J.馮·諾伊曼等人在二戰(zhàn)中研究“曼哈頓計劃”時正式提出。蒙特卡羅法是一種以概率統(tǒng)計理論為指導的數值計算方法，其基本思路是通過隨機采樣的方法來計算近似結果，且隨著采樣的增多，得到正確結果的概率也會逐漸增大，在一定的規(guī)則下，部分采樣（不完全枚舉）就能得到在概率上相當滿意的結果。蒙特卡羅法一般的操作步驟是：

Step1：模型匹配。分析實際問題所求變量的特征，尋找恰當的概率統(tǒng)計模型，使得該模型某個指標的概率分布或者數字特征恰好可以用來表達該實際問題所求的解。

Step2：模擬測試。對上述模型中的隨機變量建立抽樣方法，在計算機上進行模擬測試，抽取足夠多的隨機數，對有關事件進行統(tǒng)計。

Step3：結果分析。對模擬試驗結果加以分析，給出所求解及其精度（方差）的估計。

Step4：模型改進。若上述Step3得到的結果不夠理想，或實驗方案費用過高，還可以考慮進一步改進模型以提高模擬計算的效率。

從應用的角度來說，用蒙特卡羅法求解整數線性規(guī)劃問題當然是可行的，而且適合于高維或者可行域較大的情形。因為在計算機模擬的條件下，低維或可行域較小的情形下蒙特卡羅法就退化成了枚舉法，或者使用前述的分支定界或割平面等方法，也能夠解決問題。事實上，蒙特卡羅方法在求解非線性整數規(guī)劃等復雜問題時會顯示出特別的優(yōu)勢。

另外，還有一類特殊的整數規(guī)劃問題，例如指派問題，我們稱之為0-1規(guī)劃;若目標函數及約束條件是線性的，我們也可稱之為0-1整數線性規(guī)劃問題。解決這類規(guī)劃問題需要用到完全枚舉法、隱枚舉法或者“匈牙利法”等特殊解法，在此不做詳述。

整數線性規(guī)劃問題首先具有線性特征，這使得它在求解過程中可以借鑒一般線性規(guī)劃問題的單純形解法，割平面法和分支定界法本質上都是一種基于線性規(guī)劃基礎上迭代的方法，利用迭代逐漸縮小可行域，最終收斂到最優(yōu)解。蒙特卡羅法主要依賴變量取整數這一特性，它本質上是一種有限枚舉法，在某種概率意義上最終收斂到最優(yōu)解。就處理能力而言，割平面法由于收斂慢，主要適用于規(guī)模較小的整數線性規(guī)劃問題，分支定界法收斂速度快一些，可以解決規(guī)模稍大一點的問題，而蒙特卡羅法作為一種隨機解法，可解決更大規(guī)模的問題，或者是某些非線性整數規(guī)劃問題。當然，對于超大規(guī)模，或者形式特別復雜的一般整數規(guī)劃問題，或許還有待開發(fā)出新的算法。

參考文獻：

[1]黃力偉，馮杰，王勤，等.軍事運籌學[M].北京：國防工業(yè)出版社，2016.

[2]楊明歌，常水珍.求解整數規(guī)劃的割平面法的研究[J].洛陽師范學院學報，2014（5）：1-4.

[3]熊偉.運籌學（第3版）[M].北京：機械工業(yè)出版社，2014：81.

[4]Kroese，D.P.;Brereton，T.;Taimre，T.;Botev，Z.I.Why the Monte Carlo method is so important today[J].WIREs Comput Stat，2014（6）：386-392.

編輯 李 爭