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

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

2、面舉例說明求解0-1型整數規(guī)劃的隱枚舉法例4.6 : 目標函數 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） 解題時先通過試探的方法找一個可行解，容易看出(x1，x2，x3)=(1，0，0)，滿足（1）（4）條件，算出相應的目標函數值z=3。我們在求最優(yōu)解時，對于極大化問題，當然希望z3，于是增加一個約束條件： 3x1-2x2+5x33 稱為過濾的條件(filtering constraint)。這樣，原問題的線性約束條件就變成5個。用全部枚舉的方法，3

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

4、不能改進，即得到最優(yōu)解，解答如前，但計算已簡化。本例計算過程實際只作16次運算。即求得最優(yōu)解(x1，x2，x3)=(1，0，1), max z=8注意：一般常重新排列xi的順序使目標函數中xi的系數是遞增(不減)的，在上例中，改寫 z=3x1-2x2+5x3=-2x2+3x1+5x3因為-2，3，5是遞增的，變量(x2，x1，x3)也按下述順序取值：(0，0，0)， (0，0，1)，(0，1，0)，(0，1，1)，這樣，最優(yōu)解容易比較早的發(fā)現。 再結合過濾條件的改進，更可使計算簡化步驟：(1)、用試探法，求出一個可行解，以它的目標值作為當前最好值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 ) 點(x2 x1 x3 ) 目標值 Z0 （1）（2）（3）（4）當前最好值 (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) 變換指派問題的系數矩陣(cij)為(bij)，使在(bij)的各行各列中都出現0元素，即 從(cij)的每行元素都減去該行的最小元素； 再從所得新系數矩陣的每列元素中減去該列的最小元素。2) 進行試指派，以尋求最優(yōu)解。 在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0

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

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

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

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

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

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