第5章整數(shù)規(guī)劃主講人：晉琳琳學(xué)習(xí)內(nèi)容整數(shù)規(guī)劃的數(shù)學(xué)模型及解分枝定界法割平面法0－1型整數(shù)規(guī)劃指派問(wèn)題整數(shù)規(guī)劃的例子例5.1（p94）貨物體積重量利潤(rùn)甲19542乙273403托運(yùn)限制1365140設(shè)：x1，x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型如右：整數(shù)規(guī)劃的例子例5.2（p73）時(shí)段12345678服務(wù)員最少數(shù)目10x18x29x311x413x5853整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)要求一部分或全部決策變量必須取整數(shù)值的規(guī)劃問(wèn)題稱為整數(shù)規(guī)劃在整數(shù)規(guī)劃中去掉取整數(shù)的約束，剩下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)題稱為該整數(shù)規(guī)劃的松弛問(wèn)題若整數(shù)規(guī)劃的松弛問(wèn)題是線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃的數(shù)學(xué)模型松弛問(wèn)題整數(shù)線性規(guī)劃的幾種類型純整數(shù)線性規(guī)劃混合整數(shù)線性規(guī)劃0-1型整數(shù)線性規(guī)劃純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整數(shù)（這時(shí)引進(jìn)的松弛變量和剩余變量可以不要求取整數(shù)）?；旌险麛?shù)規(guī)劃：只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。

0－1整數(shù)規(guī)劃：所有決策變量只能取0或1兩個(gè)整數(shù)。整數(shù)線性規(guī)劃問(wèn)題解的特點(diǎn)整數(shù)規(guī)劃的可行解集合是它的松弛問(wèn)題可行解集合的一個(gè)子集，即整數(shù)規(guī)劃的可行解一定是其松弛問(wèn)題的可行解（反之不然）整數(shù)規(guī)劃問(wèn)題的最優(yōu)目標(biāo)函數(shù)值不會(huì)優(yōu)于其松弛問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值若松弛問(wèn)題的可行解滿足整數(shù)約束，則它也是整數(shù)規(guī)劃的可行解整數(shù)規(guī)劃問(wèn)題的最優(yōu)解不能由其松弛問(wèn)題最優(yōu)解經(jīng)過(guò)簡(jiǎn)單取整得到松弛問(wèn)題最優(yōu)解整數(shù)規(guī)劃最優(yōu)解不能通過(guò)舍入取整地方法，由松弛問(wèn)題的解得到整數(shù)規(guī)劃的最優(yōu)解按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問(wèn)題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問(wèn)題的可行解集是一個(gè)有限集。

因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（4，2）點(diǎn)為最大值，Z=12。

目前，常用的求解整數(shù)規(guī)劃的方法有：

分支定界法和割平面法對(duì)于特別的0－1規(guī)劃問(wèn)題采用隱枚舉法和匈牙利法。0-1型整數(shù)規(guī)劃0-1變量：只能取值0或1的變量。0-1變量也稱為邏輯變量。它常用來(lái)表示兩個(gè)選項(xiàng)中非此即彼的選擇。如P是一個(gè)方案，則類似，設(shè)A1，A2，A3是三個(gè)方案，則可以用(x1,x2,x3)=(0,1,1)表示采用方案A2,A3但不用方案A1，(x1,x2,x3)=(1,0,1)表示采用方案A1,A3但不用方案A2再比如x1+x2+x3=1表示方案A1,A2,A3中恰好采用一個(gè)x1+x2+x3≤2表示方案A1,A2,A3中最多采用兩個(gè)x1+x2+x3≥2表示方案A1,A2,A3中至少采用兩個(gè)x1≥x3表示如果采用方案A3,則必采用方案A1??????含有相互排斥的約束條件的問(wèn)題設(shè)工序B的每周工時(shí)約束為假設(shè)工序B還有一種新的加工方式，相應(yīng)的每周工時(shí)約束為如果工序B只能從兩種加工方式中選擇其中一種，那么上面兩式就是互為排斥的兩個(gè)約束條件。為了表示在這兩個(gè)約束條件之間進(jìn)行的選擇，可以引入如下的0-1變量：y1=0，若工序B采用了原加工方式1，若工序B不采用了原加工方式y(tǒng)2=0，若工序B采用了新加工方式1，若工序B不采用了新加工方式和于是兩個(gè)互斥的約束條件可以下述三個(gè)約束條件統(tǒng)一起來(lái)：其中M1與M2都是形式上的大正數(shù)。一般地，要從p個(gè)約束條件中恰好選擇q個(gè)條件，則可以引入0-1變量：yi=0，若選擇了第i個(gè)約束條件1，若不選擇了第i個(gè)約束條件(i=1,…,p)于是采用下列約束條件組就可以達(dá)到目的：工件排序問(wèn)題（p138）產(chǎn)品1產(chǎn)品2產(chǎn)品3a11機(jī)床1a13機(jī)床3a14機(jī)床4a21機(jī)床1a22機(jī)床2a24機(jī)床4a32機(jī)床2a33機(jī)床31同一件產(chǎn)品在不同機(jī)床上的加工順序同一件產(chǎn)品在下一臺(tái)機(jī)床上加工的開(kāi)始時(shí)間不得早于在上一臺(tái)機(jī)床上加工的結(jié)束時(shí)間xij表示第i種產(chǎn)品在第j臺(tái)機(jī)床上加工的開(kāi)始時(shí)間。產(chǎn)品1：x11+a11x13

及x13+a13x14產(chǎn)品2：x21+a21x22

及x22+a22x24產(chǎn)品3：x32+a32x332每臺(tái)機(jī)床對(duì)不同產(chǎn)品的加工順序約束一臺(tái)機(jī)床在工作中，若已開(kāi)始的加工還未結(jié)束，則不能開(kāi)始加工另一產(chǎn)品。注意到每臺(tái)機(jī)床可以加工兩種產(chǎn)品。因此可以用0-1變量yi表示第i臺(tái)機(jī)床加工產(chǎn)品的順序。具體表示y1y2y3y40先加工產(chǎn)品11先加工產(chǎn)品20先加工產(chǎn)品21先加工產(chǎn)品30先加工產(chǎn)品11先加工產(chǎn)品30先加工產(chǎn)品11先加工產(chǎn)品2機(jī)床1x11+a11x21+My1及x21+a21x11+M(1-y1)機(jī)床2x22+a22x32+My2及x32+a32x22+M(1-y2)機(jī)床3x13+a13x33+My3及x33+a33x13+M(1-y3)機(jī)床4x14+a14x24+My4及x24+a24x14+M(1-y4)3產(chǎn)品2的加工總時(shí)間約束產(chǎn)品2加工開(kāi)始的時(shí)間是x21，結(jié)束加工的時(shí)間是x24+a24，于是x24+a24–x21d4目標(biāo)函數(shù)的建立設(shè)全部產(chǎn)品加工結(jié)束時(shí)間為W。由于三件產(chǎn)品的加工結(jié)束時(shí)間分別為x14+a14,x24+a24,x33+a33故W=max(x14+a14,x24+a24,x33+a33)根據(jù)問(wèn)題的要求，目標(biāo)函數(shù)為minz=W滿足Wx14+a14Wx24+a24Wx33+a33從而最后得到p140的混合整數(shù)線性規(guī)劃模型0-1型整數(shù)規(guī)劃問(wèn)題的解法枚舉法：列出變量取值為0或1的可能的組合（若有n個(gè)變量則有2n個(gè)組合），再逐一驗(yàn)證它們是否滿足約束條件，然后對(duì)滿足約束條件的可行解計(jì)算目標(biāo)函數(shù)值，其中目標(biāo)函數(shù)值最優(yōu)的就是最優(yōu)解方法的改進(jìn)：通過(guò)設(shè)置過(guò)濾條件有效地減少驗(yàn)證組合為可行解的次數(shù)。(x1,x2,x3)zABCD過(guò)濾條件(0,0,0)(0,0,1)05YYYYYYYY(0,1,0)-2YYYY(0,1,1)3YNYY(1,0,0)3YYYY(1,0,1)8YYYY(1,1,0)1YNYY(1,1,1)6YNYYz≥0z≥5z≥8(x1,x2,x3)zABCD過(guò)濾條件(0,0,0)(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)05-233816YYYYYYYYYYYYz≥0z≥5z≥8指派問(wèn)題指派問(wèn)題的標(biāo)準(zhǔn)形式有n個(gè)人和n件事，已知第i個(gè)人做第j件事的費(fèi)用為cij(i,j=1,2,…,n),要求確定人和事之間的一一指派方案，使完成這n件事的總費(fèi)用最小。標(biāo)準(zhǔn)形式的特點(diǎn)：每個(gè)人必須承擔(dān)也僅承擔(dān)一項(xiàng)任務(wù)，每項(xiàng)任務(wù)必須有人承擔(dān)承擔(dān)任務(wù)的人數(shù)與任務(wù)數(shù)相同目標(biāo)函數(shù)最小化對(duì)何人做何事沒(méi)有限制指派問(wèn)題數(shù)學(xué)模型若引入如下的0-1型變量則數(shù)學(xué)模型為每個(gè)人必須承擔(dān)也只能承擔(dān)一項(xiàng)工作每項(xiàng)工作必須指派給一人也只能指派給一人明顯地不同的n階指派問(wèn)題，有相同的可行解。但最優(yōu)解可能不同。區(qū)別在于它們目標(biāo)函數(shù)的系數(shù)不同。稱指派問(wèn)題的目標(biāo)函數(shù)系數(shù)構(gòu)成的矩陣為系數(shù)矩陣。指派問(wèn)題的解可以用矩陣表示：若矩陣X是指派問(wèn)題的一個(gè)可行解，則它的每一行恰好有一個(gè)元素等于1其余元素為零，每一列也恰好有一個(gè)元素等于1其余元素為零。因此指派問(wèn)題有n!個(gè)可行解。例（p143）B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106

系數(shù)矩陣：系數(shù)矩陣的性質(zhì)系數(shù)矩陣C=(cij)的某行（列）各元素分別減去一個(gè)常數(shù)k，得到一個(gè)新的矩陣C'=(c'ij)，則以C'和C為系數(shù)矩陣的兩個(gè)指派問(wèn)題有相同的最優(yōu)解匈牙利解法（1）變換系數(shù)矩陣：使變換后的矩陣各行各列出現(xiàn)零元素4766601300減去每行最小者減去每列最小者匈牙利解法（2）確定獨(dú)立的零元素若獨(dú)立零元素的個(gè)數(shù)小于矩陣的階數(shù)，轉(zhuǎn)下一步，否則按獨(dú)立零元素進(jìn)行指派對(duì)有唯一零元素的行（列），將零元素圈起來(lái)，再劃去其所在列（行）的其他零元素匈牙利解法（3）用最少的直線覆蓋所有的零元素對(duì)沒(méi)有獨(dú)立零元素的行打“√”在已打“√”行中，選擇劃去零元素的列打“√”在已打“√”列中，選擇圈住了的零元素的行打“√”用線條覆蓋沒(méi)打“√”的行和已打“√”的列匈牙利解法（4）繼續(xù)變換矩陣，使其中出現(xiàn)新的零元素選擇沒(méi)有被覆蓋的元素中最小的元素；沒(méi)有被覆蓋的元素減去這一最小的元素，位于直線交叉處的元素加上這個(gè)最小的元素匈牙利解法（5）重新確定獨(dú)立零元素最優(yōu)指派方案：A1→B3,A2→B2,A3→B1,A4→B4,A5→B5。按照此方案指派費(fèi)用最少，為7+9+6+6+6=34注：匈牙利解法是一反復(fù)迭代的過(guò)程非標(biāo)準(zhǔn)形式的指派問(wèn)題非標(biāo)準(zhǔn)形式的指派問(wèn)題可以化為標(biāo)準(zhǔn)形式的指派問(wèn)題求解非標(biāo)準(zhǔn)形式的指派問(wèn)題（1）最大化指派問(wèn)題：設(shè)最大化指派問(wèn)題的系數(shù)矩陣為C=(cij)，其中最大元素為m，構(gòu)造矩陣B=(bij)=(m-cij)，則以B為系數(shù)矩陣的最小化指派問(wèn)題與以C為系數(shù)矩陣的原最大化指派問(wèn)題有相同的最優(yōu)解非標(biāo)準(zhǔn)形式的指派問(wèn)題（2）人數(shù)和事數(shù)不等的指派問(wèn)題：若人少事多，則添上一些虛擬的“人”，使得人數(shù)與事數(shù)相等，而虛擬的“人”承擔(dān)各事的費(fèi)用為零若人多事少，則添加一些虛擬的事，使人數(shù)與事數(shù)相等，各人做虛擬的“事”的費(fèi)用為零非標(biāo)準(zhǔn)形式的指派問(wèn)題（3）一個(gè)人可做幾件事的指派若某人可做幾件事，則可將此人看作相同的幾個(gè)“人”，這幾個(gè)“人”做同一件事的費(fèi)用相同非標(biāo)準(zhǔn)形式的指派問(wèn)題（4）某事一定不能由某人承擔(dān)若某事一定不能由某人來(lái)做，則可取此人承擔(dān)該件事的費(fèi)用為M例如：人多事少的情形，若某人必須承擔(dān)工作任務(wù)，則此人承擔(dān)虛擬的“事”的費(fèi)用為M；類似地，在人少事多的情形，若某項(xiàng)工作必須完成，則虛擬的“人”做該工作的費(fèi)用為M非標(biāo)準(zhǔn)形式的指派問(wèn)題—例（p147例13）B1B2B3B4B54871512A179171410A2691287A34871512A1’79171410A2’691287A3’B600000048715120487151207917141007917141006912870691287000075