第四章整數(shù)規(guī)劃與分配問題(第1講)

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

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

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

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

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

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

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

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

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

10、劃問題的數(shù)學(xué)模型可以表示為：則該規(guī)劃問題的數(shù)學(xué)模型可以表示為：Page 12整數(shù)規(guī)劃的特點及應(yīng)用 )2 , 1(1 , 0)4 , 3 , 2 , 1,(0200200600400150300400350.15001200min244434241134333231242322211413121144342414433323134232221241312111414121iyjixyxxxxyxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsyyxcziijijijij混合整數(shù)規(guī)劃問題混合整數(shù)規(guī)劃問題Page 13整數(shù)規(guī)劃的特點及應(yīng)用例2 現(xiàn)有資金總額為B?？晒┻x擇的投資項目有n個，項

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

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

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

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

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

16、變量在數(shù)學(xué)模型中的應(yīng)用邏輯變量在數(shù)學(xué)模型中的應(yīng)用1、m個約束條件中只有個約束條件中只有k個起作用個起作用設(shè)有設(shè)有m m個約束條件個約束條件mibanjiij,.,2 , 1,1定義定義0-10-1整型變量：整型變量：M M是任意大正數(shù)。是任意大正數(shù)。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是任意大正數(shù)，是任意大正數(shù)，1341421

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36、全全為為整整數(shù)數(shù)0,4 30 652 5min211212121xxxxxxxxxZ解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題( (原整數(shù)規(guī)劃原整數(shù)規(guī)劃問題的松馳問題問題的松馳問題) ) 0,4 30 652 5min211212121xxxxxxxxxZLPIPPage 48分支定界法n用圖解法求松弛問題的最優(yōu)解，如圖所示。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分支： 且且為為整整數(shù)數(shù)0,1 4 30 652 )1(5min2111212121xxxxxxxxIPxxZ 且且為為整整數(shù)數(shù)0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ分別求出（分別求出（LP1）和（）和（LP2）的最優(yōu)解。）的最優(yōu)解。Page 50分支定界法n先求LP1,如圖所示。此時在B點取得最優(yōu)解。nx11, x2 =3, Z(1)16n找到整數(shù)解，問題已探明，此枝停止計算。x

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

39、xxxxxxxxxIPxxZ分別求出分別求出LP21和和LP22的最優(yōu)解的最優(yōu)解Page 52分支定界法x1x233(18/11,40/11)11BACD先求先求LP21,如圖所示。此時如圖所示。此時D 在點取得最優(yōu)解。在點取得最優(yōu)解。即即 x112/52.4, x2 =3, Z(21)-87/5-17.4 Z(211) 如對如對LP212繼續(xù)分解，其最小繼續(xù)分解，其最小值也不會低于值也不會低于15.5 ，問題探，問題探明明,剪枝。剪枝。Page 55分支定界法n原整數(shù)規(guī)劃問題的最優(yōu)解為: 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 用分枝定界法求解