整數(shù)規(guī)劃0421課件

第五章整數(shù)規(guī)劃引言什么是整數(shù)規(guī)劃在第4章中的線(xiàn)性規(guī)劃問(wèn)題，其設(shè)計(jì)變量都是連續(xù)變量，其最優(yōu)解可以出現(xiàn)分?jǐn)?shù)或小數(shù)。但當(dāng)設(shè)計(jì)變量表示零件數(shù)、勞動(dòng)力人數(shù)、設(shè)備的臺(tái)數(shù)時(shí)，其取值則必須為非負(fù)整數(shù)，此時(shí)一般的線(xiàn)性規(guī)劃求解方法就可能失效。我們稱(chēng)要求設(shè)計(jì)變量的部分分量或者全部分量取整數(shù)值的最優(yōu)化問(wèn)題為整數(shù)規(guī)劃問(wèn)題整數(shù)規(guī)劃的產(chǎn)生和發(fā)展整數(shù)規(guī)劃（IntegerProgramming，簡(jiǎn)寫(xiě)為IP）和線(xiàn)性規(guī)劃一樣屬于運(yùn)籌學(xué)中數(shù)學(xué)規(guī)劃的一個(gè)分支，其研究的問(wèn)題包括整數(shù)線(xiàn)性規(guī)劃和整數(shù)非線(xiàn)性規(guī)劃整數(shù)規(guī)劃是從1958年由R.E.Gomory提出割平面法之后形成獨(dú)立分支的。之后在該領(lǐng)域雖然也發(fā)展出諸如分枝定界法和割平面法等主流方法，但它仍是數(shù)學(xué)規(guī)劃中稍弱的一個(gè)分支，目前的方法僅適合解中等規(guī)模的整數(shù)線(xiàn)性規(guī)劃問(wèn)題，而對(duì)于大規(guī)模整數(shù)線(xiàn)性規(guī)劃和整數(shù)非線(xiàn)性規(guī)劃問(wèn)題，還沒(méi)有成熟的辦法整數(shù)規(guī)劃的分類(lèi)純整數(shù)規(guī)劃：全部設(shè)計(jì)變量都取整數(shù)混合整數(shù)規(guī)劃：部分設(shè)計(jì)變量取整數(shù)0-1規(guī)劃：設(shè)計(jì)變量?jī)H取0或l兩個(gè)值典型的整數(shù)規(guī)劃問(wèn)題裝載問(wèn)題有一列用于運(yùn)貨的火車(chē)，其最大承載能力為b。現(xiàn)有n種不同的貨物p1,p2,…,pn可供裝載，設(shè)每件pi的重量為ai，裝載收費(fèi)為ci

(i=1,2,…,n)，則應(yīng)采用何種裝載方案能夠使得該列火車(chē)載貨的收入最大？設(shè)xj為列車(chē)上裝載pj的數(shù)量，則xj必為非負(fù)整數(shù)，根據(jù)該貨船最大可承載b噸貨物可知所有集裝箱的重量之和必須b，故有約束條件：由對(duì)每個(gè)j種貨物收費(fèi)為cj，可知載貨的總收入為：該例的目標(biāo)即使得目標(biāo)函數(shù)f最大化。綜合上述分析可得如下整數(shù)規(guī)劃問(wèn)題：典型的整數(shù)規(guī)劃問(wèn)題工廠選址問(wèn)題設(shè)xij為每年從Ai運(yùn)往Bj的鋼鐵數(shù)量，于是每年的總費(fèi)用為：由鐵礦Ai運(yùn)出的所有鋼鐵將等于鐵礦Ai的產(chǎn)量ai

原鋼鐵廠B0鋼鐵的用量p0為m座鐵礦為其供應(yīng)，故其收量應(yīng)當(dāng)?shù)扔趍座鐵礦對(duì)分別對(duì)其供應(yīng)量的總和，即：同樣的，對(duì)于備選廠Bj，可知其鋼鐵的用量為p，且由m座鐵礦供應(yīng)，由于備選廠址只有一座，故在p前面需要乘以系數(shù)vj，即代表如果選擇Bj為備選廠址，則用鐵礦，否則，則該廠不存在，不需要使用鐵礦，此時(shí)，對(duì)應(yīng)的xij將全部取零值，故：由Ai向Bj鋼鐵的運(yùn)輸量均為非負(fù)實(shí)數(shù)備選的鋼鐵廠只有一處典型的整數(shù)規(guī)劃問(wèn)題工廠選址問(wèn)題根據(jù)如上分析，根據(jù)設(shè)計(jì)變量的取值規(guī)則，要么建廠取0，要么不建廠取1，同時(shí)該問(wèn)題還要確定如果選擇了廠址，應(yīng)當(dāng)如何分配m座鐵礦對(duì)兩個(gè)鋼鐵廠的鋼鐵供應(yīng)量xij，而該變量的取值為非負(fù)實(shí)數(shù)即可，故該問(wèn)題為一混合整數(shù)規(guī)劃問(wèn)題，且為混合0-1規(guī)劃，可以歸納為如下形式：典型的整數(shù)規(guī)劃問(wèn)題背包問(wèn)題

夫婦兩人要赴A地進(jìn)行長(zhǎng)途旅行，需要整理行李，現(xiàn)有3個(gè)旅行包，其容積大小分別為10升、15升和20升，兩人在列出物品清單后根據(jù)需要已經(jīng)整理出了10個(gè)包裝袋，其中一些包裝袋中裝的是必帶物品，共有7件，其體積大小分別為4升、3升、1.5升、2.5升、4.5升、7.6升和1.9升。尚有8個(gè)包裝袋可帶可不帶，不帶則可在A地購(gòu)買(mǎi)，這些可選包裝袋的容積和其對(duì)應(yīng)物品在A地的價(jià)格如表所示。試根據(jù)上述信息給出一個(gè)合理的打包方案。在這個(gè)問(wèn)題中，我們需要確定的是，選帶哪幾個(gè)可選的包裝袋，且將必帶物品和選帶物品放到哪個(gè)旅行包中。為此我們?cè)O(shè)第i個(gè)包裝袋是否放在第j個(gè)旅行包中，并以此作為設(shè)計(jì)變量。同時(shí)，設(shè)第i個(gè)包裝袋的容積可以用wi(i=1,2,3,…,15)來(lái)表示，可選包裝袋對(duì)應(yīng)的價(jià)格用pi(i=8,9,10,…,15)來(lái)表示。由于第i個(gè)包裝袋要么在第j個(gè)旅行包中，要么在要么不在，故設(shè)只取0和1，且表述如下：物品12345678容積2.545.54.83.71.67.54.5價(jià)格2050105755580200100典型的整數(shù)規(guī)劃問(wèn)題背包問(wèn)題我們的目標(biāo)就是使得在到達(dá)A地之后，所買(mǎi)物品的價(jià)格最低，即不在旅行包中的包裝袋的總價(jià)格最低，如果某包裝袋i不在旅行包中，則有：故其價(jià)格可以用來(lái)表示，故所有不在旅行包中的包裝袋的價(jià)值f可表達(dá)如下我們確定打包方案的原則就是使得f取得最小值，故綜合以上分析，該背包問(wèn)題的數(shù)學(xué)模型為：

整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型一般形式在整數(shù)規(guī)劃中還有許多其他典型的問(wèn)題，例如在第3章中提到的分派問(wèn)題，還有旅行商問(wèn)題、下料問(wèn)題等，其問(wèn)題均可以歸結(jié)為如下的一般形式上述形式是仿照線(xiàn)性規(guī)劃中的標(biāo)準(zhǔn)型給出的，其中設(shè)計(jì)變量x為n維的列向量，c為n維的行向量，A為m×n的矩陣，且A行滿(mǎn)秩，b為m維列向量。在模型中，(1)可以是最大化也可以是最小化，對(duì)于約束(2)，可以是等式的形式也可以是不等式的形式。對(duì)于對(duì)設(shè)計(jì)變量的約束(3)，如果要求x全部分量為整數(shù)，則為純整數(shù)規(guī)劃；如果要求x的部分分量為整數(shù)，則為混合整數(shù)規(guī)劃，如果要求x分量的取值只能為0和1，則為0-1規(guī)劃。整數(shù)規(guī)劃的求解直觀想法既然整數(shù)規(guī)劃問(wèn)題的可行方案數(shù)目有限，則我們經(jīng)過(guò)枚舉比較之后，總能求出最好方案，這種想法對(duì)于維數(shù)很低的整數(shù)規(guī)劃問(wèn)題行得通，但是隨著設(shè)計(jì)變量維數(shù)的增加，該方法的計(jì)算量是不可想象的，因而此種想法不可行。另一種想法更為直接，因?yàn)檎麛?shù)規(guī)劃問(wèn)題實(shí)際上是在線(xiàn)性規(guī)劃問(wèn)題的基礎(chǔ)上增加了整數(shù)約束，因而是否可以考慮先忽略整數(shù)約束，解一個(gè)線(xiàn)性規(guī)劃問(wèn)題，然后用四舍五入法取得其整數(shù)解？但事實(shí)證明，這樣經(jīng)過(guò)四舍五入的結(jié)果甚至不是問(wèn)題的可行解可行否枚舉法隨著變量維數(shù)增加呈指數(shù)增長(zhǎng)，不可行！四舍五入可能都不是可行解，不可行！四舍五入后的解不是可行解！求解整數(shù)規(guī)劃的理論基礎(chǔ)利用分解技術(shù)求解整數(shù)規(guī)劃中的幾個(gè)概念分解

對(duì)于整數(shù)規(guī)劃問(wèn)題P，令F(P)表示P的可行域。對(duì)問(wèn)題P的子問(wèn)題P1,…,Pm，若滿(mǎn)足下述條件：則稱(chēng)P問(wèn)題被分解成為子問(wèn)題P1,…,Pm之和，最常用的方法就是兩分法，例如若xj是P的0-1變量，則問(wèn)題P可以按照條件xj=0和xj=1分解成兩個(gè)問(wèn)題之和。松弛凡是放棄問(wèn)題P的某些約束后所得到的問(wèn)題Q都稱(chēng)為P的松弛問(wèn)題。通常的松弛方式是放棄設(shè)計(jì)變量的整數(shù)約束，若P是整數(shù)規(guī)劃，則Q就是線(xiàn)性規(guī)劃。由于對(duì)于P的任何松弛問(wèn)題Q，都有，故問(wèn)題P與其松弛問(wèn)題Q之間的關(guān)系為：若Q沒(méi)有可行解，則P也沒(méi)有可行解；對(duì)于最大化的目標(biāo)函數(shù)而言，

P的最大值小于或者等于Q的最大值，對(duì)于最小化的目標(biāo)函數(shù)而言，P的最小值大于或者等于Q的最小值；如果Q的一個(gè)最優(yōu)解x是P的可行解，則x也是P的一個(gè)最優(yōu)解。求解整數(shù)規(guī)劃的理論基礎(chǔ)利用分解技術(shù)求解整數(shù)規(guī)劃中的幾個(gè)概念探測(cè)假設(shè)按照某種規(guī)則，已經(jīng)將問(wèn)題P分解稱(chēng)為子問(wèn)題P1,…,Pm之和，Pi對(duì)應(yīng)的松弛問(wèn)題為Qi。且問(wèn)題需要最大化目標(biāo)函數(shù)，則有如下結(jié)論：如果Qi沒(méi)有可行解，則Pi也無(wú)可行解，因此可將Pi從P的分解表上刪去；假設(shè)已知P的一個(gè)可行解x*，其對(duì)應(yīng)的目標(biāo)函數(shù)值為f*。若Qi的目標(biāo)函數(shù)的最大值小于或者等于f*，則說(shuō)明Pi中沒(méi)有比x*更好的可行解，因此可將Pi從P的分解表上刪去；如果Qi的最優(yōu)解是Pi的可行解，則已求得Pi的最優(yōu)解，故無(wú)須進(jìn)一步考慮Pi，可從表上刪去，若Pi的最優(yōu)解比x*好，則以Pi的最優(yōu)解代替x*如果分解表上各個(gè)Qi的目標(biāo)函數(shù)值均不大于x*，則x*便是P的一個(gè)最優(yōu)解求解整數(shù)規(guī)劃的步驟首先按照某種方式確定P的松弛問(wèn)題Q，若Q無(wú)可行解則P也無(wú)可行解，若Q的最優(yōu)解為P的可行解，則也是P的最優(yōu)解。若Q的最優(yōu)解不是P的可行解，則要么以一種更好的方式確定松弛問(wèn)題Q，繼續(xù)探測(cè)P，要么將P分解成為幾個(gè)子問(wèn)題之和，然后逐個(gè)探測(cè)，當(dāng)某個(gè)子問(wèn)題已被探明時(shí)，就從表中刪除，否則繼續(xù)對(duì)子問(wèn)題進(jìn)行分解求解整數(shù)規(guī)劃的分枝定界法分枝定界法的思想根據(jù)理論基礎(chǔ)，若整數(shù)規(guī)劃問(wèn)題P除去整數(shù)約束的松弛問(wèn)題Q為線(xiàn)性規(guī)劃，則有如下幾個(gè)推論若Q無(wú)可行解，則P也一定無(wú)可行解若Q的一個(gè)最優(yōu)解是整數(shù)解，則這個(gè)解也是整數(shù)規(guī)劃P的最優(yōu)解若Q的最優(yōu)解不是整數(shù)解，則P的最優(yōu)目標(biāo)函數(shù)值不會(huì)好于Q的最優(yōu)值。因此，Q的最優(yōu)目標(biāo)函數(shù)值是P的最優(yōu)目標(biāo)函數(shù)值的一個(gè)界，在最大化目標(biāo)函數(shù)值時(shí)為上界，在最小化目標(biāo)函數(shù)值是下界如果在求解過(guò)程中已經(jīng)找到一個(gè)整數(shù)解，則最優(yōu)整數(shù)解一定不會(huì)劣于該整數(shù)解，因此，它也是最優(yōu)目標(biāo)函數(shù)值的一個(gè)界，在最大化目標(biāo)函數(shù)值時(shí)為下界，在最小化目標(biāo)函數(shù)值是上界如果用f表示Q的最優(yōu)值，用fi表示已經(jīng)找到的最佳整數(shù)解的最優(yōu)值，f*為P的最優(yōu)值，lb表示下界，ub表示上界，則對(duì)于最大化目標(biāo)函數(shù)的問(wèn)題，一定存在關(guān)系，而對(duì)于最小化目標(biāo)函數(shù)的問(wèn)題，則為，分枝定界法的思想就是不斷降低上界，提高下界，最后使得下界接近或者等于上界，通過(guò)這個(gè)方法來(lái)縮小搜索的范圍，進(jìn)而找到問(wèn)題的最優(yōu)整數(shù)解。求解整數(shù)規(guī)劃的分枝定界法說(shuō)明對(duì)于上述求解步驟中的第(4)步，特別說(shuō)明如下：如果在計(jì)算過(guò)程中已得到某一個(gè)分枝的整數(shù)最優(yōu)解，其最優(yōu)值為f0。而此時(shí)在其他分枝過(guò)程中，如果求得某一線(xiàn)性規(guī)劃所得的目標(biāo)函數(shù)值小于f0

，即可停止該枝的計(jì)算。因?yàn)檫M(jìn)一步求解的結(jié)果的最優(yōu)值也只可能比f(wàn)0更差，這也就是如何檢查下界對(duì)分枝樹(shù)進(jìn)行剪枝的原則。求解整數(shù)規(guī)劃的分枝定界法如何選擇分枝的節(jié)點(diǎn)深度優(yōu)先搜索先選擇最后的還沒(méi)有求解過(guò)的子問(wèn)題并剪去那些目標(biāo)函數(shù)值小于新下界的子問(wèn)題。在搜索的過(guò)程中，如果某子節(jié)點(diǎn)的上界小于當(dāng)前原問(wèn)題的某一可行解的值，則將該子節(jié)點(diǎn)刪去不再進(jìn)行分枝。該方法可以較早的實(shí)現(xiàn)剪枝的過(guò)程，很快的搜索到分枝樹(shù)的較底層找到一個(gè)整數(shù)解，且存儲(chǔ)空間小，缺點(diǎn)就是未顧及其他分枝，找到的整數(shù)解的質(zhì)量未必高。廣度優(yōu)先搜索始終選擇由最大目標(biāo)函數(shù)值的子問(wèn)題繼續(xù)向下分枝，在搜索的過(guò)程中，如果某子節(jié)點(diǎn)的上界小于當(dāng)前原問(wèn)題的某一可行解的值，則將該子節(jié)點(diǎn)刪去不再進(jìn)行分枝。因?yàn)樗看味家宰畲笊辖绲淖訂?wèn)題進(jìn)行處理，故用該搜索方法找到整數(shù)解的質(zhì)量較高，缺點(diǎn)是該方法要在整個(gè)分枝樹(shù)上搜索，故存儲(chǔ)空間比深度優(yōu)先搜索大，求解時(shí)間也較長(zhǎng)。預(yù)估法利用一些先驗(yàn)知識(shí)和相關(guān)技巧預(yù)先估計(jì)還未求解過(guò)的子問(wèn)題的最好可能整數(shù)解，并選擇最好預(yù)估值的子問(wèn)題向下分枝，該方法是上述兩種方法的折中選擇。求解整數(shù)規(guī)劃的分枝定界法如何選擇分枝變量按照目標(biāo)函數(shù)系數(shù)選擇選擇目標(biāo)函數(shù)中對(duì)應(yīng)系數(shù)絕對(duì)值最大的設(shè)計(jì)變量進(jìn)行分枝按非整數(shù)變量選擇選擇與整數(shù)值相差最大的非整數(shù)變量首先進(jìn)行分枝按人為給定的順序選擇例如選擇者按整數(shù)變量在問(wèn)題中的相對(duì)重要性排序求解整數(shù)規(guī)劃的分枝定界法求解整數(shù)規(guī)劃問(wèn)題P

首先求解P的松弛線(xiàn)性規(guī)劃問(wèn)題Q，可知其最優(yōu)解為：，在最優(yōu)解處取得的函數(shù)最大值為：fQ=4，此時(shí)上界為4，由于xQ的兩個(gè)分量均不為整數(shù)，故需要對(duì)問(wèn)題P進(jìn)行分枝，在此，人為取x1進(jìn)行分枝，對(duì)xP1=1.5向下取整得1，故加上互斥的約束條件x1≤1和x1≥2，那么加入該組互斥條件的作用在于：排除了區(qū)間(1,2)之內(nèi)的非整數(shù)解，縮小了搜索的范圍；形成了整數(shù)規(guī)劃P的兩個(gè)子問(wèn)題P1和P2求解整數(shù)規(guī)劃的分枝定界法由于現(xiàn)在已經(jīng)存在兩個(gè)子節(jié)點(diǎn)P1和P2，下一步選取哪個(gè)節(jié)點(diǎn)進(jìn)行分枝需要采用合適的策略，在此我們采用廣度優(yōu)先搜索的方法，由于Q2的目標(biāo)函數(shù)值較大，故對(duì)問(wèn)題P2進(jìn)行分枝，加入互斥的約束x2≤1和x2≥2，形成P2的兩個(gè)子問(wèn)題P3和P4。當(dāng)加入新的約束之后，有可能出現(xiàn)三種情況：

(1)新加入的條件和原問(wèn)題的條件獨(dú)立，即互不影響，此時(shí)直接將約束加入到問(wèn)題中；

(2)新加入的條件和原問(wèn)題的條件相矛盾，此時(shí)新的問(wèn)題無(wú)可行解；(3)新加入的約束和原約束存在交集，則此時(shí)選擇其交集作為作為新問(wèn)題的約束條件。求解整數(shù)規(guī)劃的分枝定界法

由于Q3的目標(biāo)函數(shù)值fQ3大于Q1的目標(biāo)函數(shù)值fQ1，故下一步對(duì)P3進(jìn)行分枝，加入互斥的約束x1≤2和x1≥3，形成P3的兩個(gè)子問(wèn)題P5和P6。

現(xiàn)在我們已經(jīng)在P2的分枝上找到了一組整數(shù)解，現(xiàn)在比較fQ5和fQ1，由于現(xiàn)在已有整數(shù)解的目標(biāo)函數(shù)值fQ5大于fQ1，而P1的最優(yōu)目標(biāo)函數(shù)值不會(huì)大于fQ1，故該分枝的解不會(huì)對(duì)目標(biāo)函數(shù)值有任何的改善，所以對(duì)P1進(jìn)行剪枝，即停止對(duì)P1的向下分枝，我們已經(jīng)搜索到了的最優(yōu)解。這里需要注意的，如果我們發(fā)現(xiàn)已經(jīng)求得整數(shù)解的最優(yōu)值fQ5要小于fQ1，則P的上界還并未確定，于是問(wèn)題還需要繼續(xù)分解下去。求解0-1規(guī)劃的隱枚舉法隱枚舉法的提出由EBalas在1965年提出的，該方法只檢查一部分變量組合，在這過(guò)程中根據(jù)已有信息自動(dòng)舍棄許多不可能成為最優(yōu)解的組合以求得最優(yōu)解，從而大大減少了工作量，隱枚舉法只需比較目標(biāo)函數(shù)在一小部分組合點(diǎn)上的取值大小就能求得最優(yōu)解和最優(yōu)值。隱枚舉法的思想隱枚舉法可以看作是分枝定界法的特殊情況，在求解的過(guò)程中，它不需要求解其松弛線(xiàn)性規(guī)劃問(wèn)題，利用變量只能取0或1對(duì)問(wèn)題進(jìn)行分枝。其思路是先將0-1規(guī)劃問(wèn)題轉(zhuǎn)化為既定的標(biāo)準(zhǔn)型，該標(biāo)準(zhǔn)型一般是要最小化目標(biāo)函數(shù)的值，在此前提下，首先令全部變量取0值（當(dāng)求最大值時(shí)，令全部變量取1值），檢驗(yàn)解是否滿(mǎn)足約束條件，若均滿(mǎn)足，已得最優(yōu)解；若不全滿(mǎn)足，則令一個(gè)變量分枝取值為0或1，該分枝變量稱(chēng)為固定變量，將模型分成兩個(gè)子模型，其余未被指定取值的變量稱(chēng)為自由變量，通過(guò)這種方法，依次指定一些變量為1，直至得到一個(gè)可行解，并將它作為目前最好的可行解并記錄下來(lái)。此后，經(jīng)過(guò)幾次檢驗(yàn)后，或者停止分枝，或者將另一個(gè)自由變量轉(zhuǎn)為固定變量，令其值為0或l，如此繼續(xù)進(jìn)行，依次試探變量等于0或l的某些組合，使目前最好的可行解不斷逼近最優(yōu)值，直至沒(méi)有自由變量或全部子問(wèn)題停止分枝為止，就求出了0-1規(guī)劃的最優(yōu)解，求解0-1規(guī)劃的隱枚舉法取試探解的理由為什么從全0作出初始的試探解，這是因?yàn)?-1規(guī)劃的標(biāo)準(zhǔn)型要求對(duì)目標(biāo)函數(shù)求最小值，而對(duì)于最小化目標(biāo)函數(shù)的問(wèn)題，由于在后面我們會(huì)提到0-1規(guī)劃標(biāo)準(zhǔn)型中cj≥0，故因此自由變量為0與固定變量組成的子模型能夠使得目標(biāo)函數(shù)值最小。同理，如果不用標(biāo)準(zhǔn)型求解，例如對(duì)目標(biāo)函數(shù)求最大值的問(wèn)題，則是將全1作為初始的試探解進(jìn)行分枝計(jì)算隱枚舉法和窮舉法的不同隱枚舉法和窮舉法不同，窮舉法需要將所有可行的變量組合逐個(gè)列舉，而隱枚舉法通過(guò)試探、分析和判斷，排除了許多變量組合作為最優(yōu)解的可能性。也就是說(shuō)，它們被隱含枚舉了，這也是稱(chēng)其為隱枚舉法的原因隱枚舉法的實(shí)質(zhì)從算法描述可以看出，隱枚舉法的實(shí)質(zhì)也是分枝定界法，隱枚舉法在求解過(guò)程中與一般的分枝定界法不同之處只在于在分枝產(chǎn)生子問(wèn)題時(shí)變量被固定為0或1，而不是兩個(gè)范圍之值的形式。求解0-1規(guī)劃的隱枚舉法隱枚舉法的算法描述(1)將P轉(zhuǎn)化成為標(biāo)準(zhǔn)型(2)令所有設(shè)計(jì)變量均為自由變量，初始試探解為x=0，檢驗(yàn)該解是否為可行解，如果為可行解，則x=0為P的最優(yōu)解，算法結(jié)束。否則，轉(zhuǎn)(3)；(3)按照既定的法則選取一個(gè)自由變量xk，將其轉(zhuǎn)化為固定變量進(jìn)行分枝，加入互斥的條件xk=0和xk=1，將P分為兩個(gè)子問(wèn)題，其他的自由變量取值不變，仍為0。然后對(duì)針對(duì)各個(gè)分枝進(jìn)行試探，轉(zhuǎn)(4);

(4)檢查已有的子問(wèn)題，如果有某一個(gè)子問(wèn)題滿(mǎn)足下列條件之一，就可對(duì)該子問(wèn)題進(jìn)行剪枝，即該子問(wèn)題停止向下分枝，可以在分枝樹(shù)中用相應(yīng)的符號(hào)來(lái)表示，例如△等。此時(shí)繼續(xù)檢查其他子問(wèn)題，轉(zhuǎn)(3);試探解為自由變量均取0值、固定變量取設(shè)定值，若滿(mǎn)足所有約束條件，則為可行解，該解對(duì)應(yīng)的目標(biāo)函數(shù)值為P的目標(biāo)函數(shù)值的一個(gè)上界，同時(shí)該子問(wèn)題停止向下分枝；若該子問(wèn)題所有試探解均不是可行解，即自由變量任取0或1時(shí)，都不能滿(mǎn)足某一個(gè)或者多個(gè)約束條件，則該子問(wèn)題無(wú)可行解，也停止向下分枝；設(shè)自由變量均取0值與固定變量的值一起代入目標(biāo)函數(shù)，得到的目標(biāo)值為f，此時(shí)對(duì)應(yīng)的自由變量的系數(shù)為列向量c，若f與c中任一分量的和大于已經(jīng)記錄的上界中的最小值，則說(shuō)明在該子問(wèn)題中固定任何自由試探解不是P的可行解，且此時(shí)所有變量均已設(shè)為固定變量，則該子問(wèn)題也應(yīng)該被剪枝，停止向下分枝。

變量都不可能對(duì)P的最優(yōu)值有所改善，已無(wú)更好的可行解，則該子問(wèn)題被剪枝，停止向下分枝；求解0-1規(guī)劃的隱枚舉法隱枚舉法的算法描述（續(xù)）(5)直到所有子問(wèn)題檢查完畢，轉(zhuǎn)(6)

(6)在探明所有的分枝之后算法終止。比較記錄下來(lái)的可行解的上界，其中最小者所對(duì)應(yīng)的可行解即為P的最優(yōu)解，相應(yīng)的目標(biāo)函數(shù)值即為最優(yōu)目標(biāo)值，如果該問(wèn)題沒(méi)有記錄任何上界，則說(shuō)明P無(wú)可行解，即該0-1規(guī)劃無(wú)解。求解0-1規(guī)劃的隱枚舉法求解0-1規(guī)劃P

(1)化為標(biāo)準(zhǔn)型(2)令所有設(shè)計(jì)變量為0，試探解x=[0000]T不是P的可行解，需要分枝(3)按照目標(biāo)函數(shù)中各設(shè)計(jì)變量的系數(shù)從大到小的順序來(lái)選擇分枝固定變量，即以

x1、x4、x3、x2的順序設(shè)置固定變量進(jìn)行問(wèn)題的試探求解0-1規(guī)劃的隱枚舉法首先以x1作為固定變量，加入互斥的條件x1=1和x1=0將P分枝成為兩個(gè)子問(wèn)題P1和P2。下面對(duì)子問(wèn)題進(jìn)行探查。P1的試探解為xP1=[1000]T，它是P的可行解，此時(shí)目標(biāo)函數(shù)值為fP1=20，將其記錄下來(lái)，作為P的一個(gè)上界。此時(shí)，對(duì)子問(wèn)題P1進(jìn)行剪枝，停止向下分枝。此時(shí)P1已經(jīng)探明。P2與P相同，故xP2為不可行解，以x4作為固定變量，加入互斥的條件x4=1和x4=0將P2分枝成為兩個(gè)子問(wèn)題P3和P4。P3的試探解為xP3=[0001]T為不可行解。P4與P相同，故xP4為不可行解，兩個(gè)問(wèn)題都需要繼續(xù)分枝，以x3作為固定變量，加入互斥的條件x3=1和x3=0，將P3分枝成為兩個(gè)子問(wèn)題P5和P6，將P4分枝成為兩個(gè)子問(wèn)題P7和P8。P5的試探解為xP5=[0011]T為P的可行解，此時(shí)目標(biāo)函數(shù)值為fP5=17，此時(shí)對(duì)應(yīng)的自由變量為x2，x2對(duì)應(yīng)的系數(shù)為c2=6，而此時(shí)記錄下來(lái)的P的上界為fP1=20，由fP5+c2>fP1，故停止向下分枝。按照上述方法不斷試探，最后可得所有可行解中，P9所對(duì)應(yīng)的xP9=[0101]T所取得的目標(biāo)函數(shù)值最小為fP9=15，故xP9為P的最優(yōu)解。求解過(guò)程示意圖如下一頁(yè)所示。求解0-1規(guī)劃的隱枚舉法求解過(guò)程示意圖求解分派問(wèn)題的匈牙利算法匈牙利算法的應(yīng)用對(duì)象用以解決分派問(wèn)題分派問(wèn)題是一種特殊形式的整數(shù)規(guī)劃。該問(wèn)題可以總結(jié)為，有n項(xiàng)任務(wù)需要n個(gè)人分別去完成，每個(gè)人只能完成其中的一項(xiàng)，而每項(xiàng)工作也只能由一個(gè)人完成，在問(wèn)題中會(huì)以各種形式給出各個(gè)人的專(zhuān)長(zhǎng)和工作效率，需要求解的問(wèn)題是考慮分配哪個(gè)人去完成哪項(xiàng)任務(wù)才能使得總效率最高或者花費(fèi)的總時(shí)間最短。匈牙利算法的提出由于分派問(wèn)題屬于0-1規(guī)劃，故我們可以用隱枚舉法進(jìn)行求解，但是鑒于上述問(wèn)題的特殊性，可以有更簡(jiǎn)便的方法求解此類(lèi)問(wèn)題，由于這種方法是基于匈牙利數(shù)學(xué)家狄·柯尼格（DK?nig）證明的兩個(gè)定理而發(fā)展的，故稱(chēng)之為匈牙利法。求解分派問(wèn)題的匈牙利算法匈牙利算法的0-1規(guī)劃標(biāo)準(zhǔn)型匈牙利算法是解決最優(yōu)模型可歸結(jié)為與分派問(wèn)題結(jié)構(gòu)一致的最優(yōu)化問(wèn)題的有效算法，那么首先回顧一下分派問(wèn)題的數(shù)學(xué)模型，假設(shè)由第i個(gè)人完成第j項(xiàng)工作的時(shí)間為Eij，又設(shè)問(wèn)題中的設(shè)計(jì)變量為xij，其意義如下：則分派問(wèn)題的標(biāo)準(zhǔn)型為：需要注意的是，標(biāo)準(zhǔn)型中要求的是最小化目標(biāo)函數(shù)的值，且對(duì)應(yīng)于各設(shè)計(jì)變量的系數(shù)均不小于零。這是應(yīng)用匈牙利算法的前提條件。求解分派問(wèn)題的匈牙利算法非標(biāo)準(zhǔn)型的標(biāo)準(zhǔn)化目標(biāo)函數(shù)中設(shè)計(jì)變量xmn對(duì)應(yīng)的系數(shù)為負(fù)數(shù)Emn<0可令，此時(shí)有，取可知,于是原目標(biāo)函數(shù)變?yōu)椋航?jīng)過(guò)上述轉(zhuǎn)換實(shí)現(xiàn)了將目標(biāo)函數(shù)中所有設(shè)計(jì)變量的系數(shù)變成正數(shù)目標(biāo)函數(shù)求最大令,其中M是足夠大的常數(shù)，一般方法是令M為效率矩陣元素Eij中的最大值，即，由于對(duì)于任意的i,j(i=1,2,…,n;j=1,2,…,n)均可滿(mǎn)足max(Eij)-Eij≥0，故可以保證Fij≥0，這時(shí)，系數(shù)矩陣變?yōu)椋篎=(Fij)，且滿(mǎn)足Fij≥0，對(duì)應(yīng)效率矩陣F的分派問(wèn)題的目標(biāo)函數(shù)滿(mǎn)足：

顯然可以表達(dá)成為，因?yàn)閚M為一常數(shù)，故當(dāng)f取得最小值時(shí)，可以取到最大值，即通過(guò)這種變換將原分派問(wèn)題目標(biāo)函數(shù)由最小化變成最大化，以符合匈牙利法的實(shí)施條件。

求解分派問(wèn)題的匈牙利算法匈牙利算法的基本思想在分派問(wèn)題的數(shù)學(xué)模型中，目標(biāo)函數(shù)的系數(shù)可以寫(xiě)成n×n維的矩陣形式，我們可以用效率矩陣E來(lái)表示這組參量：而匈牙利法就是通過(guò)對(duì)效率矩陣E的處理來(lái)獲得分派問(wèn)題的最優(yōu)解。在匈牙利法中，要求矩陣E的所有元素均為非負(fù)，即Eij≥0。其基本的思想就是如果在矩陣E中存在一組（n個(gè)）位于不同行且不同列的零元素，則最優(yōu)方案就是令對(duì)應(yīng)于這些零元素位置的xij=1，其他位置的xij=0。但是很顯然的，我們建立的分派模型的效率矩陣E中幾乎沒(méi)有零元素，要實(shí)現(xiàn)上述設(shè)想就必須找到合適的方法對(duì)矩陣E進(jìn)行變換，來(lái)獲得這一組位于不同行且不同列的零元素。求解分派問(wèn)題的匈牙利算法匈牙利算法的理論基礎(chǔ)引理1：如果將效率矩陣E的第i行每個(gè)元素減去一個(gè)常數(shù)ui，將第j列中每個(gè)元素減去一個(gè)常數(shù)vj，得到新的效率矩陣F，其第i行第j列的元素為Fij=aij-ui-vj，則分別對(duì)應(yīng)于E和F的兩個(gè)分派問(wèn)題的最優(yōu)解等價(jià)，其最優(yōu)值相差推論1：如果將效率矩陣E的每一行（或每一列）各元素分別減去該行（或該列）的最小元素，由此得到的新的效率矩陣F，則分別對(duì)應(yīng)于E和F的兩個(gè)分派問(wèn)題的最優(yōu)解等價(jià)引理2：若矩陣E的元素可以分成“0”元素和“非0”元素兩部分，則覆蓋所有“0”元素的最少直線(xiàn)（將直線(xiàn)上的元素全部劃去之后矩陣就不再有“0”元素，這樣所需直線(xiàn)數(shù)的最小值）等于位于不同行且不同列的“0”元素的最大個(gè)數(shù)。根據(jù)上面的結(jié)論，用匈牙利法求解分派問(wèn)題的原理即通過(guò)對(duì)原效率矩陣E各行各列元素的同加或者同減運(yùn)算，構(gòu)造出等價(jià)最優(yōu)解的效率矩陣F，且F的所有元素非負(fù)且具有n個(gè)不同行且不同列的“0”元素。這樣，n個(gè)“0”元素所對(duì)應(yīng)的人做對(duì)應(yīng)的工作就是分派問(wèn)題的最優(yōu)解求解分派問(wèn)題的匈牙利算法用匈牙利算法求解第一步，使得每一行和每一列都出現(xiàn)0元素將E的每行元素減去該行中的最小元素，使得每一行至少出現(xiàn)一個(gè)0元素；將所得矩陣的每列元素減去該列中的最小元素，使得每一列都至少出現(xiàn)一個(gè)0元素如果某行或者某列已經(jīng)有零元素，則不必再減對(duì)例題中的E，操作如下：求解分派問(wèn)題的匈牙利算法第二步，最優(yōu)性檢驗(yàn)，進(jìn)行試指派，即找出不同行不同列的0元素(I)給只有一個(gè)0元素的行中的0打上括號(hào)，記作(0)，并劃去與其同列的其余0元素，記作；(II)給只有一個(gè)0元素的列中的0打上括號(hào)，記作(0)，并劃去與其同行的其余0元素，記作；(III)反復(fù)進(jìn)行(I)和(II)，直至所有的0都被標(biāo)記為止；(IV)若仍有沒(méi)有被標(biāo)記的0元素，則可從剩余的0元素最少的行（列）開(kāi)始，選擇0元素少的那列（行）的0元素加括號(hào)（表示選擇性多的要禮讓選擇性少的）。然后，劃去同行同列的其它0元素，反復(fù)進(jìn)行，直到所有0元素都已被標(biāo)記為止。(V)若(0)元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問(wèn)題的最優(yōu)解已經(jīng)找到，若m<n，轉(zhuǎn)下一步求解分派問(wèn)題的匈牙利算法第三步，矩陣變換作能覆蓋所有0元素的最少直線(xiàn)

(a)對(duì)沒(méi)有(0)的行標(biāo)記“*”；(b)對(duì)標(biāo)記“*”行上含有0元素的列標(biāo)記“*”；(c)對(duì)標(biāo)記“*”列上有(0)的行標(biāo)記“*”(d)重復(fù)(b)(c)直到無(wú)法標(biāo)記“*”為止(e)對(duì)標(biāo)記“*”的列畫(huà)縱線(xiàn)，未標(biāo)記“*”的行畫(huà)橫線(xiàn)，這就是能覆蓋所有0元素的最少直線(xiàn)移動(dòng)0元素在未被劃去的元素中找出最小元素s，將其作為矩陣變換的調(diào)整量；將標(biāo)記“*”行的所有元素都減去s將標(biāo)記“*”列的所有元素都加上s結(jié)果將得到一個(gè)新的效率矩陣，轉(zhuǎn)第二步。求解分派問(wèn)題的匈牙利算法對(duì)于本例的示例矩陣，未被劃去的元素中最小者為2，故首先將第1行和第3行減去2，然后將第2列加上2，獲得新的效率矩陣：

返回第二步，即嘗試在上述矩陣中找到不同行且不同列的n個(gè)0元素求解分派問(wèn)題的匈牙利算法由以上求解結(jié)果，可以知道有兩種最優(yōu)的指派方式，相應(yīng)的分派方案1號(hào)成員完成2號(hào)任務(wù)，2號(hào)完成3號(hào)任務(wù)，3號(hào)完成1號(hào)任務(wù)，4號(hào)完成4號(hào)任務(wù)；1號(hào)完成1號(hào)任務(wù)，2號(hào)完成3號(hào)任務(wù)，3號(hào)完成2號(hào)任務(wù)，4號(hào)完成4號(hào)任務(wù)最優(yōu)方案耗時(shí)M1：f=21+12+29+23=85M2：f=20+13+29+23=85一般整數(shù)規(guī)劃問(wèn)題的MATLAB求解求解方法由于MATLAB優(yōu)化工具箱中并未提供求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃的函數(shù)，因而需要自行根據(jù)需要和設(shè)定相關(guān)的算法來(lái)實(shí)現(xiàn)?，F(xiàn)在有許多用戶(hù)發(fā)布的工具箱可以解決該類(lèi)問(wèn)題，例如比較著名的YALMIP，讀者可以自行到網(wǎng)上下載相關(guān)的工具包并進(jìn)行學(xué)習(xí)。這里我們給出開(kāi)羅大學(xué)的Sherif和Tawfik在MATLABCentral上發(fā)布的一個(gè)用于求解一般混合整數(shù)規(guī)劃的程序，在此命名為intprog，筆者在原程序的基礎(chǔ)上做了簡(jiǎn)單的修改，將其選擇分枝變量的算法由自然序改造成分枝變量選擇原則中的一種，即：選擇與整數(shù)值相差最大的非整數(shù)變量首先進(jìn)行分枝調(diào)用格式[x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger)一般整數(shù)規(guī)劃問(wèn)題的MATLAB求解標(biāo)準(zhǔn)形式假設(shè)x為n維設(shè)計(jì)變量，且問(wèn)題具有不等式約束m1個(gè)，等式約束m2個(gè)，那么：c、x均為n維列向量，b為m1維列向量，beq為m2維列向量，A為m1×n維矩陣，Aeq為m2×n維矩陣。輸入?yún)?shù)有c,A,b,Aeq,beq,lb,ub,M和TolXInteger。其中c為目標(biāo)函數(shù)所對(duì)應(yīng)設(shè)計(jì)變量的系數(shù)，A為不等式約束條件方程組構(gòu)成的系數(shù)矩陣，b為不等式約束條件方程組右邊的值構(gòu)成的向量。Aeq為等式約束方程組構(gòu)成的系數(shù)矩陣，beq為等式約束條件方程組右邊的值構(gòu)成的向量。lb和ub為設(shè)計(jì)變量對(duì)應(yīng)的上界和下界。M為具有整數(shù)約束條件限制的設(shè)計(jì)變量的序號(hào)，例如問(wèn)題中設(shè)計(jì)變量為x1,x2,…,x6，要求x2,x3和x6為整數(shù)，則M=[2;3;6]；若要求全為整數(shù)，則M=1:6，或者M(jìn)=[1;2;3;4;5;6]。TolXInteger為判定整數(shù)的誤差限，即若某數(shù)x和最鄰近整數(shù)相差小于該誤差限，則認(rèn)為x即為該整數(shù)。輸出參數(shù)有x,fval和exitflag。其中x為整數(shù)規(guī)劃問(wèn)題的最優(yōu)解向量，fval為整數(shù)規(guī)劃問(wèn)題的目標(biāo)函數(shù)在最優(yōu)解向量x處的函數(shù)值，exitflag為函數(shù)計(jì)算終止時(shí)的狀態(tài)指示變量。一般整數(shù)規(guī)劃問(wèn)題的MATLAB求解算法實(shí)現(xiàn)intprog.m%整數(shù)規(guī)劃的MATLAB實(shí)現(xiàn)%OriginallyDesignedBySherifA.Tawfik,RevisedByLiMing,2009-12-29%函數(shù)調(diào)用形式[x,fval,exitflag]=intprog(f,A,b,Aeq,beq,lb,ub,M,TolXInteger)%函數(shù)求解如下形式的整數(shù)規(guī)劃問(wèn)題%minf'*x%subjectto%A*x<=b%Aeq*x=beq%lb<=x<=ub%M存儲(chǔ)有整數(shù)約束的變量編號(hào)的向量%TolXInteger是判定整數(shù)的誤差限%%函數(shù)返回變量%x:整數(shù)規(guī)劃的最優(yōu)解%fval:目標(biāo)函數(shù)在最優(yōu)解處的函數(shù)值%exitflag= 1 收斂到解x% 0 達(dá)到線(xiàn)性規(guī)劃的最大迭代次數(shù)% -1 無(wú)解%function[x,fval,exitflag]=intprog(f,A,b,Aeq,beq,lb,ub,M,TolXInteger)%設(shè)置不顯示求解線(xiàn)性規(guī)劃過(guò)程中的提示信息options=optimset('display','off');%上界的初始值bound=inf;%求解原問(wèn)題P0的松弛線(xiàn)性規(guī)劃Q0，首先獲得問(wèn)題的初始解[x0,fval0]=linprog(f,A,b,Aeq,beq,lb,ub,[],options);%利用遞歸法進(jìn)行二叉樹(shù)的遍歷，實(shí)現(xiàn)分枝定界法對(duì)整數(shù)規(guī)劃的求解[x,fval,exitflag,b]=rec_BranchBound(f,A,b,Aeq,beq,lb,ub,x0,fval0,M,TolXInteger,bound);一般整數(shù)規(guī)劃問(wèn)題的MATLAB求解%分枝定界法的遞歸算法,x為問(wèn)題的初始解，v是目標(biāo)函數(shù)在x處的取值function[xx,fval,exitflag,bb]=rec_BranchBound(f,A,b,Aeq,beq,lb,ub,x,v,M,TolXInteger,bound)options=optimset('display','off');%求解不考慮整數(shù)約束的松弛線(xiàn)性規(guī)劃[x0,fval0,exitflag0]=linprog(f,A,b,Aeq,beq,lb,ub,[],options);%如果算法結(jié)束狀態(tài)指示變量為負(fù)值，即表示無(wú)可行解，返回初始輸入%或者所目標(biāo)函數(shù)值大于已經(jīng)獲得的上界，返回初始輸入ifexitflag0<=0|fval0>boundxx=x;fval=v;exitflag=exitflag0;bb=bound;return;end%確定所有變量是否均為整數(shù)，如是，則返回ind=find(abs(x0(M)-round(x0(M)))>TolXInteger);%該條件表示x0(M)不是整數(shù)%如果都是整數(shù)ifisempty(ind)exitflag=1;%如果當(dāng)前的解優(yōu)于已知的最優(yōu)解，則將當(dāng)前解作為最優(yōu)解

iffval0<bound{x0(M)=round(x0(M));xx=x0;fval=fval0;bb=fval0;}%否則，返回原來(lái)的解

else{xx=x;fval=v;bb=bound;}endreturn;end一般整數(shù)規(guī)劃問(wèn)題的MATLAB求解%程序運(yùn)行至此，說(shuō)明松弛線(xiàn)性規(guī)劃的解是一個(gè)可行解且目標(biāo)函數(shù)值比當(dāng)前記錄的上界要小，只是某些變量的%值并非整數(shù)，于是在此選擇合適的變量進(jìn)行分枝形成兩個(gè)子問(wèn)題，分別進(jìn)行遞歸求解%該處選擇與整數(shù)值相差最大的非整數(shù)變量首先進(jìn)行分枝形成兩個(gè)子問(wèn)題,第一個(gè)非整數(shù)變量的序號(hào)，且記錄該變量與其最鄰近的整數(shù)之差的絕對(duì)值[rowcol]=size(ind);br_var=M(ind(1));br_value=x(br_var);flag=abs(br_value-floor(br_value)-0.5);%用于查找非整數(shù)設(shè)計(jì)變量中整數(shù)值相差最大的設(shè)計(jì)變量，即每當(dāng)遇到與其最鄰近的整數(shù)差%別更大的非整數(shù)設(shè)計(jì)變量之時(shí)，即記錄下該設(shè)計(jì)變量的序號(hào)，直至遍歷完所有非整數(shù)變量fori=2:coltempbr_var=M(br_var);tempbr_value=x(br_var)temp_flag=abs(tempbr_value-floor(tempbr_value)-0.5);iftemp_flag>flagbr_var=tempbr_var;br_value=tempbr_value;flag=temp_flag;endendifisempty(A)[rc]=size(Aeq);else[rc]=size(A);end一般整數(shù)規(guī)劃問(wèn)題的MATLAB求解%第1個(gè)子問(wèn)題的設(shè)置,添加約束條件Xi<=floor(Xi)，i即為上面找到的最接近整數(shù)的非整數(shù)設(shè)計(jì)變量的序號(hào)A1=[A;zeros(1,c)];A1(end,br_var)=1;b1=[b;floor(br_value)];%第2個(gè)子問(wèn)題的設(shè)置,添加約束條件Xi>=ceil(Xi)，i即為上面找到的最接近整數(shù)的非整數(shù)設(shè)計(jì)變量的序號(hào)A2=[A;zeros(1,c)];A2(end,br_var)=-1;b2=[b;-ceil(br_value)];%分枝后的第一個(gè)子問(wèn)題的遞歸求解[x1,fval1,exitflag1,bound1]=rec_BranchBound(f,A1,b1,Aeq,beq,lb,ub,x0,fval0,M,TolXInteger,bound);exitflag=exitflag1;ifexitflag1>0&bound1<boundxx=x1;fval=fval1;bound=bound1;bb=bound1;elsexx=x0;fval=fval0;bb=bound;end%分枝后的第二個(gè)子問(wèn)題的遞歸求解[x2,fval2,exitflag2,bound2]=rec_BranchBound(f,A2,b2,Aeq,beq,lb,ub,x0,fval0,M,TolXInteger,bound);ifexitflag2>0&bound2<boundexitflag=exitflag2;xx=x2;fval=fval2;bb=bound2;end一般整數(shù)規(guī)劃問(wèn)題的MATLAB求解求解整數(shù)規(guī)劃問(wèn)題

上例中x和fval為整數(shù)規(guī)劃問(wèn)題對(duì)應(yīng)松弛線(xiàn)性規(guī)劃的最優(yōu)解和最優(yōu)值，x1和fval1為整數(shù)規(guī)劃的最優(yōu)解和最優(yōu)值，可見(jiàn)本例中無(wú)論如何對(duì)x進(jìn)行取整操作都無(wú)法得到整數(shù)規(guī)劃問(wèn)題的最優(yōu)解。c=[-5;-8];A=[11;59];b=[6;45];lb=[0;0];M=[1;2]; %x1,x2均要求為整數(shù)變量Tol=1e-8; %判斷是否整數(shù)的誤差限[x,fval]=linprog(c,A,b,[],[],lb,[]) %松弛問(wèn)題的解[x1,fval1]=intprog(c,A,b,[],[],lb,[],M,Tol)%整數(shù)規(guī)劃的解Optimizationterminated.x=2.25003.7500fval=-41.2500x1=05fval1=-40.0000一般整數(shù)規(guī)劃問(wèn)題的MATLAB求解求解整數(shù)規(guī)劃問(wèn)題c=[-1;-1];A=[-42;42;0-2];b=[-1;11;-1];lb=[0;0];M=[1;2]; %均要求為整數(shù)變量Tol=1e-8; %判斷是否整數(shù)的誤差限[x,fval]=linprog(c,A,b,[],[],lb,[]) %求解原問(wèn)題松弛線(xiàn)性規(guī)劃[x1,fval1]=intprog(c,A,b,[],[],lb,[],M,Tol) %求最優(yōu)解整數(shù)解x= %松弛線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解1.50002.5000fval=-4.0000x1= %整數(shù)規(guī)劃的最優(yōu)解21fval2=-3.00000-1規(guī)劃的MATLAB求解0-1規(guī)劃問(wèn)題的MATLAB標(biāo)準(zhǔn)型在上述模型中，目標(biāo)函數(shù)f需要極小化，不等式約束形式為“≤”。假設(shè)x為n維設(shè)計(jì)變量，且線(xiàn)性規(guī)劃問(wèn)題具有不等式約束m1個(gè)，等式約束m2個(gè)，那么：c、x均為n維列向量，b為m1維列向量，beq為m2維列向量，A為m1×n維矩陣，Aeq為m2×n維矩陣。如果不滿(mǎn)足標(biāo)準(zhǔn)型的要求，則需要對(duì)原問(wèn)題進(jìn)行轉(zhuǎn)化，化為標(biāo)準(zhǔn)型之后才能使用相關(guān)函數(shù)，標(biāo)準(zhǔn)化的方法和線(xiàn)性規(guī)劃中的類(lèi)似0-1規(guī)劃問(wèn)題的MATLAB求解函數(shù)MATLAB優(yōu)化工具箱中求解0-1規(guī)劃問(wèn)題的命令為bintprog0-1規(guī)劃的MATLAB求解bintprog的調(diào)用格式x=bintprog(f)x=bintprog(f,A,b)x=bintprog(f,A,b,Aeq,beq)x=bintprog(f,A,b,Aeq,beq,x0)x=bintprog(f,A,b,Aeq,Beq,x0,options)[x,fval]=bintprog(...)[x,fval,exitflag]=bintprog(...)[x,fval,exitflag,output]=bintprog(...)輸入?yún)?shù)MATLAB工具箱中的bintprog函數(shù)在求0-1規(guī)劃問(wèn)題時(shí)，提供的參數(shù)有如下幾種模型參數(shù)：x、c、b、beq、A和Aeq初始解參數(shù)：x0算法控制參數(shù)：options，我們可以通過(guò)optimset命令對(duì)這些具體的控制參數(shù)進(jìn)行設(shè)置，其中主要參數(shù)的設(shè)置方法如下一頁(yè)的表格所示0-1規(guī)劃的MATLAB求解bintprog中的控制參數(shù)設(shè)置參數(shù)名稱(chēng)參數(shù)設(shè)置BranchStrategy設(shè)置算法中分枝變量的選擇策略，當(dāng)該參數(shù)值為mininfeas時(shí)，選擇最可能為整數(shù)的變量進(jìn)行分枝，即分枝變量最接近0或1，但不等于0或1；當(dāng)該參數(shù)值為maxinfeas(默認(rèn))時(shí)，選擇最不可能為整數(shù)的變量進(jìn)行分枝，即分枝變量最接近0.5MaxIter設(shè)置算法運(yùn)行中的最大迭代次數(shù)，默認(rèn)值為100000*設(shè)計(jì)變量的個(gè)數(shù)MaxNodes設(shè)置算法搜索的最大節(jié)點(diǎn)數(shù)，默認(rèn)值為1000*設(shè)計(jì)變量的個(gè)數(shù)MaxRLPIter設(shè)置算法在求解各個(gè)節(jié)點(diǎn)的松弛線(xiàn)性規(guī)劃問(wèn)題時(shí)的最大迭代次數(shù)，默認(rèn)值為100*設(shè)計(jì)變量的個(gè)數(shù)MaxTime設(shè)置算法運(yùn)行的最大CPU時(shí)間，以秒為單位，默認(rèn)值為7200sNodeDisplayInterval設(shè)置節(jié)點(diǎn)顯示區(qū)間。即在每次顯示迭代報(bào)告之前搜索節(jié)點(diǎn)的數(shù)目。默認(rèn)值為20NodeSearchStrategy設(shè)置算法中分枝節(jié)點(diǎn)的選擇策略，當(dāng)該參數(shù)值為df時(shí)，為深度優(yōu)先搜索，即選擇最下層的孩子節(jié)點(diǎn)進(jìn)行分枝；當(dāng)該參數(shù)值為bn（默認(rèn)）時(shí)，為廣度優(yōu)先搜索，即選擇目標(biāo)函數(shù)值最優(yōu)的節(jié)點(diǎn)進(jìn)行分枝TolFun函數(shù)計(jì)算終止的誤差限，其默認(rèn)值為1e-3TolXInteger設(shè)置判斷一個(gè)數(shù)值是否為正整數(shù)的誤差限，默認(rèn)值為1.0e-8，即如果一個(gè)數(shù)和與其最鄰近的正整數(shù)之差小于1.0e-8，則被認(rèn)為是該正整數(shù)TolRLPFun設(shè)置求解松弛線(xiàn)性規(guī)劃問(wèn)題的目標(biāo)函數(shù)計(jì)算終止誤差限，默認(rèn)值為1.0e-6Diagnostics設(shè)置是否顯示函數(shù)優(yōu)化中的診斷信息，可以選擇on或者off（默認(rèn)值），該功能主要顯示一些退出信息，即bintprog函數(shù)運(yùn)算終止的原因Display設(shè)置顯示信息的級(jí)別，當(dāng)該參數(shù)值為off時(shí)，不顯示任何輸出信息；當(dāng)參數(shù)值為iter時(shí)，將顯示每一步迭代的輸出信息，iter參數(shù)值僅對(duì)大型規(guī)模算法和中型規(guī)模的單純形算法有效；當(dāng)參數(shù)值為final時(shí)，僅顯示最終的輸出信息0-1規(guī)劃的MATLAB求解輸出參數(shù)

x為0-1規(guī)劃問(wèn)題的最優(yōu)解fval為0-1規(guī)劃問(wèn)題在最優(yōu)解x處的函數(shù)值exitflag返回的是bintprog計(jì)算終止時(shí)的狀態(tài)指示，說(shuō)明算法終止的原因，其取值和其代表的具體原因如表所示輸出參數(shù)output是一個(gè)返回優(yōu)化過(guò)程中相關(guān)信息的結(jié)構(gòu)變量，它所包含的屬性及屬性代表的意義如表所示。值物理意義1已經(jīng)收斂到解x0已經(jīng)達(dá)到最大迭代次數(shù)限制options.MaxIter-2優(yōu)化問(wèn)題無(wú)可行解-4搜索節(jié)點(diǎn)數(shù)超過(guò)設(shè)置的最大節(jié)點(diǎn)數(shù)-5搜索時(shí)間超過(guò)設(shè)置的最大CPU時(shí)間options.MaxTime.-6在求解某節(jié)點(diǎn)的線(xiàn)性松弛問(wèn)題時(shí)進(jìn)行迭代的次數(shù)超過(guò)算法設(shè)置的在求解各個(gè)節(jié)點(diǎn)的松弛線(xiàn)性規(guī)劃問(wèn)題時(shí)的最大迭代次數(shù)options.MaxRLP屬性名稱(chēng)屬性含義output.iterations優(yōu)化過(guò)程的實(shí)際迭代次數(shù)output.algorithm優(yōu)化過(guò)程中所采用的具體算法output.nodes優(yōu)化過(guò)程中搜索過(guò)的節(jié)點(diǎn)數(shù)目output.time優(yōu)化過(guò)程中執(zhí)行算法消耗的CPU時(shí)間output.branchStrategy優(yōu)化過(guò)程中選擇分枝變量的策略output.nodeSearchStrategy優(yōu)化過(guò)程中選擇分枝節(jié)點(diǎn)的策略output.message退出信息參數(shù)exitflag的物理意義參數(shù)output所包含的信息0-1規(guī)劃的MATLAB求解命令詳解x=bintprog(f)該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問(wèn)題x=bintprog(c,A,b)該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問(wèn)題x=bintprog(c,A,b,Aeq,beq)該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問(wèn)題x=bintprog(c,A,b,Aeq,beq,x0)在前一個(gè)調(diào)用格式的基礎(chǔ)上同時(shí)設(shè)置求解算法的初始解為x0，如果初始解x0不在0-1規(guī)劃問(wèn)題的可行域中，算法將采用默認(rèn)的初始解x=bintprog(c,A,b,Aeq,beq,x0,options)用options指定的優(yōu)化參數(shù)進(jìn)行最小化?？梢允褂胦ptimset來(lái)設(shè)置這些參數(shù)0-1規(guī)劃的MATLAB求解命令詳解（續(xù)）[x,fval]=bintprog(...)在優(yōu)化計(jì)算結(jié)束之時(shí)返回整數(shù)規(guī)劃問(wèn)題在解x處的目標(biāo)函數(shù)值fval[x,fval,exitflag]=bintprog(...)在優(yōu)化計(jì)算結(jié)束之時(shí)返回exitflag值，描述函數(shù)計(jì)算的退出條件。[x,fval,exitflag,output]=bintprog(...)在優(yōu)化計(jì)算結(jié)束之時(shí)返回結(jié)構(gòu)變量output應(yīng)用實(shí)例求解0-1規(guī)劃問(wèn)題c=[20;6;8;9];A=[-10-6-5-2;-7-2-2-4;-2-1-1-10;011-1];b=[-4;-4;-2;1];lb=[0;0;0;0];ub=[1;1;1;1];M=1:4; %均要求為整數(shù)變量Tol=1e-8; %判斷是否整數(shù)的誤差限[x,fval]=intprog(c,A,b,[],[],lb,ub,M,Tol) %調(diào)用intprog函數(shù)[x1,fval1]=bintprog(c,A,b) %調(diào)用bintprog函數(shù)x= %用intprog函數(shù)求解0-1規(guī)劃的結(jié)果0101fval=15.0000Optimizationterminated.x1= %用bintprog函數(shù)求解0-1規(guī)劃的結(jié)果0101fval1=150-1規(guī)劃的MATLAB求解求解0-1規(guī)劃問(wèn)題

為了程序的可讀性，我們用一維下標(biāo)來(lái)表示設(shè)計(jì)變量，即用x1~x4表示x11~x14，用x5~x8表示x21~x24，用x9~x12表示x31~x34，用x13~x16表示x41~x44，于是約束條件和目標(biāo)函數(shù)分別為：

0-1規(guī)劃的MATLAB求解代碼和結(jié)果c=[20;12;33;26;22;15;29;23;21;13;31;24;22;16;32;23];Aeq=[1111000000000000;0000111100000000;0000000011110000;0000000000001111;1000100010001000;0100010001000100;0010001000100010;0001000100010001;];beq=ones(1,8);[x,fval]=bintprog(c,[],[],Aeq,beq);B=reshape(x,4,4);%由于x是一列元素，為了使結(jié)果更加直觀，故排成與效率矩陣E相對(duì)應(yīng)的形式B'fvalOptimizationterminated.ans=0100001010000001fval=85應(yīng)用實(shí)例賓館的排班問(wèn)題問(wèn)題的提出某連鎖賓館在一天的的各時(shí)間區(qū)段內(nèi)所需服務(wù)員的人數(shù)如表所示。假設(shè)服務(wù)員上班的時(shí)間在各時(shí)間段的開(kāi)始時(shí)刻，并且連續(xù)工作8個(gè)小時(shí)。問(wèn)題是，該賓館應(yīng)該至少配備多少名服務(wù)員？班次時(shí)間段需要服務(wù)員人數(shù)108:00–12:00100212:00–16:00120316:00–20:0080420:00–24:0060500:00–04:0030604:00–08:0050應(yīng)用實(shí)例賓館的排班問(wèn)題問(wèn)題分析設(shè)xi為從第i個(gè)班次開(kāi)始上班的服務(wù)員人數(shù)，則該賓館共需服務(wù)員的人數(shù)為該問(wèn)題的目標(biāo)是該賓館配備服務(wù)員的最少的數(shù)量，即f值最小。約束條件為在每一時(shí)間段至少需要配備的服務(wù)員人數(shù)如表所示。根據(jù)分析，在班次1開(kāi)始時(shí)刻即8:00開(kāi)始上班的服務(wù)員，需要連續(xù)上班8個(gè)小時(shí)到16:00，即該服務(wù)員可以上兩個(gè)班次，所以在時(shí)間段08:00–12:00之間在崗的服務(wù)員為班次6和班次1的服務(wù)員，以此類(lèi)推，在時(shí)間段12:00–16:00之間在崗的服務(wù)員為班次1和班次2的服務(wù)員，在時(shí)間段16:00–20:00之間在崗的服務(wù)員為班次2和班次3的服務(wù)員。根據(jù)上述分析，假設(shè)在班次n所在時(shí)間段需要的服務(wù)員人數(shù)為sn，則sn(n=1,2,…,6)和xi

(n=1,2,…,6)需要滿(mǎn)足的約束條件為：應(yīng)用實(shí)例賓館的排班問(wèn)題數(shù)學(xué)模型根據(jù)對(duì)問(wèn)題的分析，我們可以總結(jié)得到該問(wèn)題的數(shù)學(xué)模型為：應(yīng)用實(shí)例賓館的排班問(wèn)題代碼和結(jié)果由此可知，按照運(yùn)行結(jié)果中的人數(shù)進(jìn)行排班，即在各時(shí)間段的開(kāi)始時(shí)刻分別安排50、70、23、37、0、50個(gè)服務(wù)員上班，所需要的總?cè)藬?shù)最少，一共為230個(gè)服務(wù)員。f=ones(1,6);A=[-1-10000;0-1-1000;00-1-100;000-1-10;0000-1-1;-10000-1];b=[-120;-80;-60;-30;-50;-100];lb=[0;0;0;0;0;0];ub=[Inf;Inf;Inf;Inf;Inf;Inf];M=[1;2;3;4;5;6];%所有變量均為整數(shù)變量，故將所有序號(hào)組成向量MTol=1e-8;%判定為整數(shù)的誤差限[x,fval,exitflag]=intprog(f,A,b,[],[],lb,ub,M,Tol)x=50702337050fval=230exitflag=1應(yīng)用實(shí)例賓館的排班問(wèn)題問(wèn)題的反思在這里需要指出的是，根據(jù)實(shí)際的需求，我們?cè)趩?wèn)題中設(shè)置不等式約束是符合實(shí)際情況的，即并不一定要求恰好為限定的人數(shù)，多于此人數(shù)也是可以的。如果我們將不等式約束變?yōu)榈仁郊s束，即設(shè)定每個(gè)時(shí)間段的服務(wù)員人數(shù)為固定值，將不等號(hào)換成等號(hào)，此時(shí)可能出現(xiàn)如下情況：

(1)問(wèn)題不一定有可行解，當(dāng)有效等式約束的個(gè)數(shù)大于或者等于設(shè)計(jì)變量的個(gè)數(shù)時(shí)，就可能出現(xiàn)矛盾方程組導(dǎo)致失去優(yōu)化的自由度(2)即便有可行解，也不一定會(huì)優(yōu)于我們?cè)O(shè)定約束為不等式時(shí)的目標(biāo)函數(shù)值，最多等于設(shè)定約束為不等式時(shí)的目標(biāo)函數(shù)值。應(yīng)用實(shí)例合理下料問(wèn)題問(wèn)題的提出某廠商只有一種規(guī)格的特質(zhì)鋼管，其固定長(zhǎng)度為17m?，F(xiàn)在需要根據(jù)客戶(hù)對(duì)長(zhǎng)度的要求對(duì)其生產(chǎn)的鋼管進(jìn)行切割，如果客戶(hù)需要20根8m長(zhǎng)、40根6m長(zhǎng)和80根4m長(zhǎng)的該種特制鋼管，則應(yīng)當(dāng)如何對(duì)鋼管進(jìn)行切割才能使用料最省？應(yīng)用實(shí)例合理下料問(wèn)題問(wèn)題分析對(duì)于合理下料問(wèn)題的關(guān)鍵問(wèn)題在于確定合適的切割方案。所謂一個(gè)切割方案，是指按照客戶(hù)要求的長(zhǎng)度在原料鋼管上安排切割的一種組合。例如，我們可以將17m長(zhǎng)的鋼管切割成4根4m長(zhǎng)的鋼管，余料為1m；或者切割成8m長(zhǎng)和6m長(zhǎng)的鋼管各1根，余料為3米。在即便不能窮盡所有的方案的前提下，則需要收集盡可能多的切割方案以考慮更多的情況。在此需指出，切割模式必須合理，即余料應(yīng)當(dāng)小于客戶(hù)要求的最小尺寸，否則原料則可以繼續(xù)被切割滿(mǎn)足客戶(hù)的一種需要。例如，將17m長(zhǎng)的鋼管切割成2根6m長(zhǎng)的鋼管，余料為5m，可以進(jìn)一步將5m的余料切割成4m長(zhǎng)的鋼管，余料為1米。于是本例的切割模式有：

然后確定設(shè)計(jì)目標(biāo)，所謂的用料最省，我們可以有兩種理解：(1)所用的鋼管數(shù)量最少，這種情況適用于余料不能用作他用(2)余料最少，例如余料可以用于別的用途。在這兩種前提下的目標(biāo)函數(shù)不同，解也可能不同，在此，我們采用第一種理解。方案1方案2方案3方案4方案58m000116m012014m42120余料13113應(yīng)用實(shí)例合理下料問(wèn)題問(wèn)題解答假設(shè)用第i種方案切割的鋼管根數(shù)為xi

(i=1,2,...,5)，則所需要的原鋼管的數(shù)量為切割的鋼管數(shù)總和，即：根據(jù)表格中的數(shù)據(jù)和上述假設(shè)，可以知道經(jīng)過(guò)切割以后獲得符合客戶(hù)要求的各種規(guī)格的鋼管的數(shù)目如下，設(shè)用pi表示im長(zhǎng)的鋼管的數(shù)量，即：

由于客戶(hù)需要50根8m長(zhǎng)、60根6m長(zhǎng)和30根4m長(zhǎng)的鋼管，故各種規(guī)格的鋼管數(shù)目應(yīng)當(dāng)不小于客戶(hù)的要求，即需要滿(mǎn)足p8≥20、p6≥40、p4≥80，于是：由于鋼管的數(shù)量是非負(fù)整數(shù)值，故所采用的切割方案中的各設(shè)計(jì)變量也均為非負(fù)整數(shù)。應(yīng)用實(shí)例合理下料問(wèn)題數(shù)學(xué)模型對(duì)于該問(wèn)題的目標(biāo)，要求所用的鋼管數(shù)最少，目標(biāo)函數(shù)f=S

，故該問(wèn)題的數(shù)學(xué)模型為：應(yīng)用實(shí)例合理下料問(wèn)題代碼和結(jié)果根據(jù)上述結(jié)果可以知道，所用鋼管的最少數(shù)目為45根，其中采用各個(gè)方案切割鋼管的數(shù)目如最優(yōu)解向量x中的各分量值。c=ones(1,5);A=[000-1-1;0-1-20-1;-4-2-1-20];b=[-20;-40;-80];lb=zeros(1,5);M=[1;2;3;4;5]; %所有變量均為整數(shù)變量，故將所有序號(hào)組成向量MTol=1e-8; %判定為整數(shù)的誤差限[x,fval]=intprog(c,A,b,[],[],lb,[],M,Tol)x=5020200fval=45.0000應(yīng)用實(shí)例生產(chǎn)計(jì)劃問(wèn)題問(wèn)題的提出某工廠生產(chǎn)某種電器用以滿(mǎn)足某地區(qū)市場(chǎng)的需求。經(jīng)該工廠的市場(chǎng)銷(xiāo)售部門(mén)部門(mén)對(duì)該地區(qū)銷(xiāo)售情況的統(tǒng)計(jì)，估計(jì)該電器在明年四個(gè)季度的需求量分別為1500臺(tái)、2000臺(tái)、4000臺(tái)和1000臺(tái)。而經(jīng)該廠生產(chǎn)計(jì)劃部門(mén)的預(yù)估，該廠生產(chǎn)能力能滿(mǎn)足市場(chǎng)的需求。即不用考慮工廠的生產(chǎn)能力。如果該廠決定在某一季度開(kāi)工，需要工程準(zhǔn)備費(fèi)2萬(wàn)元，每臺(tái)電器的生產(chǎn)成本為500元，如果在滿(mǎn)足需求以后季度末有庫(kù)存產(chǎn)品剩余，則每臺(tái)電器的存儲(chǔ)費(fèi)為10元。假設(shè)開(kāi)始工廠無(wú)庫(kù)存，則應(yīng)當(dāng)如何安排生產(chǎn)，在既能滿(mǎn)足市場(chǎng)需求的前提下可以使得總費(fèi)用最省。應(yīng)用實(shí)例生產(chǎn)計(jì)劃問(wèn)題問(wèn)題分析在這里共有四個(gè)季度用i來(lái)表示，i=1,2,3,4。假設(shè)在第i個(gè)季度內(nèi)，第i個(gè)季度的需求量為ri，電器的產(chǎn)量為xi，第i個(gè)季度末的庫(kù)存為si。同時(shí)引入0-1變量vi表示某個(gè)季度是否開(kāi)工，即：由于只有開(kāi)工才會(huì)有產(chǎn)量，故當(dāng)vi=1時(shí)，第i季度才支出準(zhǔn)備費(fèi)20000，當(dāng)vi=0時(shí)，第i季度的該筆支出為零，故可知，這部分的費(fèi)用為：由于每件電器的生產(chǎn)成本為500元，故第i季度的生產(chǎn)成本為500xi，則一年中的生產(chǎn)成本：易知由于庫(kù)存而產(chǎn)生的保管費(fèi)用為綜合式上述分析，產(chǎn)生的總費(fèi)用為，將其作為目標(biāo)函數(shù)，對(duì)其最小化應(yīng)用實(shí)例生產(chǎn)計(jì)劃問(wèn)題問(wèn)題分析下面分析約束條件，由于只有某季度開(kāi)工才可能有新的產(chǎn)品生產(chǎn)出來(lái)，即在vi和xi之間存在約束關(guān)系：此時(shí)可以看出vi和xi