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

特別說明：對(duì)比整數(shù)規(guī)劃問題，非整數(shù)規(guī)劃問題的可行解通常構(gòu)成平面上的一個(gè)多邊形，可行解有無窮多個(gè)。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ù)點(diǎn)），因而線性松弛模型的解要優(yōu)于整數(shù)規(guī)劃的解。6一、一般的整數(shù)規(guī)劃模型的建立與求解（一）模型解法之一：使用線一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃模型：

松弛模型：

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

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

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

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

松弛模型：

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

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

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

程序的特點(diǎn)描述：

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

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

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

C=[629139

203;

291936324

32;

273016201

10;

83524345

30;

6

532

11736;

172123361211]

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

程序的特點(diǎn)描述：

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

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

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

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

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

特別說明：對(duì)比整數(shù)規(guī)劃問題，非整數(shù)規(guī)劃問題的可行解通常構(gòu)成平面上的一個(gè)多邊形，可行解有無窮多個(gè)。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ù)點(diǎn)），因而線性松弛模型的解要優(yōu)于整數(shù)規(guī)劃的解。29一、一般的整數(shù)規(guī)劃模型的建立與求解（一）模型解法之一：使用線一、一般的整數(shù)規(guī)劃模型的建立與求解整數(shù)規(guī)劃模型：

松弛模型：

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

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

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

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

松弛模型：

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

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

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

程序的特點(diǎn)描述：

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

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

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

C=[62913