分支定界算法的MATLAB實(shí)現(xiàn)

《分支定界算法的MATLAB實(shí)現(xiàn)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、2007年第20期職業(yè)圈NO.20,2007(總第72期)ZHIYEQUAN(CumulativetyNO.72)分支定界算法的MATLAB實(shí)現(xiàn)郭志軍(遼寧對外經(jīng)貿(mào)學(xué)院,遼寧大連116052)【摘要】分支定界法可求純整數(shù)或混合整數(shù)線性規(guī)劃問題,(2)LP有最優(yōu)解,并且解變量都是整數(shù),因而它也是ILP的求解方法由分支和定界組成?！胺种А睘檎麛?shù)規(guī)劃最優(yōu)解的出現(xiàn)最優(yōu)解,則停止;創(chuàng)造了條件,而“定界”則可以提高搜索的效率。用MATLAB編(3)LP有最優(yōu)解,但不符合ILP中的整數(shù)條件,此時(shí)記它的寫程序,通過計(jì)算機(jī)來完成這一復(fù)雜的過程。目標(biāo)函數(shù)值為,這時(shí)若記為ILP的最優(yōu)目標(biāo)函數(shù)

2、值,則必【關(guān)鍵詞】整數(shù)規(guī)劃;分支定界法;編寫程序有【中圖分類號】TH164【文獻(xiàn)標(biāo)識碼】A其次,給出算法的步驟:【文章編號】1671-5969(2007)20-0139-03第一步——分支:在LP的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量,設(shè)其值為,是不超過的最大整數(shù)。構(gòu)造兩一、求整數(shù)最優(yōu)解問題的提出個(gè)約束條件:和,將兩個(gè)條件分別加入其松把線性規(guī)劃中的某些變量的非負(fù)約束條件改為非負(fù)整變弛問題LP,將LP分成兩個(gè)后繼問題LP1和LP2。不考慮整數(shù)條量,所得到的模型叫做整數(shù)線性規(guī)劃(integerlinearprogramming,件要求,求解LP1和LP2。根據(jù)需要各后繼問題

3、可用類似的方法簡記作ILP),還簡稱為整數(shù)規(guī)劃。如果所有變量都是整變量,叫進(jìn)行分支,如此不斷繼續(xù),直到獲得整數(shù)規(guī)劃的最優(yōu)解,這就是做純整數(shù)規(guī)劃,全是{0,1}變量的,叫做{0,1}規(guī)劃。否則是混合整所謂的“分支”。數(shù)規(guī)劃。第二步——定界:以每個(gè)后繼子問題為一分支并標(biāo)明求解對于整數(shù)規(guī)劃的一個(gè)數(shù)字題,把它的整數(shù)約束條件改為非的結(jié)果,與其他問題的解的結(jié)果一道,找出最優(yōu)目標(biāo)函數(shù)值最小負(fù)約束,得到一個(gè)普通線性規(guī)劃的題目,這個(gè)過程叫做從原問題者作為新的下界,替換,從已符合整數(shù)條件的各分支中,找出ILP得到它的一個(gè)松弛問題LP,說它是“松弛”的,是因?yàn)閺恼麛?shù)目標(biāo)函數(shù)值為最小者作為新的

4、上界,即有。變?yōu)閷?shí)數(shù),條件放寬了許多。第三步——比較與剪支:各分支的最優(yōu)目標(biāo)函數(shù)中若有大于者,則剪掉這一支;若小于,且不符合整數(shù)條件,則重復(fù)第一步驟,一直到最后得到最優(yōu)目標(biāo)函數(shù)值為止,從而得最I(lǐng)LP:優(yōu)整數(shù)解,“分支”為整數(shù)規(guī)劃最優(yōu)解的出現(xiàn)創(chuàng)造了條件,而“定界”則可以提高搜索的效率。經(jīng)驗(yàn)表明:在可能的情況下根據(jù)對實(shí)際問LP:題的了解,實(shí)現(xiàn)選擇一個(gè)合理的“界限”,可以提高分支定界法的搜索效率。下面用一個(gè)例子來說明上述過程:其中例1求解下列整數(shù)規(guī)劃。給定一個(gè)整數(shù)規(guī)劃的數(shù)字題,一個(gè)直觀的求解思路是先做出它的松弛問題。如果松弛問題的最優(yōu)解中每一個(gè)整變量(即分量)的值都滿足各自的

5、整數(shù)約束,原問題得到解決。如果松弛問題的最優(yōu)解中,某個(gè)變量的值不是整數(shù),問題就很難解決。實(shí)踐表明,求解整數(shù)規(guī)劃是一個(gè)很困難的工作。隨著計(jì)算機(jī)技術(shù)的迅猛發(fā)展,數(shù)學(xué)運(yùn)算軟件得到了廣泛的解設(shè)原整數(shù)規(guī)劃問題為ILP,其松弛問題為使用,如:matlab,mathematica,maple等。計(jì)算機(jī)已經(jīng)成為應(yīng)用數(shù)學(xué)軟件求解問題的主要運(yùn)算工具。二、求解整數(shù)規(guī)劃的算法——分支定界法LP:分支定界算法是上個(gè)世紀(jì)60年代初由Land,Doig和Dakin等人提出的可用于求解純整數(shù)或混合整數(shù)線性規(guī)劃問題的算求解線性規(guī)劃問題LP得:法。對于一個(gè)純整數(shù)規(guī)劃ILP問題,求解它的一個(gè)分支定界法的,的

6、基本思路,正如它的名字那樣,主要由“分支”和“定界”組成。按條件和將問題LP分解成子問題LP1和首先討論LP與ILP解的相關(guān)問題:LP2并賦它們下界為14.2.LP的解,可能有以下情況之一:(1)LP沒有可行解,這時(shí)ILP也沒有可行解,則停止;·求線性規(guī)劃子問題LP1得:,;-139-·求線性規(guī)劃子問題LP2得:,;ifnargin<6

7、isempty(lb),lb=zeros(size(f));endmin{}=;ifnargin<5,heq=[];end中1/3,因此以條件和將LP2分成兩ifnargin<4,Geq=[];end個(gè)子問題LP3和LP4并賦它們下界為

8、了14.33.upper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id;·求線性規(guī)劃子問題LP3得:,;ftemp=ILP(lb(:),ub(:));·求線性規(guī)劃子問題LP4得:,;x=opt;y=upper;由于和是原整數(shù)規(guī)劃問題的可行解且min{,}=%下面是子函數(shù)=15,所以置這上界。functionftemp=ILP(vlb,vub)以下再將LP1分支,因所以可按條件globalupperoptcx0AbAeqbeqIDoptions;將LP1分成兩個(gè)問題LP5和LP6,并賦予它們下界14.