基于分支定界法的整數規劃問題研究與應用

張晗 陳曉曉 魏禧辰

摘要：整數規劃是日常生活中較為常見的一種特殊的規劃問題，需要使用特殊的方式來進行求解.分支定界法作為一種枚舉型的求解思想，通過分割解空間來限定最優解的上下界，從而較為高效地獲得整數規劃問題的最優解.本文對分支定界法進行了建模分析，給出了分支定界法求解最優解的一般思路和求解方法，同時使用分支定界法進行了實證分析，利用分支定界法對飛機排班問題和生產用料最優化問題進行了實際的模擬求解，并分析了分支定界法的優點和不足.

關鍵詞：整數規劃;分支定界法;實證分析;Mathematica

中圖分類號：O221.4;F201? 文獻標識碼：A? 文章編號：1673-260X（2019）04-0020-04

1 研究背景

整數規劃是一種情況較為特殊的規劃問題，其所含的變量的取值均為整數，這就為求解問題設置了障礙：一般情況下，最優解并不一定是整數解.

在日常生活中，整數規劃的實例很多，例如裝載問題、固定費用問題、探險隊問題等等.整數規劃是NP困難的，存在某個多項式算法來進行求解和檢驗的，有很高的計算復雜性，我們可以先從求解整數規劃中的線性問題，再從線性形式逼近最接近的整數.分支定界法就是解決一般的整數規劃的一個很有效的方法.

本文將通過分支定界法來對整數規劃問題進行理論模型的建立、推導以及求解，并進行了實際應用.本文研究了組合優化的工廠下料問題，以及航空公司航班安排問題，從理論分析入手，經過模型建立，理論求解，利用數學軟件進行實際模擬，并最終得到問題的結果.

2 相關理論

2.1 整數規劃

在線性規劃問題求解中，最優解可能是小數或分數，但在實際生活中，常會限制某些變量的解必須是整數，那么全部或者個別變量是整數的線性規劃就被稱作整數規劃.由于問題中對求解變量的要求不同，又分為純整數規劃和混合整數規劃.

2.2 分支定界法的發展

分支定界法是由學者理查德·卡普在二十世紀60年代發明，他成功求解了旅行商問題.Kolen等利用此方法求解時間窗約束的車輛巡回問題，取得良好效果，其對于時間的計算也體現很強的優勢.分支定界發被廣泛而普遍地應用于工業化生產之中，對于生產物料消耗的最優化組合問題具有很好的解決能力.李播等利用分支定界法進行了手術計劃的調度研究，用以在擇期病人的安排最大化和預留應急手術室以應對急診病人之間達到利用最大化的手術時間安排.李秋陽采用分支定界法，研究了電能表計量電路容差的設計方法;王建輝利用分支定界方法對不平衡的氣象數據進行了氣象的預測和晴雨的分析.可以看出，分支定界的思想在規劃和優化組合的問題上有著至關重要的地位.

2.3 分支定界法的基本思想

分支定界法的最基本思想就是對規劃問題的所有可行解空間進行查找，通過將解空間進行分割成小的分支，為每一個分支的解計算一個下界，從而尋找到最終的最優解.這也是分支定界法的三個步驟：分支、松弛和下界.

2.4 分支

對于整數規劃問題M，設F（M）為問題M的允許解集，對于子問題M1，M2，…，Mn，若有

2.5 松弛

在放棄M的某些條件后，得到的問題都是M的松弛問題，顯然M的松弛問題的約束條件要弱于M，則M的松弛問題有以下特點：

（1）若松弛問題無解，則原問題無解;

（2）原問題的最優解不優于松弛問題的最優解;

（3）若松弛問題的最優解是原問題的允許解，那么這個解也是原問題的最優解.

通常來說，我們在實際求解過程中，最經常放棄的條件就是變量的整數性要求.

2.6 定界

假設問題M已經分解為M1，M2，…，Mn的和，并且各個子問題都已經有了對應的松弛問題，那么如果某個松弛問題無解，那么該松弛問題對應的子問題就沒有允許解，那么就將該子問題從M的分解表上刪去;

如果已經可以求得M的某一個允許解X，若某松弛問題的最優解不好于該允許解，那么說明其對應的子問題中沒有比X更好的允許解，因此可以將對應的子問題從M的分解表中去掉;

如果某個松弛問題的最優解是其對應子問題的允許解，則我們就已知了該子問題的一個最優解，則我們也無需考慮該子問題了，就可以將其從分解表上去掉，如果這個時候子問題的最優解比X要好，那么就將X替換掉.

如果分解表上的松弛問題的最優解都不比原允許解要好，那么原允許解就是M的一個最優解.

從算法的角度看，分支定界法形為在一棵深度為n的樹上進行尋找，通過對樹上每個節點進行線性規劃求解，來尋找每個節點的下界，以此確定下界的最小節點，并把該節點作為下一個分支的節點，最終找到可行解，并且將目前尋找到的最好的可行解和下一個分支尋找到的可行解進行比較，留下更優的解.通過一層一層的篩選和比較，最終找到最優解.分支定界的方法，通過分支大大減少了枚舉法帶來的運算復雜度，在變量較多的規劃問題中，可以凸顯其運算精簡的優勢.

3 理論推導

3.1 模型的基本形式

對于整數規劃問題，基本的形式為

3.2 模型求解

首先我們求解整數規劃問題的松弛問題，即

如果該松弛問題的最優解x0為整數解，那么此最優解也是原整數規劃問題的最優解.

如果該松弛問題的最優解不是整數解，那么該最優解就是原整數規劃問題最優解的一個下界，我們就可以把原整數規劃問題分為兩個子問題

對這兩個子問題繼續進行松弛問題的求解，也會得到兩個不同的最優解，通過比較進行篩選，確定新的下界.通過重復該過程，若在某一個子問題中扎到了整數解xm，則該解為原整數規劃問題的一個上界.此時，對于子問題k，若該問題的下界xk>xm，那么該分支就可以直接刪去，否則就將分支過程繼續下去，直到找到最優解為止.

4 實際應用

4.1 飛機航班問題

航空運輸業在運營過程中，由于飛機不論是長時間處于空閑狀態或者是滿負荷狀態都會增加航空公司的運營成本和飛機的維修成本，因此航空公司需要在能夠滿足航班需求的基礎上使每一架飛機的飛行時間和負荷能夠達到均衡的水平.同時，也要求航空公司的維護成本、機隊均衡都能夠滿足需求.簡而言之，就是航空公司要根據航班計劃和飛機的維護狀態來對每一架飛機的執飛進行航班安排，以達到飛機使用的平均化.

4.1.1 模型建立

根據問題的求解，我們可以知道，所需求解的問題為整數規劃問題，則可以以此建立模型：

令F=航班集合;

R為可航行的航班環集合

M為維護場地集合

J表示可行航班組，也就是能夠理論上可以安排飛行的方法安排

I表示航班

aij=1，航班i在可行航班j中0，航班i不在可行航班j中

N為飛機總數

Tj為可航行航班組j的飛行時間

Q為所有航班的飛行總時間

xij=1，若可行航班組j被選上，否則取值為0

模型表達為：

其中cj=|Tj-Q/N|，表示該模型利用每個可行航班環的飛行時間和當天的每架飛機的平均飛行時間的差值來確定均衡性.該模型的限制條件對飛機的數量，即飛機總數不能多于公司擁有的飛機數;飛機飛行的現實條件，即每一個航班只能由一架飛機執飛都進行了限定.

由于分支定界法是對可行情況進行一定程度的枚舉，因此變量的復雜程度直接影響了分支定界法的計算復雜度.由于分支定界法的算法復雜度依賴于需要進行排班的航班數，因此如果能盡可能將可以排班的航班范圍縮小，就而可以更加便于得到結果.由于我國的有關規定，飛機必須能夠在規定時間飛到正確的維修場地過夜和維護，因此，通過篩選我們可以從所有航班中篩選出滿足要求的可排班航班組組成集合R，該集合相比集合F能夠更加簡化運算的復雜度.

4.1.2 模型求解

在本問題中，為了快速得到整數解，我們按照最小下界優先原則進行分支求解，具體步驟如下：

首先令該問題為M，該問題的松弛問題為放棄xj的0-1取值后的問題;

求解松弛問題，記錄松弛問題的最優解和求得的最小值，如果此時該最優解滿足原問題的要求，則該解為原問題M的最優解，算法結束;若該最優解不能滿足原問題的要求，則令該松弛問題的最小值為原問題目標函數值的下界.

選擇M的子問題，對其松弛問題進行求解，如果松弛問題無允許解或者其最小值大于原問題的松弛問題的最小值，那么將其刪去，若求得子問題的松弛問題的最優解也是原子問題的允許解，那么看求得的最小值與原問題松弛問題的最小值孰小;將較小值保存為原目標函數值的新的下界;若求得子問題的松弛問題的最優解不是子問題的允許解，則選取系數最大的證書變量進行分支，按照0和1分成兩個子問題，并重復進行松弛和定界的過程.

循環往復此過程，直到找到原目標問題的最優解結束.

4.1.3 實際模擬

我們收集了國內某家航空公司的飛行數據進行了實際模擬.首先該公司需要執飛68個航班，飛機的維修場地一共有3個，飛機12架，同時根據我國航空運輸的相關規定，在這68個航班中，可以組成233個可行航班環，同時每個可行航班環的飛行時間也是已知的，其中航班集合F中含有68個元素，可行航班環集合R中有233個元素，設定目標函數cj=|Tj-Q/N|，Tj為航班環的飛行時間，一共有233個決策變量，除了整數約束外，共有69個約束條件.利用Mathematica軟件進行處理，用分支定界法一共進行了38次循環處理，得到了12架飛機的執飛安排圖，同時可以利用分支定界法進行輪班，一次可以得到長期的飛機執飛安排.

4.2 物料最優解問題

在工業生產中，經常遇到同一種生產原料生產幾種不同的產品，這時候如何最大化利用固有的原料，使產能達到最大化，材料的利用率達到最大就變得至關重要.可以通過利用分支定界法，在有限的時間、空間以及其他原料條件下得到最優的解，從而對客觀實際產生幫助.

4.2.1 問題提出

現要利用某種布匹生產不同種類的服裝，根據便于生產和節約布料的原則，現在可以有n中不同的制作分配方式.假設第j種生產方式種可以得到第i種服裝aij件，同時第i種服裝的需求量為bi個，那么究竟該如何分配原料布匹，才能夠既滿足需求，又能使所使用的原料布匹最少？

4.2.2 模型建立

上述問題可以用表格表示

令xj表示第Bj種分配方式所消耗的布料數量，則該問題可以歸納為整數規劃問題

4.2.3 模型求解

運用分支定界法進行求解，首先我們求原整數規劃的松弛問題

若得到的最優解是整數，則最優解是原線性整數規劃的最優解，求解過程結束.若非整數，則得到的最優解是原線性整數規劃最優解的一個下界，這樣我們就將原問題分成兩個子問題，對子問題松弛問題分別求解;若在某個求解過程中得到了一個整數解，這個整數解就是原線性整數規劃的一個上界，此時，若從子問題k開始進行分支，但是該問題的下界要大于原整數規劃的解的上界，那么該子問題中找不到小于原線性整數規劃的上界的解，則該問題可以直接舍去;若子問題k的下界小于原整數規劃的上界，那么分支定界的過程仍繼續，直到找出最優解.

4.2.4 實際模擬

假設某服裝廠有一批長為180米的布料用來制造服裝，其中由三種服裝，第一種服裝消耗布料70米，第二種服裝消耗布料52米，第三種布料消耗布料35米，三種服裝的需求量分別為100件，150件和100件，先要計算如何裁制服裝才能使消耗的布料最少.

像這樣的問題我們可以通過優化組合的方法來給出最合理的資源分配方式，設x1，x2，x3分別表示制造三種服裝的數量，那么就有70x1+50x2+35x3≤180，其中x1，x2，x3均為整數，并且x1≤2.

則使用數學表達式則為

利用Mathematica進行編程模擬，可以得到結果：X=[28，42，1，1，1，30，1，1]，也即是，在生產過程中，如果按照B1的裁制方式裁制28套布料，按照B2的裁制方式裁制42套布料，按照B3的裁制方式裁制1套布料，按照B4的裁制方式裁制1套布料，按照B5的裁制方式裁制1套布料，按照B6的裁制方式裁制30套布料，按照B7的裁制方式裁制1套布料，按照B8的裁制方式裁制1套布料，那么此時布料的利用效率是最高的，可達到96.5%，同時滿足對每一種服裝的生產需求，此時就是最優解.

5 結論

本文不僅從理論上對分支定界法進行了建模和求解分析，還從實際出發，從不同的案例著手對分支定界法進行了實際層面的建模和求解.對飛機排班問題，首先篩選可行航班環來減少運算量，再使用分支定界法對飛機排班進行最優化求解，選擇總體最優化的排班方案.利用了分支定界法，對服裝廠利用長度一定的整卷布料生產不同耗用布料數量的三種服裝，使其在充分滿足每種服裝的需求的基礎上，原料的利用率達到最大，并且根據實際情況，利用數學軟件進行了編程運算，從而得到了最優化的解法.

參考文獻：

〔1〕范永俊，吳東華.基于分支定界法的飛機均衡排班計劃求解[J].統計與決策，2017（20）：60-63.

〔2〕李平風，劉海峰.線性整數規劃分支定界法并行化研究[J].電腦知識與技術，2016，12（24）：28-30.

〔3〕劉霞，高岳林.整數二次規劃問題的一種新型分支定界算法[J].中北大學學報（自然科學版），2015，36（04）：412-417.

〔4〕馬艷利.混合整數非線性規劃問題的分支定界算法研究[D].寧夏大學，2014.

〔5〕李紅霞，張琛.基于整數規劃的模糊關系方程極小解的求解算法[J].佳木斯大學學報（自然科學版），2012，30（05）：788-790.

〔6〕艾杰.基于分支定界算法的護士排班模型研究[J].科學技術與工程，2012，12（13）：3074-3077.

〔7〕秦平平.分支定界算法在運籌學模型中的應用[D].燕山大學，2009.

〔8〕郭志軍.Mathematica求解整數規劃研究[J].黑龍江科技信息，2007（24）：35+178.

〔9〕管琳，白艷萍.用分支定界算法求解旅行商問題[J].中北大學學報（自然科學版），2007（02）：104-107.

〔10〕劉壽春，胡雁玲，洪文.整數規劃模型研究[J].皖西學院學報，2004（02）：6-8.

〔11〕倪明放，徐南榮.混合整數兩層線性規劃的一個代理約束方法[J].東南大學學報，1994（01）：77-82.

〔12〕俞玉森.數學規劃的原理和方法[M].武漢：華中理工大學出版社，1993.

〔13〕陳學松.運籌學中模型優化與算法研究[D].華中科技大學，2015.