整數規劃模型的Matlab程序實現

顧文亞　孟祥瑞

摘 要：整數規劃是線性規劃的基礎上，對部分或全部決策變量為整數的最優化問題的模型、算法及應用等研究，是運籌學和管理科學中應用最基本的模型之一。大多數整數規劃問題的計算求解存在實際的困難，求解一般線性規劃的方法無法求解整數規劃。為加深學生的理解，提高動手能力，本文介紹了一般整數規劃和0-1整數規劃的Matlab命令，并給出具體的實例。

關鍵詞：整數規劃 0-1整數規劃 割平面法 分枝定界法 Matlab

中圖分類號：O221.4 文獻標識碼：A 文章編號：1672-3791（2018）12（c）-0009-02

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

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

1 整數規劃的Matlab函數

3 結語

直接調用Matlab R2014a工具箱，只須編寫很簡單的幾行程序代碼，即可實現對整數規劃，包括對0-1整數規劃的求解，且結果可靠，計算精度高，避免了應用其他語言程序過于復雜、調試困難等缺點，提高了計算效果。

參考文獻

[1] 顧文亞，孟祥瑞，陳允杰.運籌學（上）[M].鎮江：江蘇大學出版社，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 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科學計算[M].北京：清華大學出版社， 2017.