混合整數(shù)規(guī)劃性質(zhì)及其構(gòu)造的超加性函數(shù)

楊孝斌

(凱里學(xué)院 數(shù)學(xué)科學(xué)學(xué)院， 貴州 凱里 556011)

?

混合整數(shù)規(guī)劃性質(zhì)及其構(gòu)造的超加性函數(shù)

楊孝斌

(凱里學(xué)院 數(shù)學(xué)科學(xué)學(xué)院， 貴州 凱里 556011)

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

關(guān)鍵詞：混合整數(shù)規(guī)劃； 超加性函數(shù)； 割平面； 線性松弛規(guī)劃

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

1混合整數(shù)規(guī)劃的性質(zhì)

混合整數(shù)規(guī)劃問題為

(1)

線性松弛規(guī)劃問題為

(2)

線性松弛規(guī)劃問題對應(yīng)的約束條件形成的凸集為

(3)

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

(4)

式(4)中: MIP為整數(shù)混合規(guī)劃.

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

定義2要使得bx+cy≤d0成為混合整數(shù)規(guī)劃問題的割平面，必須滿足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假設(shè)有多個快遞公司可以解決第j個電商客戶的需求bj，第i個快遞公司的快遞車輛數(shù)量為gi，承載能力為hi，第i個快遞公司為第j個電商客戶完成運(yùn)輸任務(wù)的費(fèi)用是fi,j，相應(yīng)的整數(shù)規(guī)劃問題為

(6)

實例3假設(shè)一個整數(shù)規(guī)劃問題的集合為

有效不等式為

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

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

(7)

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

(8)

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

3超加性函數(shù)的構(gòu)造及其應(yīng)用

假設(shè)存在一個函數(shù)G∶Rm→R1，并且這個函數(shù)滿足

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

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

則函數(shù)G稱之為超加性函數(shù).

當(dāng)p≤q時，G(p)≤G(q)，超加性函數(shù)是非降的.

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

假設(shè)一個混合整數(shù)規(guī)劃的線性松弛問題，其中的最優(yōu)單純型表的某一行表示為

(9)

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

超加性函數(shù)中的參數(shù)κ的不同取值對應(yīng)不同規(guī)劃的割平面.

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

2) 當(dāng)κ=f≠0時，可以獲得混合整數(shù)規(guī)劃的取整割平面；

3) 當(dāng)κ為min{f,f1,…,fn}時，可以獲得混合整數(shù)規(guī)劃的整數(shù)割平面.

參考文獻(xiàn)：

[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]董振宇，馮恩民，尹洪超，等.國際原油價格預(yù)測的雙層隨機(jī)整數(shù)規(guī)劃模型、算法及應(yīng)用[J].運(yùn)籌學(xué)學(xué)報,2015,19(3):18-25.

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

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

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

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

[9]張章，汪亞明，鄭俊褒，等.混沌遺傳算法用于求解混合整數(shù)規(guī)劃問題[J].工業(yè)控制計算機(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]李枝勇,馬良,張惠珍.整數(shù)規(guī)劃的量子行為蝙蝠算法[J].計算機(jī)工程與科學(xué),2014,36(7):1336-1340.

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

[14]張小玲,李端.整數(shù)規(guī)劃新進(jìn)展[J].運(yùn)籌學(xué)學(xué)報,2014,18(1):39-68.

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

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

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

文獻(xiàn)標(biāo)志碼：A

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

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

收稿日期：2015-12-22

doi:10.11830/ISSN.1000-5013.2016.02.0257

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