0-1線性規(guī)劃模型的MATLAB實(shí)現(xiàn)及應(yīng)用

《0-1線性規(guī)劃模型的MATLAB實(shí)現(xiàn)及應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、萬(wàn)方數(shù)據(jù)第22卷第12期V01．22No．12徐州工程學(xué)院學(xué)報(bào)JournalofXuzhouInstituteofTechnology2007年12月DEC2007O一1線性規(guī)劃模型的MATLAB實(shí)現(xiàn)及應(yīng)用管志忠1，呂楠2(1．池州職業(yè)技術(shù)學(xué)院，安徽澎州247100)2．徐州工程學(xué)院，江蘇徐州221008)【摘要】用MATLAB程序?qū)崿F(xiàn)了0-1線性規(guī)劃問(wèn)題數(shù)學(xué)模型的求解方法，并進(jìn)一步通過(guò)實(shí)例模型求解方法的分析比較，證明所采用的程序方法有效快捷．文中的程序簡(jiǎn)單明了且具有通用性，只需輸入規(guī)劃模型中對(duì)應(yīng)的相關(guān)矩陣，立即得到最優(yōu)解和最優(yōu)值．【關(guān)鍵詞】O一1線性規(guī)劃；數(shù)學(xué)模型)MATLAB)最優(yōu)

2、解；最優(yōu)值【中圖分類號(hào)】0221．1【文獻(xiàn)標(biāo)識(shí)碼】A【文章編號(hào)】1673—0704(2007)12—0064—040—1線性規(guī)劃是一種特殊形式的整數(shù)規(guī)劃．0—1規(guī)劃在工廠選址問(wèn)題、運(yùn)輸問(wèn)題、投資問(wèn)題、JJn-r．問(wèn)題、開(kāi)發(fā)新產(chǎn)品問(wèn)題等方面有著廣泛的應(yīng)用，隨著一些數(shù)學(xué)計(jì)算軟件包如MATLAB、LINDO等的開(kāi)發(fā)與應(yīng)用，0-1規(guī)劃方法在為管理人員作決策時(shí)提供了科學(xué)的依據(jù)，是實(shí)現(xiàn)管理現(xiàn)代化的有力工具．本文利用MAT—LAB軟件對(duì)0-I線性規(guī)劃模型實(shí)施了程序化，通過(guò)程序的應(yīng)用以及與其它求解方法的分析對(duì)比可以看出，用0-I線性規(guī)劃程序來(lái)解0—1線性規(guī)劃問(wèn)題比現(xiàn)有的隱枚舉法、排序法、窮舉法等方法求

3、解要簡(jiǎn)單快捷得多．1O—l線性規(guī)劃的基本模型在實(shí)際管理中，很多問(wèn)題無(wú)法歸結(jié)為線性規(guī)劃的數(shù)學(xué)模型，但卻可以通過(guò)設(shè)置邏輯變量建立起整數(shù)規(guī)劃的數(shù)學(xué)模型．例如選址決策問(wèn)題：隨著業(yè)務(wù)發(fā)展，某制造公司必須在甲地或乙地建立1至2個(gè)新工廠，此外還考慮建一個(gè)倉(cāng)庫(kù)．若倉(cāng)庫(kù)與工廠設(shè)在同一地點(diǎn)，就可以節(jié)省運(yùn)輸費(fèi)用(若不準(zhǔn)備建工廠，也就不需要建任何倉(cāng)庫(kù))．問(wèn)題的關(guān)鍵是新廠建在甲地還是乙地，或同時(shí)在兩地建廠，建廠同時(shí)還必須考慮建一個(gè)倉(cāng)庫(kù)，倉(cāng)庫(kù)必須建在新廠所在地．當(dāng)不考慮財(cái)務(wù)因素時(shí)，這兩個(gè)地點(diǎn)的優(yōu)劣不相上下，管理層認(rèn)為應(yīng)該在財(cái)務(wù)分析的基礎(chǔ)上做出決策．對(duì)于這樣的問(wèn)題事實(shí)上就是“是一否”或“有一無(wú)”問(wèn)題，可借助整數(shù)規(guī)劃

4、中的O一1整數(shù)變量，確定目標(biāo)函數(shù)，建立數(shù)學(xué)模型．0一I線性規(guī)劃模型的基本形式是：minZ=∑叩』』魯1．。f∑aqXi≤bji=I'2’．．’，m【z，=0或1．『一1，2，?，n0-1線性規(guī)劃模型的解，其實(shí)質(zhì)是各變量間0或1的組合．隨著變量數(shù)目的增加，組合方案數(shù)目將會(huì)很多．目前隱枚舉法和排序法求0-1線性規(guī)劃模型的解，除了對(duì)特殊結(jié)構(gòu)的0-1線性規(guī)劃模型有較高的效率外，一般收效較慢，特別對(duì)于大規(guī)模系統(tǒng)，求解工作量非常大．以下程序很好地解決了此問(wèn)題．2模型求解的Matlab程序?qū)崿F(xiàn)收稿日期：2007—09—21作者簡(jiǎn)介：管志忠(1965一)，男，安徽池州人，副教授，碩士，主要從事應(yīng)用數(shù)學(xué)

5、研究．·64·萬(wàn)方數(shù)據(jù)管志忠，等：0-1線性規(guī)劃模型的MATLAB實(shí)現(xiàn)及應(yīng)用根據(jù)以上0-1線性規(guī)劃數(shù)學(xué)模型，運(yùn)用Matlab軟件編寫的程序(不妨取文件名：LOln．m)Jt口下；functionI-xmin，f3=L01n(c，A，b，N，pre)％求。一1整數(shù)規(guī)劃．minf=c，*《，S．t．A*誓≤b，其中N表示前N個(gè)約束是等式，Pre是等式約束的精度．輸出最優(yōu)解xmin和最優(yōu)值f．ifnargin<5，pre=0；ifnargin<4，N一0；end；end；c=c(：)；b=b(；)；m，n]=size(A)；f=sum(abs(e))；x=zeros(1，n)；ft--0；w

6、hile1JJ一0；ft=dot(e，x)；tl=ft—f；while(t1<=O)&(jjNiftl>0JJ=0lendselseifabs(t1)>preJJ=O；breaksend；endsendifjj=一mf—ft；xmin=x；JJ—O；endsk=1；whilex(k)一=1x(k)一O；ifk=一nreturnsendk=k+1；endx(k)一1；end在本程序中，整數(shù)變量的個(gè)數(shù)不受限制，并且充分利用已經(jīng)得到的計(jì)算結(jié)果來(lái)推出下一步的結(jié)果，使得程序中只使用了加減運(yùn)算，從而大大地減少了目標(biāo)函數(shù)和約束條件

7、的計(jì)算量．運(yùn)用此程序解答0-1線性規(guī)劃問(wèn)題時(shí)，根據(jù)實(shí)際問(wèn)題的模型寫出矩陣c、A、b，確定模型中的約束等式數(shù)N和等式約束的精度pre，然后在Matlab命令窗口中分別輸入c、A、b，再輸A[xmin，f]=L01n(e，A’b，N，pre)，立即得到該模型的最優(yōu)解X。和最優(yōu)值Xo"_-f．3模型程序的應(yīng)用與比較通常解0-1整數(shù)規(guī)劃問(wèn)題所采用的是人們所熟悉的隱枚舉法、排序法等，隱枚舉法簡(jiǎn)單地說(shuō)就是每次只檢查。一1變量組合的一部分就能確定其是否可能成