數(shù)學(xué)建模應(yīng)用中整數(shù)線性規(guī)劃問題的常用解法初探

徐曉輝

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

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

[中圖分類號]? O151.2? ? ? ? ? ? ? ? ?[文獻(xiàn)標(biāo)志碼]? A? ? ? ? ? ? ? ?[文章編號]? 2096-0603（2021）07-0178-02

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

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

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

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

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

二、割平面法

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

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

從上述過程可以看出，基于嚴(yán)謹(jǐn)?shù)睦碚撏茖?dǎo)的割平面法，比較適用于求解規(guī)模較小的整數(shù)線性規(guī)劃問題，但該方法收斂的速度比較慢，而且割平面的選取不唯一，這些都增加了其使用的復(fù)雜性。

三、分支定界法

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

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

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

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

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

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

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

四、蒙特卡羅及其他方法

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

Step1：模型匹配。分析實(shí)際問題所求變量的特征，尋找恰當(dāng)?shù)母怕式y(tǒng)計模型，使得該模型某個指標(biāo)的概率分布或者數(shù)字特征恰好可以用來表達(dá)該實(shí)際問題所求的解。

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

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

Step4：模型改進(jìn)。若上述Step3得到的結(jié)果不夠理想，或?qū)嶒?yàn)方案費(fèi)用過高，還可以考慮進(jìn)一步改進(jìn)模型以提高模擬計算的效率。

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

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

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

參考文獻(xiàn)：

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

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

[3]熊偉.運(yùn)籌學(xué)（第3版）[M].北京：機(jī)械工業(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.

編輯 李 爭