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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

顯然可以表達成為，因為nM為一常數(shù)，故當f取得最小值時，可以取到最大值，即通過這種變換將原分派問題目標函數(shù)由最小化變成最大化，以符合匈牙利法的實施條件。

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

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

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

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

else{xx=x;fval=v;bb=bound;}endreturn;end一般整數(shù)規(guī)劃問題的MATLAB求解%程序運行至此，說明松弛線性規(guī)劃的解是一個可行解且目標函數(shù)值比當前記錄的上界要小，只是某些變量的%值并非整數(shù)，于是在此選擇合適的變量進行分枝形成兩個子問題，分別進行遞歸求解%該處選擇與整數(shù)值相差最大的非整數(shù)變量首先進行分枝形成兩個子問題,第一個非整數(shù)變量的序號，且記錄該變量與其最鄰近的整數(shù)之差的絕對值[rowcol]=size(ind);br_var=M(ind(1));br_value=x(br_var);flag=abs(br_value-floor(br_value)-0.5);%用于查找非整數(shù)設計變量中整數(shù)值相差最大的設計變量，即每當遇到與其最鄰近的整數(shù)差%別更大的非整數(shù)設計變量之時，即記錄下該設計變量的序號，直至遍歷完所有非整數(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ī)劃問題的MATLAB求解%第1個子問題的設置,添加約束條件Xi<=floor(Xi)，i即為上面找到的最接近整數(shù)的非整數(shù)設計變量的序號A1=[A;zeros(1,c)];A1(end,br_var)=1;b1=[b;floor(br_value)];%第2個子問題的設置,添加約束條件Xi>=ceil(Xi)，i即為上面找到的最接近整數(shù)的非整數(shù)設計變量的序號A2=[A;zeros(1,c)];A2(end,br_var)=-1;b2=[b;-ceil(br_value)];%分枝后的第一個子問題的遞歸求解[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%分枝后的第二個子問題的遞歸求解[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ī)劃問題的MATLAB求解求解整數(shù)規(guī)劃問題

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

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

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

0-1規(guī)劃的MATLAB求解代碼和結果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是一列元素，為了使結果更加直觀，故排成與效率矩陣E相對應的形式B'fvalOptimizationterminated.ans=0100001010000001fval=85應用實例賓館的排班問題問題的提出某連鎖賓館在一天的的各時間區(qū)段內(nèi)所需服務員的人數(shù)如表所示。假設服務員上班的時間在各時間段的開始時刻，并且連續(xù)工作8個小時。問題是，該賓館應該至少配備多少名服務員？班次時間段需要服務員人數(shù)108:00–12:00100212:00–16:00120316:00–20:0080420:00–24:0060500:00–04:0030604:00–08:0050應用實例賓館的排班問題問題分析設xi為從第i個班次開始上班的服務員人數(shù)，則該賓館共需服務員的人數(shù)為該問題的目標是該賓館配備服務員的最少的數(shù)量，即f值最小。約束條件為在每一時間段至少需要配備的服務員人數(shù)如表所示。根據(jù)分析，在班次1開始時刻即8:00開始上班的服務員，需要連續(xù)上班8個小時到16:00，即該服務員可以上兩個班次，所以在時間段08:00–12:00之間在崗的服務員為班次6和班次1的服務員，以此類推，在時間段12:00–16:00之間在崗的服務員為班次1和班次2的服務員，在時間段16:00–20:00之間在崗的服務員為班次2和班次3的服務員。根據(jù)上述分析，假設在班次n所在時間段需要的服務員人數(shù)為sn，則sn(n=1,2,…,6)和xi

(n=1,2,…,6)需要滿足的約束條件為：應用實例賓館的排班問題數(shù)學模型根據(jù)對問題的分析，我們可以總結得到該問題的數(shù)學模型為：應用實例賓館的排班問題代碼和結果由此可知，按照運行結果中的人數(shù)進行排班，即在各時間段的開始時刻分別安排50、70、23、37、0、50個服務員上班，所需要的總人數(shù)最少，一共為230個服務員。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ù)變量，故將所有序號組成向量MTol=1e-8;%判定為整數(shù)的誤差限[x,fval,exitflag]=intprog(f,A,b,[],[],lb,ub,M,Tol)x=50702337050fval=230exitflag=1應用實例賓館的排班問題問題的反思在這里需要指出的是，根據(jù)實際的需求，我們在問題中設置不等式約束是符合實際情況的，即并不一定要求恰好為限定的人數(shù)，多于此人數(shù)也是可以的。如果我們將不等式約束變?yōu)榈仁郊s束，即設定每個時間段的服務員人數(shù)為固定值，將不等號換成等號，此時可能出現(xiàn)如下情況：

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

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

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

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

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