基于分支定界法的整數(shù)規(guī)劃問題研究與應(yīng)用

張晗 陳曉曉 魏禧辰

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

關(guān)鍵詞：整數(shù)規(guī)劃;分支定界法;實證分析;Mathematica

中圖分類號：O221.4;F201? 文獻(xiàn)標(biāo)識碼：A? 文章編號：1673-260X（2019）04-0020-04

1 研究背景

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

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

本文將通過分支定界法來對整數(shù)規(guī)劃問題進(jìn)行理論模型的建立、推導(dǎo)以及求解，并進(jìn)行了實際應(yīng)用.本文研究了組合優(yōu)化的工廠下料問題，以及航空公司航班安排問題，從理論分析入手，經(jīng)過模型建立，理論求解，利用數(shù)學(xué)軟件進(jìn)行實際模擬，并最終得到問題的結(jié)果.

2 相關(guān)理論

2.1 整數(shù)規(guī)劃

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

2.2 分支定界法的發(fā)展

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

2.3 分支定界法的基本思想

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

2.4 分支

對于整數(shù)規(guī)劃問題M，設(shè)F（M）為問題M的允許解集，對于子問題M1，M2，…，Mn，若有

2.5 松弛

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

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

（2）原問題的最優(yōu)解不優(yōu)于松弛問題的最優(yōu)解;

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

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

2.6 定界

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

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

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

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

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

3 理論推導(dǎo)

3.1 模型的基本形式

對于整數(shù)規(guī)劃問題，基本的形式為

3.2 模型求解

首先我們求解整數(shù)規(guī)劃問題的松弛問題，即

如果該松弛問題的最優(yōu)解x0為整數(shù)解，那么此最優(yōu)解也是原整數(shù)規(guī)劃問題的最優(yōu)解.

如果該松弛問題的最優(yōu)解不是整數(shù)解，那么該最優(yōu)解就是原整數(shù)規(guī)劃問題最優(yōu)解的一個下界，我們就可以把原整數(shù)規(guī)劃問題分為兩個子問題

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

4 實際應(yīng)用

4.1 飛機(jī)航班問題

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

4.1.1 模型建立

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

令F=航班集合;

R為可航行的航班環(huán)集合

M為維護(hù)場地集合

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

I表示航班

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

N為飛機(jī)總數(shù)

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

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

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

模型表達(dá)為：

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

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

4.1.2 模型求解

在本問題中，為了快速得到整數(shù)解，我們按照最小下界優(yōu)先原則進(jìn)行分支求解，具體步驟如下：

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

求解松弛問題，記錄松弛問題的最優(yōu)解和求得的最小值，如果此時該最優(yōu)解滿足原問題的要求，則該解為原問題M的最優(yōu)解，算法結(jié)束;若該最優(yōu)解不能滿足原問題的要求，則令該松弛問題的最小值為原問題目標(biāo)函數(shù)值的下界.

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

循環(huán)往復(fù)此過程，直到找到原目標(biāo)問題的最優(yōu)解結(jié)束.

4.1.3 實際模擬

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

4.2 物料最優(yōu)解問題

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

4.2.1 問題提出

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

4.2.2 模型建立

上述問題可以用表格表示

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

4.2.3 模型求解

運(yùn)用分支定界法進(jìn)行求解，首先我們求原整數(shù)規(guī)劃的松弛問題

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

4.2.4 實際模擬

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

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

則使用數(shù)學(xué)表達(dá)式則為

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

5 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

〔7〕秦平平.分支定界算法在運(yùn)籌學(xué)模型中的應(yīng)用[D].燕山大學(xué)，2009.

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

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

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

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

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

〔13〕陳學(xué)松.運(yùn)籌學(xué)中模型優(yōu)化與算法研究[D].華中科技大學(xué)，2015.