5北交大經(jīng)管學(xué)院939管理運(yùn)籌學(xué)教案講義很詳細(xì)有較多例題價(jià)值第7章整數(shù)

1、第四節(jié)0-1整數(shù)規(guī)劃問題的提出：0-1整數(shù)規(guī)劃是線性規(guī)劃及整數(shù)規(guī)劃的一種特殊形式。模型結(jié)構(gòu)和形式是線性規(guī)劃，只是決策變量取0或1。0-1規(guī)劃模型的建立方法例1：投資場所的選定某公司擬在城市的東、西、南三區(qū)建立，擬議中有七個位置Ai（i=1, 2,7), 如選用Ai點(diǎn),設(shè)備投資估計(jì)為bi元, 每年可獲利潤估計(jì)為ci元, 但投資總額利潤為最大?過B元, 問應(yīng)選擇那幾個點(diǎn)年1當(dāng)Ai點(diǎn)被選用xi=1, ,7 0令i當(dāng)Ai點(diǎn)未被選用7maxZcxiii17bxBiis . tix10or1i另外，項(xiàng)目有一些規(guī)定在A1,A2,A3三個點(diǎn)中至多選兩個;在A4,A5兩點(diǎn)中至少選一個;在A6,A7中只能選一個；

2、A1,A7不能同時選；只有在A被選中的情況下，A 才能被選；某市共有6個區(qū)，每個區(qū)都可以設(shè)消防站。市希望設(shè)置消防站最少以便節(jié)省費(fèi)用，但必須保證在城區(qū)任何地方發(fā)生火警時，消防車能在15分鐘內(nèi)趕到現(xiàn)場。據(jù)實(shí)地測定，各區(qū)之間消防車行駛時間如表2所示。建立該問題的規(guī)劃模型。表2一區(qū)二區(qū) 三區(qū) 四區(qū) 五區(qū) 六區(qū)一區(qū)二區(qū)三區(qū)四區(qū)五區(qū)六區(qū)01000272125140例某廠擬采用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運(yùn)(車運(yùn))所受限制如下表, 如采用船運(yùn), 其體積托運(yùn)限制則為45,問兩種貨物托運(yùn)多少箱，可使獲得利潤為最大？貨物體積每箱（ m3）重量每箱（噸） 利潤每箱（百元） 甲424乙51

3、3托運(yùn)限制206解: 設(shè)x1, x2分別表示甲乙兩種貨物的托運(yùn)箱數(shù), 則其整數(shù)規(guī)劃數(shù)學(xué)模型為Z4 x 1max3 x22442xx x55xx x22045yM( 1 12y ) M12s . t610 x 1 , xx 1 , x 2 取整數(shù)10其中當(dāng)采用船運(yùn)方式當(dāng)采用車運(yùn)方式y(tǒng)一般情況下, m個相互排斥的約束條件, 則可變成為:ai1x1+ai2x2+ainxnbi+yiM, y1+y2+ym=m-1其中yi是0, 1變量，且只有一個取0。若上述個方程中，至少有個方程必須滿足時（約束條件相容）？i=1,2,m例設(shè)兩種產(chǎn)品的利潤分別為1,2，需要的工時是和，成本和工時的關(guān)系，確定產(chǎn)品的產(chǎn)量。

4、成本，要求建立整數(shù)規(guī)劃模型，200001500010000工時200030005000Max Z=c1x1+c2x2-10000y1-15000y2-20000y36x1+4x2 2000y1 y1+y2+y3=1yj 為0或1，x j 非負(fù)y2y3例4 某工廠有3種不同的生產(chǎn)方式可供選擇，產(chǎn)量不同，固定成本和變動成本也不相同，各種方式的總成本為Kj+cjxj0 xj 0 xj =0pj=Min Z=(K1y1+c1x1 )+ （K2y2+c2x2 ）+（K3y3+c2x2 ）xj yjM0-1整數(shù)規(guī)劃問題的解法若有n個決策變量, 則可以產(chǎn)生2n個可能變量的組合, 故完全枚舉是不可能的. 求解

5、0-1整數(shù)規(guī)劃問題的解法均是部分枚舉法或稱為隱枚舉法(Implicit enumeration)是: 在2n個可能的變量組合中, 往往只有一部分是可行基本解. 只要發(fā)現(xiàn)某個變量組合不滿足其中的某一約束條件時, 就不必要檢驗(yàn)其它的約束條件是否可行。 若發(fā)現(xiàn)一個可行解, 則根據(jù)它的目標(biāo)函數(shù)值可以產(chǎn)生一個過濾條件(Filtering constra), 對于目標(biāo)函數(shù)值比它差的的變量組合就不必再去檢驗(yàn)它的可行性（類似分支定界法中的定界。實(shí)際上，隱枚舉法是一種特殊的分支定界法）。 在以后求解過程中, 每當(dāng)發(fā)現(xiàn)比原來更好的可行解, 則依次替代原來的過濾條件 (可減少運(yùn)算次數(shù), 較快地發(fā)現(xiàn)最優(yōu)解)。以例子說

6、明上述求解方法例1:求解下述0-1整數(shù)規(guī)劃問題3maZx24s . tx 1 3x36x2 4x 230or1解：求解過程見下表所以，最優(yōu)解為（x1，x2，x3)T=(1,0,1)T, 最優(yōu)值為8.(x1,x2,x3)Z 值約束條件過濾條件（ 0,0,0）0Z0(0,0,1)5Z5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8Z8(1,1,0)1(1,1,1)6注： 當(dāng)決策變量(x1, x2 , x3)按(0,0,0), (0,0,1), (0,1,0), (0,1,1),.方式取值時, 為了減少計(jì)算次數(shù), 通常將目標(biāo)函數(shù)中的決策變量的順序按其系數(shù)的大小重新排序, 以使最優(yōu)

7、較早出現(xiàn)。對最大化問題, 按從小到大的順序排列；對極小化問題, 則相反。例2：求解下述0-1整數(shù)規(guī)劃問題minZx1 x4x44403845s . t5x 4,3or1解：重新排序?yàn)閙iZnxx1x3658s . t3, 3x 4 0or1(x 2 ,x1 ,x4 ,x3 )Z 值約束條件 過濾條件 （ 0,0 ,0 ,0 ）0(0 ,0,0 ,1 )-1(0 ,0,1 ,0 )1(0 ,0,1 ,1 )0(0 ,1,0 ,0 )3(0 ,1,0 ,1 )2(0 ,1,1 ,0 )4(0 ,1,1 ,1 )3Z 3(1 ,0,0 ,0 )7(1 ,0,0 ,1 )6(1 ,0,1 ,0 )8(

8、1 ,0,1 ,1 )7(1 ,1,0 ,0 )10(1 ,1,0 ,1 )9(1 ,1,1 ,0 )11(1 ,1,1 ,1 )10練習(xí)：求解下述整數(shù)規(guī)劃問題min Z 5 1 x4 x4 x5 x525362x2-xo1rs.t.-12 x5 ,2 ,1j0,5j第五節(jié)指派問題（Assignment Problem）1. 標(biāo)準(zhǔn)指派問題的提法及模型指派問題的標(biāo)準(zhǔn)形式是：有n個人和n件事，已知第i個人做第j件事的費(fèi)用為cij（i，j=1，2，n），要求確定人和事之間的一一對應(yīng)的指派方 案，使完成這n件事的總費(fèi)用最小。1若指派第i個人做第j件事 xij設(shè)n2個0-1變量(i,j=1,2, n)0

9、若不指派第i個人做第j件事nn i 1j 1Zminc ij x ijn x ij1數(shù)學(xué)模型為: i 1n s .tx ij1 j 1j x0or1,i ,1, 2 , , nij其中矩陣C稱為是效率矩陣或系數(shù)矩陣。其解的形式可用0-1矩陣的形式來描述，即 (xij)nn。標(biāo)準(zhǔn)的指派問題是一類特殊的整數(shù)規(guī)劃問題，又是特殊的0-1問題。1955年W. W. Kuhn利用匈牙利數(shù)學(xué)規(guī)劃問題和特殊的家D. Konig關(guān)于矩陣中獨(dú)立零元素的定理, 提出了解指派問題的一種算法,上稱之為匈牙利解法。2. 匈牙利解法匈牙利解法的關(guān)鍵是指派問題最優(yōu)解的以下性質(zhì)：若從指派問題的系數(shù)矩陣C=（cij）的某行（或某

10、列）各元素分別減去一個常數(shù)k，得到一個新的矩陣C=（c )，則以C和C為系數(shù)矩陣的兩ij個指派問題有相同的最優(yōu)解。（這種變化不影響約束方程組，而只是使目標(biāo)函數(shù)值減少了常數(shù)k，所以，最優(yōu)解并不改變。）作變換，其不變性是最優(yōu)解對于指派問題，由于系數(shù)矩陣均非負(fù)，故若能在在系數(shù)矩陣中找到n和不同列的零元素（獨(dú)立的0元素），則對應(yīng)的指派方個位于不案總費(fèi)用為零，從而一定是最優(yōu)的。匈牙利法的步驟如下：步1：變換系數(shù)矩陣。對系數(shù)矩陣中的每行元素分別減去該行的最小元素；再對系數(shù)矩陣中的每列元素分別減去該列中的最小元素。若某行或某列已有0元素，就不必要在減了（不能出現(xiàn)負(fù)元素）。步2：在變換后的系數(shù)矩陣中確定獨(dú)立0

11、元素（試指派）。若獨(dú)立0元素已有n個，則已得出最優(yōu)解；若獨(dú)立0元素的個數(shù)少于n個，轉(zhuǎn)步3。確定獨(dú)立0元素的方法：當(dāng)n較小時，可用觀察法、或試探法；當(dāng)n較大時，可按下列順序進(jìn)行從只有一個0元素的行（列）開始，給這個0元素加圈，記作，然后劃去所在的列（行）的其它0元素，記作。給只有一個0元素的列（行）的0加圈，記作，然后劃去所在行的0元素，記作。反復(fù)進(jìn)行，直到系數(shù)矩陣中的所有0元素都被圈去或劃去為止。如遇到行或列中0元素都不只一個（存在0元素的閉回路），可任選其中一個0元素加圈，同時劃去素即是獨(dú)立的0元素。和同列中的其它0元素。被劃圈的0元步3：作最少數(shù)目的直線，覆蓋所有0元素（目的是確定系數(shù)矩陣

12、的下一個變換），可按下述方法進(jìn)行對沒有的行打“”號；在已打“”號的行中，對 所在列打“”在已打“”號的列中，對所在的行打“”號；重復(fù)2）3），直到再也找不到可以打“”號的行或列為止；對沒有打“”的行劃一橫線，對打“”的列劃一縱線，這樣就得到覆蓋所有0元素的最少直線數(shù)。步4：繼續(xù)變換系數(shù)矩陣，目的是增加獨(dú)立0元素的個數(shù)。方法是在未被直線覆蓋的元素中找出一個最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這 一最小元素，以保持原來0元素不變（為了消除負(fù)元素）。得到新的系數(shù)矩陣，返回步2。以例說明匈牙利法的應(yīng)用。例1：求解效率矩陣為如下的指派問題的最優(yōu)指派方案。4979 1

13、2107109有0元素）解：第一步：系數(shù)矩陣的變換（目的是得到某行或52099 003108620007 209795212030645104710第二步：確定獨(dú)立0元素520900310820007 2052元素的個數(shù)m=4，而n=5，進(jìn)行第三步。0306456第三步：作最少的直線覆蓋所有的0元素，目的是確定系數(shù)矩陣的下一個變換。50202230000210850709406365第四步：對上述矩陣進(jìn)行變換，目的是增加獨(dú)立0元素的個數(shù)。方法是在未被直線覆蓋的元素中找出一個最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保持原來0元素不變（消除負(fù)元素）

14、。得到新的系數(shù)矩陣。（它的最優(yōu)解和原問題相同，為什么？）74003200002 00 000110000000100100000100354指派方案和最優(yōu)值為32。由解矩陣?yán)? 某大型工程有五個工程項(xiàng)目，決定向社會公開招標(biāo)，有五家建筑能力相當(dāng)?shù)慕ㄖ痉謩e獲得中標(biāo)承建。已知建筑公司Ai（I=1，2，3，4，5）的報(bào)價(jià)cij（百萬元）見表，問該部門應(yīng)該怎樣分配建造任務(wù)，才能使總的建造費(fèi)用最?。抗こ坦綛1B2B3B4B5A14871512A279171410A3691287A46714610A56912106Z 4 x8 x 10 x6 xmin 1j 1,2, ,5xij i 5 j xij

15、1i 1,2, ,5s.txij 0i, j 1,2, ,5or1有0元素）117解：第一步：系數(shù)矩陣的變換（目的是得到某行或000006307812 712023140935320467129610第二步：確定獨(dú)立0元素, 即加圈000003073531172048120231 元素的個數(shù)m=4，而n=5，進(jìn)4 行第三步。0第三步：作最少的直線覆蓋所有的0元素，目的是確定系數(shù)矩陣的下一個變換。0301180120735720301 4 00 0234第四步：對上述矩陣進(jìn)行變換，目的是增加獨(dú)立0元素個數(shù)。方法是在未被直線覆蓋的元素中找出一個最小元素，然后在打“”行各元素中都減去這一元素，而在打

16、“”列的各元素都加上這一最小元素，以保持原來0元素不變（消除負(fù)元素）。得到新的系數(shù)矩陣。（它的最優(yōu)解和原問題相同，為什么？因?yàn)閮H在目標(biāo)函數(shù)系數(shù)中進(jìn)行操作）0301161048130102062531161048 1202 016253 10 00 014 02400110 3010206253116104802 00 14 10 此矩陣中已有5個獨(dú)立的0元素，故指派問題的最優(yōu)指派方案為：0010001000100000001000001也就是說，最優(yōu)指派方案為：讓A1承建B3， A2承建B2，A3承建 B1，A4承建B4，A5承建B5。這樣安排建造費(fèi)用為最小，即7+9+6+6+6=34（百萬元

17、）3. 一般的指派問題在實(shí)際應(yīng)用中，常會遇到各種非標(biāo)準(zhǔn)形式的指派問題。通常的處理方法是先將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利解法求解。最大化指派問題設(shè)最大化指派問題系數(shù)矩陣C中最大元素為m。令矩陣B=(bij)=(m-cij),則以B為系數(shù)矩陣的最小化指派問題和以C為系數(shù)矩陣的原最大化指派問題有相同的最優(yōu)解。人數(shù)和事數(shù)不等的指派問題若人少事多，則添上一些虛擬的“人”。這些虛擬的人作各事的費(fèi)用系數(shù)可取0，理解為這些費(fèi)用實(shí)際上不會發(fā)生。若人多事少，則添上一些虛擬的“事”。這些虛擬的事被各人做的費(fèi)用系數(shù)同樣也取0。一個人可做幾件事的指派問題若某個人可做幾件事，則可將該人看做相同的幾個人來接受指派。這幾

18、個人作同一件事的費(fèi)用系數(shù)當(dāng)然都一樣。某事一定不能由作的指派問題若某事一定不能由某個人做，則可將相應(yīng)的費(fèi)用系數(shù)取做足夠大的數(shù)M。例3：對于例2的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍 棄建筑公司A4和A5，而讓技術(shù)力量較強(qiáng)的建設(shè)公司A1，A2，A3參加招標(biāo)承建，根據(jù)實(shí)際情況，可允許每家建設(shè)公司承建一項(xiàng)或二項(xiàng)工程。求使總費(fèi)用最少的指派方案。工程公司B1B2B3B4B5A14871512A279171410A3691287解：由于每家建筑公司最多可以承建兩項(xiàng)，因此可把每家建筑公司看成兩家建筑公司，其系數(shù)矩陣為B41B2B3B 415B5 1A287A 3上面的系數(shù)矩陣有6行5列，為了使“人”和“事”的數(shù)目相同，引入一件虛擬的事B6，使之成為標(biāo)準(zhǔn)指派問題的系數(shù)矩陣：BBBBBBA 1A 1 0A02487812 4715141079A 2A 30 97 66121288 97 A 30 費(fèi)用最省為4+7+9+8+7=35（百萬元）然后，用匈牙利解法求解。練習(xí)：某最大化指派問題的效率矩陣如下，求最優(yōu)