一般的整數(shù)規(guī)劃模型的建立與求解課件

數(shù)學建模理論與實踐——基于整數(shù)規(guī)劃的數(shù)學建模1數(shù)學建模理論與實踐——基于整數(shù)規(guī)劃的數(shù)學建模1基于整數(shù)規(guī)劃的數(shù)學建模一、一般的整數(shù)規(guī)劃模型的建立與求解二、0-1規(guī)劃模型的建立與求解三、指派模型的建立與求解2基于整數(shù)規(guī)劃的數(shù)學建模一、一般的整數(shù)規(guī)劃模型的建立與求解2一、一般的整數(shù)規(guī)劃模型的建立與求解問題的提出：一般的整數(shù)規(guī)劃是指線性規(guī)劃中的一類特殊的問題，其特點是決策變量只取整數(shù)。建立整數(shù)規(guī)劃模型如同建立一般線性規(guī)劃模型一樣，要確定決策變量、目標函數(shù)和約束條件。所不同的是，這里的可行解中各變量只取整數(shù)。如果只有兩個決策變量，可行解只可能是平面上坐標是整數(shù)的點。因而在各決策變量有界的條件下，可行解只可能是有限多個。這個特點使我們有可能用一些特殊方法求解整數(shù)規(guī)劃模型。

特別說明：對比整數(shù)規(guī)劃問題，非整數(shù)規(guī)劃問題的可行解通常構(gòu)成平面上的一個多邊形，可行解有無窮多個。3一、一般的整數(shù)規(guī)劃模型的建立與求解問題的提出：一一、一般的整數(shù)規(guī)劃模型的建立與求解解下列整數(shù)規(guī)劃模型：

4一、一般的整數(shù)規(guī)劃模型的建立與求解解下列整數(shù)規(guī)劃模型：4一、一般的整數(shù)規(guī)劃模型的建立與求解（一）模型解法之一：使用線性松弛模型（二）模型解法之二：窮舉法

（三）模型解法之三：割平面法

（四）模型解法之四：分支定界法5一、一般的整數(shù)規(guī)劃模型的建立與求解（一）模型解法之一：使用線一、一般的整數(shù)規(guī)劃模型的建立與求解（一）模型解法之一：使用線性松弛模型線性松弛模型的定義：去掉整數(shù)規(guī)劃中的整數(shù)要求后得到的非整數(shù)規(guī)劃問題稱為原整數(shù)規(guī)劃的線性松弛模型。注意，這里線性松弛模型的可行解的區(qū)域（多邊形）包含了整數(shù)規(guī)劃的可行解的集合（多邊形內(nèi)的整數(shù)點），因而線性松弛模型的解要優(yōu)于整數(shù)規(guī)劃的解。6一、一般的整數(shù)規(guī)劃模型的建立與求解（一）模型解法之一：使用線一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃模型：

松弛模型：

解為（2.5,2）7一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃模型：松弛模型：一、一般的整數(shù)規(guī)劃模型的建立與求解（二）模型解法之二：窮舉法

先忽略整數(shù)的限制，求解其松弛模型。自然要求松弛模型的可行解是一個有界區(qū)域；否則沒辦法進行窮舉求解。如同求解一般線性規(guī)劃，先畫出由諸不等式約束確定的多邊形。但是這里的可行解由在該多邊區(qū)域內(nèi)的有限多個整數(shù)點構(gòu)成。8一、一般的整數(shù)規(guī)劃模型的建立與求解（二）模型解法之二：窮舉法一、一般的整數(shù)規(guī)劃模型的建立與求解9一、一般的整數(shù)規(guī)劃模型的建立與求解9一、一般的整數(shù)規(guī)劃模型的建立與求解

整數(shù)規(guī)劃的可行解應該含在松弛模型的可行解內(nèi)部，并僅僅由在該多邊區(qū)域內(nèi)的有限多個整數(shù)點構(gòu)成。圖中顯示，共有12個可行解，依次代入目標函數(shù)，得到一系列函數(shù)值：整數(shù)點(0,0)(0,1)(0,2)(0,3)(1,0)(1,1)目標函數(shù)值04812610整數(shù)點(1,2)(2,0)(2,1)(2,2)(3,0)(3,1)目標函數(shù)值141216181822A、B兩種機器分別購買3臺和1臺，產(chǎn)值最多增加22萬元。10一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃的可行解應該一、一般的整數(shù)規(guī)劃模型的建立與求解（三）模型解法之三：割平面法

割平面法的思想及過程：在整數(shù)規(guī)劃對應的線性松弛模型中逐次增加一個新約束（即割平面），割去原可行域中一部分不含整數(shù)解的區(qū)域，逐次切割直至最終得到松弛問題可行域的一個最優(yōu)解頂點為整數(shù)解為止。特別說明：由線性規(guī)劃的特點，最優(yōu)解一定能在可行解區(qū)域的某個頂點達到。新增約束必須滿足的條件：(1)不能割去滿足條件的整數(shù)點；(2)必須將前一次模型的最優(yōu)解割去。11一、一般的整數(shù)規(guī)劃模型的建立與求解（三）模型解法之三：割平面一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃模型：

松弛模型：

12一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃模型：松弛模型：一、一般的整數(shù)規(guī)劃模型的建立與求解（四）模型解法之四：分支定界法詳細參見文件：分支定界法原理簡介.pdf

分支定界法是一種廣義搜索算法，人工使用非常繁瑣，但由于計算機的運算速度快的特點，這種算法十分適合計算機進行。分支定界法是計算機最擅長的廣義搜索窮舉算法。13一、一般的整數(shù)規(guī)劃模型的建立與求解（四）模型解法之四：分支定一、一般的整數(shù)規(guī)劃模型的建立與求解三種方法（窮舉法、割平面法、分支定界法）小結(jié)與對照如下：1、窮舉法解整數(shù)規(guī)劃問題的原理及算法：求出所有的可行解，代入目標函數(shù)比較求得最優(yōu)解。2、割平面法的思想及過程：在整數(shù)規(guī)劃的線性松弛模型中逐次增加一個新約束（即割平面），割去原可行域中一部分不含整數(shù)點的區(qū)域。逐次切割直至最終所得線性松弛模型可行域的一個最優(yōu)解頂點為整數(shù)解為止。新增約束必須滿足的條件：(1)不能割去滿足條件的整數(shù)點；(2)必須將前一次松弛模型的最優(yōu)解（非整數(shù)解）割去。14一、一般的整數(shù)規(guī)劃模型的建立與求解三種方法（窮舉法、割平面法一、一般的整數(shù)規(guī)劃模型的建立與求解三種方法（窮舉法、割平面法、分支定界法）小結(jié)與對照如下：3、分支定界法的一般原理及基本步驟：分支定界法思想就是不斷降低上界，提高下界，最后使得上下界相等，即求得最優(yōu)解?；静襟E：⑴尋找替代問題并求解（放寬或取消原問題某些約束，并求解，一般取消整數(shù)約束）；⑵分支與定界；⑶剪支。15一、一般的整數(shù)規(guī)劃模型的建立與求解三種方法（窮舉法、割平面法二、0-1規(guī)劃模型的建立與求解1.0-1規(guī)劃含義0-1規(guī)劃是整數(shù)規(guī)劃中的特殊情況，此時決策變量只取0或1值。只取0或1值的變量稱為0-1變量，決策變量為0-1變量的線性規(guī)劃稱為0-1規(guī)劃。2.0-1規(guī)劃模型典型解法：隱枚舉法由于0-1規(guī)劃是特殊的整數(shù)規(guī)劃，顯然可以使用整數(shù)規(guī)劃的一切方法（如上述的線性松弛模型、窮舉法、割平面法、分支定界法等方法）求解0-1規(guī)劃。對一個有n個決策變量的0-1規(guī)劃模型，其所要考慮的情況最多有2^n種。如果變量不多，可以用窮舉法來求解。隱枚舉法的本質(zhì)是窮舉法，但是應用隱枚舉法可以更快地得到最優(yōu)解。詳細參見文件：隱枚舉法簡介.pdf16二、0-1規(guī)劃模型的建立與求解1.0-1規(guī)劃三、指派模型的建立與求解1.指派模型含義指派模型是一種特殊的0-1規(guī)劃模型，當然也是一種特殊的整數(shù)規(guī)劃模型。毋庸置疑，其更是一種特殊的線性規(guī)劃模型。在指派問題中假設：（1）被指派的人數(shù)與任務的數(shù)目相等。（2）每個被指派的人員只完成一項任務，而且每項任務必有一人去完成。（3）第i個被指派的人去完成第j項任務的費用為ci,j

.矩陣(ci,j)稱為效益矩陣。17三、指派模型的建立與求解1.指派模型含義17三、指派模型的建立與求解18三、指派模型的建立與求解18三、指派模型的建立與求解2.指派模型的典型解法：匈牙利解法由于指派模型是特殊的0-1規(guī)劃模型，顯然可以使用整數(shù)規(guī)劃的一切方法（如上述的線性松弛模型、窮舉法、割平面法、分支定界法等方法），以及前述的隱枚舉法來求解指派模型。對于指派模型，還有非常著名的典型解法：匈牙利解法。由于篇幅限制以及還要補充若干數(shù)學背景知識的原因，我們這里忽略講解匈牙利解法。有興趣的同學可以自學下列的有關(guān)內(nèi)容。詳細內(nèi)容參見文件：匈牙利解法簡介.pdf可參照的程序見下頁19三、指派模型的建立與求解2.指派模型的典型解法：匈牙利解法三、指派模型的建立與求解附件：匈牙利法求解指派問題的所有最優(yōu)解的程序

程序的特點描述：

（A）是Matlab程序；用到遞歸方法求方陣的積和式函數(shù)per.m（小于10階可用函數(shù)perj.m求方陣的積和式）；

（B）文件zhipaic.m可求解指派問題的所有最優(yōu)解；

（C）但代入下例C則會死循環(huán)，原因待查！可能是個反例，說明該方法不適當。

C=[629139

203;

291936324

32;

273016201

10;

83524345

30;

6

532

11736;

172123361211]

20三、指派模型的建立與求解附件：匈牙利法求解指派問題的所有最優(yōu)三、指派模型的建立與求解實際應用中，我們一般用計算機軟件MATLAB/LINDO/LINGO來求解指派模型。但一個嚴酷的事實是：MATLAB/LINDO/LINGO軟件一般僅僅求出其中的一個解。對于可能有多解的指派模型，如果要求出全部的解，應該掌握好匈牙利解法。但這個算法非常難以理解，編程也有難度，這在前面已經(jīng)看到。為了可以求解指派模型而又不采用匈牙利解法，這里推薦采用窮舉法求解小型的指派模型。詳細可參照下頁的窮舉法程序21三、指派模型的建立與求解實際應用中，我們一般用計三、指派模型的建立與求解附件：窮舉法求解指派問題的所有最優(yōu)解的程序

程序的特點描述：

（A）是Matlab程序；用到函數(shù)文件zhipai.m；

（B）文件zhipai.m中調(diào)用0-1整數(shù)線性規(guī)劃函數(shù)bintprog求解；

（C）僅僅利用zhipai.m的效果類似于LINDO/LINGO求解---僅求出一個解；

（D）而利用窮舉法以及上述函數(shù)zhipai.m可求解指派問題的所有最優(yōu)解。22三、指派模型的建立與求解附件：窮舉法求解指派問題的所有最優(yōu)教材P62第1、2、3題要求：1）解答題，寫出具體解法；

2）程序設計題，寫出用有關(guān)軟件實現(xiàn)的、并且是調(diào)試通過的程序。書面作業(yè)23教材P62第1、2、3題書面作業(yè)23數(shù)學建模理論與實踐——基于整數(shù)規(guī)劃的數(shù)學建模24數(shù)學建模理論與實踐——基于整數(shù)規(guī)劃的數(shù)學建模1基于整數(shù)規(guī)劃的數(shù)學建模一、一般的整數(shù)規(guī)劃模型的建立與求解二、0-1規(guī)劃模型的建立與求解三、指派模型的建立與求解25基于整數(shù)規(guī)劃的數(shù)學建模一、一般的整數(shù)規(guī)劃模型的建立與求解2一、一般的整數(shù)規(guī)劃模型的建立與求解問題的提出：一般的整數(shù)規(guī)劃是指線性規(guī)劃中的一類特殊的問題，其特點是決策變量只取整數(shù)。建立整數(shù)規(guī)劃模型如同建立一般線性規(guī)劃模型一樣，要確定決策變量、目標函數(shù)和約束條件。所不同的是，這里的可行解中各變量只取整數(shù)。如果只有兩個決策變量，可行解只可能是平面上坐標是整數(shù)的點。因而在各決策變量有界的條件下，可行解只可能是有限多個。這個特點使我們有可能用一些特殊方法求解整數(shù)規(guī)劃模型。

特別說明：對比整數(shù)規(guī)劃問題，非整數(shù)規(guī)劃問題的可行解通常構(gòu)成平面上的一個多邊形，可行解有無窮多個。26一、一般的整數(shù)規(guī)劃模型的建立與求解問題的提出：一一、一般的整數(shù)規(guī)劃模型的建立與求解解下列整數(shù)規(guī)劃模型：

27一、一般的整數(shù)規(guī)劃模型的建立與求解解下列整數(shù)規(guī)劃模型：4一、一般的整數(shù)規(guī)劃模型的建立與求解（一）模型解法之一：使用線性松弛模型（二）模型解法之二：窮舉法

（三）模型解法之三：割平面法

（四）模型解法之四：分支定界法28一、一般的整數(shù)規(guī)劃模型的建立與求解（一）模型解法之一：使用線一、一般的整數(shù)規(guī)劃模型的建立與求解（一）模型解法之一：使用線性松弛模型線性松弛模型的定義：去掉整數(shù)規(guī)劃中的整數(shù)要求后得到的非整數(shù)規(guī)劃問題稱為原整數(shù)規(guī)劃的線性松弛模型。注意，這里線性松弛模型的可行解的區(qū)域（多邊形）包含了整數(shù)規(guī)劃的可行解的集合（多邊形內(nèi)的整數(shù)點），因而線性松弛模型的解要優(yōu)于整數(shù)規(guī)劃的解。29一、一般的整數(shù)規(guī)劃模型的建立與求解（一）模型解法之一：使用線一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃模型：

松弛模型：

解為（2.5,2）30一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃模型：松弛模型：一、一般的整數(shù)規(guī)劃模型的建立與求解（二）模型解法之二：窮舉法

先忽略整數(shù)的限制，求解其松弛模型。自然要求松弛模型的可行解是一個有界區(qū)域；否則沒辦法進行窮舉求解。如同求解一般線性規(guī)劃，先畫出由諸不等式約束確定的多邊形。但是這里的可行解由在該多邊區(qū)域內(nèi)的有限多個整數(shù)點構(gòu)成。31一、一般的整數(shù)規(guī)劃模型的建立與求解（二）模型解法之二：窮舉法一、一般的整數(shù)規(guī)劃模型的建立與求解32一、一般的整數(shù)規(guī)劃模型的建立與求解9一、一般的整數(shù)規(guī)劃模型的建立與求解

整數(shù)規(guī)劃的可行解應該含在松弛模型的可行解內(nèi)部，并僅僅由在該多邊區(qū)域內(nèi)的有限多個整數(shù)點構(gòu)成。圖中顯示，共有12個可行解，依次代入目標函數(shù)，得到一系列函數(shù)值：整數(shù)點(0,0)(0,1)(0,2)(0,3)(1,0)(1,1)目標函數(shù)值04812610整數(shù)點(1,2)(2,0)(2,1)(2,2)(3,0)(3,1)目標函數(shù)值141216181822A、B兩種機器分別購買3臺和1臺，產(chǎn)值最多增加22萬元。33一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃的可行解應該一、一般的整數(shù)規(guī)劃模型的建立與求解（三）模型解法之三：割平面法

割平面法的思想及過程：在整數(shù)規(guī)劃對應的線性松弛模型中逐次增加一個新約束（即割平面），割去原可行域中一部分不含整數(shù)解的區(qū)域，逐次切割直至最終得到松弛問題可行域的一個最優(yōu)解頂點為整數(shù)解為止。特別說明：由線性規(guī)劃的特點，最優(yōu)解一定能在可行解區(qū)域的某個頂點達到。新增約束必須滿足的條件：(1)不能割去滿足條件的整數(shù)點；(2)必須將前一次模型的最優(yōu)解割去。34一、一般的整數(shù)規(guī)劃模型的建立與求解（三）模型解法之三：割平面一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃模型：

松弛模型：

35一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃模型：松弛模型：一、一般的整數(shù)規(guī)劃模型的建立與求解（四）模型解法之四：分支定界法詳細參見文件：分支定界法原理簡介.pdf

分支定界法是一種廣義搜索算法，人工使用非常繁瑣，但由于計算機的運算速度快的特點，這種算法十分適合計算機進行。分支定界法是計算機最擅長的廣義搜索窮舉算法。36一、一般的整數(shù)規(guī)劃模型的建立與求解（四）模型解法之四：分支定一、一般的整數(shù)規(guī)劃模型的建立與求解三種方法（窮舉法、割平面法、分支定界法）小結(jié)與對照如下：1、窮舉法解整數(shù)規(guī)劃問題的原理及算法：求出所有的可行解，代入目標函數(shù)比較求得最優(yōu)解。2、割平面法的思想及過程：在整數(shù)規(guī)劃的線性松弛模型中逐次增加一個新約束（即割平面），割去原可行域中一部分不含整數(shù)點的區(qū)域。逐次切割直至最終所得線性松弛模型可行域的一個最優(yōu)解頂點為整數(shù)解為止。新增約束必須滿足的條件：(1)不能割去滿足條件的整數(shù)點；(2)必須將前一次松弛模型的最優(yōu)解（非整數(shù)解）割去。37一、一般的整數(shù)規(guī)劃模型的建立與求解三種方法（窮舉法、割平面法一、一般的整數(shù)規(guī)劃模型的建立與求解三種方法（窮舉法、割平面法、分支定界法）小結(jié)與對照如下：3、分支定界法的一般原理及基本步驟：分支定界法思想就是不斷降低上界，提高下界，最后使得上下界相等，即求得最優(yōu)解?；静襟E：⑴尋找替代問題并求解（放寬或取消原問題某些約束，并求解，一般取消整數(shù)約束）；⑵分支與定界；⑶剪支。38一、一般的整數(shù)規(guī)劃模型的建立與求解三種方法（窮舉法、割平面法二、0-1規(guī)劃模型的建立與求解1.0-1規(guī)劃含義0-1規(guī)劃是整數(shù)規(guī)劃中的特殊情況，此時決策變量只取0或1值。只取0或1值的變量稱為0-1變量，決策變量為0-1變量的線性規(guī)劃稱為0-1規(guī)劃。2.0-1規(guī)劃模型典型解法：隱枚舉法由于0-1規(guī)劃是特殊的整數(shù)規(guī)劃，顯然可以使用整數(shù)規(guī)劃的一切方法（如上述的線性松弛模型、窮舉法、割平面法、分支定界法等方法）求解0-1規(guī)劃。對一個有n個決策變量的0-1規(guī)劃模型，其所要考慮的情況最多有2^n種。如果變量不多，可以用窮舉法來求解。隱枚舉法的本質(zhì)是窮舉法，但是應用隱枚舉法可以更快地得到最優(yōu)解。詳細參見文件：隱枚舉法簡介.pdf39二、0-1規(guī)劃模型的建立與求解1.0-1規(guī)劃三、指派模型的建立與求解1.指派模型含義指派模型是一種特殊的0-1規(guī)劃模型，當然也是一種特殊的整數(shù)規(guī)劃模型。毋庸置疑，其更是一種特殊的線性規(guī)劃模型。在指派問題中假設：（1）被指派的人數(shù)與任務的數(shù)目相等。（2）每個被指派的人員只完成一項任務，而且每項任務必有一人去完成。（3）第i個被指派的人去完成第j項任務的費用為ci,j

.矩陣(ci,j)稱為效益矩陣。40三、指派模型的建立與求解1.指派模型含義17三、指派模型的建立與求解41三、指派模型的建立與求解18三、指派模型的建立與求解2.指派模型的典型解法：匈牙利解法由于指派模型是特殊的0-1規(guī)劃模型，顯然可以使用整數(shù)規(guī)劃的一切方法（如上述的線性松弛模型、窮舉法、割平面法、分支定界法等方法），以及前述的隱枚舉法來求解指派模型。對于指派模型，還有非常著名的典型解法：匈牙利解法。由于篇幅限制以及還要補充若干數(shù)學背景知識的原因，我們這里忽略講解匈牙利解法。有興趣的同學可以自學下列的有關(guān)內(nèi)容。詳細內(nèi)容參見文件：匈牙利解法簡介.pdf可參照的程序見下頁42三、指派模型的建立與求解2.指派模型的典型解法：匈牙利解法三、指派模型的建立與求解附件：匈牙利法求解指派問題的所有最優(yōu)解的程序

程序的特點描述：

（A）是Matlab程序；用到遞歸方法求方陣的積和式函數(shù)per.m（小于10階可用函數(shù)perj.m求方陣的積和式）；

（B）文件zhipaic.m可求解指派問題的所有最優(yōu)解；

（C）但代入下例C則會死循環(huán)，原因待查！可能是個反例，說明該方法不適當。

C=[62913