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

1、整數(shù)規(guī)劃 概論 整數(shù)規(guī)劃的一般模型 整數(shù)規(guī)劃解的求解方法 0-1規(guī)劃解的模型與求解方法 蒙特卡洛法一、概論1.定義：數(shù)學(xué)規(guī)劃中的變量（全部或部分）限制為整數(shù)時，稱為整數(shù)規(guī)劃。例如，所求的解是機(jī)器的臺數(shù)、人數(shù)、車輛船只數(shù)等。2.整數(shù)規(guī)劃的分類純整數(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個生產(chǎn)

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

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

4、zxxstxxxxxxz其最優(yōu)實(shí)數(shù)解為而對應(yīng)的整數(shù)規(guī)劃無可行解。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)將原問題A中整數(shù)約束去掉變?yōu)閱栴}B，求出B

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

6、，求B1和B2的解定界：對每一個子問題的求解結(jié)果，找出最優(yōu)值最小者為新的上界 ，從所有符合整數(shù)得約束條件的分枝中找出目標(biāo)函數(shù)值最大的為新下限jjxb1jjjjxbxb和4）比較與剪枝：各分支問題的最優(yōu)值同 比較，如果其值小于 ，則這個分枝可以減掉，以后不再考慮。 如果其值大于 ，且又不是A的可行解，則繼續(xù)分枝，返回（3），直到最后得到最優(yōu)解使 ，即 為最優(yōu)解 *zz(1,2, )jxjn四、0-1整數(shù)規(guī)劃如果整數(shù)線性規(guī)劃問題的所有決策變量 僅限于取0或1兩個值，則稱此問題為0-1線性規(guī)劃，簡稱為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、指派（或分配）問題 在生產(chǎn)管理上，總希望把人員最佳分配，以發(fā)揮其最大工作效率，創(chuàng)造最大的價值。 例如：擬分配n人去做n項工作，每人做且僅做一項工作，若分配第i人去做第j項工作，需花費(fèi) 單位時間，問應(yīng)如何分配工作才能使工人花費(fèi)的總時間最少？ 容易看出，只需給出矩陣C=（ ），C為指派問題的系數(shù)矩陣。ijcijc引入0-1變量 1,0,ijijxij第 人做第 項工作第 人不做第 項工作上述指派問題的數(shù)學(xué)模型為1111min,1,1, , ,1,1, ,01, ,1, .ijnnijijnijjnijiijc xxins

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

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

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