數(shù)學(xué)建模算法之整數(shù)規(guī)劃

1、整數(shù)規(guī)劃 概論 整數(shù)規(guī)劃的一般模型 整數(shù)規(guī)劃解的求解方法 0-1規(guī)劃解的模型與求解方法 蒙特卡洛法一、概論1.定義：數(shù)學(xué)規(guī)劃中的變量（全部或部分）限制為整數(shù)時(shí)，稱為整數(shù)規(guī)劃。例如，所求的解是機(jī)器的臺(tái)數(shù)、人數(shù)、車(chē)輛船只數(shù)等。2.整數(shù)規(guī)劃的分類(lèi)純整數(shù)規(guī)劃：全部決策變量都必須取整數(shù)的線性規(guī)劃?；旌险麛?shù)規(guī)劃：決策變量中有一部分必須取整數(shù)，另一部分可以不取整數(shù)的線性規(guī)劃0-1整數(shù)規(guī)劃：決策變量只能取0或1的線性規(guī)劃二、整數(shù)規(guī)劃的一般模型1max(min)njjjZc x. .st1( , )nijjija xb 0jx i=1,2,n j=1,2mX1,x2xn中部分或全部取整數(shù)例題：設(shè)某企業(yè)有n個(gè)生產(chǎn)

2、車(chē)間需要m種資源，對(duì)于第i個(gè)生產(chǎn)車(chē)間分別利用第j種資源 進(jìn)行生產(chǎn),單位資源可以獲得利潤(rùn)為 （i=1,2n;j=1,2m).若第j種資源的單位價(jià)格為 （j=1,2m),該企業(yè)現(xiàn)有資金M元 。試問(wèn)該企業(yè)應(yīng)購(gòu)買(mǎi)多少第j種資源（總量為 ），又如何分配給所屬的n個(gè)生產(chǎn)車(chē)間，使得總利潤(rùn)最大？ijxijrjajX解 設(shè)決策變量為 （i=1,2n;j=1,2m)表示分配給第i個(gè)車(chē)間第j種資源的資源量，均為非負(fù)整數(shù)，第j種資源的需求總量 (j=1,2m)也都為整數(shù)。 jX1111max,(1,2,),. .0(1,2, )0(1,2,)nnijijijnijjimjjjijjzr xxXjma XMstxinX

3、jm，且為整數(shù)且為整數(shù)問(wèn)題的目標(biāo)函數(shù)為總利潤(rùn)求 的最大值。11nnijijijzr x在這個(gè)問(wèn)題中，所求解均是整數(shù)，初看起來(lái)，似乎只要把已得到的帶有分?jǐn)?shù)或者小數(shù)的解的經(jīng)過(guò)舍入化整就可以了，實(shí)際上這常常是不行的，因?yàn)榛夂蟛灰?jiàn)得是可行解，或雖是可行解但不一定是最優(yōu)解。這種求最優(yōu)整數(shù)規(guī)劃的問(wèn)題就是整數(shù)規(guī)劃。整數(shù)規(guī)劃解的特點(diǎn)：（1）原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致（2）原線性規(guī)劃有可行解但不是整數(shù)，則整數(shù)規(guī)劃無(wú)可行解例1. 原線性規(guī)劃為（3）原線性規(guī)劃有可行解且存在整數(shù)，則整數(shù)規(guī)劃有可行解，但最優(yōu)解值變差12121212min,. .245,0,0.550,min,44

4、zxxstxxxxxxz其最優(yōu)實(shí)數(shù)解為而對(duì)應(yīng)的整數(shù)規(guī)劃無(wú)可行解。1212121212min,. .246,0,0.330,min22=11 min2.zxxstxxxxxxzxxz其最優(yōu)實(shí)數(shù)解為。若限制為整數(shù)，得，三、整數(shù)規(guī)劃解的求解方法1、分支定界法2、割平面法分支定界法1.1分支定界法的基本思想11max(min)( , ) (1,2,)0,njjjnijjijjjzc xa xb imxx 為整數(shù) (j=1,2,? ,n)11max(min)( , ) (1,2,)0,(1,2, )njjjnijjijjzc xa xb imxjn (A)(B)將原問(wèn)題A中整數(shù)約束去掉變?yōu)閱?wèn)題B，求出B

5、的最優(yōu)解1.2分支界定法的一般步驟1）將原整數(shù)規(guī)劃問(wèn)題A去掉所有的整數(shù)約束變?yōu)榫€性規(guī)劃問(wèn)題B,用線性規(guī)劃的方法求解問(wèn)題B:問(wèn)題B無(wú)可行解，則A也無(wú)可行解，停止；問(wèn)題B有最優(yōu)解 ，并是A的可行解，則此解就是A的最優(yōu)解，結(jié)束；問(wèn)題B有最優(yōu)解 ，但不是A的可行解，轉(zhuǎn)下一步*X*X2）將 代入目標(biāo)函數(shù)，其值記為 ，并用觀察法找出A的一個(gè)可行解（整數(shù)解，不妨可取 ），求的目標(biāo)函數(shù)值（下界值），記為 ，則A的最優(yōu)解記為 ，既有 ，轉(zhuǎn)下一步*Xz0(1,2, )jxjnz*z*zzz3）分枝：在問(wèn)題B的最優(yōu)解中任選一個(gè)不滿足整數(shù)約束的變量 ，附加兩個(gè)整數(shù)不等式約束： 到問(wèn)題B中，構(gòu)成兩個(gè)新的子問(wèn)題B1和B2

6、，求B1和B2的解定界：對(duì)每一個(gè)子問(wèn)題的求解結(jié)果，找出最優(yōu)值最小者為新的上界 ，從所有符合整數(shù)得約束條件的分枝中找出目標(biāo)函數(shù)值最大的為新下限jjxb1jjjjxbxb和4）比較與剪枝：各分支問(wèn)題的最優(yōu)值同 比較，如果其值小于 ，則這個(gè)分枝可以減掉，以后不再考慮。 如果其值大于 ，且又不是A的可行解，則繼續(xù)分枝，返回（3），直到最后得到最優(yōu)解使 ，即 為最優(yōu)解 *zz(1,2, )jxjn四、0-1整數(shù)規(guī)劃如果整數(shù)線性規(guī)劃問(wèn)題的所有決策變量 僅限于取0或1兩個(gè)值，則稱此問(wèn)題為0-1線性規(guī)劃，簡(jiǎn)稱為0-1規(guī)劃。0-1規(guī)劃一般模型：jx11max(min)( , ) (1,2,)01(1,2, )n

7、jjjnijjijjzc xa xb imxjn 或1、0-1整數(shù)規(guī)劃模型2、指派（或分配）問(wèn)題 在生產(chǎn)管理上，總希望把人員最佳分配，以發(fā)揮其最大工作效率，創(chuàng)造最大的價(jià)值。 例如：擬分配n人去做n項(xiàng)工作，每人做且僅做一項(xiàng)工作，若分配第i人去做第j項(xiàng)工作，需花費(fèi) 單位時(shí)間，問(wèn)應(yīng)如何分配工作才能使工人花費(fèi)的總時(shí)間最少？ 容易看出，只需給出矩陣C=（ ），C為指派問(wèn)題的系數(shù)矩陣。ijcijc引入0-1變量 1,0,ijijxij第 人做第 項(xiàng)工作第 人不做第 項(xiàng)工作上述指派問(wèn)題的數(shù)學(xué)模型為1111min,1,1, , ,1,1, ,01, ,1, .ijnnijijnijjnijiijc xxins

8、 txjnxi jn或上述指派問(wèn)題的可行解可以用一個(gè)矩陣表示，其每行每列均有且只有一個(gè)元素為一，其余元素均為0.例：五、蒙特卡洛法求解各種類(lèi)型規(guī)劃1.1概論 蒙特卡羅方法又稱隨機(jī)抽樣技巧或統(tǒng)計(jì)試驗(yàn)方法。半個(gè)多世紀(jì)以來(lái)，由于科學(xué)技術(shù)的發(fā)展和電子計(jì)算機(jī)的發(fā)明 ，這種方法作為一種獨(dú)立的方法被提出來(lái)，并首先在核武器的試驗(yàn)與研制中得到了應(yīng)用。蒙特卡羅方法是一種計(jì)算方法，但與一般數(shù)值計(jì)算方法有很大區(qū)別。它是以概率統(tǒng)計(jì)理論為基礎(chǔ)的一種方法。由于蒙特卡羅方法能夠比較逼真地描述事物的特點(diǎn)及物理實(shí)驗(yàn)過(guò)程，解決一些數(shù)值方法難以解決的問(wèn)題，因而該方法的應(yīng)用領(lǐng)域日趨廣泛。1.2基本思想當(dāng)所求問(wèn)題的解是某個(gè)事件的概率，或

9、者是某個(gè)隨機(jī)變量的數(shù)學(xué)期望，或者是與概率、數(shù)學(xué)期望有關(guān)的量時(shí)，通過(guò)某種試驗(yàn)的方法，得出該事件發(fā)生的頻率，或者該隨機(jī)變量若干個(gè)具體觀察值的算術(shù)平均值，通過(guò)它得到問(wèn)題的解。這就是蒙特卡羅方法的基本思想。 因此，可以通俗地說(shuō)，蒙特卡羅方法是用隨機(jī)試驗(yàn)的方法計(jì)算積分，即將所要計(jì)算的積分看作服從某種分布密度函數(shù)f(r)的隨機(jī)變量(r)的數(shù)學(xué)期望 通過(guò)某種試驗(yàn)，得到個(gè)觀察值r1，r2，rN（用概率語(yǔ)言來(lái)說(shuō)，從分布密度函數(shù)f(r)中抽取個(gè)子樣r1，r2，rN，），將相應(yīng)的個(gè)隨機(jī)變量的值g(r1)，g(r2)，g(rN)的算術(shù)平均值 作為積分的估計(jì)值（近似值）。 0)()(drrfrggNiiNrgNg1)(

10、1例例 y=x2,y=12-x與x軸在第一象限圍成一個(gè)曲邊三角形。設(shè)計(jì)一個(gè)隨機(jī)試驗(yàn)，求該圖形面積的近似值。解解 設(shè)計(jì)的隨機(jī)試驗(yàn)思想如下：在矩形區(qū)域 上產(chǎn)生服從均勻分布的107個(gè)隨機(jī)點(diǎn)，統(tǒng)計(jì)隨機(jī)點(diǎn)落在曲邊三角形的頻數(shù)，則曲邊三角形的面積近似為上述矩形的面積乘以頻率。 0,120 9，1.3蒙特卡洛法的特點(diǎn) 優(yōu)點(diǎn)1) 能夠比較逼真地描述具有隨機(jī)性質(zhì)的事物的特點(diǎn)及物理實(shí)驗(yàn)過(guò)程。2) 受幾何條件限制小。3) 收斂速度與問(wèn)題的維數(shù)無(wú)關(guān)。4) 具有同時(shí)計(jì)算多個(gè)方案與多個(gè)未知量的能力。5) 誤差容易確定。6) 程序結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)。 缺點(diǎn)1) 收斂速度慢。2) 誤差具有概率性。3) 在粒子輸運(yùn)問(wèn)題中，計(jì)算結(jié)果與系統(tǒng)大小有關(guān)。1.4主要應(yīng)用范圍蒙特卡羅方法所特有的優(yōu)點(diǎn)，使得它的應(yīng)用范圍越來(lái)越廣。它的主要應(yīng)用范圍包括：粒子輸運(yùn)問(wèn)題，統(tǒng)計(jì)物理，典型數(shù)學(xué)問(wèn)題，真空技術(shù)，激光技術(shù)以及醫(yī)學(xué)，生物，探礦等方面。隨著科學(xué)技術(shù)的發(fā)展，其應(yīng)用范圍將更加