物流運籌學課件3

物流運籌學

LogisticsOperationalResearch物流管理專業(yè)基礎課程郭淑紅guoshuhong_1982@163.cohapter4整數規(guī)劃

(IntegerProgramming)整數規(guī)劃問題及數學模型分支定界法割平面法0—1規(guī)劃與隱枚舉法指派問題與匈牙利法本章主要內容：第一節(jié)整數規(guī)劃問題及數學模型線性規(guī)劃的決策變量取值可以是任意非負實數，但許多實際問題中，只有當決策變量的取值為整數時才有意義例如，產品的件數、機器的臺數、裝貨的車數、完成工作的人數等，分數或小數解顯然是不合理的。要求全部或部分決策變量的取值為整數的線性規(guī)劃問題，稱為整數規(guī)劃(IntegerProgramming)。全部決策變量的取值都為整數，則稱為全整數規(guī)劃(AllIP)僅要求部分決策變量的取值為整數，則稱為混合整數規(guī)劃(MixedIP)要求決策變量只取0或1值，則稱0-1規(guī)劃(0-1Programming)

整數規(guī)劃（簡稱：IP）

要求一部分或全部決策變量取整數值的規(guī)劃問題稱為整數規(guī)劃。不考慮整數條件，由余下的目標函數和約束條件構成的規(guī)劃問題稱為該整數規(guī)劃問題的松弛問題。若該松弛問題是一個線性規(guī)劃，則稱該整數規(guī)劃為整數線性規(guī)劃。整數線性規(guī)劃數學模型的一般形式：第一節(jié)整數規(guī)劃問題及數學模型一、純整數規(guī)劃第一節(jié)整數規(guī)劃問題及數學模型第一節(jié)整數規(guī)劃問題及數學模型解：例：某公司擬建設A、B兩種類型的生產基地若干個，兩種類型的生產基地每個占地面積，所需經費，建成后生產能力及現(xiàn)有資源情況如下表所示。問A、B類型基地各建設多少個，可使總生產能力最大？

解：設A、B兩類基地各建設個，則其模型為：第一節(jié)整數規(guī)劃問題及數學模型人員安排規(guī)劃某服務部門各時段(每2小時為一時段)需要的服務人數如表：解：設第j時段開始時上班的服務員人數為xj第j時段來上班的服務員將在第j+3時段結束時下班，故決策變量有x1,x2,x3,x4,x5

。按規(guī)定，服務員連續(xù)工作8小時(4個時段)為一班。請安排服務員的工作時間，使服務員總數最少.第一節(jié)整數規(guī)劃問題及數學模型二、0-1規(guī)劃登山隊員可攜帶最大重量為25公斤。問都帶哪些物品的重要性最大。解：對于每一種物品無非有兩種狀態(tài)，帶或者不帶，不妨設

序號1234567物品食品氧氣冰鎬繩索帳篷相機設備重量55261224重要性系數2015181484100-1規(guī)劃的模型：第一節(jié)整數規(guī)劃問題及數學模型三、混合整數規(guī)劃例：某產品有n個區(qū)域市場，各區(qū)域市場的需求量為bj噸/月；現(xiàn)擬在m個地點中選址建生產廠，一個地方最多只能建一家工廠；若選i地建廠，生產能力為

ai噸/月，其運營固定費用為F元/月；已知址i至j區(qū)域市場的運價為cij元/噸。如何選址和安排調運，可使總費用最??？解：選址建廠與否是個0-1型決策變量，假設yi=1，選擇第i

址建廠，

yi=0，不選擇第i

址建廠；計劃從i址至區(qū)域市場j的運輸運量xij為實數型決策變量。第一節(jié)整數規(guī)劃問題及數學模型例工廠A1和A2生產某種物資。由于該種物資供不應求，故需要再建一家工廠。相應的建廠方案有A3和A4兩個。這種物資的需求地有B1,B2,B3,B4四個。各工廠年生產能力、各地年需求量、各廠至各需求地的單位物資運費cij，見下表：B1B2B3B4年生產能力A12934400A28357600A37612200A44525200年需求量350400300150工廠A3或A4開工后，每年的生產費用估計分別為1200萬或1500萬元?，F(xiàn)要決定應該建設工廠A3還是A4，才能使今后每年的總費用最少。第一節(jié)整數規(guī)劃問題及數學模型解：這是一個物資運輸問題，特點是事先不能確定應該建A3還是A4中哪一個，因而不知道新廠投產后的實際生產物資。為此，引入0-1變量：再設xij為由Ai運往Bj的物資數量，單位為千噸；z表示總費用，單位萬元。則該規(guī)劃問題的數學模型可以表示為：第一節(jié)整數規(guī)劃問題及數學模型混合整數規(guī)劃問題第一節(jié)整數規(guī)劃問題及數學模型思考：整數規(guī)劃的求解思路放松整數約束后，整數規(guī)劃問題變成線性規(guī)劃問題，稱為整數規(guī)劃的線性規(guī)劃松弛問題；整數規(guī)劃一個線性規(guī)劃問題＋整數約束。第一節(jié)整數規(guī)劃問題及數學模型整數規(guī)劃問題解的特征：

整數規(guī)劃問題的可行解集合是它松弛問題可行解集合的一個子集，任意兩個可行解的凸組合不一定滿足整數約束條件，因而不一定仍為可行解。整數規(guī)劃問題的可行解一定是它的松弛問題的可行解（反之不一定），但其最優(yōu)解的目標函數值不會優(yōu)于后者最優(yōu)解的目標函數值。第一節(jié)整數規(guī)劃問題及數學模型舍入化整法為了滿足整數解的要求，自然想到“舍入”或“截尾”處理，以得到與最優(yōu)解相近的整數解。這樣做除少數情況外，一般不可行，因為化整后的解有可能超出了可行域，成為非可行解；或者雖是可行解，卻不是最優(yōu)解。第一節(jié)整數規(guī)劃問題及數學模型例

設整數規(guī)劃問題如下首先不考慮整數約束，得到線性規(guī)劃問題（一般稱為松弛問題）。第一節(jié)整數規(guī)劃問題及數學模型用圖解法求出最優(yōu)解為：x1＝3/2,x2=10/3，且有Z=29/6

現(xiàn)求整數解(最優(yōu)解):如用舍入取整法可得到4個點即(1，3),(2，3),(1，4),(2，4)。顯然，它們都不可能是整數規(guī)劃的最優(yōu)解。x1x2⑴⑵33(3/2,10/3)

按整數規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內且為整數點。故整數規(guī)劃問題的可行解集是一個有限集，如右圖所示。其中(2,2),(3,1)點的目標函數值最大，即為Z=4。第一節(jié)整數規(guī)劃問題及數學模型窮舉整數法

對于決策變量少，可行的整數解又較少時，這種窮舉法有時是可行的，并且也是有效的。但對于大型的整數規(guī)劃問題，可行的整數解數量很多，用窮舉法求解是不可能的。例如，指派問題。5x1+7x2=352x1+x2=9?(3,3)??????????x1x2123125344第一節(jié)整數規(guī)劃問題及數學模型結論：

目前比較成熟的幾種求解方法：分配問題的匈牙利法、分枝定界法、割平面法和0—1規(guī)劃。第一節(jié)整數規(guī)劃問題及數學模型第二節(jié)分支定界法分支定界法

LandDoig和Dakin于60年代提出一種隱枚舉法,用來解純整數規(guī)劃及混合整數規(guī)劃.第二節(jié)分支定界法一、分支定界法原理

整數規(guī)劃的可行域是相應的線性規(guī)劃松弛問題可行域的子集；因此，松弛問題最優(yōu)解是整數規(guī)劃最優(yōu)解的一個界（對于max，為上界；對于min，為下界）。第二節(jié)分支定界法求解松弛問題的最優(yōu)解：分析整數規(guī)劃問題A對應的松弛問題B的最優(yōu)解（對于max）：B無可行解，則整數規(guī)劃問題A也無可行解；B最優(yōu)解為整數（即符合整數規(guī)劃A的可行解），則為A的最優(yōu)解；B最優(yōu)解為小數（不符合A的可行解），其目標函數值為A的上界，記—→分枝；分枝與定界：分枝——任取一小數的解，向下取整后，構造2個約束條件，分別在問題B加上約束條件，繼續(xù)求解（問題B分為2個枝B1,B2）；定界——取問題B1,B2的最優(yōu)解中最大的一個進行分析（其為上界），若仍為小數繼續(xù)分枝。說明：該方法可計算機求解；在部分可行解中求解，計算量小于枚舉法；對于大問題，計算量仍較大。第二節(jié)分支定界法例解：第一步，求相應松弛問題最優(yōu)解不考慮整數約束，求出相應松弛問題LP0的最優(yōu)解：二、分支定界法舉例

第二節(jié)分支定界法第二步，定界過程。這個解不滿足整數約束，因此不是原整數規(guī)劃的最優(yōu)解。因為這個問題是求最大化問題，前面說過整數規(guī)劃是在線性規(guī)劃的基礎上增加了整數約束，現(xiàn)在不考慮整數約束求得這個解，其目標函值Z是原整數規(guī)劃目標函數的上界，記。由于必然滿足整數約束，其目標函數值為0，確定為現(xiàn)有下界，記。第二節(jié)分支定界法第三步，分枝過程，將不滿足整數約束的變量x1進行分枝，構造兩個新的約束條件：這樣就把相應的線性規(guī)劃的可行域分成兩個部分5

x2

1

2

5

3

4

x1

1

2

3

4

2x1+x2=9

5x1+7x2=35

第二節(jié)分支定界法由于區(qū)域中不包含整數點，使可行域逐步的縮小了一部分，因此分枝后不影響整數規(guī)劃的最優(yōu)解。把新構造的兩個約束分別并入原整數規(guī)劃相應的線性規(guī)劃中，構成:LP1的數學模型：LP2的數學模型：對于問題LP1求解得：對于問題LP2求解得：第二節(jié)分支定界法第四步，定界過程。

LP2的解滿足整數約束，不必再分枝，它的目標函數值是29，大于原有下界0，則新的下界為29，即現(xiàn)有上界為未分枝子問題中目標函數最大值，即為LP1的解仍不滿足整數約束的要求，且現(xiàn)有上界大于現(xiàn)有下界，則應繼續(xù)分枝。第五步，分枝過程。選LP1的作為分枝變量，構造以下兩個新的約束條件：這樣就把LP1相應的線性規(guī)劃的可行域分成兩個部分，分別并入LP1，構造兩個新的線性規(guī)劃LP3、LP4。第二節(jié)分支定界法LP3數學模型：LP4數學模型：求解線性規(guī)劃LP3，得最優(yōu)解：求解LP4得最優(yōu)解：第二節(jié)分支定界法第六步，定界過程。

LP3的解滿足整數約束要求，不必再進行分枝，比較所有整數可行解，選擇目標函數值最大者為新的下界，即現(xiàn)有下界仍為為29，而LP3不優(yōu)于現(xiàn)有下界，應當剪枝；現(xiàn)有上界，上下界不相等，說明介于和整數解29之間還有可能存在其它解，應接著將上界所對應的線性規(guī)劃問題再次LP4分枝。第二節(jié)分支定界法第七步，分枝過程。

選LP4的作為分枝變量，構造以下兩個新的約束條件：或。這樣又把LP4相應的線性規(guī)劃的可行域分成兩個部分，分別并入LP4，構造兩個新的線性規(guī)劃LP5、LP6。第二節(jié)分支定界法LP5數學模型：LP6數學模型：求解線性規(guī)劃LP5，得最優(yōu)解：求解LP6得最優(yōu)解：無最優(yōu)解第二節(jié)分支定界法第八步，定界過程。

LP6無最優(yōu)解，應當剪枝；LP5的解不滿足整數約束，所以下界仍為（已經獲得整數解中選擇目標函數最大值）；上界為（沒有分枝問題中選擇目標函數最大值）。上下界不相等，說明還無法判定滿足整數約束的LP2解是否就是整數規(guī)劃的最優(yōu)解，應接著將上界所對應的線性規(guī)劃問題再次LP5分枝。第二節(jié)分支定界法第九步，分枝過程。

選LP5的作為分枝變量，構造以下兩個新的約束條件：或。這樣又把LP5相應的線性規(guī)劃的可行域分成兩個部分，分別并入LP5，構造兩個新的線性規(guī)劃LP7、LP8。第二節(jié)分支定界法LP7數學模型：LP8數學模型：求解線性規(guī)劃LP7，得最優(yōu)解

求解LP8得最優(yōu)解：。第二節(jié)分支定界法第十步，定界過程。

LP7的最優(yōu)解，滿足整數約束，不必再分枝，但其整數解不優(yōu)于現(xiàn)有下界，所以下界仍為29；現(xiàn)有上界為未分枝子問題中目標函數最大值，即為29。雖然LP8的解仍不滿足整數約束的要求，它的目標函數值小于現(xiàn)有下界29，應當進行剪枝，則不再繼續(xù)分枝。上界=下界=29，所以得到整數規(guī)劃問題的最優(yōu)解就是LP2的最優(yōu)解，即將分枝過程用一個樹形圖來表示。圖中的結點表示各線性規(guī)劃，結點旁邊的數值表示相應線性規(guī)劃的最優(yōu)解和最優(yōu)目標函數值。第二節(jié)分支定界法x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3x2≤3x2≥4第二節(jié)分支定界法1）求整數規(guī)劃的松弛問題最優(yōu)解； 若松弛問題的最優(yōu)解滿足整數要求，得到整數規(guī)劃的最優(yōu)解,否則轉下一步；2）分支與定界： 任意選一個非整數解的變量xi，在松弛問題中加上約束：xi≤[xi]和xi≥[xi]+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目標值是分枝問題的下界。

分支定界法的解題步驟：第二節(jié)分支定界法

檢查所有分枝的解及目標函數值，若某分枝的解是整數并且目標函數值大于（max）等于其它分枝的目標值，則將其它分枝剪去不再計算，若還存在非整數解并且目標值大于(max)整數解的目標值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。分支定界法的解題步驟：第二節(jié)分支定界法例

用分枝定界法求解整數規(guī)劃問題解：首先去掉整數約束，變成一般線性規(guī)劃問題(原整數規(guī)劃問題的松馳問題)LPIP第二節(jié)分支定界法用圖解法求松弛問題的最優(yōu)解，如圖所示。x1x2⑴⑵3(18/11,40/11)⑶21123x1＝18/11,x2=40/11Z=－218/11≈(－19.8)即Z也是IP最小值的下限。對于x1＝18/11≈1.64，取值x1≤1，x1≥2對于x2=40/11≈3.64，取值x2≤3，x2≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2第二節(jié)分支定界法分支：分別求出（LP1）和（LP2）的最優(yōu)解。第二節(jié)分支定界法先求LP1,如圖所示。此時在B點取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數解，問題已探明，此枝停止計算。x1x2⑴⑵33(18/11,40/11)⑶11BAC同理求LP2,如圖所示。在C

點取得最優(yōu)解。即:x1＝2,x2=10/3,Z(2)＝－56/3≈－18.7∵Z(2)<Z(1)＝－16∴原問題有比－16更小的最優(yōu)解，但x2不是整數，故繼續(xù)分支。第二節(jié)分支定界法在IP2中分別再加入條件：x2≤3,x2≥4得下式兩支：分別求出LP21和LP22的最優(yōu)解第二節(jié)分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACD先求LP21,如圖所示。此時D在點取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(21)＝-87/5≈-17.4<Z(1)=-16但x1＝12/5不是整數，可繼續(xù)分枝。即3≤x1≤2。求LP22，如圖所示。無可行解，故不再分枝。第二節(jié)分支定界法

在（LP21）的基礎上繼續(xù)分枝。加入條件3≤x1≤2有下式：分別求出（LP211）和（LP212）的最優(yōu)解第二節(jié)分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACDEF先求（LP211）,如圖所示。此時在E點取得最優(yōu)解。即x1＝2,x2=3,Z(211)＝－17找到整數解，問題已探明，此枝停止計算。求（LP212），如圖所示。此時F在點取得最優(yōu)解。即x1＝3,x2=2.5,Z(212)＝－31/2≈－15.5>Z(211)

如對LP212繼續(xù)分解，其最小值也不會低于－15.5，問題探明,剪枝。第二節(jié)分支定界法

原整數規(guī)劃問題的最優(yōu)解為:x1=2,x2=3,Z*=－17

以上的求解過程可以用一個樹形圖表示如右：LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP21x1=12/5,x2=3Z(21)

＝－17.4LP22無可行解LP211x1=2,x2=3Z(211)

＝－17LP212x1=3,x2=5/2Z(212)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃第二節(jié)分支定界法例

用分枝定界法求解解:先求對應的松弛問題（記為LP0）用圖解法得到最優(yōu)解X＝(3.57,7.14),Z0=35.7,如下圖所示。第二節(jié)分支定界法1010松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC第二節(jié)分支定界法10x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8①②LP2:X=(4,6.5),Z2=35.5第二節(jié)分支定界法10x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.336第二節(jié)分支定界法10x1x2oACLP1346LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212第二節(jié)分支定界法上述分枝過程可用下圖表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP21:X=(4.33,6)Z21=35.33x2≤6LP211:X=(4,6)Z211=34LP212:X=(5,5)Z212=35x1≤4x1≥5LP22無可行解x2≥7第二節(jié)分支定界法小結學習要點：掌握一般整數規(guī)劃問題概念及模型結構掌握分支定界法原理能夠用分支定界法求解一般整數規(guī)劃問題課后練習：第二節(jié)分支定界法割平面法（Gomory，58年）（不常用，了解）第三節(jié)割平面法計算步驟——舉例求解整數規(guī)劃模型：化標準型：）分析：第一步，如果原問題的系數有小數，將其化為整數。如第一個約束化為第三節(jié)割平面法第二步，用單純形法求松弛問題，得最終單純形表。cj→8500CB基bx1x2x3x40x31223100x46[2]－101cj－zj85000x360[4]1－18x131－1/201/2cj－zj090－45x23/2011/4－1/48x115/4101/83/8cj－zj00－9/4－7/4松弛問題的最優(yōu)解，，非整數規(guī)劃的可行解。第三節(jié)割平面法第三步，引進割平面在最終單純形表中選擇分數部分最大的基變量列出該行約束：將所有系數分成整數與一個正的分數之和：將分數部分移至右端：分析右邊的分數項，其取值小于1，即得到了Gomory約束：第三節(jié)割平面法本節(jié)內容的安排引入0-1變量的實際問題0-1型整數規(guī)劃的解法第四節(jié)0-1規(guī)劃與隱枚舉法

如果線性規(guī)劃中的所有決策變量的取值只能取0、1，則這類線性規(guī)劃問題是一種特殊的整數規(guī)劃問題稱之為0-1規(guī)劃，把只能取0或1值的變量稱為0-1變量。0-1變量是一種邏輯變量。第四節(jié)0-1規(guī)劃與隱枚舉法其數學模型如下：第四節(jié)0-1規(guī)劃與隱枚舉法本節(jié)先介紹引入0-1變量的實際問題：

①

投資場所（項目）的選定②相互排斥的約束條件③關于固定費用的問題然后，再研究0-1規(guī)劃問題的一般解法---隱枚舉法。第四節(jié)0-1規(guī)劃與隱枚舉法一、引入0-1變量的實際問題投資場所的選定——相互排斥的計劃例:

某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個位置(點)Ai(i=1，2，…，7)可供選擇。規(guī)定：在東區(qū)，由A1，A2，A3三個點中至多選兩個；在西區(qū)，由A4，A5兩個點中至少選一個；在南區(qū)，由A6，A7兩個點中至少選一個。如選用Ai點，設備投資估計為bi元，每年可獲利潤估計為ci元，但投資總額不能超過B元。問應選擇哪幾個點可使年利潤為最大?解題時先引入0-1變量xi(=1,2，…，7)問題建模：

2.相互排斥的約束條件設運貨有車運和船運兩種方式，用車運的體積限制條件為：

5x1+4x2≤24用船運的體積限制條件為：

7x1+3x2≤45這兩條件是互相排斥的。為了統(tǒng)一在一個問題中，引入0-1變量y，令（1）兩個約束條件中只有一個起作用5x1+4x2≤24+yM7x1+3x2≤45+(1-y)M

其中M是充分大的數,y是0-1變量。2.相互排斥的約束條件例：利用0–1變量將下題表示成一般線性約束條件x1+x22或2x1+3x25;解：2.相互排斥的約束條件變量x只能取值0、3、5或7中的一個;2.相互排斥的約束條件例：利用0–1變量將下題表示成一般線性約束條件變量x或等于0，或50;例：利用0–1變量將下題表示成一般線性約束條件2.相互排斥的約束條件若x1

2，則x2

1，否則x2

4;例：利用0–1變量將下題表示成一般線性約束條件2.相互排斥的約束條件2.相互排斥的約束條件以下四個約束條件中至少滿足兩個x1+x2

5，x12，x3

2，x3+x46例：利用0–1變量將下題表示成一般線性約束條件2.相互排斥的約束條件3.關于固定費用的問題在討論線性規(guī)劃時，有些問題是要求使成本為最小。這時總假定固定成本為常數，并在線性規(guī)劃的模型中不必明顯列出。但有些固定費用(固定成本)的問題不能用一般線性規(guī)劃來描述，但可改變?yōu)榛旌险麛稻€性規(guī)劃來解決。一.引入0-1變量的實際問題一.引入0-1變量的實際問題項目投資選擇有600萬元投資5個項目，收益如表，求利潤最大的方案？0-1變量的實際問題舉例互斥約束問題例如關于煤資源的限制，其約束條件為：企業(yè)也可以考慮采用天然氣進行加熱處理：這兩個條件是互相排斥的。引入0—1變量y，令互斥問題可由下述的條件來代替，其中M是充分大的數。

0-1變量的實際問題舉例租賃生產問題

服裝公司租用生產線擬生產T恤、襯衫和褲子。每年可用勞動力8200h，布料8800m2。T恤襯衫褲子勞動力326布料0.81.11.5售價250400600可變成本100180300生產線租金(萬)201510假設：yj=1，要租用生產線j

yi=0，不租用生產線j

第j種服裝生產量xj0-1變量的實際問題舉例現(xiàn)有資金總額為B?？晒┻x擇的投資項目有n個，項目j所需投資額和預期收益分別為aj和cj（j＝1,2,..,n），此外由于種種原因，有三個附加條件：若選擇項目1，就必須同時選擇項目2。反之不一定項目3和4中至少選擇一個；項目5,6,7中恰好選擇2個。應該怎樣選擇投資項目，才能使總預期收益最大。0-1變量的實際問題舉例解：對每個投資項目都有被選擇和不被選擇兩種可能，因此分別用0和1表示，令xj表示第j個項目的決策選擇，記為：投資問題可以表示為：0-1變量的實際問題舉例二、0-1規(guī)劃與隱枚舉法隱枚舉法的步驟：

1.找出任意一可行解，目標函數值為Z0

2.

原問題求最大值時，則增加一個約束當求最小值時，上式改為小于等于約束

3.列出所有可能解，對每個可能解先檢驗式（*），若滿足再檢驗其它約束，若不滿足式（*），則認為不可行，若所有約束都滿足，則認為此解是可行解，求出目標值

4.目標函數值最大（最?。┑慕饩褪亲顑?yōu)解

第四節(jié)0-1規(guī)劃與隱枚舉法【例】用隱枚舉法求解下面問題【解】（1）不難看出，當所有變量等于0或1的任意組合時，第一個約束滿足，說明第一個約束沒有約束力，是多余的，從約束條件中去掉。還能通過觀察得到X0＝(1，0，0，1)是一個可行解，目標值Z0=11是該問題的下界,增加下面約束第四節(jié)0-1規(guī)劃與隱枚舉法(2)列出變量取值0和1的組合，共24＝16個，分別代入約束條件判斷是否可行。首先判斷式（3.9a）是否滿足，如果滿足，接下來判斷其它約束，否則認為不可行。

第四節(jié)0-1規(guī)劃與隱枚舉法j

Xj

3.9a

3.9b

3.9c

3.9d

Zj

j

Xj

3.9a

3.9b

3.9c

3.9d

Zj

1(0,0,0,0)×

9(1,0,0,0)×

2(0,0,0,1)×

10(1,0,0,1)√

√

√

√

113(0,0,1,0)×

11(1,0,1,0)×

4(0,0,1,1)×

12(1,0,1,1)√

√

√

√

145(0,1,0,0)×

13(1,1,0,0)×

6(0,1,0,1)×

14(1,1,0,1)√

√

√

√

137(0,1,1,0)×

15(1,1,1,0)√

×

8(0,1,1,1)×

16(1,1,1,1)√

√

√

×

(3)由表知，該問題的最優(yōu)解：X＝（1，0，1，1），最優(yōu)值Z＝14第四節(jié)0-1規(guī)劃與隱枚舉法

選擇不同的初始可行解，計算量會不一樣。一般地，當目標函數求最大值時，首先考慮目標函數系數最大的變量等于1。當目標函數求最小值時，先考慮目標函數系數最大的變量等于0。第四節(jié)0-1規(guī)劃與隱枚舉法例：求解如下0-1規(guī)劃

max

z=3x1

-

2x2

+

5x3x1

+

2x2

-

x3

≤

2①x1

+

4x2

+

x3

≤

4②x1

+

x2

≤

3③

4x2

+

x3

≤

6④x1,x2,x3=0或1

解：(1)觀察一個可行解x1=1x2=x3=0

此時，z=3(2)增加一個過濾條件

3x1-2x2+5x3≥3*第四節(jié)0-1規(guī)劃與隱枚舉法(3)列表計算x1x2x3*①②③④可行？zx1x2x3*①②③④可行？z000001010011100101110111x1x2x3*①②③④可行？z0000×001010011100101110111x1x2x3*①②③④可行？z0000×0015-1101√5010011100101110111x1x2x3*①②③④可行？z0000×0015-1101√5010-2×011100101110111x1x2x3*①②③④可行？z0000×0015-1101√5010-2×011315×100101110111x1x2x3*①②③④可行？z0000×0015-1101√5010-2×011315×10031110√3101110111x1x2x3*①②③④可行？z0000×0015-1101√5010-2×011315×10031110√310180211√8110111x1x2x3*①②③④可行？z0000×0015-1101√5010-2×011315×10031110√310180211√81101×111x1x2x3*①②③④可行？z0000×0015-1101√5010-2×011315×10031110√310180211√81101×111626×∴最優(yōu)解：x1*=1x2*=0x3*=1此時，z*=8第四節(jié)0-1規(guī)劃與隱枚舉法例：用窮舉法解0-1整數規(guī)劃第四節(jié)0-1規(guī)劃與隱枚舉法

約束一二三四是否滿足約束條件S值最優(yōu)方案000001010011100101110111000012-1-243225510120124-1-155236711**--**--0-132*最優(yōu)解為最優(yōu)值為S=3.第四節(jié)0-1規(guī)劃與隱枚舉法在實際中經常會遇到這樣的問題，有n項不同的任務，需要n個人分別完成其中的一項，但由于任務的性質和各人的專長不同，因此各人去完成不同的任務的效率（或花費的時間或費用）也就不同。于是產生了一個問題，應指派哪個人去完成哪項任務，使完成n項任務的總效率最高（或所需時間最少），這類問題稱為分配問題或指派問題。一、指派問題及數學模型第五節(jié)指派問題與匈牙利法指派問題舉例甲、乙、丙、丁四個人，A、B、C、D四項任務，不同的人做不同的工作效率不同，如何指派不同的人去做不同的工作使效率最高，即花費的總時間最短？解：對于這個問題，很容易建立一個數學模型的，引入0-1變量，當=1時，表示分配第i個人完成第j項任務當=0時，表示不分配第i個人完成第j項任務

第五節(jié)指派問題與匈牙利法一項任務只由一個人完成，有如下約束一人只能完成一項任務，有如下約束第五節(jié)指派問題與匈牙利法例：

人事部門欲安排四人到四個不同崗位工作，每個崗位一個人。經考核四人在不同崗位的成績（百分制）如表所示，如何安排他們的工作使總成績最好。

工作人員ABCD甲85927390乙95877895丙82837990丁86908088第五節(jié)指派問題與匈牙利法設數學模型如下：要求每人做一項工作，約束條件為：第五節(jié)指派問題與匈牙利法每項工作只能安排一人，約束條件為：變量約束：第五節(jié)指派問題與匈牙利法第五節(jié)指派問題與匈牙利法指派問題的數學模型:

工作任務效率工人要求每個工人有一項工作,每項工作只有一個工人來作.如何安排使總的效益最好.第五節(jié)指派問題與匈牙利法第五節(jié)指派問題與匈牙利法二、指派問題的解法—匈牙利法匈牙利法(1955年W.W.Kuhn求解分配問題,使用了匈牙利數學家Kuhn的兩個定理,故稱匈牙利解法.定理1

第五節(jié)指派問題與匈牙利法定理2

若方陣中的一部分元素為零,一部分非零,則覆蓋方陣內所有零元素的最小直線數,等于方陣內位于不同行不同列的零元素的最多個數。第五節(jié)指派問題與匈牙利法第一步：變換指派問題的系數矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素第二步：進行試分配，以尋求最優(yōu)解。如果得到最優(yōu)解，運算結束，否則轉到第三步。第三步：作最少的直線覆蓋所有0元素。第四步：變換矩陣(bij)以增加0元素，轉到第二步。根據定理1,2設計出分配問題的一般解法:第五節(jié)指派問題與匈牙利法第一步:將效率矩陣A的每一行各減去該行的最小元素,再從新矩陣中的各列減去該列的最小元素,得矩陣B;第二步:從有零元素最少的行(列)開始,圈出零元素后劃去同行(列)的其他零元素.若被圈出的零元素恰好布滿B的不同行不同列,則將這些零元素改為1,其余元素改為0,得最優(yōu)分配矩陣.否則轉第三步;第五節(jié)指派問題與匈牙利法分配問題的一般解法詳解:⑴對沒有被圈出零的行打”√”;⑵對有√的行上所有有零元素的列打√;⑶再對打√的列上有被圈出零的行打√;第三步:根據定理2作出覆蓋零元素的最小直線集:第五節(jié)指派問題與匈牙利法⑷重復⑵,⑶直到得不出新打√的行,列為止;⑸對沒有打√的行畫橫虛線;對所有打√的列畫縱虛線,這就是覆蓋所有零元素的最小直線集,轉第四步;第四步:在沒有被覆蓋的元素中找出最小元素,對沒有畫直線的行上各元素都減去這個最小元素;對畫有直線的列上各元素都加上這個最小元素,這樣得到的矩陣如果不同行不同列上都有被圈出的零,則可將其換為1,其余元素換為0,最優(yōu)分配方案求出,否則轉第三步.第五節(jié)指派問題與匈牙利法例：某配送中心有四項配送任務,分配給四輛汽車去完成,每輛汽車完成各項配送任務的時間如下表,問如何分配任務使總的用時最少.

任務效率車輛2151341041415914161378119第五節(jié)指派問題與匈牙利法解:取出效率矩陣進行運算.在B中找出位于不同行,不同列的四個零元素,作法如下:⑴先從零元素最少的行(列)開始,選取一個零元素將其圈起來,同時將零元素所在行,列的其余零元素劃去;⑵如果恰有四個被圈起來的零元素,處于不同行不同列,則將這些零改為1,其余元素改為0,得到最優(yōu)分配方案.第五節(jié)指派問題與匈牙利法最優(yōu)分配方案是:最優(yōu)值(即總用時)是minS=4+4+9+11=28.注意:對于來說不是最優(yōu)方案,但對整體來說達到最優(yōu),這就是運籌學思想.第五節(jié)指派問題與匈牙利法例：工廠有五個獨立車間,該廠計劃生產五種產品,由于產品性質和各車間設備不同,每個車間生產各種產品消耗的資金(萬元)不同,如下表.問如何安排生產任務,使總的耗資最少.

產品資金消耗車間127979

89666717121412151466104107106第五節(jié)指派問題與匈牙利法解:√√√第五節(jié)指派問題與匈牙利法最優(yōu)分配方案:最優(yōu)值為第五節(jié)指派問題與匈牙利法例

已知五人分別完成五項工作耗費如下表，求最優(yōu)分配方案。

任務人員ABCDE甲759811乙9127119丙85468丁73696戊467511第五節(jié)指派問題與匈牙利法-1-2解：1）變換系數矩陣，增加0元素。第五節(jié)指派問題與匈牙利法◎?◎◎◎??2）試指派（找獨立0元素）獨立0元素的個數l＝4<5，故畫直線調整矩陣。第五節(jié)指派問題與匈牙利法◎?◎◎◎??√√√選擇直線外的最小元素為1；直線外元素減1，直線交點元素加1，其他保持不變。第五節(jié)指派問題與匈牙利法◎?◎?◎?◎?√√√√√√√l=m=4<n=5選擇直線外最小元素為1，直線外元素減1，直線交點元素加1，其他保持不變，得到新的系數矩陣。第五節(jié)指派問題與匈牙利法◎??◎??◎?◎?◎總費用為=5+7+6+6+4=28注：此問題有多個最優(yōu)解第五節(jié)指派問題與匈牙利法◎??◎??◎?◎?◎總費用為=7+9+4+3+5=28第五節(jié)指派問題與匈牙利法◎??◎??◎?◎?◎總費用為=8+9+4+3+4=28第五節(jié)指派問題與匈牙利法課堂練習：用匈牙利法求解下列指派問題。第五節(jié)指派問題與