課件及學(xué)習(xí)運(yùn)籌學(xué)20134整數(shù)

1、 4.1 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 4.2 分配問題與匈牙利法 4.3 分枝定界法 4.4 0-1型整數(shù)規(guī)劃 4 整數(shù)規(guī)劃 4.1 整數(shù)規(guī)劃問題的特點(diǎn)及應(yīng)用 在求解線性規(guī)劃問題時(shí)，得到的最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但許多實(shí)際問題要求得到的解為整數(shù)才行。這種要求線性規(guī)劃有整數(shù)解的問題,稱為整數(shù)規(guī)劃(Integer Programming)或簡(jiǎn)稱IP。 例1 某廠擬用火車裝運(yùn)甲、乙兩種貨物集裝箱，每箱的體積、重量、可獲利潤(rùn)以及裝運(yùn)所受限制如下： 貨物集裝箱 體積(米3) 重量(百斤) 利潤(rùn)(百元) 甲 5 2 20 乙 4 5 10 托運(yùn)限制 24 13 問兩種貨物各裝運(yùn)多少箱，可使獲得利潤(rùn)最大？ 是不是

2、可通過把不考慮整數(shù)要求求得的最優(yōu)解經(jīng)過“化整”得到滿足整數(shù)要求的最優(yōu)解呢？ 設(shè)甲、乙兩種貨物裝運(yùn)箱數(shù)分別為x1和x2。顯然，x1、x2都要求為整數(shù),于是可建立整數(shù)規(guī)劃模型如下：Max z20 x1+10 x2 (1) 5x1+4x224 (2) 2x1+5x213 (3) x1,x20 (4) x1,x2為整數(shù) (5) 它和線性規(guī)劃問題的區(qū)別在于條件(5)。 此例可解得x1=4.8,x2=0，湊整為x1=5,x2=0，這就破壞了條件(2)，因而不是可行解；如截?cái)嘈?shù)變?yōu)閤1=4,x2=0，這當(dāng)然滿足所有約束條件，但不是最優(yōu)解，因?yàn)閷?duì)x1=4,x2=0有z80，而對(duì)x1=4,x2=1（也是可行解

3、）有z90。因此要專門研究整數(shù)規(guī)劃的解法。 整數(shù)規(guī)劃的模型對(duì)管理問題的研究意義重大。很多管理問題無法歸結(jié)為線性規(guī)劃的數(shù)學(xué)模型，但是可以通過設(shè)置邏輯變量，建立起整數(shù)規(guī)劃的數(shù)學(xué)模型。1. m個(gè)約束條件中只有k個(gè)起作用2. 約束條件的右端項(xiàng)可能是r個(gè)值（b1,b2,br）中的某一個(gè)3. 兩組條件中滿足其中一組若x14，則x21；否則（ 即x14時(shí) ）， x2 3。4. 用以表示含固定費(fèi)用的函數(shù)例如用xj代表產(chǎn)品j的生產(chǎn)數(shù)量，其生產(chǎn)費(fèi)用函數(shù)通?？杀硎緸椋菏街蠯j是同產(chǎn)量無關(guān)的生產(chǎn)準(zhǔn)備費(fèi)用。問題的目標(biāo)函數(shù)是使所有產(chǎn)品的總生產(chǎn)費(fèi)用為最小。 例 有一份說明書，需譯成英、日、德、俄四種文字?，F(xiàn)有甲、乙、丙、丁

4、四個(gè)人，他們將說明書譯成不同文字所需的時(shí)間如下表。問應(yīng)指派哪個(gè)人完成哪項(xiàng)工作，使所需的總時(shí)間最少？ 一般地，有n項(xiàng)任務(wù)、n個(gè)完成人，第i人完成第j項(xiàng)任務(wù)的代價(jià)為cij（i,j1,2,n）。為了求得總代價(jià)最小的指派方案，引入0-1型變量xij，并令 1 指派第i人去完成第j項(xiàng)任務(wù) xij 0 不指派第i人去完成第j項(xiàng)任務(wù)4.2 分配問題與匈牙利法 指派問題的求解，最簡(jiǎn)便易行的方法是匈牙利法。 可見指派問題是0-1型整數(shù)規(guī)劃的特例。不難發(fā)現(xiàn)，指派問題也是運(yùn)輸問題的特例，其產(chǎn)地和銷地?cái)?shù)都為n，各產(chǎn)地的產(chǎn)量和各銷地的銷量都為1。 數(shù)學(xué)模型為 Min zcijxij n xij1 j=1,2,n i=1

5、 n xij1 i=1,2,n j=1 xij0或1 匈牙利法基于下面的效率矩陣： c11 c12 c1n （cij）= c21 c22 c2n . cn1 cn2 cnn 匈牙利法基于這樣一個(gè)明顯的事實(shí)：如果系數(shù)矩陣的所有元素滿足cij0，而其中有n個(gè)位于不同行不同列的一組0元素，則只要令對(duì)應(yīng)于這些0元素位置的xij1，其余的xij0，就得到最優(yōu)解。 匈牙利法求解分配問題的步驟如下： 0 4 2 0 例如： （cij）= 2 0 7 8 3 1 5 0 0 6 0 3 第一步：變換系數(shù)矩陣，使每行每列都出現(xiàn)0元素。(1)系數(shù)矩陣的各行分別減去各行中的最小元素；(2)所得系數(shù)矩陣的各列再分別減

6、去各列中的最小元素。 第二步：試求最優(yōu)解。 (1)給只有一個(gè)0元素（不含劃去的0）的行中的“0”畫，劃去與同列的其它“0”； (2)給只有一個(gè)0元素（不含劃去的0）的列中的“0”畫，劃去與同行的其它“0”； (3)重復(fù)(1)、(2)，直到無新的畫出。若系數(shù)矩陣中已無未畫也未劃去的“0”，則已得到最多的，轉(zhuǎn)(5)；否則，便出現(xiàn)了0元素的閉回路，轉(zhuǎn)(4)。 (4)從0元素的閉回路上任選一個(gè)“0”畫，劃去其同行同列的其它“0”，轉(zhuǎn)(1)。 (5)顯然，按上述步驟得到的是位于不同行不同列的。若已達(dá)n個(gè)，則指派問題的最優(yōu)解已得到，結(jié)束計(jì)算；否則，轉(zhuǎn)第三步。 第三步：用最少的直線覆蓋所有0元素。 (1)給

7、無的行打“”； (2)給打行中含有0元素的列打“”； (3)給打列中含有元素的行打“”； (4)重復(fù)(2)、(3)，直到無新的“”打出。 (5)給沒有打的行畫橫線，給打的列畫縱線。 第四步：變換系數(shù)矩陣，增加0元素。在未被畫線覆蓋的其它元素中找出最小元素，各打“”行減去最小元素，各打“”列加上最小元素，轉(zhuǎn)第二步。 例 求下列指派問題的最小解。 解： 12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 9 5 0 2 0 22 3 0 0 00 10 5 7 29 8 0 0 40 6 3 6 5 7 0 2 0 2 4 3 0 0

8、0 0 8 3 5 011 8 0 0 4 0 4 1 4 3 于是此問題的最優(yōu)解為:甲B,乙C,丙E, 丁D, 戊A 所需的總費(fèi)用為：Min z=7+6+9+6+4=32 幾種特殊指派問題的處理： 1、目標(biāo)為取極大值的情況。把系數(shù)矩陣中的元素都取其相反數(shù)。 2、任務(wù)數(shù)多于人數(shù)的情況。虛設(shè)人，而虛人完成各項(xiàng)任務(wù)的代價(jià)一般都定為0。 3、人數(shù)多于任務(wù)數(shù)的情況。虛設(shè)任務(wù)，每個(gè)人完成虛任務(wù)的代價(jià)一般都定為0。 分枝定界法是20世紀(jì)60年代由Land-Doig和Dakin等人提出的。這種方法既可用于純整數(shù)規(guī)劃問題，也可用于混合整數(shù)規(guī)劃問題，而且便于用計(jì)算機(jī)求解，所以很快成為解整數(shù)規(guī)劃的最主要的方法。4

9、.3 分枝定界法 設(shè)有最大化的整數(shù)規(guī)劃問題R，與它相應(yīng)的線性規(guī)劃問題為R0，分枝定界法的做法是： (1)用觀察法求R的一個(gè)可行解，其目標(biāo)值便是R的最優(yōu)目標(biāo)值z(mì)*的一個(gè)下界z。 (2)求解R0，得R0的最優(yōu)解x(0)和最優(yōu)值z(mì)0。若x(0)符合R的整數(shù)條件，則顯然x(0)也是R的最優(yōu)解，結(jié)束；否則，以R0作為一個(gè)分枝標(biāo)明求解的結(jié)果，z0是問題R的最優(yōu)目標(biāo)值z(mì)*的一個(gè)上界z。 (3)分枝。取目標(biāo)函數(shù)值最大的一個(gè)枝Rs，在Rs的解中任選一不符合整數(shù)條件的變量xj，其值為bj，構(gòu)造兩個(gè)約束條件xjbj和xjbj+1。將兩個(gè)約束條件分別加入問題Rs，得兩個(gè)后繼規(guī)劃問題Rs1和Rs2。不考慮整數(shù)條件求解這

10、兩個(gè)后繼問題，以每個(gè)后繼問題為一分枝標(biāo)明求解的結(jié)果。 (4)定界。在各分枝中找出目標(biāo)函數(shù)值最大者作為新的上界z；從已符合整數(shù)要求的各分枝中，找出目標(biāo)函數(shù)值最大者作為新的下界z。 (5)比較與剪枝。各分枝的最優(yōu)目標(biāo)函數(shù)值中如果有小于z者，則剪掉這一枝（用打表示），即以后不再考慮了。若已沒有大于z的分枝，則已得到R的最優(yōu)解，結(jié)束；否則，轉(zhuǎn)(3)。例 求解問題 Max z=40 x1+90 x2 9x1+7x2 56 7x1+20 x270 x1,x20, 整數(shù)R0: z0=356 x1=4.81 x2=1.82R1:z1=349 x1=4.00 x2=2.10R2:z2=341 x1=5.00 x

11、2=1.57R12:z12=327x1=1.42x2=3.00 x23R11:z11=340 x1=4.00 x2=2.00R21:z21=308x1=5.44x2=1.00R22:無可行解x1 4x1 1x15x12問題R0為:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x270 x1,x20問題R2為:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 5 x1,x2 0問題R1為:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x1,x20 x2 2問題R11為:Max z=40 x

12、1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x2 2 x1,x20問題R12為:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x2 3 x1,x2 0 0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊形式，它的變量xj僅取值0或1。這種只能取0或1的變量稱為0-1變量或二進(jìn)制變量。 例: 某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個(gè)位置Ai（i=1,2, ,7）可供選擇。規(guī)定：(1)在東區(qū)A1、A2、A3三個(gè)點(diǎn)中至多選兩個(gè)；(2)在西區(qū)A4、A5兩個(gè)點(diǎn)中至少選一個(gè)；(3)在南區(qū)A6、A7兩個(gè)點(diǎn)中至少選一個(gè)。 如選用Ai點(diǎn)，設(shè)備

13、投資估計(jì)為bi元，每年可獲利潤(rùn)估計(jì)為ci元，但投資總額不超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大？4.4 0-1型整數(shù)規(guī)劃 引入0-1變量xi（i=1,2,7）,令 1, 當(dāng)Ai點(diǎn)被選用, xi= 0, 當(dāng)Ai點(diǎn)沒被選用。 （i=1,2,7)Max z= c1x1+c2x2+c7x7 b1x1+b2x2+b7x7B x1+x2+x32x4+x51x6+x71 xi=0或1, i=1,2,7于是建立下列模型: 求解0-1型整數(shù)規(guī)劃最常用的方法是隱枚舉法。 雖然0-1型整數(shù)規(guī)劃的變量取值比較簡(jiǎn)單，但當(dāng)變量個(gè)數(shù)n較大時(shí)，要使用窮舉法求解，即對(duì)變量取值為0或1的每一種組合驗(yàn)證約束條件、比較目標(biāo)函數(shù)值

14、以求得最優(yōu)解，其計(jì)算量仍然是難以完成的。隱枚舉法通過引入過濾條件，將大量不可能是最優(yōu)解的變量取值組合濾掉，從而大幅度減少了計(jì)算量。下面用舉例說明： 例 Max z3x1-2x2+5x3 x1+2x2-x3 2 x1+4x2+x34 x1+ x2 3 4x2+x36 x1, x2, x30或1 先找一個(gè)可行解。容易看出x(1, 0, 0)T就是一個(gè)滿足約束條件的可行解，算出其目標(biāo)值為z3。 增加一個(gè)約束條件 3x1-2x2+5x33 稱為過濾條件。對(duì)每個(gè)解首先驗(yàn)證條件是否滿足。 在計(jì)算過程中，若遇到可行解的z值已超過過濾條件的右端常數(shù)項(xiàng)，則用該z值對(duì)其更新。 xT z值 (0,0,0) (0,0

15、,1) 55(0,1,0) (0,1,1) (1,0,0) (1,0,1) 88(1,1,0) (1,1,1) 于是得最優(yōu)解：x1*1, x2*0, x3*1, z*8 例 求解0-1型整數(shù)規(guī)劃問題 Max z=8x1+2x2-4x3-7x4-5x5 3x1+3x2+x3+2x4+3x54 5x1+3x2-2x3-x4+ x54 xj=0或1，j=1,2,5 變成標(biāo)準(zhǔn)型，要求如下：目標(biāo)函數(shù)求極大化。 對(duì)于目標(biāo)函數(shù)為Min z的極小化問題，令z=-z，使其變?yōu)槟繕?biāo)函數(shù)為Max z的極大化問題。目標(biāo)函數(shù)中所有變量的系數(shù)都為正數(shù)。如果目標(biāo)函數(shù)中變量xj的系數(shù)為負(fù)數(shù)，令xj=1-xj，把模型中的xj用xj代換。變量的排列順序按變量在目標(biāo)函數(shù)中的系數(shù)值從小到大排列。 求解0-1型整數(shù)規(guī)劃，可使用效率更高的分枝定界法。下面用實(shí)例說明：x2 =x3=x5= x4=x1=1, z=10,不可行z=6,不可行z=5,不可行z=3,不可行z=2,不可行x2=0 x1=0z=4, 可行x3=0 x3=0z=