整數(shù)規(guī)劃模型的Matlab程序?qū)崿F(xiàn)

顧文亞　孟祥瑞

摘 要：整數(shù)規(guī)劃是線性規(guī)劃的基礎(chǔ)上，對(duì)部分或全部決策變量為整數(shù)的最優(yōu)化問(wèn)題的模型、算法及應(yīng)用等研究，是運(yùn)籌學(xué)和管理科學(xué)中應(yīng)用最基本的模型之一。大多數(shù)整數(shù)規(guī)劃問(wèn)題的計(jì)算求解存在實(shí)際的困難，求解一般線性規(guī)劃的方法無(wú)法求解整數(shù)規(guī)劃。為加深學(xué)生的理解，提高動(dòng)手能力，本文介紹了一般整數(shù)規(guī)劃和0-1整數(shù)規(guī)劃的Matlab命令，并給出具體的實(shí)例。

關(guān)鍵詞：整數(shù)規(guī)劃 0-1整數(shù)規(guī)劃 割平面法 分枝定界法 Matlab

中圖分類號(hào)：O221.4 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2018）12（c）-0009-02

整數(shù)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，給一些或全部決策變量附加取整約束得到的。在整數(shù)規(guī)劃中，如果所有變量都限制為整數(shù)，則稱為純整數(shù)規(guī)劃；如果僅一部分變量限制為整數(shù)，則稱為混合整數(shù)規(guī)劃。整數(shù)規(guī)劃的一種特殊情形是0-1規(guī)劃，它的變量?jī)H限于0或1[1-3]。

若按線性規(guī)劃的方法來(lái)求解整數(shù)規(guī)劃問(wèn)題，最優(yōu)解如果不是整數(shù)，似乎把已得的非整數(shù)解舍入化整就可以了。但實(shí)際上化整后的數(shù)一般不是最優(yōu)解，所以整數(shù)規(guī)劃有自身特有的方法來(lái)求解。目前比較成功又流行的方法是分枝定界法和割平面法[4，5]。求解0-1規(guī)劃的常用方法是枚舉法和隱枚舉法[6]，對(duì)各種特殊問(wèn)題還有一些特殊方法，例如求解指派問(wèn)題的匈牙利法[7，8]。

1 整數(shù)規(guī)劃的Matlab函數(shù)

3 結(jié)語(yǔ)

直接調(diào)用Matlab R2014a工具箱，只須編寫很簡(jiǎn)單的幾行程序代碼，即可實(shí)現(xiàn)對(duì)整數(shù)規(guī)劃，包括對(duì)0-1整數(shù)規(guī)劃的求解，且結(jié)果可靠，計(jì)算精度高，避免了應(yīng)用其他語(yǔ)言程序過(guò)于復(fù)雜、調(diào)試?yán)щy等缺點(diǎn)，提高了計(jì)算效果。

參考文獻(xiàn)

[1] 顧文亞，孟祥瑞，陳允杰.運(yùn)籌學(xué)（上）[M].鎮(zhèn)江：江蘇大學(xué)出版社，2015.

[2] Ping-Qi PAN.Linear Programming Computation[M].Berlin Heidlberg：Springer Verlag，2014.

[3] Williams，H.Paul.Logic and integer programming[M]. Berlin Heidlberg：Springer Verlag，2009.

[4] R.E. Gomory. Outline of an algorithm for integer solutions to linear programs[J]. Bulletin of the American Mathematical Society，1958，64（5）：275-278.

[5] A.H. Land， A.G. Doig.An automatic method of solving discrete programming problems[J].Econometrica，1960，28（3）：497-520.

[6] E Balas，F(xiàn) Glover，S Zionts. An Additive Algorithm for Solving Linear Programs with Zero-One Variable[J]. Operations Research，1965，13（4）：517-549.

[7] Harold W. Kuhn. The Hungarian Method for the assignment problem[J].Naval Research Logistics Quarterly，1955（2）：83-97.

[8] Harold W. Kuhn. Variants of the Hungarian method for assignment problems[J].Naval Research Logistics Quarterly，1956（3）：253-258.

[9] 溫正.MATLAB科學(xué)計(jì)算[M].北京：清華大學(xué)出版社， 2017.