第四章 整數(shù)規(guī)劃

1、數(shù)學(xué)建模基礎(chǔ)數(shù)學(xué)建?；A(chǔ)青島科技大學(xué)數(shù)理學(xué)院王天順整整 數(shù)數(shù) 規(guī)規(guī) 劃劃 講講 義義2012年04月 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ī)

2、劃問題的求解方法分類：二、整數(shù)規(guī)劃問題的求解方法分類： 1 1、（、（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ī)劃。2 2整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法 對(duì)

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

4、慮，這稱剪枝。子集不再進(jìn)一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。這就是分枝定界法的主要思路。分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。由于這方法分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。由于這方法靈活且便于用計(jì)算機(jī)求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的重要方靈活且便于用計(jì)算機(jī)求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的重要方法。目前已成功地應(yīng)用于求解生產(chǎn)進(jìn)度問題、旅行推銷員問題、法。目前已成功地應(yīng)用于求解生產(chǎn)進(jìn)度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等。工廠選址問題、背包問題及分配問題等。設(shè)有最大化的整數(shù)規(guī)劃問題設(shè)有最大化的整數(shù)規(guī)劃問題A，與它相應(yīng)的線性

5、規(guī)劃為問題，與它相應(yīng)的線性規(guī)劃為問題B，從，從解問題解問題B開始，若其最優(yōu)解不符合開始，若其最優(yōu)解不符合A的整數(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ù)的一個(gè)下界。數(shù)值將是它的最優(yōu)目標(biāo)函數(shù)的一個(gè)下界。分枝定界法就是將分枝定界法就是將B的可行域分成子區(qū)域的方法。逐步減小上界的可行域分成子區(qū)域的方法。逐步減小上界和增大下界，最終求到最優(yōu)目標(biāo)函數(shù)值和增大下界，最終求到最優(yōu)目標(biāo)函數(shù)值 。 LPXbAXtsXCfBnjxXbAXtsXCfATjT標(biāo)準(zhǔn)問題為整數(shù)，設(shè)線

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

7、和定界：),(),()()(),()(1)(變量個(gè)不符合整數(shù)條件的解中的B 在1.1212121BBBcccbxcbxbxstepiiiiii（2）定界，以每個(gè)后繼問題為一分枝標(biāo)明求解的結(jié)）定界，以每個(gè)后繼問題為一分枝標(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)

8、函數(shù)中若有小于小于 者，則剪掉這枝，即以后不再考慮了。若大者，則剪掉這枝，即以后不再考慮了。若大于于 ，且不符合整數(shù)條件，則重復(fù)第一步驟。一，且不符合整數(shù)條件，則重復(fù)第一步驟。一直到最后得到直到最后得到 為止。得最優(yōu)整數(shù)解。為止。得最優(yōu)整數(shù)解。 fffffff例 求解下述整數(shù)規(guī)劃，且為整數(shù)02, 17022017562719.290140maxxxxxxxTSxxf3 3 0-1型整數(shù)規(guī)劃10 xj3.1 引入引入0-1變量的實(shí)際問題變量的實(shí)際問題 3.1.1 投資場(chǎng)所的選定投資場(chǎng)所的選定相互排斥的計(jì)劃相互排斥的計(jì)劃 例例4 某公司擬在市東、西、南三區(qū)建立門市部。擬議中有某公司擬在市東、西、南

9、三區(qū)建立門市部。擬議中有7個(gè)個(gè)位置（點(diǎn)）位置（點(diǎn)）Ai(i=1,27)可供選擇。規(guī)定可供選擇。規(guī)定 在東區(qū)。由在東區(qū)。由A1,A2,A3三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)； 在西區(qū)。由在西區(qū)。由A4,A5兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由在南區(qū)，由A6,A7兩個(gè)點(diǎn)中至少選一個(gè)。兩個(gè)點(diǎn)中至少選一個(gè)。 如選用如選用Ai點(diǎn)，設(shè)備投資估計(jì)為點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤估計(jì)為元，每年可獲利潤估計(jì)為ci元，元，但投資總額不能超過但投資總額不能超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤為最元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤為最大？大？先引入先引入0-1變量令變量令于是問題可列寫成：于是問

10、題可列寫成： 72 , 1Ai0Ai1ixi點(diǎn)沒被選中當(dāng)點(diǎn)被選中當(dāng)101761542321. .71或xixxxxxxxBbixitsi71maxicixiz3.1.2 相互排斥的約束條件相互排斥的約束條件有兩個(gè)相互排斥的約束條件有兩個(gè)相互排斥的約束條件5x1+4x224 或或7x1+3x2 45 。為了統(tǒng)一在一個(gè)問題中，引入為了統(tǒng)一在一個(gè)問題中，引入0-1變量變量y，則上述約束條件可改，則上述約束條件可改寫寫為：為： 5x1+4x224+yM,7x1+3x2 45+(1-y)M,y=0或或1 其中其中M是充分大的數(shù)。是充分大的數(shù)。約束條件約束條件x1=0 或或500 x1 800可改寫為可改

11、寫為500 yx1 800y, y=0或或1 如果有如果有m個(gè)互相排斥的約束條件：個(gè)互相排斥的約束條件： ai1x1+ainxn bi, i=1,2,m為了保證這個(gè)約束條件只有一個(gè)起作用，我們引入為了保證這個(gè)約束條件只有一個(gè)起作用，我們引入m個(gè)個(gè)0-1變量變量和一個(gè)充分大的常數(shù)和一個(gè)充分大的常數(shù)M而下面這一組而下面這一組m+1個(gè)約束條件個(gè)約束條件ai1x1+ainxn bi+yiM, i=1,2,m （1）y1+ym=m-1 （2）就合于上述的要求。這是因?yàn)?，由于（就合于上述的要求。這是因?yàn)?，由于?），），m個(gè)個(gè)yi中只有一個(gè)中只有一個(gè)能取能取0值，設(shè)值，設(shè)yi*=0，代入（，代入（1），就

12、只有），就只有i=i*的約束條件起作的約束條件起作用，而別的式子都是多余的用，而別的式子都是多余的 3.2 0-1型整數(shù)規(guī)劃解法之一（過濾隱枚舉法）型整數(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個(gè)組合。對(duì)個(gè)組合。對(duì)于變量個(gè)數(shù)于變量個(gè)數(shù)n較大較大,這幾乎是不可能的。因此常設(shè)計(jì)一些方法，只這幾乎是不可

13、能的。因此常設(shè)計(jì)一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。這樣的檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。這樣的方法稱為隱枚舉法（方法稱為隱枚舉法（Implicit Enumeration），分枝定界法也是），分枝定界法也是一種隱枚舉法。當(dāng)然，對(duì)有些問題隱枚舉法并不適用，所以有時(shí)一種隱枚舉法。當(dāng)然，對(duì)有些問題隱枚舉法并不適用，所以有時(shí)窮舉法還是必要的。窮舉法還是必要的。例例321523Maxxxxz10,64344223213221321321或xxxxxxxxxxxxx 求解思路及改進(jìn)措施：求解思路及改進(jìn)措施：（i） 先試探性求一個(gè)可行解，易看出先試探性求一個(gè)可行

14、解，易看出(x1,x2,x3)=(1,0,0)滿足約束條件，故為一個(gè)可行解，且滿足約束條件，故為一個(gè)可行解，且z=3。（ii） 因?yàn)槭乔髽O大值問題，故求最優(yōu)解時(shí)，凡是因?yàn)槭乔髽O大值問題，故求最優(yōu)解時(shí)，凡是目標(biāo)值目標(biāo)值z(mì)3的解不必檢驗(yàn)是否滿足約束條件即可刪的解不必檢驗(yàn)是否滿足約束條件即可刪除，因它肯定不是最優(yōu)解，于是應(yīng)增加一個(gè)約束除，因它肯定不是最優(yōu)解，于是應(yīng)增加一個(gè)約束條件（目標(biāo)值下界）：（條件（目標(biāo)值下界）：（iii） 改進(jìn)過濾條件。改進(jìn)過濾條件。（iv） 由于對(duì)每個(gè)組合首先計(jì)算目標(biāo)值以驗(yàn)證過由于對(duì)每個(gè)組合首先計(jì)算目標(biāo)值以驗(yàn)證過濾條件，故應(yīng)優(yōu)先計(jì)算目標(biāo)值大的組合，這樣可濾條件，故應(yīng)優(yōu)先計(jì)算目

15、標(biāo)值大的組合，這樣可提前抬高過濾門檻，以減少計(jì)算量。提前抬高過濾門檻，以減少計(jì)算量。 4 4分派問題及解法分派問題及解法艘艘船船去去航航行行等等。條條航航線線有有項(xiàng)項(xiàng)任任務(wù)務(wù)；臺(tái)臺(tái)機(jī)機(jī)床床加加工工類類似似有有：率率最最高高。決決定定如如何何指指派派可可使使總總效效同同任任務(wù)務(wù)的的效效率率不不同同，去去完完成成，各各人人對(duì)對(duì)完完成成不不個(gè)個(gè)人人（每每人人一一項(xiàng)項(xiàng)）項(xiàng)項(xiàng)任任務(wù)務(wù)要要分分配配給給題題）：一一、分分派派問問題題（指指派派問問nnnnproblemAssignmentnn 10, 1, 1, 1, 1.min)(01:0.11111或或每每人人一一項(xiàng)項(xiàng)任任務(wù)務(wù)每每項(xiàng)項(xiàng)任任務(wù)務(wù)一一人人模模

16、型型：否否則則項(xiàng)項(xiàng)任任務(wù)務(wù)個(gè)個(gè)人人完完成成第第第第引引入入（時(shí)時(shí)間間成成本本等等）項(xiàng)項(xiàng)任任務(wù)務(wù)的的效效率率個(gè)個(gè)人人完完成成第第第第設(shè)設(shè)一一般般模模型型：ijnjijniijninjijijijijxnixnjxtsxcfPjixjic稱為指派問題的系數(shù)矩陣稱為指派問題的系數(shù)矩陣二、求解方法二、求解方法1 1、直接利用直接利用Matlab的函數(shù)的函數(shù)binprog。整數(shù)規(guī)劃問題的求解可以使用整數(shù)規(guī)劃問題的求解可以使用Lingo等專用軟件。對(duì)于一般的整數(shù)等專用軟件。對(duì)于一般的整數(shù)規(guī)劃規(guī)劃問題，無法直接利用規(guī)劃規(guī)劃問題，無法直接利用Matlab的函數(shù)，必須利用的函數(shù)，必須利用Matlab編編程實(shí)現(xiàn)分

17、枝定界解法和割平面解法。但對(duì)于指派問題等特殊的整程實(shí)現(xiàn)分枝定界解法和割平面解法。但對(duì)于指派問題等特殊的整數(shù)規(guī)劃問題，有時(shí)可以直接利用數(shù)規(guī)劃問題，有時(shí)可以直接利用Matlab的函數(shù)的函數(shù)binprog。 nnnnnncccccccccC212222111211陣陣上上：數(shù)數(shù)據(jù)據(jù)集集中中在在下下列列系系數(shù)數(shù)矩矩kiackicbakCproofBbBaCkjijijnmij那么，行各元素加上的第設(shè)從與原問題有相同的解。為系數(shù)矩陣的分派問題以那么得到矩陣加上同一個(gè)實(shí)數(shù)素中的一行（或一列）各元若從矩陣,.,)(2、匈牙利算法由于指派問題的特殊性，又存在著由匈牙利數(shù)學(xué)家Konig提出的更為簡便的解法匈牙利

18、算法。算法主要依據(jù)以下事實(shí)： 響最優(yōu)解。目標(biāo)函數(shù)的常數(shù)項(xiàng)不影目標(biāo)函數(shù)：afxaxcxbfnkiinjkjnjijijninjijij11111條條直直線線覆覆蓋蓋所所有有零零至至少少個(gè)個(gè)獨(dú)獨(dú)立立零零元元素素至至少少有有直直線線數(shù)數(shù)。覆覆蓋蓋所所有有零零元元素素的的最最少少的的最最多多個(gè)個(gè)數(shù)數(shù)等等于于系系數(shù)數(shù)矩矩陣陣中中獨(dú)獨(dú)立立零零元元素素匈匈牙牙利利關(guān)關(guān)于于獨(dú)獨(dú)立立元元素素的的定定理理336072395006024310.).(. 3 ExnigoKD nmmn 有有）（覆蓋零的直線數(shù)（覆蓋零的直線數(shù)直線數(shù)直線數(shù)找最少的覆蓋全部零的找最少的覆蓋全部零的）數(shù)為數(shù)為（獨(dú)立零個(gè)（獨(dú)立零個(gè)找最多的獨(dú)立

19、零個(gè)數(shù)找最多的獨(dú)立零個(gè)數(shù)對(duì)偶”關(guān)系對(duì)偶”關(guān)系注：這里提供的一種“注：這里提供的一種“”；標(biāo)為“列的其他零元素劃去，同時(shí)把該元素所在”則給它加圈，標(biāo)為“中只有一個(gè)零元素，對(duì)每行檢查，若當(dāng)前行：試派，即找獨(dú)立零元素每列均有零元素；，反復(fù)進(jìn)行，至每行、（列）各元素的最小值列）分別減去該行對(duì)矩陣的每一行（每一各元素步驟：設(shè)求匈牙利法求解分派問題0,)0(1. 2. 10min,stepstep。中單個(gè)零元素均被處理，直到所有行、列，反復(fù)執(zhí)行”；“去，標(biāo)為在的行的其它零元素劃同時(shí)把該元素所加圈，標(biāo)為不算），給它劃去的零個(gè)零元素中只有一對(duì)每列檢查，若當(dāng)前列210),0(0(2. 3, 0, 1.3210,

20、)0(13stepnmxxnmmijij時(shí)時(shí)，轉(zhuǎn)轉(zhuǎn)當(dāng)當(dāng)即即為為最最優(yōu)優(yōu)解解。其其余余應(yīng)應(yīng)的的時(shí)時(shí)，停停止止，所所加加圈圈零零對(duì)對(duì)當(dāng)當(dāng)記記加加圈圈零零的的個(gè)個(gè)數(shù)數(shù)為為處處理理。，直直至至所所有有的的零零元元素素被被，反反復(fù)復(fù)進(jìn)進(jìn)行行”；與與列列的的其其它它零零元元?jiǎng)潉澣トァ巴瑫r(shí)時(shí)把把該該元元素素所所在在的的行行”“元元素素加加圈圈或或列列，把把其其中中任任一一個(gè)個(gè)零零選選零零元元素素個(gè)個(gè)數(shù)數(shù)較較少少的的行行個(gè)個(gè)，類類似似上上述述辦辦法法：均均多多于于若若同同行行（列列）中中零零元元素素 ”的的行行，列列為為止止。直直到到得得不不出出新新記記“，重重復(fù)復(fù)”；行行，記記“”元元素素所所在在”列列中

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