混合整數規劃性質及其構造的超加性函數

楊孝斌

(凱里學院 數學科學學院， 貴州 凱里 556011)

?

混合整數規劃性質及其構造的超加性函數

楊孝斌

(凱里學院 數學科學學院， 貴州 凱里 556011)

摘要：針對混合整數規劃的一般性案例，給出其對應的線性松弛規劃表達.用3個具體案例來解讀有效不等式在整數規劃問題中的使用，引出Gomory整數割平面.構造超加性函數并探尋它和混合整數規劃割平面的關系.分析結果表明：當超加性函數中的參數取值不同時，可以獲得Gomory整數割平面、混合整數規劃的取整割平面及混合整數規劃的整數割平面.

關鍵詞：混合整數規劃； 超加性函數； 割平面； 線性松弛規劃

在整數規劃松弛中求解有效不等式，往往可以將那些非整數最優解排除，并且將整數最優解保留下來[1-3].這個區分非整數最優解和整數最優解的位置，稱為“割平面”，獲得“割平面”的處理也被稱之為“取整”[4-6].大量的研究成果證實，“取整”操作是可以在有限次的運算步驟之后獲得有效不等式[7-11].在整數割平面的理論基礎之上，小數割平面理論也得以建立[12].相關的證明表明：如果獲得小數割平面的方法得當，可以通過有限收斂獲得小數割平面.通過整數割平面理論和小數割平面理論的結合，混合整數割平面理論也得以建，混合整數割平面的有限次收斂特性也被證實[13].在混合整數規劃問題中，獲取混合整數集合的有效不等式是一類重要問題，超加性函數是可以獲取此類有效不等式的重要方法之一[14-15].本文針對混合整數規劃問題展開研究，深入分析混合整數規劃的性質，并探尋獲取混合整數規劃有效不等式的超加性函數方法，進而研究超加性函數中幾類割平面的關系.

1混合整數規劃的性質

混合整數規劃問題為

(1)

線性松弛規劃問題為

(2)

線性松弛規劃問題對應的約束條件形成的凸集為

(3)

式(1)對應的混合整數規劃問題中約束凸包所形成的離散混合集合為

(4)

式(4)中: MIP為整數混合規劃.

定義1對于混合整數規劃問題，要使bx+cy≤d0成為有效不等式，則(x,y)∈QMIP.

定義2要使得bx+cy≤d0成為混合整數規劃問題的割平面，必須滿足Q∩{(x,y)∈Rn+p∶bx+cy≤d0?Q.

2實例

實例1有限容量選址問題的約束模型為

(5)

式(5)中：xi,j≥0；yj∈{0,1}.如果所有可行解都滿足xi,j≤djyj，yj∈{0,1}，那么，xi,j≤min{bi,ci}yj為有效不等式.

實例2假設有多個快遞公司可以解決第j個電商客戶的需求bj，第i個快遞公司的快遞車輛數量為gi，承載能力為hi，第i個快遞公司為第j個電商客戶完成運輸任務的費用是fi,j，相應的整數規劃問題為

(6)

實例3假設一個整數規劃問題的集合為

有效不等式為

對不等式左側執行向上取整操作，即2x1+2x2+x3+x4≥6，其為QIF的有效不等式.

在最優單純型表的條件下，假設該行的基變量是整數變量，同時滿足最優值并不是整數.用一行約束形成割平面，以獲得線形松弛問題的最優解，保留所有整數解.假設單純型表內，行的集合表示為

(7)

設d0?Z，滿足fj=bj-[bj],fj=hj-[hj]，f0=b0-[b0]，那么，式(7)所對應的混合整數割平面為

(8)

因此，式(8)也是QMIP的有效不等式.

3超加性函數的構造及其應用

假設存在一個函數G∶Rm→R1，并且這個函數滿足

1) 函數初值為G(0)=0；

2) 對于Rm域上存在的全部p,q，滿足G(p)+G(q)≤G(p+q)，

則函數G稱之為超加性函數.

當p≤q時，G(p)≤G(q)，超加性函數是非降的.

1)函數Gκ表達的也是一個超加性函數，并且這個超加性函數是非降的；

假設一個混合整數規劃的線性松弛問題，其中的最優單純型表的某一行表示為

(9)

式(9)中：N1為整數變量的非基變量的集合；N2為非整數變量的非基變量的集合.

超加性函數中的參數κ的不同取值對應不同規劃的割平面.

1) 當κ為max{f,f1,…,fn}時，可以獲得Gomory整數割平面；

2) 當κ=f≠0時，可以獲得混合整數規劃的取整割平面；

3) 當κ為min{f,f1,…,fn}時，可以獲得混合整數規劃的整數割平面.

參考文獻：

[1]ARBOBC,MARINELLIF,VENTURAP.One-dimensionalcuttingstockwithalimitednumberofopenstacks:Boundsandsolutionsfromanewintegerlinearprogrammingmodel[J].InternationalTransactionsinOperationalResearch,2016,23(2):47-63.

[2]PAQUAYC,SCHYNSM,LIMBOURGS.Amixedintegerprogrammingformulationforthethree-dimensionalbinpackingproblemderivingfromanaircargoapplication[J].InternationalTransactionsinOperationalResearch,2016,23(2):187-213.

[3]KAYAO,UREKB.Amixedintegernonlinearprogrammingmodelandheuristicsolutionsforlocation,inventoryandpricingdecisionsinaclosedloopsupplychain[J].ComputersandOperationResearch,2016,65(8):93-103.

[4]董振宇，馮恩民，尹洪超，等.國際原油價格預測的雙層隨機整數規劃模型、算法及應用[J].運籌學學報,2015,19(3):18-25.

[5]張甲江，高岳林，高晨陽.非線性混合整數規劃問題的改進量子粒子群算法[J].太原理工大學學報,2015,46(2):196-200.

[6]莊巧莉，戴文戰，王壽光.基于混合整數規劃的一般Petri網死鎖檢測方法[J].控制理論與應用,2015,32(3):374-379.

[7]盧敬.一種求解0-1背包問題的整數混沌粒子群優化算法[J].華僑大學學報(自然科學版),2013,34(5):516-520.

[8]BEHIRYSH.Erratum:SolutionofnonlinearFredholmintegro-differentialequationsusingahybridofblockpulsefunctionsandnormalizedBernsteinpolynomials[J].JournalofComputationalandAppliedMathematics,2016,294:446.

[9]張章，汪亞明，鄭俊褒，等.混沌遺傳算法用于求解混合整數規劃問題[J].工業控制計算機,2015,28(4):123-125.

[10]NAVICKAS Z,RAGULSKIS M.Comments on a new algorithm for automatic computation of solitary wave solutions to nonlinear partial differential equations based on the exp-function method[J].Applied Mathematics and Computation,2014,243(11):419-425.

[11]MESAROS A,HEITTOLA T,DIKMEN O,et al.Sound event detection in real life recordings using coupled matrix factorization of spectral representations and class activity annotations[C]∥IEEE International Conference on Acoustics, Speech and Signal Proceeding.Brisbane:ESTA Press,2015：151-155.

[12]李枝勇,馬良,張惠珍.整數規劃的量子行為蝙蝠算法[J].計算機工程與科學,2014,36(7):1336-1340.

[13]楊明歌,常水珍.求解整數規劃的割平面法的研究[J].洛陽師范學院學報,2014,33(5):1-5.

[14]張小玲,李端.整數規劃新進展[J].運籌學學報,2014,18(1):39-68.

[15]高海云.非線性混合整數規劃的一類罰函數法[J].福州大學學報(自然科學版),2014,42(2):219-225.

(責任編輯： 陳志賢 英文審校： 黃心中)

Properties of Mixed Integer Programming and the Structured of Super Additive Function

YANG Xiaobin

(College of Mathematical Sciences, Kaili University, Kaili 556011, China)

Abstract：To the general case of mixed integer programming, and the corresponding linear relaxation programming is given. By three specific examples to interpret the effective inequality in integer programming problem, and then the Gomory integer cutting plane is introduced. Finally, we construct the super additive function and explore its relation between the cutting plane of the mixed integer programming. Results show that: when the parameters of the super additive functions are respectively chosen different, gomory integer cutting plane, mixed integer linear programming rounding cut plane, mixed integer programming integer cutting plane can be obtained.

Keywords：mixed integer programming; super additive function; cutting plane; linear relaxation programming

中圖分類號：O 221.4

文獻標志碼：A

基金項目：貴州省教育廳優秀科技創新人才科研基金資助項目(2013153)； 凱里學院高層次人才科研啟動項目(BS201309)

通信作者：楊孝斌(1979-)，男，副教授，主要從事混合整數規劃和超加性函數的研究.E-mail:328880809@qq.com.

收稿日期：2015-12-22

doi:10.11830/ISSN.1000-5013.2016.02.0257

文章編號：1000-5013(2016)02-0257-04