運(yùn)籌學(xué)與系統(tǒng)分析：第3章 整數(shù)規(guī)劃

1、第三章 整數(shù)規(guī)劃主要內(nèi)容整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)分枝定界法0-1型整數(shù)規(guī)劃指派問題一、整數(shù)規(guī)劃數(shù)學(xué)模型的一般形式整數(shù)線性規(guī)劃可分為：（1）純整數(shù)線性規(guī)劃：全部變量必須取整數(shù)的線性規(guī)劃；（2）混合整數(shù)線性規(guī)劃：部分變量必須取整數(shù)的線性規(guī)劃；（3）0-1整數(shù)線性規(guī)劃：變量只能取0或1的整數(shù)線性規(guī)劃。Max(或 Min)整數(shù)規(guī)劃的松弛問題：不考慮整數(shù)條件的線性規(guī)劃問題。二、整數(shù)規(guī)劃的例子例1：某服務(wù)部門各時(shí)段（每2h為一個(gè)時(shí)段）需要的服務(wù)員人數(shù)如下表，按規(guī)定，服務(wù)員連續(xù)工作8h（4個(gè)時(shí)段）為一班?，F(xiàn)要求安排服務(wù)員的工作時(shí)間，使服務(wù)部門服務(wù)員總數(shù)最少。時(shí)段12345678服務(wù)員最少人數(shù)108911

2、13853解：設(shè)在第 j時(shí)段開始時(shí)上班的服務(wù)員人數(shù)為 xj。由于第 j時(shí)段開始時(shí)上班的服務(wù)員在第(j+3)時(shí)段結(jié)束時(shí)下班，故決策變量只需要考慮x1x5。問題的數(shù)學(xué)模型為：例2：現(xiàn)有資金總額為B?？晒┻x擇的投資項(xiàng)目有n個(gè)，項(xiàng)目j所需投資額和預(yù)期收益分別為 aj和 cj（j=1,2,n）。由于某些原因，有三個(gè)附加條件，第一，若選擇項(xiàng)目1，就必須同時(shí)選擇項(xiàng)目2，反之則不一定；第二，項(xiàng)目3和項(xiàng)目4中至少選擇一個(gè)；第三，項(xiàng)目5，6，7中恰好選擇2個(gè)。問應(yīng)如何選擇投資項(xiàng)目，使得總預(yù)期收益最大？解：每個(gè)投資項(xiàng)目都有被選擇和不被選擇的可能，因此令該整數(shù)規(guī)劃數(shù)學(xué)模型可表示為此為0-1整數(shù)規(guī)劃問題。例3：工廠A1

3、和A2生產(chǎn)某種物資。由于該種物資供不應(yīng)求，故計(jì)劃再建一家工廠。現(xiàn)有A3，A4兩個(gè)建廠方案，只能選擇一個(gè)方案。這種物資的需求地有B1，B2，B3，B4四個(gè)。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運(yùn)費(fèi)cij（i, j=1,2,3,4）見下表。工廠A3，A4每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬元和1500萬元。問應(yīng)建工廠A3還是A4，使每年總費(fèi)用（全部物資運(yùn)費(fèi)與新工廠生產(chǎn)費(fèi)用）最少？cij(萬/kt)B1B2B3B4生產(chǎn)能力ktA12934400A28357600A37612200A44525200需求量kt350400300150解：設(shè)xij為由Ai工廠運(yùn)往Bj需求地的物資數(shù)量(單

4、位kt)，A3和A4只能選擇一個(gè)方案，引入0-1變量則問題的數(shù)學(xué)模型為：三、整數(shù)規(guī)劃解的特點(diǎn)(1)整數(shù)規(guī)劃問題的可行解集合是它的松弛問題可行解集合的一個(gè)子集；(2)整數(shù)規(guī)劃問題的可行解一定也是它的松弛問題的可行解，反之則不一定，因此整數(shù)規(guī)劃最優(yōu)解的目標(biāo)函數(shù)值不會優(yōu)于其松弛問題最優(yōu)解的目標(biāo)函數(shù)值。(3)松弛問題的最優(yōu)解一般不會剛好滿足整數(shù)約束條件，因此對松弛問題最優(yōu)解簡單地取整，所得到的解不一定是整數(shù)規(guī)劃的最優(yōu)解，甚至也不一定是整數(shù)規(guī)劃的可行解。例4：用圖解法求解下面整數(shù)規(guī)劃問題解：畫圖，四邊形OBPC及其內(nèi)部為松弛問題的可行域，整數(shù)格點(diǎn)為整數(shù)規(guī)劃問題的可行解。 根據(jù)目標(biāo)函數(shù)等值線優(yōu)化方向，知P

5、點(diǎn)（x1=18/7, x2=19/7）為其松弛問題的最優(yōu)解，對應(yīng)目標(biāo)函數(shù)值z=94/7。在P點(diǎn)附近對x1，x2簡單取整，得四點(diǎn)A1,A2,A3,A4,其中A1,A2為非可行解，A3,A4雖可行，但不是最優(yōu)解。本例最優(yōu)解為A*(x1=4, x2=2),目標(biāo)函數(shù)值z=12。x1x212345678234maxBA1A2PCOA*A3A4對松弛問題最優(yōu)解簡單取整不是求整數(shù)規(guī)劃的有效方法！3.2 分支定界法分支定界法：一種部分枚舉法，不是一種高效的算法。分支：設(shè)整數(shù)規(guī)劃的松弛問題的最優(yōu)解xi=bi不符合整數(shù)要求，若bi是不超過bi的最大整數(shù)，構(gòu)造兩個(gè)約束條件xibi 和xibi+1，將其并入松弛問題中

6、，形成兩個(gè)分支（后繼問題）。每個(gè)后繼問題又可以產(chǎn)生自己的兩個(gè)分支，這樣不斷按分支搜索最優(yōu)解。定界：在分支過程中，若某后繼問題恰巧獲得整數(shù)規(guī)劃問題的一個(gè)可行解，它的目標(biāo)值就是一個(gè)“界限”，用作衡量處理其它分支的依據(jù)。對于最優(yōu)解目標(biāo)函數(shù)值低于已知“界限”的后繼問題（分支），可以不用分析。分支縮減了最優(yōu)解搜索范圍，定界提高了搜索效率。例：求解整數(shù)規(guī)劃問題x1x212323maxSA(3/2,10/3)01解：設(shè)松弛問題為LP，整數(shù)規(guī)劃問題為IP。圖中S為LP可行域，黑點(diǎn)為IP可行解。用單純形法求得LP最優(yōu)解為A點(diǎn)(x1=3/2, x2=10/3), max z=29/6。此時(shí)LP最優(yōu)解不符合整數(shù)要求

7、。分支：任選一變量。設(shè)選x13/2進(jìn)行分支，可構(gòu)造兩個(gè)分支： x12 () 對應(yīng)LP1 x11 () 對應(yīng)LP2x1x212323maxS201S1CBS1與S2是LP1與LP2的可行域。解LP1分支，最優(yōu)解為B點(diǎn)（x1=2, x2=23/9），Z41/9；解LP2分支，最優(yōu)解為C點(diǎn)（x1=1, x2=7/3），Z=10/3；兩個(gè)解都不符合整數(shù)要求，需繼續(xù)分支。由于B點(diǎn)目標(biāo)函數(shù)值大于C點(diǎn)，優(yōu)先選擇LP1分支進(jìn)行再分支。B點(diǎn)x2=23/9不符合整數(shù)要求，可構(gòu)造兩個(gè)分支： x23 對應(yīng)LP11 x22 對應(yīng)LP12LP11無可行域（不用分析），LP12的可行域?yàn)镾12。解LP12分支，最優(yōu)解為D點(diǎn)

8、（x1=33/14, x2=2），Z61/14；最優(yōu)解不符合整數(shù)要求，需繼續(xù)分支。x1x212323max01S12DS11CB由于D點(diǎn)目標(biāo)函數(shù)值大于C點(diǎn)，優(yōu)先選擇LP12分支進(jìn)行再分支。D點(diǎn)x1=33/14不符合整數(shù)要求，可構(gòu)造兩個(gè)分支： x13 對應(yīng)LP121 x12 對應(yīng)LP122x1x212323max01S121DEBCS122FGS121是LP121的可行域，S122是線段FG，是LP122的可行域；解LP121，最優(yōu)解為E點(diǎn)（x1=3, x2=1），Z4；解LP122，最優(yōu)解為F點(diǎn)（x1=2, x2=2 ），Z4這兩個(gè)解同時(shí)符合整數(shù)要求，目標(biāo)函數(shù)值相等，Z4可作為該整數(shù)規(guī)劃問題目

9、標(biāo)函數(shù)值的一個(gè)界限（下界）。因?yàn)樗笥贑點(diǎn)Z值（10/3），故LP2不用再分析，所有分支分析結(jié)束。原整數(shù)規(guī)劃問題最優(yōu)解為x1=3, x2=1，或x1=2, x2=2。上述分支定界法的過程可用圖表示為：A: x1=3/2, x2=10/3,z=29/6SC: x1=1, x2=7/3,Z=10/3S2B: x1=2, x2=23/9,Z41/9S1D: x1=33/14, x2=2,Z61/14S12無可行解S11F: x1=2, x2=2 ,Z4S122E: x1=3, x2=1,Z4S121x11x12x22x23x12x13總結(jié)：分枝定界法的解題步驟 （1）不考慮整數(shù)約束，解相應(yīng)LP問題（

10、2）檢查是否符合整數(shù)要求，是則得最優(yōu)解，完畢。否則，轉(zhuǎn)下一步（3）任取一個(gè)非整數(shù)變量xi=bi，構(gòu)造兩個(gè)新的約束條件：xibi，xibi+1,分別加入到上一個(gè)LP問題，形成兩個(gè)新的分枝問題。（4）不考慮整數(shù)要求，解分枝問題，若其最優(yōu)解為整數(shù)且此整數(shù)解的Z值大于所有分枝最優(yōu)解的Z值，則得最優(yōu)解。否則取Z值最大的非整數(shù)解，繼續(xù)分解，轉(zhuǎn)第 3步。3.3 0-1型整數(shù)規(guī)劃一、0-1變量及其應(yīng)用 若變量只能取0或1，稱為0-1變量。通常用來表示決策時(shí)是否采取了某個(gè)特定方案，例如 0-1變量也可用于含有相互排斥約束條件的問題中，例：設(shè)工序B原工時(shí)約束條件為 且設(shè)B還有一種新加工方式，對應(yīng)的工時(shí)約束條件為

11、若B只能采用一種加工方式，如何將兩種工時(shí)約束條件統(tǒng)一起來寫入模型中？設(shè)：則工時(shí)約束條件可統(tǒng)一寫為： M是充分大的數(shù)，y1、y2必有一個(gè)為1另一個(gè)為0。當(dāng)采用原加工方式，y1=0，條件成立，條件多余。反之亦然。例：固定費(fèi)用問題。有三種資源(A,B,C)被用于生產(chǎn)三種產(chǎn)品(I,II,III)，資源量、產(chǎn)品單件可變費(fèi)用及售價(jià)、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用如下表。請制訂生產(chǎn)計(jì)劃使總收益最大，試寫出整數(shù)規(guī)劃模型。單耗量IIIIII資源量248500234300123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價(jià)81012 解：總收益等于銷售收入減去生產(chǎn)上述產(chǎn)品的固定費(fèi)用和可變費(fèi)用之

12、和。事先不確定某種產(chǎn)品是否生產(chǎn)，相應(yīng)固定費(fèi)用不能確定。 設(shè)xj是第j種產(chǎn)品的產(chǎn)量，且設(shè)則0-1整數(shù)規(guī)劃模型為： 其中：Mj為xj的某個(gè)上界，根據(jù)前三約束條件可取M1=100, M2=50, M3=34。當(dāng)生產(chǎn)第j種產(chǎn)品，yj1, xj0, 否則yj0，xj0。例：工件排序問題。用4臺機(jī)床加工3件產(chǎn)品，各產(chǎn)品的機(jī)床加工順序、以及產(chǎn)品i在機(jī)床j上的加工工時(shí)aij如下表，已知產(chǎn)品2加工總時(shí)間不得超過d。若要求最短時(shí)間內(nèi)加工完所有產(chǎn)品，請寫出整數(shù)規(guī)劃模型。產(chǎn)品1機(jī)床1(a11)-機(jī)床3(a13)-機(jī)床4（a14）產(chǎn)品2機(jī)床1(a21)-機(jī)床2(a22)-機(jī)床4（a24）產(chǎn)品3 機(jī)床2(a32)-機(jī)床3

13、（a33） 解：設(shè)xij為產(chǎn)品i在機(jī)床j上開始加工的時(shí)間（1）產(chǎn)品加工順序約束：同一產(chǎn)品在下一機(jī)床開始時(shí)間不早于上一機(jī)床結(jié)束時(shí)間（2）機(jī)床對產(chǎn)品的加工順序約束：已開始的加工還沒結(jié)束不能開始另一產(chǎn)品的加工。由于4臺機(jī)床都只加工兩個(gè)產(chǎn)品，引入0-1變量則其中M是足夠大的數(shù)（3）產(chǎn)品2的總加工時(shí)間約束 （4）目標(biāo)函數(shù)的建立 三件產(chǎn)品的加工結(jié)束時(shí)間的最大值為全部產(chǎn)品加工時(shí)間 ，即全部產(chǎn)品實(shí)際加工時(shí)間為 而目標(biāo)函數(shù)可以表示為 最后，整數(shù)規(guī)劃模型可表示為：一、0-1整數(shù)規(guī)劃的解法 0-1整數(shù)規(guī)劃若有n個(gè)變量，則有2n個(gè)可能變量組合，完全枚舉法幾乎不可能，一般用隱枚舉法。因?yàn)?n個(gè)組合中往往只有部分是可行解

14、，只要發(fā)現(xiàn)一個(gè)組合不滿足某一條件，即可放棄分析該組合，同時(shí)針對目標(biāo)函數(shù)可以設(shè)置過濾條件。例：求解0-1整數(shù)規(guī)劃max(a)(b)(c)(d)解：隱枚舉法求解過程如下表16Z8833-2Z55（1，1，0）（1，1，1）（1，0，1）（1，0，0）（0，1，1）（0，1，0）（0，0，1）Z00（0，0，0）dcba過濾條件約束條件Z值（x1,x2,x3)最優(yōu)解=(1,0,1),max z=8。上述算法只用了20次運(yùn)算。3.4 指派問題一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型 有n個(gè)人和n件事，已知第i人做第j事的費(fèi)用為cij，請確定人和事之間的一一對應(yīng)指派方案，使完成n件事的總費(fèi)用最少。 稱矩陣C=

15、(cij)nn為指派問題的系數(shù)矩陣。在實(shí)際問題中，cij可以是費(fèi)用、成本、時(shí)間等。 建立指派問題的數(shù)學(xué)模型時(shí)可引入n2個(gè)0-1變量：問題的數(shù)學(xué)模型可寫為：（）（）（） 約束條件表示每件事必須有且只能由一個(gè)人去做；約束條件表示每個(gè)人必做且只做一件事。例：某商業(yè)公司計(jì)劃開5家新商店，指派5家建筑公司分別承建。已知建筑公司Ai對新商店Bj的建造費(fèi)用報(bào)價(jià)為cij,如下表，寫出指派問題的數(shù)學(xué)模型，使總費(fèi)用最少。cijB1B2B3B4B5A14871512A279171410A3691287A46714610A56912106解：設(shè)0-1變量指派問題的數(shù)學(xué)模型可寫為：二、匈牙利解法 1955年，庫恩利用匈

16、牙利數(shù)學(xué)家康尼格的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問題的一種算法，稱為匈牙利解法。 指派問題最優(yōu)解的性質(zhì)：若從指派問題的系數(shù)矩陣C=(cij)nn的某行（或某列）各元素分別減去一個(gè)常數(shù)k，得到新的系數(shù)矩陣C=(cij)nn。C與C為系數(shù)矩陣的兩個(gè)指派問題有相同的最優(yōu)解。 這種變化并不影響數(shù)學(xué)模型的約束方程組，只是使目標(biāo)函數(shù)值減少了k，所以最優(yōu)解不變。匈牙利解法的一般步驟：（1）變換系數(shù)矩陣(n階)。先對各行元素減去本行最小元素，再對各列元素減去本列最小元素。各行各列至少有一個(gè)0元素，且不出現(xiàn)負(fù)元素；（2）確定獨(dú)立零元素。先在只有1個(gè)0的行（或列）將該0圈中()，同時(shí)這個(gè)所在的列（或行）

17、上所有其它0劃去()， (圈完1個(gè)零的行或列后，2個(gè)0以上的行或列任選1個(gè)0加圈再 ） ，直至所有0被圈或被劃去，被圈的即為獨(dú)立零元素。若有n個(gè)獨(dú)立零元素，令它們都為1，其它元素為0，即得最優(yōu)解矩陣。若少于n個(gè)獨(dú)立零元素，則做能覆蓋所有零元素的最少直線數(shù)目的直線集合，方法如下： 對沒有 的行打“”; 在已打“”的行中，對 所在列打“”; 在已打“”的列中，對 所在行打“”; 重復(fù) 步，直到不能找到打“”的行和列; 對沒有打“”的行劃橫線，對打“”的列劃垂線 。（3）繼續(xù)變換系數(shù)矩陣。 方法:在未被直線覆蓋的元素中找出一個(gè)最小元素，對未被直線覆蓋的元素所在行（或列）都減去這一最小元素，這樣未被直

18、線覆蓋的元素出現(xiàn)0元素，同時(shí)已被直線覆蓋的元素會出現(xiàn)負(fù)元素，為消除負(fù)元素，對它所在列（或行）中各元素都加上這一最小元素即可。返回步驟（2）。如此重復(fù)直到找到最優(yōu)解矩陣。例：用匈牙利解法求解上一例指派問題。其系數(shù)矩陣為解：(1)先對各行元素減去本行最小元素，然后各列也如此得：（2）確定獨(dú)立零元素，對C加圈 只有4個(gè)獨(dú)立零元素，少于矩陣階數(shù)5，則做能覆蓋所有零元素的最少直線數(shù)的直線集合。（3）為使未被直線覆蓋的元素中出現(xiàn)零元素，將第2和第3行元素減去未覆蓋元素的最小元素1，第1列出現(xiàn)負(fù)元素，將第1列所有元素加1，得到（4）回到步驟2，對C”重新加圈確定獨(dú)立零元素（5）已有5個(gè)獨(dú)立零元素，可確定最優(yōu)解絕陣：即最優(yōu)指派方案為：A1承建B3，A2承建B2，A3承建B1，A4承建B4，A5承建B5，總費(fèi)用34萬元。三、非標(biāo)準(zhǔn)形式指派問題 非標(biāo)準(zhǔn)形式的指派問題通常先轉(zhuǎn)換成標(biāo)準(zhǔn)形式，再用匈牙利法求解。（1）最大化指派問題 設(shè)最大化指派問題的系數(shù)矩陣為C=(cij)nn ，其中最大元素為m，令矩陣B=(bij)nn =(m-cij) nn，則以B為系數(shù)矩陣的最小化指派問題和以C為系數(shù)矩陣的原最大化指派問題有相同最優(yōu)解。（2）人數(shù)和事件數(shù)不相等的指派問題 若人少事多，則添上一些虛擬的人，虛擬人做事的費(fèi)用系數(shù)取0；若人多事少，添上一些虛擬的事，它們被人做的費(fèi)用系數(shù)也取0。（3）