第4章：整數(shù)規(guī)劃

1、第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃(Integer Programming)整數(shù)規(guī)劃的基本問題及其數(shù)學(xué)模型整數(shù)規(guī)劃的基本問題及其數(shù)學(xué)模型割平面法割平面法分支定界法分支定界法0-10-1整數(shù)規(guī)劃整數(shù)規(guī)劃指派問題指派問題WinQSBWinQSB軟件應(yīng)用軟件應(yīng)用第一節(jié)第一節(jié) 整數(shù)規(guī)劃的基本問題整數(shù)規(guī)劃的基本問題及其數(shù)學(xué)模型及其數(shù)學(xué)模型一、問題的提出一、問題的提出 實際工作中的某些規(guī)劃問題要求部分變量或全部變量取整實際工作中的某些規(guī)劃問題要求部分變量或全部變量取整數(shù)值，我們稱這樣的問題為整數(shù)規(guī)劃問題數(shù)值，我們稱這樣的問題為整數(shù)規(guī)劃問題(Integer (Integer ProgrammingProgram

2、ming，IP)IP)。不考慮整數(shù)要求，由其他約束條件和目標不考慮整數(shù)要求，由其他約束條件和目標函數(shù)構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的函數(shù)構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題松弛問題(Slack (Slack Problem)Problem)。若松弛問題是一個線性規(guī)劃問題，我們稱該整數(shù)規(guī)。若松弛問題是一個線性規(guī)劃問題，我們稱該整數(shù)規(guī)劃問題為整數(shù)線性規(guī)劃劃問題為整數(shù)線性規(guī)劃(Integer Linear ProgrammingILP)(Integer Linear ProgrammingILP)。 【例【例5-15-1】某工地需要長度不同、直徑相同的成套鋼筋，每】某工地需要長度不同、直徑相

3、同的成套鋼筋，每套鋼筋由兩根套鋼筋由兩根7 7米長和七根米長和七根2 2米長的鋼筋組成。現(xiàn)有長米長的鋼筋組成?，F(xiàn)有長1515米的圓米的圓鋼毛坯鋼毛坯150150根，應(yīng)如何下料，使廢料最少？根，應(yīng)如何下料，使廢料最少？ 解：解：本題中沒有說明本題中沒有說明1515米長的圓鋼毛坯有哪些下料方式，米長的圓鋼毛坯有哪些下料方式，故需要首先找出下料方式。將故需要首先找出下料方式。將1515米長的圓鋼毛坯切割為米長的圓鋼毛坯切割為7 7米和米和2 2米兩種長度的鋼筋有三種方式，如表米兩種長度的鋼筋有三種方式，如表5-15-1所示。所示。 表表5-15-1170304121021廢料(米)2米長的鋼筋(根)

4、7米長的鋼筋(根)下料方式321xxx、 設(shè)設(shè) 分別表示采用第分別表示采用第1 1、2 2、3 3種下料方式所切割的種下料方式所切割的圓鋼毛坯數(shù)目。則廢料可表示為下列形式：圓鋼毛坯數(shù)目。則廢料可表示為下列形式： 31xxz 看約束條件。首先，工地需要的是成套鋼筋，故看約束條件。首先，工地需要的是成套鋼筋，故7 7米長和米長和2 2米米長的鋼筋數(shù)之比應(yīng)滿足長的鋼筋數(shù)之比應(yīng)滿足2 2：7 7，用線性方程來表示，即：，用線性方程來表示，即： 774223221xxxx整理得：整理得： 01414321xxx另外，圓鋼毛坯總數(shù)為另外，圓鋼毛坯總數(shù)為150150根，故根，故 還應(yīng)滿足下面這個還應(yīng)滿足下面

5、這個條件，即：條件，即： 321xxx、150321xxx綜合分析，問題的數(shù)學(xué)模型為：綜合分析，問題的數(shù)學(xué)模型為： 31minxxz且均取整數(shù)值0,15001414321321321xxxxxxxxx 【例【例5-25-2】現(xiàn)有資金總額為】現(xiàn)有資金總額為B B，可供投資項目有，可供投資項目有n n個，項目個，項目j j所需所需投資額和預(yù)期收益分別為投資額和預(yù)期收益分別為a aj j和和c cj j(j(j1,21,2，n)n)。同時，由于。同時，由于種種原因，有三個附加條件：第一，若選擇項目種種原因，有三個附加條件：第一，若選擇項目1 1，就必須同時，就必須同時選擇項目選擇項目2 2，反之則不

6、一定；第二，項目，反之則不一定；第二，項目3 3和項目和項目4 4中至少選擇一中至少選擇一個；第三，項目個；第三，項目5 5、項目、項目6 6和項目和項目7 7中恰好選擇兩個。應(yīng)當怎樣選中恰好選擇兩個。應(yīng)當怎樣選擇投資項目，才能使總預(yù)期收益最大？擇投資項目，才能使總預(yù)期收益最大？ 解：解：每一個投資項目都有被選擇和不被選擇兩種可能，為此每一個投資項目都有被選擇和不被選擇兩種可能，為此令：令： ），（不投資對項目投資對項目njjjxj2101n,1,2,j10210max765432111或jjnjjnjjjxxxxxxxxBxaxcz則問題可表示為：則問題可表示為： 【例【例5-35-3】工廠

7、】工廠A A1 1和和A A2 2生產(chǎn)某種物資，由于該種物資供不應(yīng)生產(chǎn)某種物資，由于該種物資供不應(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(j=1,2,3,4)(j=1,2,3,4)見表見表5-25-2。 表表5-25-2150300400350需求量(千噸/年)2005254A42

8、002167A36007538A24004392A1生產(chǎn)能力(千噸/年)B4B3B2B1 cij BjAi 工廠工廠A A3 3或或A A4 4開工后，每年的生產(chǎn)費用估計分別為開工后，每年的生產(chǎn)費用估計分別為12001200萬元或萬元或15001500萬元?，F(xiàn)要決定應(yīng)該建設(shè)工廠萬元。現(xiàn)要決定應(yīng)該建設(shè)工廠A A3 3還是還是A A4 4，才能使今后每年，才能使今后每年的總費用的總費用( (即全部物資運費和新工廠生產(chǎn)費用之和即全部物資運費和新工廠生產(chǎn)費用之和) )最少。最少。 解：解：這是一個物資運輸問題，其特點是事先不能確定應(yīng)該建這是一個物資運輸問題，其特點是事先不能確定應(yīng)該建A A3 3和和A

9、 A4 4中的哪一個，因而不知道新廠投產(chǎn)后的實際生產(chǎn)費用。中的哪一個，因而不知道新廠投產(chǎn)后的實際生產(chǎn)費用。為此，引入為此，引入0-10-1變量：變量： 4301AAy若建工廠若建工廠 設(shè)設(shè)x xijij為由為由A Ai i運往運往B Bj j的物資數(shù)量的物資數(shù)量( (千噸千噸) )，( (i i，j j1,2,3,4)1,2,3,4)。則問題的數(shù)學(xué)模型為：則問題的數(shù)學(xué)模型為： 115001200min4141yyxczijijij35041312111xxxx40042322212xxxx30043332313xxxxxx40014131211xxxx60024232

10、221xxxxyxxxx20034333231yxxxx120044434241)4 , 3 , 2 , 1,(0jixij10或y二、整數(shù)規(guī)劃模型的一般形式及解的特點二、整數(shù)規(guī)劃模型的一般形式及解的特點 整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式為：整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式為： njjjxcz1min)(max 或部分或全部取整數(shù)、njijnjijxxxnjxmibxa,), 2 , 1(0), 2 , 1()(211一般來說，整數(shù)線性規(guī)劃可分為以下幾種類型：一般來說，整數(shù)線性規(guī)劃可分為以下幾種類型： 1. 1. 純整數(shù)線性規(guī)劃純整數(shù)線性規(guī)劃(Pure Integer Linear Program

11、ming)(Pure Integer Linear Programming)：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃，也稱為全整指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃，也稱為全整數(shù)規(guī)劃。數(shù)規(guī)劃。 2. 2. 混合整數(shù)線性規(guī)劃混合整數(shù)線性規(guī)劃(Mixed Integer Linear (Mixed Integer Linear Programming)Programming)：指決策變量中一部分必須取整數(shù)值，而另一部：指決策變量中一部分必須取整數(shù)值，而另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。分可以不取整數(shù)值的整數(shù)線性規(guī)劃。 3. 0-1 3. 0-1整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃(Zero-on

12、e Integer Linear (Zero-one Integer Linear Programming)Programming)：指決策變量只能?。褐笡Q策變量只能取0 0或或1 1兩個值的整數(shù)線性規(guī)劃。兩個值的整數(shù)線性規(guī)劃。 （三）整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系（三）整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系 從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實際上兩者滿足整數(shù)要求的解即可。但實際上兩者卻有很大的不同，通過舍入得到的解卻有很大的不

13、同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時甚（整數(shù)）也不一定就是最優(yōu)解，有時甚至不能保證所得倒的解是整數(shù)可行解。至不能保證所得倒的解是整數(shù)可行解。舉例說明。舉例說明。例：設(shè)整數(shù)規(guī)劃問題如下例：設(shè)整數(shù)規(guī)劃問題如下 且為整數(shù)0,13651914max21212121xxxxxxxxZ 首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。為松弛問題）。0,13651914max21212121xxxxxxxxZ用用 解法求出最優(yōu)解解法求出最優(yōu)解x13/2, x2 = 10/3且有且有Z = 29/6x1x233(3/2,10/3) 現(xiàn)求整數(shù)

14、解（最優(yōu)解）：現(xiàn)求整數(shù)解（最優(yōu)解）：如用如用“舍入取整法舍入取整法”可可得到得到4個點即個點即(1，3) (2，3)(1，4)(2，4)。顯然，。顯然，它們都不可能是整數(shù)規(guī)它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。劃的最優(yōu)解。 按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如圖所示。是一個有限集，如圖所示。圖圖 因此，可將集合內(nèi)的整數(shù)點一一找出，其最因此，可將集合內(nèi)的整數(shù)點一一找出，其最大目標函數(shù)的值為最優(yōu)解，此法為完全枚舉法。大目標函數(shù)的值為最優(yōu)解，此

15、法為完全枚舉法。 如上例：其中如上例：其中（2，2）（）（3，1）點為最點為最大值，大值，Z=4。. .若若( ( LPLP ) )沒有可行解，則沒有可行解，則( ( ILPILP ) )也沒有可行解，停止計算。也沒有可行解，停止計算。. .若若( ( LPLP ) )有最優(yōu)解，并符合有最優(yōu)解，并符合( ( ILPILP ) )的整數(shù)條件，則的整數(shù)條件，則( ( LPLP ) )的最優(yōu)解即為的最優(yōu)解即為( ( IPIP ) )的最優(yōu)解，停止計算。的最優(yōu)解，停止計算。. .若若( ( LPLP ) )有最優(yōu)解，但不符合有最優(yōu)解，但不符合( ( ILPILP ) )的整數(shù)條件，可用相的整數(shù)條件，可

16、用相應(yīng)方法求解。應(yīng)方法求解。 整數(shù)規(guī)劃與其松馳問題解的關(guān)系：整數(shù)規(guī)劃與其松馳問題解的關(guān)系： 目前，常用的求解整數(shù)規(guī)劃的方法有：目前，常用的求解整數(shù)規(guī)劃的方法有： 分支定界法和割平面法；分支定界法和割平面法； 對于特別的對于特別的0 01 1規(guī)劃問題采用隱枚舉法和匈規(guī)劃問題采用隱枚舉法和匈牙利法。牙利法。第二節(jié)第二節(jié) 割平面法割平面法 割平面法由高莫瑞割平面法由高莫瑞(Gomory)(Gomory)于于19581958年提出。其年提出。其基本思想基本思想是是放寬變量的整數(shù)約束，首先求對應(yīng)的松弛問題最優(yōu)解，當某個放寬變量的整數(shù)約束，首先求對應(yīng)的松弛問題最優(yōu)解，當某個變量變量x xi i不滿足整數(shù)約

17、束時，尋找一個約束方程并添加到松弛問不滿足整數(shù)約束時，尋找一個約束方程并添加到松弛問題中，其作用是割掉非整數(shù)部分，縮小原松弛問題的可行域，題中，其作用是割掉非整數(shù)部分，縮小原松弛問題的可行域，最后逼近整數(shù)問題的最優(yōu)解。最后逼近整數(shù)問題的最優(yōu)解。一、割平面法的基本思想一、割平面法的基本思想 考慮松弛問題為標準形線性規(guī)劃問題的純整數(shù)規(guī)劃問題考慮松弛問題為標準形線性規(guī)劃問題的純整數(shù)規(guī)劃問題(ILP)(ILP)： njjjxcz1max), 2 , 1(0), 2 , 1(1njxmibxajijnjij且均為整數(shù) 假設(shè)約束條件中假設(shè)約束條件中a aijij( (i i1,2,1,2,m m ；j j

18、1,21,2，,n n) )和和b bi i( (i i1,2,1,2,m m) )均為整數(shù)均為整數(shù)( (若不為整數(shù)，可令等式兩邊同乘一個倍數(shù)若不為整數(shù)，可令等式兩邊同乘一個倍數(shù)化為整數(shù)化為整數(shù)) )。 下面先通過一個例子來說明割平面法的基本思想。下面先通過一個例子來說明割平面法的基本思想。 【例【例5-55-5】 21maxxxz102321 xx522x均取整數(shù)0,21xx將該問題圖示如下圖將該問題圖示如下圖 ： 從圖從圖(a)(a)中可以看出，松弛問中可以看出，松弛問題的最優(yōu)解為題的最優(yōu)解為X X* *=(5/3=(5/3，5/2)5/2)T T，它，它不是一個整數(shù)解。因此我們設(shè)法不是一

19、個整數(shù)解。因此我們設(shè)法給原線性規(guī)劃問題增加一個約束給原線性規(guī)劃問題增加一個約束條件，從而把包括條件，從而把包括X X* *在內(nèi)的一部分在內(nèi)的一部分不含整數(shù)點的可行域從原可行域不含整數(shù)點的可行域從原可行域中分割出去。再求增加了這個約中分割出去。再求增加了這個約束條件后的新的線性規(guī)劃問題的束條件后的新的線性規(guī)劃問題的最優(yōu)解。最優(yōu)解。 從圖從圖5-1(b)5-1(b)中可以看出，當我們增加了約束條件中可以看出，當我們增加了約束條件“6221 xx”后，得到新的最優(yōu)解后，得到新的最優(yōu)解X X* *= (2= (2，2)2)T T，它便是整數(shù)規(guī)劃問題最優(yōu)，它便是整數(shù)規(guī)劃問題最優(yōu)解。因此，割平面法的關(guān)鍵就

20、在于如何尋找這類新的約束條件。解。因此，割平面法的關(guān)鍵就在于如何尋找這類新的約束條件。 二、二、GomoryGomory約束約束 假設(shè)用單純形法求得的線性規(guī)劃問題最優(yōu)解不是整數(shù)解，其假設(shè)用單純形法求得的線性規(guī)劃問題最優(yōu)解不是整數(shù)解，其中必然有某個或某幾個基變量不為整數(shù)。記中必然有某個或某幾個基變量不為整數(shù)。記B B為松弛問題的最優(yōu)為松弛問題的最優(yōu)基，則問題的基最優(yōu)解為：基，則問題的基最優(yōu)解為： 01NBXbbBX，不妨設(shè)第不妨設(shè)第r r個分量個分量 不為整數(shù)，根據(jù)最優(yōu)單純形表可得：不為整數(shù)，根據(jù)最優(yōu)單純形表可得： rbrjNjrjBrbxax(5.1)rja10iiifbN的整數(shù)部分，為10r

21、jrjrjfaN的整數(shù)部分，為代入上式得：代入上式得：rjrjrjfNa(5.2)(5.3)NjjrjNjrrjrjBrxffNxNx(5.4)移項，得：移項，得：jNjrjrrjNjrjBrxffNxNx(5.5)將將 和和 分成整數(shù)部分和非負真分數(shù)之和，即：分成整數(shù)部分和非負真分數(shù)之和，即：rbrrrfNb 因為變量必須取整數(shù)，即上式左邊必須是整數(shù)，從上式右邊因為變量必須取整數(shù)，即上式左邊必須是整數(shù)，從上式右邊看，因為看，因為0f0fi i11，所以不能為正，即：，所以不能為正，即： 割平面方程割平面方程0jNjrjrxff(5.6)即即: : rjNjrjfxf(5.7)割平面的兩個性質(zhì)

22、：割平面的兩個性質(zhì)： (1) (1)割平面割平面(5.7)(5.7)式割去了式割去了(ILP)(ILP)的松弛問題的松弛問題(LP)(LP)的基最優(yōu)解。的基最優(yōu)解。 (2)(2)割平面割平面(5.7)(5.7)式未割去原問題式未割去原問題(ILP)(ILP)的任一的任一( (整數(shù)整數(shù)) )可行解?？尚薪狻?三、割平面法的算法步驟三、割平面法的算法步驟 步驟步驟1 1：將約束條件系數(shù)及右端項化為整數(shù)，用單純形法求將約束條件系數(shù)及右端項化為整數(shù)，用單純形法求解整數(shù)規(guī)劃問題解整數(shù)規(guī)劃問題(ILP)(ILP)的松弛問題的松弛問題(LP)(LP)。設(shè)得到最優(yōu)基。設(shè)得到最優(yōu)基B B，相應(yīng)，相應(yīng)的基最優(yōu)解為

23、的基最優(yōu)解為X X* *。 步驟步驟2 2：判別判別X X* *的所有分量是否全為整數(shù)？如是，則的所有分量是否全為整數(shù)？如是，則X X* *即為即為(ILP)(ILP)的最優(yōu)解，算法終止；若否，則取的最優(yōu)解，算法終止；若否，則取X X* *中分數(shù)最大的分中分數(shù)最大的分量量 ，引入割平面，引入割平面(5.7)(5.7)。 *Brx 步驟步驟3 3：將式將式(5.7)(5.7)引入松弛變量后加入原最終單純形表，用對引入松弛變量后加入原最終單純形表，用對偶單純形法繼續(xù)求解。轉(zhuǎn)步驟偶單純形法繼續(xù)求解。轉(zhuǎn)步驟2 2?！纠纠?-65-6】用割平面法求解例】用割平面法求解例5-55-5。 首先，將整數(shù)約束

24、去掉，將松弛問題化為標準形，并用單首先，將整數(shù)約束去掉，將松弛問題化為標準形，并用單純形法求解，結(jié)果見下表純形法求解，結(jié)果見下表: : 21maxxxz102321 xx522x均取整數(shù)0,21xx-1/6-1/300j-1/31/21/3001105/35/2x1x211x4x3x2x1bxBcB0011cj 因基變量因基變量x x1 15/35/3，x x2 25/25/2，均為非整數(shù)，故該最優(yōu)解不是整數(shù)規(guī)劃的，均為非整數(shù)，故該最優(yōu)解不是整數(shù)規(guī)劃的可行解。若以變量可行解。若以變量x x1 1所在的行為源行，得到相應(yīng)的割平面為：所在的行為源行，得到相應(yīng)的割平面為： 32323143xx(5.

25、8)對式對式(5.8)(5.8)左端加入松弛變量，得到：左端加入松弛變量，得到： 323231543xxx(5.9)將式將式(5.9)(5.9)加入上表中，用對偶單純形法繼續(xù)求解如下表：加入上表中，用對偶單純形法繼續(xù)求解如下表： 因基變量因基變量x x1 15/35/3，x x2 25/25/2，均為非整數(shù)，故該最優(yōu)解不是，均為非整數(shù)，故該最優(yōu)解不是整數(shù)規(guī)劃的可行解。若以分數(shù)部分最大的變量整數(shù)規(guī)劃的可行解。若以分數(shù)部分最大的變量x x1 1所在的行為源所在的行為源行，得到相應(yīng)的割平面為：行，得到相應(yīng)的割平面為： -1/40-1/400j-1/23/4-3/20011/2-1/41/201010

26、0221x1x2x41100-1/6-1/300j001-1/31/21/30-1/30101005/35/2-2/3x1x2x5110 x5x4x3x2x1bxBcB00011cj-2/3 由上表可知，增加約束條件后的線性規(guī)劃問題最優(yōu)解為由上表可知，增加約束條件后的線性規(guī)劃問題最優(yōu)解為X X* *=(2=(2，2 2，0 0，1 1，0)0)T T，因此，原整數(shù)規(guī)劃問題的最優(yōu)解為，因此，原整數(shù)規(guī)劃問題的最優(yōu)解為X X* *=(2=(2，2)2)T T，其最優(yōu)值，其最優(yōu)值z z* *=4=4。 43xx 、21xx、 如果將式如果將式(5.8)(5.8)中的變量中的變量 用原問題的決策變量用原

27、問題的決策變量 來表示，就得到：來表示，就得到： 322532231031221）（）（xxx整理后得到：整理后得到： 6221 xx例：用割平面法求解數(shù)規(guī)劃問題例：用割平面法求解數(shù)規(guī)劃問題 且且為為整整數(shù)數(shù)0, 205462max21212121xxxxxxxxZCj1100CBXBbx1x2x3x40 x3621100 x42045011100CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3001/61/6初初始始表表最最終終表表在松弛問題最優(yōu)解中，在松弛問題最優(yōu)解中，x1, x2 均為非整數(shù)解，由上表有：均為非整數(shù)解，由上表有：383132356165

28、432431 xxxxxx將系數(shù)和常數(shù)都分解成整數(shù)和非負真分數(shù)之和將系數(shù)和常數(shù)都分解成整數(shù)和非負真分數(shù)之和: : 32231)311(321)651(65432431 xxxxxx 以上式子只須考慮一個即可，解題經(jīng)驗表明，考慮式子右端以上式子只須考慮一個即可，解題經(jīng)驗表明，考慮式子右端最大真分數(shù)的式子，往往會較快地找到所需割平面約束條件。最大真分數(shù)的式子，往往會較快地找到所需割平面約束條件。以上兩個式子右端真分數(shù)相等，可任選一個考慮?，F(xiàn)選第二個以上兩個式子右端真分數(shù)相等，可任選一個考慮?，F(xiàn)選第二個式子，并將真分數(shù)移到右邊得：式子，并將真分數(shù)移到右邊得： )(313224332xxxx 32)(

29、3143 xx引入松弛變量引入松弛變量s1 后得到下式，將此約束條件加到上表中，繼續(xù)后得到下式，將此約束條件加到上表中，繼續(xù)求解。求解。 323131143 sxxCj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31001/61/60Cj11000CBXBbx1x2x3x4s11 x10100101x24010120 x320011300001/2 得到整數(shù)最優(yōu)解，即為整數(shù)規(guī)劃的最優(yōu)解，而且此整數(shù)規(guī)劃得到整數(shù)最優(yōu)解，即為整數(shù)規(guī)劃的最優(yōu)解，而且此整數(shù)規(guī)劃有兩個最優(yōu)解：有兩個最優(yōu)解： X= (0, 4), z =

30、4, 或 X= (2, 2), z = 4。 且且為為整整數(shù)數(shù)練練習(xí)習(xí)：0,421625421411max2121212121xxxxxxxxxxZCBXBbx1x2x3x4x50 x34001-1/34/34x24/30102/9-5/911x18/31001/92/9Z000-19/9-2/9CBXBbx1x2x3x4x5s10 x30001-1064x230101/20-5/211x121000010 x530001/21-9/2Z000-20-1（2 ，3）第三節(jié)第三節(jié) 分枝定界法分枝定界法 分枝定界法是在分枝定界法是在2020世紀世紀6060年代初由年代初由Land DoingLan

31、d Doing和和DakinDakin等人等人提出的適合于解純整數(shù)或混合正數(shù)規(guī)劃問題。提出的適合于解純整數(shù)或混合正數(shù)規(guī)劃問題。 通過分枝枚舉來尋找最優(yōu)解。首先不考慮對變量的整數(shù)要通過分枝枚舉來尋找最優(yōu)解。首先不考慮對變量的整數(shù)要求，求解相應(yīng)的線性規(guī)劃模型，如求得最優(yōu)解不符合整數(shù)要求，求解相應(yīng)的線性規(guī)劃模型，如求得最優(yōu)解不符合整數(shù)要求，則把原模型分解為兩部分，每一部分都增加新的約束條求，則把原模型分解為兩部分，每一部分都增加新的約束條件以減少相應(yīng)線性規(guī)劃模型的可行域。通過不斷分解，逐步件以減少相應(yīng)線性規(guī)劃模型的可行域。通過不斷分解，逐步逼近滿足要求的整數(shù)最優(yōu)解，在這個過程中包括了逼近滿足要求的整

32、數(shù)最優(yōu)解，在這個過程中包括了“分枝分枝”和和“定界定界”兩個關(guān)鍵步驟。兩個關(guān)鍵步驟。一、分支定界法的基本思想一、分支定界法的基本思想 n基本思想：基本思想：q先求出整數(shù)規(guī)劃相應(yīng)的線性規(guī)劃(即不考慮整數(shù)限制)的最優(yōu)解，q若求得的最優(yōu)解符合整數(shù)要求，則這個解就是原整數(shù)規(guī)劃的最優(yōu)解；q若不滿足整數(shù)條件，則任選一個不滿足整數(shù)條件的變量來構(gòu)造新的約束，在原可行域中剔除部分非整數(shù)解。q然后，再在縮小的可行域中求解新構(gòu)造的線性規(guī)劃的最優(yōu)解，這樣通過求解一系列線性規(guī)劃問題，最終得到原整數(shù)規(guī)劃的最優(yōu)解。n定界的含義：定界的含義：q整數(shù)規(guī)劃是在相應(yīng)的線性規(guī)劃的基礎(chǔ)上增加變量為整數(shù)的約束條件，整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)

33、于相應(yīng)線性規(guī)劃的最優(yōu)解。q對極大化問題來說，相應(yīng)線性規(guī)劃的目標函數(shù)最優(yōu)值是原整數(shù)規(guī)劃函數(shù)值的上界；q對極小化問題來說，相應(yīng)線性規(guī)劃的目標函數(shù)的最優(yōu)值是原整數(shù)規(guī)劃目標函數(shù)值的下界。下面我們用一例說明求解步驟例例 maxZ= 6x1 +5 x2 2x1 + x2 9 5x1 +7 x2 35 x1, x2 0 x1, x2取整數(shù)取整數(shù)n第一步，不考慮變量的整數(shù)約束，求相應(yīng)的LP(問題1)的最優(yōu)解： x1=28/9，x2 =25/9，Z1=293/9n第二步，定界過程q這個解不是原整數(shù)規(guī)劃的最優(yōu)解，這時目標函值Z1=293/9是原整數(shù)規(guī)劃目標函數(shù)的上界；因為x1=x2=0是整數(shù)規(guī)劃問題的可行解，所以

34、下界為0。界限一（0 0，293/9293/9）n第三步，分枝過程 將不滿足整數(shù)約束的變量x1進行分枝，x1稱為分枝變量，構(gòu)造兩個新的約束條件 x1 28/9=3，x1 28/9 +1=4 并將新約束添加到原問題當中去：問題問題2：maxZ= 6x1 +5 x2 問題問題3： maxZ= 6x1 +5 x2 2x1 + x2 9 2x1 + x2 9 5x1 +7 x2 35 5x1 +7 x2 35 x13 x1 4 x1, x2 0 x1, x2 0 x1, x2取整數(shù)取整數(shù) x1, x2取整數(shù)取整數(shù)這樣就把相應(yīng)的線性規(guī)劃的可行域分成兩個部分，如下圖所示。5x1 +7 x2 =352x1

35、+ x2 =9x1x2123125344求解問題求解問題2相應(yīng)的線性規(guī)劃的最優(yōu)解：相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=3，x2 =20/7，Z2=226/733.2 求解問題求解問題3相應(yīng)的線性規(guī)劃的最優(yōu)解：相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=4，x2 =1，Z3=29n第四步，定界過程qLP3的解滿足整數(shù)約束，不必再分枝，它的目標函數(shù)值是29，大于原有下界0，則新的下界為29；q現(xiàn)有上界為未分枝子問題未分枝子問題中目標函數(shù)最大值，即為226/733.2。界限二（29，226/7）qLP2的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值226/7大于現(xiàn)有下界，則應(yīng)繼續(xù)分枝。n第五步，分枝過程 將不滿足整數(shù)約束的

36、變量x2進行分枝，構(gòu)造兩個新的約束條件： x2 20/7=2，x2 20/7 +1=3 問題問題4：maxZ= 6x1 +5 x2 問題問題5： maxZ= 6x1 +5 x2 2x1 + x2 9 2x1 + x2 9 5x1 +7 x2 35 5x1 +7 x2 35 x13 x1 3 x22 x2 3 x1, x2 0 x1, x2 0 x1, x2取整數(shù)取整數(shù) x1, x2取整數(shù)取整數(shù)x2 =2 x2=35x1 +7 x2 =352x1 + x2 =9x1x2123125344x1=4x1=3求解問題4相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=3，x2 =2，Z4=28 求解問題5相應(yīng)的線性規(guī)劃的

37、最優(yōu)解：x1=14/5，x2 =3，Z5=159/531.8n第六步，定界過程qLP4的解滿足整數(shù)約束，不必再分枝，它的目標函數(shù)值是28，小于原有下界29，則下界仍為29；q現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為159/5。 界限三（29，159/5）qLP5的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值159/5大于現(xiàn)有下界29，則應(yīng)繼續(xù)分枝。n第七步，分枝過程 將不滿足整數(shù)約束的變量x1進行分枝，構(gòu)造兩個新的約束條件： x1 14/5=2，x1 14/5 +1=3 問題問題6：maxZ= 6x1 +5 x2 問題問題7： maxZ= 6x1 +5 x2 2x1 + x2 9 2x1 +

38、x2 9 5x1 +7 x2 35 5x1 +7 x2 35 x13 x1 3 x2 3 x2 3 x12 x1 3 x1, x2 0 x1, x2 0 x1, x2取整數(shù)取整數(shù) x1, x2取整數(shù)取整數(shù)x2 =2 x2=35x1 +7 x2 =352x1 + x2 =9x1x2123125344x1=4x1=3x1=2求解問題6相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=2，x2 =25/7，Z6=209/729.8 求解問題7相應(yīng)的線性規(guī)劃的最優(yōu)解：問題7的可行域是一個空集，所以無最優(yōu)解。n第八步，定界過程第八步，定界過程qLP7的無最優(yōu)解，不必再分枝，下界仍為29；q現(xiàn)有上界為未分枝子問題中目標函數(shù)最

39、大值，即為209/7。界限四（29，29.8）qLP6的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值209/7大于現(xiàn)有下界29，則應(yīng)繼續(xù)分枝。n第九步，分枝過程 將不滿足整數(shù)約束的變量x2進行分枝，構(gòu)造兩個新的約束條件： x2 3，x2 4 問題問題8：maxZ= 6x1 +5 x2 問題問題9： maxZ= 6x1 +5 x2 2x1 + x2 9 2x1 + x2 9 5x1 +7 x2 35 5x1 +7 x2 35 x13 x1 3 x2 3 x2 3 x12 x12 x23 x2 4 x1, x2 0 x1, x2 0 x1, x2取整數(shù)取整數(shù) x1, x2取整數(shù)取整數(shù)x2=35x1 +

40、7 x2 =352x1 + x2 =9x1x2123125344x1=4x1=3x1=2x2 =2 x2 =4求解問題8相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=2，x2 =3，Z8=27 求解問題9相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=7/5，x2 =4，Z9=142/528.4n第十步，定界過程qLP8的最優(yōu)解，滿足整數(shù)約束，不必再分枝，下界仍為29；q現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為142/5。界限五（29， 142/5 ）q雖然LP9的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值142/5小于現(xiàn)有下界29，則不再繼續(xù)分枝。q上界=下界，得整數(shù)規(guī)劃問題的最優(yōu)解為下界下界： x1=4，x2 =1，Z=

41、29分枝定界過程分枝定界過程7232,762, 3 221Zxx：問題9532,972,913 121Zxx：問題29, 1,4 321Zxx：問題28,2,3421Zxx：問題5431,3,542521Zxx：問題7629,743,2621Zxx：問題無可行解：問題727,3,2821Zxx：問題5228,4,521921Zxx：問題x13x1 4x22x2 3x12x1 3x23x2 409532下界：上界：297232下界：上界：295431下界：上界：297629下界：上界：2929下界：上界：1.先求解先求解ILPILP總是所對應(yīng)的松馳問題。總是所對應(yīng)的松馳問題。若問題若問題(LP)

42、(LP)不可行，則不可行，則(ILP)(ILP)也不可行，算法終止；若問也不可行，算法終止；若問題題(LP)(LP)的最優(yōu)解的最優(yōu)解X X* *為為(ILP)(ILP)的可行解，則它就是的可行解，則它就是(ILP)(ILP)的最優(yōu)解，算法終止。若問題的最優(yōu)解，算法終止。若問題(LP)(LP)的最優(yōu)解存在，但的最優(yōu)解存在，但不滿足不滿足(ILP)(ILP)的整數(shù)要求，轉(zhuǎn)步驟的整數(shù)要求，轉(zhuǎn)步驟2 2。2 2、對當前問題進行分枝和定界：、對當前問題進行分枝和定界： 分技：分技：不妨設(shè)當前問題為不妨設(shè)當前問題為(A)(A)，其松弛問題，其松弛問題(B)(B)的最優(yōu)解不符合整的最優(yōu)解不符合整數(shù)約束，任取

43、非整數(shù)的分量數(shù)約束，任取非整數(shù)的分量 x xr r 。構(gòu)造兩個附加約束：。構(gòu)造兩個附加約束： x xr r x xr r 和和 x xr r x xr r+1 +1 ，對，對(A)(A)分別加入這兩個約束，可得到兩個子問分別加入這兩個約束，可得到兩個子問題題(A(A1 1) )和和(A(A2 2) )，顯然這兩個子問題的可行解集的并是，顯然這兩個子問題的可行解集的并是(A)(A)的可行解的可行解集；集； 定界：定界：根據(jù)前面分析，對每個當前問題根據(jù)前面分析，對每個當前問題(A)(A)可以通過求解松弛問可以通過求解松弛問題題(B)(B)，以及找，以及找(A)(A)的可行解得到當前問題的上、下界的

44、可行解得到當前問題的上、下界 zz和和 z z 。 3 3、比較與剪枝：、比較與剪枝： 對當前子問題進行考察，若不需再進行計算，對當前子問題進行考察，若不需再進行計算，則稱之為剪枝。一般遇到下列情況就需剪枝：則稱之為剪枝。一般遇到下列情況就需剪枝： (B)(B)無可行解；無可行解； (B)(B)的最優(yōu)解符合整數(shù)約束；的最優(yōu)解符合整數(shù)約束； (B)(B)的最優(yōu)值的最優(yōu)值 z z z z 。 通過比較，若子問題不剪枝則返回通過比較，若子問題不剪枝則返回 2 2 。 分枝定界法當所有子問題都剪枝了，即沒有需要處理的子問題時，達到當前上界 z 的可行解即原問題的最優(yōu)解， 算法結(jié)束。 分枝定界法是求整數(shù)

45、規(guī)劃的一種常用的有效分枝定界法是求整數(shù)規(guī)劃的一種常用的有效的方法，既能解決純整數(shù)規(guī)劃的問題，也能解決的方法，既能解決純整數(shù)規(guī)劃的問題，也能解決混合整數(shù)規(guī)劃的問題?；旌险麛?shù)規(guī)劃的問題。例例 2 2n求解求解A A max z=40 x max z=40 x1 1+90 x+90 x2 2 9x 9x1 1+7x+7x2 256 56 7x 7x1 1+20 x+20 x2 270 70 x x1 1，x x2 20 0 x x1 1，x x2 2整數(shù)整數(shù) n解為：解為：X14，X22，Z=340解解 先不考慮條件先不考慮條件，即解相應(yīng)的線性規(guī)劃，即解相應(yīng)的線性規(guī)劃B,B,( (見見圖圖) )，得

46、最優(yōu)解，得最優(yōu)解x x1 1=4.81=4.81，x x2 2=1.82=1.82，z z0 0=356 =356 可見它不符合整數(shù)條件可見它不符合整數(shù)條件。這時這時z z0 0是問題是問題A A的最優(yōu)目標函數(shù)值的最優(yōu)目標函數(shù)值z z* *的上界，記作的上界，記作z z0 0= = 。而在。而在x x1 1=0=0，x x2 2=0=0時，顯然是問題時，顯然是問題A A的一個整數(shù)的一個整數(shù)可行解，這時可行解，這時z=0z=0，是，是z z* *的一個下的一個下界，記作界，記作 =0=0，即，即0z0z* *356356。zzzz分支定界法的解法分支定界法的解法n首先注意其中一個非整數(shù)變量的解，

47、如首先注意其中一個非整數(shù)變量的解，如x x1 1，在問題，在問題B B的解的解中中x x1 1=4.81=4.81。于是對原問題增加兩個約束條件。于是對原問題增加兩個約束條件 x x1 144，x x1 155n可將原問題分解為兩個子問題可將原問題分解為兩個子問題B B1 1和和B B2 2( (即兩支即兩支) )，給每支增，給每支增加一個約束條件，如圖加一個約束條件，如圖5-35-3所示。這并不影響問題所示。這并不影響問題A A的可行的可行域，不考慮整數(shù)條件解問題域，不考慮整數(shù)條件解問題B B1 1和和B B2 2，稱此為第一次迭代。，稱此為第一次迭代。得到最優(yōu)解為：得到最優(yōu)解為： 圖圖5-

48、3n x14，x15n顯然沒有得到全部變量是整數(shù)的解。因顯然沒有得到全部變量是整數(shù)的解。因z z1 1z z2 2，故將故將 改為改為349349，那么必存在最優(yōu)整數(shù)解，得，那么必存在最優(yōu)整數(shù)解，得到到z z* *，并且，并且0z0z* *349349z繼續(xù)對問題繼續(xù)對問題B B1 1和和B B2 2進行分解進行分解n因因z z1 1z z2 2，故先分解，故先分解B B1 1為兩支。增加條件為兩支。增加條件x x2 222者，者，稱為問題稱為問題B B3 3；增加條件；增加條件x x2 233者稱為問題者稱為問題B B4 4。在。在圖圖5-35-3中再舍去中再舍去x x2 22 2與與x x

49、3 33 3之間的可行域，之間的可行域，n再進行第二次迭代。再進行第二次迭代。繼續(xù)對問題繼續(xù)對問題B B2 2進行分解進行分解 解題的解題的過程都過程都列在圖列在圖5-45-4中中。 圖圖5-4割平面法與分枝定界法的比較 這兩種方法的共同特點：通過增加附加約束，這兩種方法的共同特點：通過增加附加約束，使使 整數(shù)最優(yōu)解最終成為線性規(guī)劃的一個頂整數(shù)最優(yōu)解最終成為線性規(guī)劃的一個頂點，于是整點，于是整 個問題就可使用單純形法找到個問題就可使用單純形法找到這個整數(shù)最優(yōu)解；它這個整數(shù)最優(yōu)解；它 們的相異之處是附加們的相異之處是附加約束條件的選取原則及方法不同。約束條件的選取原則及方法不同。第四節(jié)第四節(jié) 0

50、 01 1整數(shù)規(guī)劃整數(shù)規(guī)劃一、一、0-10-1變量的應(yīng)用變量的應(yīng)用 第一節(jié)中我們討論過第一節(jié)中我們討論過0-10-1變量，即只能取變量，即只能取0 0或或1 1的變量，它是的變量，它是邏輯變量，通常用來表示在是與否之間二選一的問題，如某個邏輯變量，通常用來表示在是與否之間二選一的問題，如某個方案方案A A是否被選中，可用下面的是否被選中，可用下面的0-10-1變量來表示：變量來表示： 01x當采取方案A時 當不采取方案A 時【例【例5-85-8】含有相互排斥的約束條件的問題?！亢邢嗷ヅ懦獾募s束條件的問題。 設(shè)某廠生產(chǎn)第設(shè)某廠生產(chǎn)第j j 種產(chǎn)品的數(shù)量為種產(chǎn)品的數(shù)量為x xj j(j=1(j=

51、1，2 2，3)3)，其材料可，其材料可在甲或乙中選擇一種，當選擇甲或乙時，相應(yīng)的材料消耗的約在甲或乙中選擇一種，當選擇甲或乙時，相應(yīng)的材料消耗的約束條件分別為：束條件分別為： 和和180652321xxx(5.12 a)300534321xxx(5.12 a)試問這類相互排斥的約束條件如何體現(xiàn)在模型中？試問這類相互排斥的約束條件如何體現(xiàn)在模型中？ 解：解：引入引入0-10-1變量：變量： 當不選用材料甲時當選用材料甲時101y和和當不選用材料乙時當選用材料乙時102y 因而，兩個相互排斥的約束條件可用下列線性約束條件統(tǒng)一因而，兩個相互排斥的約束條件可用下列線性約束條件統(tǒng)一起來：起來： )12

52、. 5(1)12. 5(300534)12. 5(1806522123211321eyydMyxxxcMyxxx其中其中M M是一個充分大的數(shù)。是一個充分大的數(shù)。 若若y y1 1=1=1，而，而y y2 2=0=0，即選用材料乙，由，即選用材料乙，由(5.12d) (5.12d) 式得：式得：300534321xxx式式(5.12c)(5.12c)自然成立；自然成立； 若若y y1 1=0=0，而，而y y2 2=1=1，即選用材料甲，由，即選用材料甲，由(5.12c) (5.12c) 式得：式得：式式(5.12d)(5.12d)自然成立自然成立. . 180652321xxx 【例【例5-

53、95-9】固定費用問題。有一種自然資源被用于生產(chǎn)三種產(chǎn)】固定費用問題。有一種自然資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費用及售價、資源單位消耗量及組品，資源量、產(chǎn)品單件可變費用及售價、資源單位消耗量及組織三種產(chǎn)品生產(chǎn)的固定費用見表織三種產(chǎn)品生產(chǎn)的固定費用見表5-55-5。要求制訂一個生產(chǎn)計劃，。要求制訂一個生產(chǎn)計劃，使總收益最大。使總收益最大。 12108單位售價200150100固定費用654 單位可變費用100321C300432B500842A資源量IIIIII 單耗量資源產(chǎn)品解：解：設(shè)設(shè)x xj j表示三種產(chǎn)品的產(chǎn)量表示三種產(chǎn)品的產(chǎn)量( (j j=1=1，2 2，3)3)。 引入

54、引入0-10-1變量：變量： )3 , 2 , 1(01jjjyj種產(chǎn)品若不生產(chǎn)第種產(chǎn)品若生產(chǎn)第則問題的數(shù)學(xué)模型可歸結(jié)如下：則問題的數(shù)學(xué)模型可歸結(jié)如下： 321321200150100)612()510()48(maxyyyxxxz500842321xxx300432321xxx10032321xxx) 3 , 2 , 1( jyMxjjj)3 , 2 , 1(0jxj且為整數(shù))3 , 2 , 1(10jyj或 如果生產(chǎn)第如果生產(chǎn)第j j種產(chǎn)品，則其產(chǎn)量種產(chǎn)品，則其產(chǎn)量x xj j0 0，由，由x xj jM Mj jy yj j知，知，y yj j1 1。因此，相應(yīng)的固定費用在目標函數(shù)中將被

55、考慮。因此，相應(yīng)的固定費用在目標函數(shù)中將被考慮。 同理，如果不生產(chǎn)第同理，如果不生產(chǎn)第j j種產(chǎn)品，則其產(chǎn)量種產(chǎn)品，則其產(chǎn)量x xj j=0=0，由，由x xj jM Mj jy yj j知，知，y yj j可以取可以取0 0或或1 1。因此，相應(yīng)的固定費用不應(yīng)在目標函數(shù)中將被。因此，相應(yīng)的固定費用不應(yīng)在目標函數(shù)中將被考慮?？紤]。 二、二、0-10-1型整數(shù)規(guī)劃的解法型整數(shù)規(guī)劃的解法 0-1 0-1型規(guī)劃是一類特殊的整數(shù)規(guī)劃，因為變量只有型規(guī)劃是一類特殊的整數(shù)規(guī)劃，因為變量只有0 0或或1 1兩個兩個可能的取值，故最多有可能的取值，故最多有2 2n n個可行解，理論上可以用枚舉法進行個可行解，

56、理論上可以用枚舉法進行求解。但當求解。但當n n較大時，采用完全枚舉法求解幾乎是不可能的。較大時，采用完全枚舉法求解幾乎是不可能的。 隱枚舉法是求解隱枚舉法是求解0-10-1整數(shù)規(guī)劃問題的一種比較簡便的方法。整數(shù)規(guī)劃問題的一種比較簡便的方法。其實質(zhì)也是一種分支定界法。其實質(zhì)也是一種分支定界法。 隱枚舉法是是在隱枚舉法是是在2 2n n個可能的變量組合中，只有一部分是可行個可能的變量組合中，只有一部分是可行解。只要發(fā)現(xiàn)某個變量組合不滿足其中一個約束條件，就不必解。只要發(fā)現(xiàn)某個變量組合不滿足其中一個約束條件，就不必再檢驗是否滿足其它約束。如所有約束條件都滿足，就是再檢驗是否滿足其它約束。如所有約束

57、條件都滿足，就是0-10-1規(guī)規(guī)劃的一個可行解，可根據(jù)相應(yīng)的目標函數(shù)值產(chǎn)生一個過濾條件，劃的一個可行解，可根據(jù)相應(yīng)的目標函數(shù)值產(chǎn)生一個過濾條件，對于目標函數(shù)值劣于該可行解的變量組合不必再去檢驗其可行對于目標函數(shù)值劣于該可行解的變量組合不必再去檢驗其可行性。在以后的求解過程中，如發(fā)現(xiàn)某個可行解比原來保留的可性。在以后的求解過程中，如發(fā)現(xiàn)某個可行解比原來保留的可行解更優(yōu)，則用它替換原來的過濾條件。行解更優(yōu)，則用它替換原來的過濾條件。 【例【例5-115-11】求解】求解0-10-1整數(shù)規(guī)劃整數(shù)規(guī)劃 10,6434422523max3213221321321321或xxxxxxxxxxxxxxxxz

58、(5.13a)(5.13b)(5.13c)(5.13d)解：解：求解過程可以用表求解過程可以用表5-75-7表示。表示。 (1(1，1 1，1)1)(1(1，1 1，0)0)(1(1，0 0，1)1)(1(1，0 0，0)0)(0(0，1 1，1)1)(0(0，1 1，0)0)(0(0，0 0，1)1)(0(0，0 0，0)0)d dc cb ba a過濾條件過濾條件約束條件約束條件z z值值( (x x1 1，x x2 2，x x3 3) )0 0z z 0 05 5z z 5 5-2-23 33 38 8z z 8 81 16 6所以，最優(yōu)解所以，最優(yōu)解( (x x1 1，x x2 2，x

59、 x3 3) )T T=(1=(1，0 0，1)1)T T，max max z z = 8 = 8。 為了使最優(yōu)解盡可能早出現(xiàn)，可先將目標函數(shù)中各變量的為了使最優(yōu)解盡可能早出現(xiàn)，可先將目標函數(shù)中各變量的順序按其系數(shù)大小重新排列，這樣可進一步減少計算量。例順序按其系數(shù)大小重新排列，這樣可進一步減少計算量。例5-5-1212給出了用隱枚舉法求解給出了用隱枚舉法求解0-10-1整數(shù)規(guī)劃問題的一般步驟。整數(shù)規(guī)劃問題的一般步驟。 【例【例5-125-12】求解】求解0-10-1整數(shù)規(guī)劃整數(shù)規(guī)劃 5432157428maxxxxxxz4323354321xxxxx423554321xxxxx)5 , 4

60、, 3 , 2 , 1(10jxj或步驟步驟1 1：將問題轉(zhuǎn)化為如下標準形式：將問題轉(zhuǎn)化為如下標準形式： njjjxcz1min), 2 , 1(1mibxaijnjij), 2 , 1(10njxj 或zzzminnxnnxx1 如目標函數(shù)為如目標函數(shù)為max zmax z，令，令 ，可化為，可化為 。如某。如某個變量個變量 的系數(shù)為負，令的系數(shù)為負，令 ，使系數(shù)變正。，使系數(shù)變正。 其中其中c cj j00，且，且c c1 1c c2 2c cn n。 如約束條件為如約束條件為，兩邊同乘，兩邊同乘(-1)(-1)；如約束條件為等式，；如約束條件為等式，可令變量可令變量 ，代入目標函數(shù)和其它