1、2022-4-71運籌學運籌學OPERATIONS RESEARCH2022-4-72第四章第四章 整數規劃與分配問題整數規劃與分配問題（Integer Programming, IP) n整數規劃的有關概念及特點整數規劃的有關概念及特點 n整數規劃的求解方法：分枝定界法、割平面法整數規劃的求解方法：分枝定界法、割平面法 n指派問題及匈牙利解法指派問題及匈牙利解法 n整數規劃的應用整數規劃的應用Page 34.1 整數規劃的特點及應用要求一部分或全部決策變量取整數值的規劃問題稱為整數規劃。不考慮整數條件，由余下的目標函數和約束條件構成的規劃問題稱為該整數規劃問題的松弛問題。若該松弛問題是一個線

2、性規劃，則稱該整數規劃為整數線性規劃。整數線性規劃數學模型的一般形式：整數線性規劃數學模型的一般形式：11max(min) (1.2)0 (j1.2n) njjjnijjijjZZc xa xbimx且部分或全部為整數或Page 4整數規劃的特點及應用 純整數線性規劃：指全部決策變量都必須取整數值的整數純整數線性規劃：指全部決策變量都必須取整數值的整數線性規劃。線性規劃。 混合整數線性規劃：決策變量中有一部分必須取整數值，混合整數線性規劃：決策變量中有一部分必須取整數值，另一部分可以不取整數值的整數線性規劃。另一部分可以不取整數值的整數線性規劃。 0-10-1型整數線性規劃：決策變量只能取值型

3、整數線性規劃：決策變量只能取值0 0或或1 1的整數線性的整數線性規劃。規劃。Page 5一般形式一般形式11max(min) (1.2). .0 (j1.2n) njjjnijjijjZZc xa xbimstx或且部分或全部為整數依照決策變量取整要求的不同，整數規劃可分為純整數規劃、全整數規依照決策變量取整要求的不同，整數規劃可分為純整數規劃、全整數規劃、混合整數規劃、劃、混合整數規劃、0 01 1整數規劃。整數規劃。4.1.1 整數規劃問題的數學模型整數規劃問題的數學模型2022-4-76純整數規劃：純整數規劃：在整數規劃中，如果所有的變量都為非負整在整數規劃中，如果所有的變量都為非負整

4、 數，則稱為數，則稱為純整數規劃問題純整數規劃問題；混合整數規劃：混合整數規劃：如果有一部分變量為非負整數，則稱之為如果有一部分變量為非負整數，則稱之為 混合整數規劃問題混合整數規劃問題。0-10-1變量：變量：在整數規劃中，如果變量的取值只限于在整數規劃中，如果變量的取值只限于0 0和和1 1，這，這 樣的變量我們稱之為樣的變量我們稱之為0-10-1變量變量。0-10-1規劃：規劃：在整數規劃問題中，如果所有的變量都為在整數規劃問題中，如果所有的變量都為0-10-1變變 量，則稱之為量，則稱之為0-10-1規劃規劃。1 1 整數規劃的有關概念及特點整數規劃的有關概念及特點一、一、 概念概念整

5、數規劃：整數規劃： 要求決策變量取整數值的規劃問題。要求決策變量取整數值的規劃問題。 （線性整數規劃、非線性整數規劃等）（線性整數規劃、非線性整數規劃等）2022-4-77求整數解的線性規劃問題，不是用求整數解的線性規劃問題，不是用四舍五入四舍五入法或法或去尾法去尾法對對性規劃的非整數解加以處理就能解決的，用性規劃的非整數解加以處理就能解決的，用枚舉法枚舉法又往往又往往會計算量太大，所以要用整數規劃的特定方法加以解決。會計算量太大，所以要用整數規劃的特定方法加以解決。例：例： 求解下列整數規劃：求解下列整數規劃：二、二、 整數規劃的求解特點整數規劃的求解特點并取整數, 0,5 . 45 . 0

6、1432.23max21212121xxxxxxtsxxz2022-4-781x2x143221 xx5 . 45 . 021xx2123xxz)5 . 2,25. 3(分析：分析： 若當作一般線性規劃求若當作一般線性規劃求解，圖解法的結果如下。解，圖解法的結果如下。1、非整數規劃、非整數規劃最優解最優解 顯然不是整數規劃的可行解。顯然不是整數規劃的可行解。2、四舍五入后的結果四舍五入后的結果 也不是整數規劃的可行解。也不是整數規劃的可行解。)5 . 2,25. 3()3, 3(3、可行解是陰影區可行解是陰影區域交叉點，可比較這域交叉點，可比較這些點對應的函數值，些點對應的函數值，找出最優。找

7、出最優。) 1, 4(2022-4-79分析：分析： 若當作一般線性規劃求若當作一般線性規劃求解，圖解法的結果如下。解，圖解法的結果如下。1、非整數規劃、非整數規劃最優解最優解 顯然不是整數規劃的可行解。顯然不是整數規劃的可行解。2、四舍五入后的結果四舍五入后的結果 也不是整數規劃的可行解。也不是整數規劃的可行解。3、可行解是陰影區可行解是陰影區域交叉點，可比較這域交叉點，可比較這些點對應的函數值，些點對應的函數值，找出最優。找出最優。) 5 . 2,25. 3 (Page 10整數規劃的特點及應用例例1 1 工廠工廠A A1 1和和A A2 2生產某種物資。由于該種物資供不應求，故需要再生產

8、某種物資。由于該種物資供不應求，故需要再建一家工廠。相應的建廠方案有建一家工廠。相應的建廠方案有A A3 3和和A A4 4兩個。這種物資的需求地有兩個。這種物資的需求地有B B1 1,B,B2 2,B,B3 3,B,B4 4四個。各工廠年生產能力、各地年需求量、各廠至各需四個。各工廠年生產能力、各地年需求量、各廠至各需求地的單位物資運費求地的單位物資運費c cijij，見下表：，見下表：B1B2B3B4年生產能力年生產能力A12934400A28357600A37612200A44525200年需求量年需求量350400300150工廠工廠A3A3或或A4A4開工后，每年的生產費用估計分別為

9、開工后，每年的生產費用估計分別為12001200萬或萬或15001500萬元。萬元。現要決定應該建設工廠現要決定應該建設工廠A3A3還是還是A4A4，才能使今后每年的總費用最少。，才能使今后每年的總費用最少。Page 11整數規劃的特點及應用解：這是一個物資運輸問題，特點是事先不能確定應該建A3還是A4中哪一個，因而不知道新廠投產后的實際生產物資。為此，引入0-1變量：)2 , 1(01 iyi若不建工廠若不建工廠若建工廠若建工廠再設再設x xijij為由為由A Ai i運往運往B Bj j的物資數量，單位為千噸；的物資數量，單位為千噸；z z表示總費用，表示總費用，單位萬元。單位萬元。則該規

10、劃問題的數學模型可以表示為：則該規劃問題的數學模型可以表示為：Page 12整數規劃的特點及應用 )2 , 1(1 , 0)4 , 3 , 2 , 1,(0200200600400150300400350.15001200min244434241134333231242322211413121144342414433323134232221241312111414121iyjixyxxxxyxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsyyxcziijijijij混合整數規劃問題混合整數規劃問題Page 13整數規劃的特點及應用例2 現有資金總額為B。可供選擇的投資項目有n個，項

11、目j所需投資額和預期收益分別為aj和cj（j1,2,.,n），此外由于種種原因，有三個附加條件：q若選擇項目1，就必須同時選擇項目2。反之不一定q項目3和4中至少選擇一個；q項目5,6,7中恰好選擇2個。應該怎樣選擇投資項目，才能使總預期收益最大。Page 14整數規劃的特點及應用解：對每個投資項目都有被選擇和不被選擇兩種可能，因此分別用0和1表示，令xj表示第j個項目的決策選擇，記為：),.,2 , 1(01njjjxj 不不投投資資對對項項目目投投資資對對項項目目投資問題可以表示為：投資問題可以表示為： ）（或或者者nxxxxxxxxBxatsxczjnjjjnjjj, 2 , 1j102

12、1.max765431211Page 15整數規劃的特點及應用n例4.3 指派問題或分配問題。人事部門欲安排四人到四個不同崗位工作，每個崗位一個人。經考核四人在不同崗位的成績（百分制）如表所示，如何安排他們的工作使總成績最好。 工作工作人員人員ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088Page 16整數規劃的特點及應用設設 工作時工作時人做人做不分配第不分配第工作時工作時人做人做分配第分配第jijixij01數學模型如下：數學模型如下：444342413433323124232221141312118880908690798382957887959

13、0739285maxxxxxxxxxxxxxxxxxZ 要求每人做一項工作，約束條件為：要求每人做一項工作，約束條件為： 111144434241343332312423222114131211xxxxxxxxxxxxxxxxPage 17整數規劃的特點及應用n每項工作只能安排一人，約束條件為： 111144342414433323134232221241312111xxxxxxxxxxxxxxxx變量約束：變量約束：4 , 3, 2, 110 jixij、，或或Page 18例例 某人有一個背包可以裝某人有一個背包可以裝5公斤重、公斤重、0.02m3 的物品。他準備用來裝的物品。他準備用來裝

14、A、B兩種物品，每件物品的重量、體積和價值如表兩種物品，每件物品的重量、體積和價值如表3-2所示。問兩種物品各所示。問兩種物品各裝多少件才能使所裝物品的總價值最大？裝多少件才能使所裝物品的總價值最大？表表Page 19解：解：設設A、B兩種物品的裝載件數分別為兩種物品的裝載件數分別為 x1，x2，則該問題的數學模型為，則該問題的數學模型為12121212max451.20.55. . 0.0030.00250.02,0,Zxxxxs txxxx且為整數假設此人還有一只旅行箱，最大載重量為假設此人還有一只旅行箱，最大載重量為10公斤，其體積是公斤，其體積是0.018 m3。背包和行李箱只能選擇其

15、一，如果所需攜帶物品不變，問該如何裝載物背包和行李箱只能選擇其一，如果所需攜帶物品不變，問該如何裝載物品，使所裝物品價值最大？品，使所裝物品價值最大？Page 20解：解：引入引入0-1變量（或稱邏輯變量）變量（或稱邏輯變量）yi ，令，令1,=1,20,iiiyi采用第 種方式裝載時 不采用第 種方式裝載時 則該整數規劃數學模型為則該整數規劃數學模型為12122121212112max451.20.55100.0030.00250.020.018. .1,0,i=iZxxxxyyxxyystyyx xy且為整數； =0或1， 1,22022-4-7212 2 應用舉例應用舉例 一、一、 邏輯

16、變量在數學模型中的應用邏輯變量在數學模型中的應用1、m個約束條件中只有個約束條件中只有k個起作用個起作用設有設有m m個約束條件個約束條件mibanjiij,.,2 , 1,1定義定義0-10-1整型變量：整型變量：M M是任意大正數。是任意大正數。10iy第第i i個約束起作用個約束起作用第第i i個約束不起作用個約束不起作用則原約束中只有則原約束中只有k k個真正起作用的情況可表示為：個真正起作用的情況可表示為：kmyyymiMybamnjiiij.,.,2 , 1,2112022-4-7222、約束條件右端項是、約束條件右端項是r個可能值中的一個個可能值中的一個rnjijbbba或或,.

17、,211則通過定義則通過定義10iy約束條件右端項不是約束條件右端項不是b bi i約束條件右端項是約束條件右端項是b bi i可將上述條件表示為可將上述條件表示為 1.,2111rnjriiiijyyyyba2022-4-7233、兩組條件中滿足其中一組、兩組條件中滿足其中一組例如表示條件：若例如表示條件：若 ，則，則 ； 否則否則 時時則通過定義則通過定義10iy第第i i組條件起作用，組條件起作用，i=1i=1，2 2第第i i組條件不起作用組條件不起作用可將上述條件表示為可將上述條件表示為 , 41x, 32x, 41x, 12x又：又：M M是任意大正數，是任意大正數，1341421

18、22211211yyMyxMyxMyxMyx2022-4-724定義定義4、表示含有固定費用的函數、表示含有固定費用的函數例如：例如： 表示產品表示產品 j 的生產數量，其生產費用函數為：的生產數量，其生產費用函數為： jx目標函數：目標函數：00, 0,)(jjjjjjjxxxcKxC其中其中 是與產量無是與產量無關的生產準備費用關的生產準備費用 jKnjjjxCz1)(min10jy0jx0jx則原問題可表示為則原問題可表示為)(min1njjjjjyKxcz100.或jjjyMyxtsPage 25整數規劃的特點及應用 整數規劃問題的可行解集合是它松弛問題可行解集合的一整數規劃問題的可行

19、解集合是它松弛問題可行解集合的一個子集，任意兩個可行解的凸組合不一定滿足整數約束條件，個子集，任意兩個可行解的凸組合不一定滿足整數約束條件，因而不一定仍為可行解。因而不一定仍為可行解。 整數規劃問題的可行解一定是它的松弛問題的可行解（反整數規劃問題的可行解一定是它的松弛問題的可行解（反之不一定），但其最優解的目標函數值不會優于后者最優解之不一定），但其最優解的目標函數值不會優于后者最優解的目標函數值。的目標函數值。Page 26整數規劃的特點及應用n例4.3 設整數規劃問題如下 且且為為整整數數0,13651914max21212121xxxxxxxxZ首先不考慮整數約束，得到線性規劃問題（一

20、般稱為松弛問首先不考慮整數約束，得到線性規劃問題（一般稱為松弛問題）。題）。 0,13651914max21212121xxxxxxxxZPage 27整數規劃的特點及應用用圖解法求出最優解為：x13/2, x2 = 10/3，且有Z = 29/64.83現求整數解(最優解):如用舍入取整法可得到4個點即(1，3),(2，3),(1，4),(2，4)。顯然，它們都不可能是整數規劃的最優解。x1x233(3/2,10/3)按整數規劃約束條件，其可行解肯定在線性規劃問題的可行域內且為整數點。故整數規劃問題的可行解集是一個有限集，如右圖所示。其中(2,2),(3,1)點的目標函數值最大，即為Z=4。

21、Page 28整數規劃的特點及應用n整數規劃問題的求解方法： 分支定界法和割平面法分支定界法和割平面法 匈牙利法（指派問題）匈牙利法（指派問題）思考思考: 應如何求解整數線性規劃問題應如何求解整數線性規劃問題(IP)?枚舉法枚舉法2022-4-7294 4 分枝定界法分枝定界法 分枝定界法分枝定界法是求解整數規劃的一種常用的有效的方法，它是求解整數規劃的一種常用的有效的方法，它既能解決純整數規劃的問題，又能解決混合整數規劃的問既能解決純整數規劃的問題，又能解決混合整數規劃的問題。題。 大多數求解整數規劃的商用軟件就是基于分枝定界法編大多數求解整數規劃的商用軟件就是基于分枝定界法編制而成的。制而

22、成的。下面舉例來說明分枝定界法的思想和步驟。下面舉例來說明分枝定界法的思想和步驟。2022-4-730性質性質 求求MAXMAX的問題的問題：整數規劃的最優目標函數值整數規劃的最優目標函數值小于或小于或等于等于相應的線性規劃的最優目標函數值；相應的線性規劃的最優目標函數值； 求求MINMIN的問題：的問題：整數規劃的最優目標函數值整數規劃的最優目標函數值大于或大于或等于等于相應的線性規劃的最優目標函數值。相應的線性規劃的最優目標函數值。1、求解整數規劃相應的一般線性規劃問題（即先去掉整數、求解整數規劃相應的一般線性規劃問題（即先去掉整數約束）。約束）。 易知：整數規劃的可行域（小）包含于線性規

23、劃的可行易知：整數規劃的可行域（小）包含于線性規劃的可行域域 (大）。大）。 若線性規劃的最優解恰是整數解，則其就是整數規劃的若線性規劃的最優解恰是整數解，則其就是整數規劃的最優解。否則該最優解，是整數規劃最優解的上界或下界。最優解。否則該最優解，是整數規劃最優解的上界或下界。2022-4-731例：例： 求解下列整數規劃：求解下列整數規劃：并取整數, 0 x,x5 . 4x5 . 0 x14x3x2t . sx2x3zmax212121210,5 . 45 . 01432.23max21212121xxxxxxtsxxz解：解：1 1、解對應的線性規劃：、解對應的線性規劃：其最優解為其最優解

24、為 ，顯然不是整數規劃的可行顯然不是整數規劃的可行解。解。)5 . 2,25. 3(L0：75.140z2022-4-7322 2、分枝與定界：分枝與定界： 將對應的線性規劃問題分解成幾個子問題，每個子問將對應的線性規劃問題分解成幾個子問題，每個子問題就是一分枝，而所有子問題的解集之和要包含原整數規題就是一分枝，而所有子問題的解集之和要包含原整數規劃的解集。劃的解集。 求解每一分枝子問題：求解每一分枝子問題： 若其最優解滿足整數約束，則它就是原問題的一個可行若其最優解滿足整數約束，則它就是原問題的一個可行解（不一定是最優）；否則，就是該枝的上界或下界。解（不一定是最優）；否則，就是該枝的上界或

25、下界。 若所有分支的最優解都不滿足整數條件（即不是原問題若所有分支的最優解都不滿足整數條件（即不是原問題的可行解），則選取一個邊界值最優的分支繼續分解，直的可行解），則選取一個邊界值最優的分支繼續分解，直至找到一個原問題的可行解。至找到一個原問題的可行解。 若在同一級分枝中同時出現兩個以上的原問題可行解，若在同一級分枝中同時出現兩個以上的原問題可行解，則保留目標值最優的一個，其余不再考慮。則保留目標值最優的一個，其余不再考慮。從各分枝中找原問題可行解的目的是為下一步的比較與剪枝。從各分枝中找原問題可行解的目的是為下一步的比較與剪枝。2022-4-733將上述線性規劃問題分為兩枝，并求解。將上述

26、線性規劃問題分為兩枝，并求解。5 .14, 2, 5 . 3121zxx解得5 .13, 3, 5 . 2221zxx解得L1：L2：0,25 . 45 . 01432.23max212212121xxxxxxxtsxxz0,35 . 45 . 01432.23max212212121xxxxxxxtsxxz顯然兩個分枝均非整數可行解，選邊界值較大的顯然兩個分枝均非整數可行解，選邊界值較大的L L1 1繼續分繼續分枝。枝。 2022-4-734將將L1分為兩枝，并求解。分為兩枝，并求解。13, 2, 3121zxx解得14, 1, 4221zxx解得L11：L12：0,325 . 45 . 0

27、1432.23max2112212121xxxxxxxxtsxxz兩個分枝均是整數可行解，保留目標值較大的兩個分枝均是整數可行解，保留目標值較大的L L1212。 0,425 . 45 . 01432.23max2112212121xxxxxxxxtsxxz2022-4-7353 3、比較與剪枝比較與剪枝 將各子問題的邊界值與保留下的整數可行解對應的目將各子問題的邊界值與保留下的整數可行解對應的目標值比較，將邊界值劣于可行行解的分支減剪去。標值比較，將邊界值劣于可行行解的分支減剪去。 若比較剪枝后，只剩下所保留的整數可行解，則該解就若比較剪枝后，只剩下所保留的整數可行解，則該解就是原整數規劃的

28、最優解；否則選取邊界值最大的一個分枝是原整數規劃的最優解；否則選取邊界值最大的一個分枝繼續分解，在其后的過程中出現新的整數可行解時，則與繼續分解，在其后的過程中出現新的整數可行解時，則與原可行解比較，保留較優的一個，重復第三步。原可行解比較，保留較優的一個，重復第三步。2022-4-736L0：X22X23X13X14用圖表示上例的求解過程與求解結果用圖表示上例的求解過程與求解結果75.14, 5 . 2,25. 3121zxx5 .14, 2, 5 . 3121zxx5 .13, 3, 5 . 2221zxx13, 2, 3121zxx14, 1, 4221zxx2022-4-7375 割平

29、面法割平面法 一、一、 基本思想基本思想 在整數規劃的松弛問題中，依次引進新的約束條件在整數規劃的松弛問題中，依次引進新的約束條件（割平面），使問題的可行域逐步減小，但每次割去（割平面），使問題的可行域逐步減小，但每次割去的只是部分非整數解，直到使問題的目標函數值達到的只是部分非整數解，直到使問題的目標函數值達到最優的整數點成為縮小后的可行域的一個頂點，這樣最優的整數點成為縮小后的可行域的一個頂點，這樣就可以用線性規劃的方法求得整數最優解。就可以用線性規劃的方法求得整數最優解。2022-4-738例：例： 求解下列整數規劃：求解下列整數規劃：并取整數, 0,5 . 45 . 01432.23m

30、ax21212121xxxxxxtsxxz0,921432.23max21212121xxxxxxtsxxz解：解：1 1、解對應的線性規劃（松弛問題），并將約束條件的系解對應的線性規劃（松弛問題），并將約束條件的系數均化為整數：數均化為整數：2022-4-739加入松弛變量后求解，得最終單純形表：加入松弛變量后求解，得最終單純形表：25/2011/2-1/2313/410-1/43/400-1/4-5/41x4x3x1x2x2xj如果上述求解結果是整數解，則結束；否則轉下一步；如果上述求解結果是整數解，則結束；否則轉下一步；2 2、找出非整數解中分數部分最大的一個基變量，并將該行找出非整數解

31、中分數部分最大的一個基變量，并將該行對應的約束方程所有常數（系數及常數項）分解成一個整數對應的約束方程所有常數（系數及常數項）分解成一個整數與一個正分數之和；將所有分式項移到等式右端。與一個正分數之和；將所有分式項移到等式右端。例如上例，取第一行約束例如上例，取第一行約束 2022-4-74043424324322121212212)211(21252121xxxxxxxxxx易知，左端為整數，要是等式成立，右端也必為整數，且易知，左端為整數，要是等式成立，右端也必為整數，且02121211212121214343xxxx將將 代入上式，得代入上式，得214213293214xxxxxx112

32、221 xx2022-4-7411x2x143221 xx5 . 45 . 021xx2123xxz)5 . 2,25. 3() 1, 4(112221 xx這就是一個割平面。將這就是一個割平面。將其添加到原約束中，得其添加到原約束中，得到新的可行域如圖所示。到新的可行域如圖所示。割去的只是部分非整數割去的只是部分非整數解。解。112221 xx2022-4-7423 3、將新的約束添加到原問題中，得到一個新的線性規劃問將新的約束添加到原問題中，得到一個新的線性規劃問題，求解此問題，可用靈敏度分析的方法。題，求解此問題，可用靈敏度分析的方法。4 4、重復上述的重復上述的1-31-3步，直至求出

33、整數最優解。步，直至求出整數最優解。25/2011/2-1/20313/410-1/43/400-1/200-1/2-1/2100-1/4-5/40212121021212154343xxxxx將將 反應到最終表中，得反應到最終表中，得1x4x3x1x2x2xj5x5x2022-4-743運用對偶單純形法，解得運用對偶單純形法，解得22010-11/231001-1/2010011-2000-1-1/21x4x3x1x2x2xj3x5x213此解仍非整數解，將基變量此解仍非整數解，將基變量 對應的約束分解為：對應的約束分解為： 1x55415412121321321xxxxxxx得到新的約束得

34、到新的約束 212102121655xxx2022-4-74422010-11/2031001-1/20010011-200-1/20000-1/21000-1-1/201x4x3x1x2x2xj3x5x2136x21010-1023410010-10300110-40100001-2000-10-11x2x3x5x此時已得整數最優解。此時已得整數最優解。2022-4-7451x2x143221 xx5 . 45 . 021xx2123xxz)5 . 2,25. 3() 1, 4(521 xx521 xx021215x約束約束即為即為Page 46分支定界法1）求整數規劃的松弛問題最優解；若松

35、弛問題的最優解滿足整數要求，得到整數規劃的最優解,否則轉下一步；2）分支與定界：任意選一個非整數解的變量xi，在松弛問題中加上約束：xixi 和 xixi+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目標值是分枝問題的下界。3 ) 剪枝 檢查所有分枝的解及目標函數值，若某分枝的解是整數并且目標函數值大于（max）等于其它分枝的目標值，則將其它分枝剪去不再計算，若還存在非整數解并且目標值大于(max)整數解的目標值，需要繼續分枝，再檢查，直到得到最優解。Page 47分支定界法n例 用分枝定界法求解整數規劃問題 且且

36、全全為為整整數數0,4 30 652 5min211212121xxxxxxxxxZ解：首先去掉整數約束，變成一般線性規劃問題解：首先去掉整數約束，變成一般線性規劃問題( (原整數規劃原整數規劃問題的松馳問題問題的松馳問題) ) 0,4 30 652 5min211212121xxxxxxxxxZLPIPPage 48分支定界法n用圖解法求松弛問題的最優解，如圖所示。x1x23(18/11,40/11)21123x118/11, x2 =40/11Z=218/11(19.8)即即Z 也是也是IP最小值的下限。最小值的下限。對于對于x118/111.64，取值取值x1 1， x1 2對于對于x2

37、 =40/11 3.64，取值，取值x2 3 ，x2 4先將（先將（LP）劃分為（）劃分為（LP1）和（和（LP2）,取取x1 1, x1 2Page 49分支定界法n分支： 且且為為整整數數0,1 4 30 652 )1(5min2111212121xxxxxxxxIPxxZ 且且為為整整數數0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ分別求出（分別求出（LP1）和（）和（LP2）的最優解。）的最優解。Page 50分支定界法n先求LP1,如圖所示。此時在B點取得最優解。nx11, x2 =3, Z(1)16n找到整數解，問題已探明，此枝停止計算。x

38、1x233(18/11,40/11)11BAC同理求同理求LP2,如圖所示。在如圖所示。在C 點點取得最優解。即取得最優解。即:x12, x2 =10/3, Z(2)56/318.7 Z(2) Z(1)16 原問題有比原問題有比16更小的最優更小的最優解，但解，但 x2 不是整數，故繼續不是整數，故繼續分支。分支。Page 51分支定界法n在IP2中分別再加入條件： x23, x24 得下式兩支： 且且為為整整數數0,3 2 4 30 652 )21(5min21211212121xxxxxxxxxIPxxZ 且且為為整整數數0,4 2 4 30 652 )22(5min21211212121

39、xxxxxxxxxIPxxZ分別求出分別求出LP21和和LP22的最優解的最優解Page 52分支定界法x1x233(18/11,40/11)11BACD先求先求LP21,如圖所示。此時如圖所示。此時D 在點取得最優解。在點取得最優解。即即 x112/52.4, x2 =3, Z(21)-87/5-17.4 Z(211) 如對如對LP212繼續分解，其最小繼續分解，其最小值也不會低于值也不會低于15.5 ，問題探，問題探明明,剪枝。剪枝。Page 55分支定界法n原整數規劃問題的最優解為: nx1=2, x2 =3, Z* =17n以上的求解過程可以用一個樹形圖表示如右：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.5x11x12x23x24x12x13Page 56分支定界法n例4.5 用分枝定界法求解