第2講整數(shù)規(guī)劃

1、整整 數(shù)數(shù) 規(guī)規(guī) 劃劃2009年8月 1 1 整數(shù)規(guī)劃問題的提出整數(shù)規(guī)劃問題的提出一、整數(shù)規(guī)劃問題的特征：一、整數(shù)規(guī)劃問題的特征： 規(guī)劃中的變量（部分或全部）限制為整數(shù)，若在規(guī)劃中的變量（部分或全部）限制為整數(shù)，若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。效地求解一切整數(shù)規(guī)劃。 二、整數(shù)規(guī)劃問題的求解方法分類：二、整數(shù)規(guī)劃問題的求解方法分類： 1 1、

2、（、（i i）分枝定界法）分枝定界法可求純或混合整數(shù)線性規(guī)劃?？汕蠹兓蚧旌险麛?shù)線性規(guī)劃。（iiii）割平面法）割平面法可求純或混合整數(shù)線性規(guī)劃?？汕蠹兓蚧旌险麛?shù)線性規(guī)劃。（iiiiii）隱枚舉法）隱枚舉法求解求解“0-1”0-1”整數(shù)規(guī)劃：整數(shù)規(guī)劃： 過濾隱枚舉法；過濾隱枚舉法； 分枝隱枚舉法。分枝隱枚舉法。（iviv）匈牙利法）匈牙利法解決指派問題（解決指派問題（“0-1”0-1”規(guī)劃特殊情規(guī)劃特殊情形）。形）。（v v）蒙特卡洛法）蒙特卡洛法求解各種類型規(guī)劃。求解各種類型規(guī)劃。 對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的所有可解空對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的所有可解空

3、間恰當(dāng)?shù)剡M行系統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部間恰當(dāng)?shù)剡M行系統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可行解空間反復(fù)地分割為越來越小的子集，稱為分枝；并且對每可行解空間反復(fù)地分割為越來越小的子集，稱為分枝；并且對每個子集內(nèi)的解集計算一個目標(biāo)下界（對于最小值問題），這稱為個子集內(nèi)的解集計算一個目標(biāo)下界（對于最小值問題），這稱為定界。在每次分枝后，凡是界限超出已知可行解集目標(biāo)值的那些定界。在每次分枝后，凡是界限超出已知可行解集目標(biāo)值的那些子集不再進一步分枝，這樣，許多子集可不予考慮，這稱剪枝。子集不再進一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。這就是分枝定

4、界法的主要思路。分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。由于這方法分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。由于這方法靈活且便于用計算機求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的重要方靈活且便于用計算機求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的重要方法。目前已成功地應(yīng)用于求解生產(chǎn)進度問題、旅行推銷員問題、法。目前已成功地應(yīng)用于求解生產(chǎn)進度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等。工廠選址問題、背包問題及分配問題等。設(shè)有最大化的整數(shù)規(guī)劃問題設(shè)有最大化的整數(shù)規(guī)劃問題A，與它相應(yīng)的線性規(guī)劃為問題，與它相應(yīng)的線性規(guī)劃為問題B，從，從解問題解問題B開始，若其最優(yōu)解不符合開始，若其最優(yōu)解不符合A的整

5、數(shù)條件，那么的整數(shù)條件，那么B的最優(yōu)目的最優(yōu)目標(biāo)函數(shù)必是標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函數(shù)的上界；而的最優(yōu)目標(biāo)函數(shù)的上界；而A的任意可行解的目標(biāo)函的任意可行解的目標(biāo)函數(shù)值將是它的最優(yōu)目標(biāo)函數(shù)的一個下界。數(shù)值將是它的最優(yōu)目標(biāo)函數(shù)的一個下界。分枝定界法就是將分枝定界法就是將B的可行域分成子區(qū)域的方法。逐步減小上界的可行域分成子區(qū)域的方法。逐步減小上界和增大下界，最終求到最優(yōu)目標(biāo)函數(shù)值和增大下界，最終求到最優(yōu)目標(biāo)函數(shù)值 。 LPXbAXtsXCfBnjxXbAXtsXCfATjT標(biāo)準(zhǔn)問題為整數(shù)，設(shè)線性整數(shù)規(guī)劃問題：0.max)(,2,10.max)(fffffnjxAAfBiiiAxiiABiBj時有的最優(yōu)

6、目標(biāo)函數(shù)值，這表示問題以，值，記為試探，求得其目標(biāo)函數(shù)一般可取的一個整數(shù)可行解，用觀察法找最優(yōu)值的的上界，轉(zhuǎn)為記為的整數(shù)條件但不符合有最優(yōu)解若的解。則停（剪枝），得到的整數(shù)條件且符合有最優(yōu)解若無可行解；），說明無可行解，則停（剪枝若：可能得到以下情況之一求解驟）分枝定界法：（一般步A, 1, 0)(22)(,A,)()(,A,)()()(),(1B進行迭代兩個后繼問題。不考慮整數(shù)條件求解這中得到兩個子問題分別加入把，構(gòu)造兩個約束條件：，其值為任選一最優(yōu)）分枝：（分枝與定界：以下進行分枝和定界：),(),()()(),()(1)(變量個不符合整數(shù)條件的解中的B 在1.1212121BBBcccb

7、xcbxbxstepiiiiii（2）定界，以每個后繼問題為一分枝標(biāo)明求解的結(jié)）定界，以每個后繼問題為一分枝標(biāo)明求解的結(jié)果，與其它問題的解的結(jié)果中，找出最優(yōu)目標(biāo)函數(shù)果，與其它問題的解的結(jié)果中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界值最大者作為新的上界 ，從已符合整數(shù)條件的各，從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界若無作用若無作用 不變。不變。第二步：比較與剪枝，各分枝的最優(yōu)目標(biāo)函數(shù)中若有第二步：比較與剪枝，各分枝的最優(yōu)目標(biāo)函數(shù)中若有小于小于 者，則剪掉這枝，即以后不再考慮了。若大者，則剪掉這枝，即以后不再考慮了。若大于于 ，且不符

8、合整數(shù)條件，則重復(fù)第一步驟。一直，且不符合整數(shù)條件，則重復(fù)第一步驟。一直到最后得到到最后得到 為止。得最優(yōu)整數(shù)解。為止。得最優(yōu)整數(shù)解。 fffffff例 求解下述整數(shù)規(guī)劃，且為整數(shù)02, 17022017562719.290140maxxxxxxxTSxxf10 xj3.1 引入引入0-1變量的實際問題變量的實際問題 3.1.1 投資場所的選定投資場所的選定相互排斥的計劃相互排斥的計劃 例例4 某公司擬在市東、西、南三區(qū)建立門市部。擬議中有某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個個位置（點）位置（點）Ai(i=1,27)可供選擇。規(guī)定可供選擇。規(guī)定 在東區(qū)。由在東區(qū)。由A1,A2,A

9、3三個點中至多選兩個；三個點中至多選兩個； 在西區(qū)。由在西區(qū)。由A4,A5兩個點中至少選一個；兩個點中至少選一個；在南區(qū)，由在南區(qū)，由A6,A7兩個點中至少選一個。兩個點中至少選一個。 如選用如選用Ai點，設(shè)備投資估計為點，設(shè)備投資估計為bi元，每年可獲利潤估計為元，每年可獲利潤估計為ci元，元，但投資總額不能超過但投資總額不能超過B元。問應(yīng)選擇哪幾個點可使年利潤為最元。問應(yīng)選擇哪幾個點可使年利潤為最大？大？先引入先引入0-1變量令變量令于是問題可列寫成：于是問題可列寫成： 72 , 1Ai0Ai1ixi點沒被選中當(dāng)點被選中當(dāng)101761542321. .71或xixxxxxxxBbixits

10、i71maxicixiz3.1.2 相互排斥的約束條件相互排斥的約束條件有兩個相互排斥的約束條件有兩個相互排斥的約束條件5x1+4x224 或或7x1+3x2 45 。為了統(tǒng)一在一個問題中，引入為了統(tǒng)一在一個問題中，引入0-1變量變量y，則上述約束條件可改寫，則上述約束條件可改寫為：為： 5x1+4x224+yM,7x1+3x2 45+(1-y)M,y=0或或1 其中其中M是充分大的數(shù)。是充分大的數(shù)。約束條件約束條件x1=0 或或500 x1 800可改寫為可改寫為500 yx1 800y, y=0或或1 如果有如果有m個互相排斥的約束條件：個互相排斥的約束條件： ai1x1+ainxn bi

11、, i=1,2,m為了保證這個約束條件只有一個起作用，我們引入為了保證這個約束條件只有一個起作用，我們引入m個個0-1變量變量和一個充分大的常數(shù)和一個充分大的常數(shù)M而下面這一組而下面這一組m+1個約束條件個約束條件ai1x1+ainxn bi+yiM, i=1,2,m （1）y1+ym=m-1 （2）就合于上述的要求。這是因為，由于（就合于上述的要求。這是因為，由于（2），），m個個yi中只有一個中只有一個能取能取0值，設(shè)值，設(shè)yi*=0，代入（，代入（1），就只有），就只有i=i*的約束條件起作的約束條件起作用，而別的式子都是多余的用，而別的式子都是多余的 3.2 0-1型整數(shù)規(guī)劃解法之一（

12、過濾隱枚舉法）型整數(shù)規(guī)劃解法之一（過濾隱枚舉法）解解0-1型整數(shù)規(guī)劃最容易想到的方法，和一般整數(shù)規(guī)劃的情形一型整數(shù)規(guī)劃最容易想到的方法，和一般整數(shù)規(guī)劃的情形一樣，就是窮舉法，即檢查變量取值為樣，就是窮舉法，即檢查變量取值為0或或1的每一種組合，比較目的每一種組合，比較目標(biāo)函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的標(biāo)函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的2n個組合。對個組合。對于變量個數(shù)于變量個數(shù)n較大較大,這幾乎是不可能的。因此常設(shè)計一些方法，只這幾乎是不可能的。因此常設(shè)計一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。這樣的檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。

13、這樣的方法稱為隱枚舉法（方法稱為隱枚舉法（Implicit Enumeration），分枝定界法也是），分枝定界法也是一種隱枚舉法。當(dāng)然，對有些問題隱枚舉法并不適用，所以有時一種隱枚舉法。當(dāng)然，對有些問題隱枚舉法并不適用，所以有時窮舉法還是必要的。窮舉法還是必要的。例例321523Maxxxxz10,64344223213221321321或xxxxxxxxxxxxx 求解思路及改進措施：求解思路及改進措施：（i） 先試探性求一個可行解，易看出先試探性求一個可行解，易看出(x1,x2,x3)=(1,0,0)滿足約束條件，故為一個可行解，且滿足約束條件，故為一個可行解，且z=3。（ii） 因為是

14、求極大值問題，故求最優(yōu)解時，凡是因為是求極大值問題，故求最優(yōu)解時，凡是目標(biāo)值目標(biāo)值z3的解不必檢驗是否滿足約束條件即可刪的解不必檢驗是否滿足約束條件即可刪除，因它肯定不是最優(yōu)解，于是應(yīng)增加一個約束除，因它肯定不是最優(yōu)解，于是應(yīng)增加一個約束條件（目標(biāo)值下界）：（條件（目標(biāo)值下界）：（iii） 改進過濾條件。改進過濾條件。（iv） 由于對每個組合首先計算目標(biāo)值以驗證過由于對每個組合首先計算目標(biāo)值以驗證過濾條件，故應(yīng)優(yōu)先計算目標(biāo)值大的組合，這樣可濾條件，故應(yīng)優(yōu)先計算目標(biāo)值大的組合，這樣可提前抬高過濾門檻，以減少計算量。提前抬高過濾門檻，以減少計算量。 4 4分派問題及解法分派問題及解法艘艘船船去去航

15、航行行等等。條條航航線線有有項項任任務(wù)務(wù)；臺臺機機床床加加工工類類似似有有：率率最最高高。決決定定如如何何指指派派可可使使總總效效同同任任務(wù)務(wù)的的效效率率不不同同，去去完完成成，各各人人對對完完成成不不個個人人（每每人人一一項項）項項任任務(wù)務(wù)要要分分配配給給題題）：一一、分分派派問問題題（指指派派問問nnnnproblemAssignmentnn 10, 1, 1, 1, 1.min)(01:0.11111或或每每人人一一項項任任務(wù)務(wù)每每項項任任務(wù)務(wù)一一人人模模型型：否否則則項項任任務(wù)務(wù)個個人人完完成成第第第第引引入入（時時間間成成本本等等）項項任任務(wù)務(wù)的的效效率率個個人人完完成成第第第第設(shè)設(shè)

16、一一般般模模型型：ijnjijniijninjijijijijxnixnjxtsxcfPjixjic稱為指派問題的系數(shù)矩陣稱為指派問題的系數(shù)矩陣二、求解方法二、求解方法1 1、直接利用直接利用Matlab的函數(shù)的函數(shù)binprog。整數(shù)規(guī)劃問題的求解可以使用整數(shù)規(guī)劃問題的求解可以使用Lingo等專用軟件。對于一般的整數(shù)等專用軟件。對于一般的整數(shù)規(guī)劃規(guī)劃問題，無法直接利用規(guī)劃規(guī)劃問題，無法直接利用Matlab的函數(shù)，必須利用的函數(shù)，必須利用Matlab編編程實現(xiàn)分枝定界解法和割平面解法。但對于指派問題等特殊的整程實現(xiàn)分枝定界解法和割平面解法。但對于指派問題等特殊的整數(shù)規(guī)劃問題，有時可以直接利用數(shù)

17、規(guī)劃問題，有時可以直接利用Matlab的函數(shù)的函數(shù)binprog。 nnnnnncccccccccC212222111211陣陣上上：數(shù)數(shù)據(jù)據(jù)集集中中在在下下列列系系數(shù)數(shù)矩矩kiackicbakCproofBbBaCkjijijnmij那么，行各元素加上的第設(shè)從與原問題有相同的解。為系數(shù)矩陣的分派問題以那么得到矩陣加上同一個實數(shù)素中的一行（或一列）各元若從矩陣,.,)(2、匈牙利算法由于指派問題的特殊性，又存在著由匈牙利數(shù)學(xué)家Konig提出的更為簡便的解法匈牙利算法。算法主要依據(jù)以下事實： 響最優(yōu)解。目標(biāo)函數(shù)的常數(shù)項不影目標(biāo)函數(shù)：afxaxcxbfnkiinjkjnjijijninjijij1

18、1111條條直直線線覆覆蓋蓋所所有有零零至至少少個個獨獨立立零零元元素素至至少少有有直直線線數(shù)數(shù)。覆覆蓋蓋所所有有零零元元素素的的最最少少的的最最多多個個數(shù)數(shù)等等于于系系數(shù)數(shù)矩矩陣陣中中獨獨立立零零元元素素匈匈牙牙利利關(guān)關(guān)于于獨獨立立元元素素的的定定理理336072395006024310.).(. 3 ExnigoKD nmmn 有有）（覆蓋零的直線數(shù)（覆蓋零的直線數(shù)直線數(shù)直線數(shù)找最少的覆蓋全部零的找最少的覆蓋全部零的）數(shù)為數(shù)為（獨立零個（獨立零個找最多的獨立零個數(shù)找最多的獨立零個數(shù)對偶”關(guān)系對偶”關(guān)系注：這里提供的一種“注：這里提供的一種“”；標(biāo)為“列的其他零元素劃去，同時把該元素所在”則

19、給它加圈，標(biāo)為“中只有一個零元素，對每行檢查，若當(dāng)前行：試派，即找獨立零元素每列均有零元素；，反復(fù)進行，至每行、（列）各元素的最小值列）分別減去該行對矩陣的每一行（每一各元素步驟：設(shè)求匈牙利法求解分派問題0,)0(1. 2. 10min,stepstep。中單個零元素均被處理，直到所有行、列，反復(fù)執(zhí)行”；“去，標(biāo)為在的行的其它零元素劃同時把該元素所加圈，標(biāo)為不算），給它劃去的零個零元素中只有一對每列檢查，若當(dāng)前列210),0(0(2. 3, 0, 1.3210,)0(13stepnmxxnmmijij時時，轉(zhuǎn)轉(zhuǎn)當(dāng)當(dāng)即即為為最最優(yōu)優(yōu)解解。其其余余應(yīng)應(yīng)的的時時，停停止止，所所加加圈圈零零對對當(dāng)當(dāng)記

20、記加加圈圈零零的的個個數(shù)數(shù)為為處處理理。，直直至至所所有有的的零零元元素素被被，反反復(fù)復(fù)進進行行”；與與列列的的其其它它零零元元劃劃去去“同同時時把把該該元元素素所所在在的的行行”“元元素素加加圈圈或或列列，把把其其中中任任一一個個零零選選零零元元素素個個數(shù)數(shù)較較少少的的行行個個，類類似似上上述述辦辦法法：均均多多于于若若同同行行（列列）中中零零元元素素 ”的的行行，列列為為止止。直直到到得得不不出出新新記記“，重重復(fù)復(fù)”；行行，記記“”元元素素所所在在”列列中中，加加圈圈零零“再再對對有有“”；記記“”元元素素所所在在列列，”行行中中，劃劃去去零零“對對有有“；記記號號，無無妨妨記記“對對無

21、無加加圈圈零零元元素素的的行行作作最最小小直直線線數(shù)數(shù)。確確定定覆覆蓋蓋全全部部零零元元素素的的 32)0(3021. 3step)(2. 4.4成功，重新試派成功，重新試派說明試探不說明試探不時，轉(zhuǎn)時，轉(zhuǎn)當(dāng)當(dāng)時，轉(zhuǎn)時，轉(zhuǎn)當(dāng)當(dāng)總線數(shù)總線數(shù)”的列畫一縱線，記”的列畫一縱線，記對所有有“對所有有“”的行畫一橫線；”的行畫一橫線；對所有無“對所有無“stepnlstepnll . 2. 4stepstep轉(zhuǎn)轉(zhuǎn)?！钡牡牧辛兄兄懈鞲髟厮丶蛹由仙纤杏杏浻洝?，”的的行行中中各各元元素素減減去去所所有有記記“，對對最最小小元元素素為為設(shè)設(shè)無無直直線線覆覆蓋蓋部部分分中中的的不不得得出出現(xiàn)現(xiàn)負(fù)負(fù)元元。素素的的個個數(shù)數(shù)，但但變變換換矩矩陣陣，以以增增加加零零元元 減減各各行行最最小小元元，例例467679107104106614159141217766698