0-1整數(shù)規(guī)劃解法

1、二 0-1型整數(shù)規(guī)劃的一般解法-隱枚舉法解0-1型整數(shù)規(guī)劃最容易想到的方法，和一般整數(shù)線性規(guī)劃的情形一樣，就是窮舉法，即檢查變量取值為0或1的每一種組合，比較目標(biāo)函數(shù)值以求得最優(yōu)解， 這就需要檢查變量取值的2n個(gè)組合。對(duì)于變量個(gè)數(shù)n較大(例如n10)，這幾乎是不可能的。而隱枚舉法就是在此基礎(chǔ)上改進(jìn)的，通過加入一定的條件，就能較快的求得最優(yōu)解。只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解，這樣的方法稱為隱枚舉法(implicit enumeration)，分枝定界法也是一種隱枚舉法。其解題關(guān)鍵是尋找可行解，產(chǎn)生過濾條件。 過濾條件：是滿足目標(biāo)函數(shù)值優(yōu)于計(jì)算過的可行解目標(biāo)函數(shù)值的約束條件。下

2、面舉例說明求解0-1型整數(shù)規(guī)劃的隱枚舉法例4.6 : 目標(biāo)函數(shù) max z=3x1-2x2+5x3 約束條件： x1+2x2-x32 （1） x1+4x2+x34 （2） x1+x23 （3） 4x2+x36 （4） x1，x2，x3=0或1 （5） 解題時(shí)先通過試探的方法找一個(gè)可行解，容易看出(x1，x2，x3)=(1，0，0)，滿足（1）（4）條件，算出相應(yīng)的目標(biāo)函數(shù)值z=3。我們?cè)谇笞顑?yōu)解時(shí)，對(duì)于極大化問題，當(dāng)然希望z3，于是增加一個(gè)約束條件： 3x1-2x2+5x33 稱為過濾的條件(filtering constraint)。這樣，原問題的線性約束條件就變成5個(gè)。用全部枚舉的方法，3

3、個(gè)變量共有23=8個(gè)解，原來4個(gè)約束條件，共需32次運(yùn)算。 現(xiàn)在增加了過濾條件，如按下述方法進(jìn)行，就可減少運(yùn)算次數(shù)。將5個(gè)約束條件按（4）順序排好。 對(duì)每個(gè)解，依次代入約束條件左側(cè)，求出數(shù)值，看是否適合不等式條件，如某一條件不適合，同行以下各條件就不必再檢查，因而就減少了運(yùn)算次數(shù)。在計(jì)算過程中，若遇到z值已超過條件右邊的值，應(yīng)改變條件，使右邊值為迄今為止最大者， 然后繼續(xù)作。例如，當(dāng)檢查點(diǎn)(0，0，1)時(shí)，因z=5(3)，所以改進(jìn)過濾條件，用3x1-2x2+5x35 代替，繼續(xù)進(jìn)行。這種對(duì)過濾條件的改進(jìn)，更可以減少計(jì)算量。再改進(jìn)過濾條件，用3x1-2x2+5x38代替，再繼續(xù)進(jìn)行。至此，z值已

4、不能改進(jìn)，即得到最優(yōu)解，解答如前，但計(jì)算已簡化。本例計(jì)算過程實(shí)際只作16次運(yùn)算。即求得最優(yōu)解(x1，x2，x3)=(1，0，1), max z=8注意：一般常重新排列xi的順序使目標(biāo)函數(shù)中xi的系數(shù)是遞增(不減)的，在上例中，改寫 z=3x1-2x2+5x3=-2x2+3x1+5x3因?yàn)?2，3，5是遞增的，變量(x2，x1，x3)也按下述順序取值：(0，0，0)， (0，0，1)，(0，1，0)，(0，1，1)，這樣，最優(yōu)解容易比較早的發(fā)現(xiàn)。 再結(jié)合過濾條件的改進(jìn)，更可使計(jì)算簡化步驟：(1)、用試探法，求出一個(gè)可行解，以它的目標(biāo)值作為當(dāng)前最好值Z0(2)、增加過濾條件Z Z0(3)、將xi

5、按ci由小大排列。最小化問題反之。maxZ = 3x1 -2x2+5x3x1 +2x2 - x3 2 （1）x1 +4x2 +x3 4 （2）x1 + x2 3 （3） 4x2+x3 6 （4）x1 , x2 , x3為0或1解：1.觀察得解(x1 , x2 , x3 )=(1 ,0 ,0) ，Z0 =3 2.過濾條件：3x1 - 2x2+5x3 3 3.將(x1 x2 x3 ) (x2 x1 x3 ) 點(diǎn)(x2 x1 x3 ) 目標(biāo)值 Z0 （1）（2）（3）（4）當(dāng)前最好值 (0 ,0 ,0) 0 5 (0 ,1 ,0) 3 8 (1 ,0 ,0) -2 (1 ,0 ,1) 3 (1 ,1

6、 ,0) 1 (1 ,1 ,1) 6 最優(yōu)解 x = (1 ,0 ,1 )T ， Z=8maxZ = -2x2 + 3x1 +5x3x1 +2x2 - x3 2 （1）x1 +4x2 + x3 4 （2）x1 + x2 3 （3） 4x2+ x3 6 （4）指派問題與匈牙利法指派問題的求解步驟：1) 變換指派問題的系數(shù)矩陣(cij)為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即 從(cij)的每行元素都減去該行的最小元素； 再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。2) 進(jìn)行試指派，以尋求最優(yōu)解。 在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0

7、元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。指派問題與匈牙利法找獨(dú)立0元素，常用的步驟為： 從只有一個(gè)0元素的行開始，給該行中的0元素加圈，記作 。然后劃去 所在列的其它0元素，記作 ；這表示該列所代表的任務(wù)已指派完，不必再考慮別人了。依次進(jìn)行到最后一行。 從只有一個(gè)0元素的列開始（畫的不計(jì)在內(nèi)），給該列中的0元素加圈，記作；然后劃去 所在行的0元素，記作 ，表示此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進(jìn)行到最后一列。 若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少

8、的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。指派問題與匈牙利法 若 元素的數(shù)目m 等于矩陣的階數(shù)n（即：mn），那么這指派問題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。3) 用最少的直線通過所有0元素。其方法： 對(duì)沒有的行打“”； 對(duì)已打“” 的行中所有含元素的列打“” ； 再對(duì)打有“”的列中含 元素的行打“” ； 重復(fù)、直到得不出新的打號(hào)的行、列為止； 對(duì)沒有打號(hào)的行畫橫線，有打號(hào)的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù) l 。注：l 應(yīng)等于m，若不相等，說明試指派過程有誤，回到第2步，另行試指派；若 lm n，表示還不能確定最優(yōu)指派方案，須再變換

9、當(dāng)前的系數(shù)矩陣，以找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第4步。指派問題與匈牙利法4) 變換矩陣(bij)以增加0元素在沒有被直線通過的所有元素中找出最小值，沒有被直線通過的所有元素減去這個(gè)最小元素；直線交點(diǎn)處的元素加上這個(gè)最小值。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第2步。指派問題與匈牙利法例7 有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D。現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？ 任務(wù)人員ABCD甲67112乙4598丙31104丁5982指派問題與匈牙利法解：1）變換系數(shù)矩陣，增加0元素。52）試指

10、派（找獨(dú)立0元素） 找到 3 個(gè)獨(dú)立零元素 但 m = 3 n = 4指派問題與匈牙利法3）作最少的直線覆蓋所有0元素 獨(dú)立零元素的個(gè)數(shù)m等于最少直線數(shù)l，即lm=3n=4；4）沒有被直線通過的元素中選擇最小值為1，變換系數(shù)矩陣，將沒有被直線通過的所有元素減去這個(gè)最小元素；直線交點(diǎn)處的元素加上這個(gè)最小值。得到新的矩陣，重復(fù)2）步進(jìn)行試指派指派問題與匈牙利法000 0 00試指派得到4個(gè)獨(dú)立零元素， 所以最優(yōu)解矩陣為： 即完成4個(gè)任務(wù)的總時(shí)間最少為：241+8=15指派問題與匈牙利法練習(xí) 已知五人分別完成五項(xiàng)工作耗費(fèi)如下表，求最優(yōu)指派方案。 任務(wù)人員ABCDE甲759811乙9127119丙85

11、468丁73696戊467511指派問題與匈牙利法-1-2解：1）變換系數(shù)矩陣，增加0元素。指派問題與匈牙利法2）試指派（找獨(dú)立0元素） 獨(dú)立0元素的個(gè)數(shù)l45，故畫直線調(diào)整矩陣。指派問題與匈牙利法選擇直線外的最小元素為1；直線外元素減1，直線交點(diǎn)元素加1，其他保持不變。指派問題與匈牙利法l =m=4 n=5選擇直線外最小元素為1，直線外元素減1，直線交點(diǎn)元素加1，其他保持不變，得到新的系數(shù)矩陣。指派問題與匈牙利法總費(fèi)用為=5+7+6+6+4=28注：此問題有多個(gè)最優(yōu)解指派問題與匈牙利法總費(fèi)用為=8+9+4+3+4=28指派問題與匈牙利法2. 不平衡的指派問題 當(dāng)人數(shù)m大于工作數(shù)n時(shí)，加上mn

12、項(xiàng)虛擬工作，例如： 當(dāng)人數(shù)m小于工作數(shù)n時(shí)，加上nm個(gè)人，例如指派問題與匈牙利法3. 一個(gè)人可做幾件事的指派問題若某人可做幾件事，則將該人化作相同的幾個(gè)“人”來接受指派，且費(fèi)用系數(shù)取值相同。例如：丙可以同時(shí)任職A和C工作，求最優(yōu)指派方案。指派問題與匈牙利法4. 某事一定不能由某人做的指派問題將該人做此事的效率系數(shù)取做足夠大的數(shù)，可用M表示。練習(xí) 指派甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)。每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示。由于任務(wù)數(shù)多于人數(shù)，考慮任務(wù)E必須完成，其他4項(xiàng)中可任選3項(xiàng)完成。試確定最優(yōu)指派方案，使完成任務(wù)的總時(shí)間最少。 任務(wù)人員ABCDE甲2529314237乙3938262033丙3427284032丁2442362345指派問題與匈牙利法解: 1) 這是不平衡的指派問題，首先轉(zhuǎn)換為標(biāo)準(zhǔn)型，再用匈牙利法求解。