整數(shù)規(guī)劃整數(shù)規(guī)劃的數(shù)學(xué)模型設(shè)置邏輯變量建立整數(shù)規(guī)劃模型分配問(wèn)題與匈牙利法分枝定界法、割平面法應(yīng)用舉例整數(shù)規(guī)劃整數(shù)規(guī)劃的數(shù)學(xué)模型

從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過(guò)舍入取整，尋求滿(mǎn)足整數(shù)要求的解即可。但實(shí)際上兩者卻有很大的不同，通過(guò)舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚至不能保證所得到的解是整數(shù)可行解。3分枝定界法從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種例：設(shè)整數(shù)規(guī)劃問(wèn)題如下

首先不考慮整數(shù)約束,得到線性規(guī)劃問(wèn)題（一般稱(chēng)為松弛問(wèn)題）3分枝定界法例：設(shè)整數(shù)規(guī)劃問(wèn)題如下首先不考慮整用圖解法求出最優(yōu)解x1＝3/2,x2=10/3且有z=29/6x1x2⑴⑵33(3/2,10/3)現(xiàn)求整數(shù)解(最優(yōu)解):如用“舍入取整法”可得到4個(gè)點(diǎn)即(1,3)(2,3)(1,4)(2,4).顯然,它們都不可能是整數(shù)規(guī)劃的最優(yōu)解.按整數(shù)規(guī)劃約束條件,其可行解肯定在線性規(guī)劃問(wèn)題的可行域內(nèi)且為整數(shù)點(diǎn).故整數(shù)規(guī)劃問(wèn)題的可行解集是一個(gè)有限集,如圖所示.用圖解法求出最優(yōu)解x1x2⑴⑵33(3/2,10/3)

因此,可將集合內(nèi)的整數(shù)點(diǎn)一一找出,其最大目標(biāo)函數(shù)的值為最優(yōu)解,此法為完全枚舉法.

如上例:其中(2,2)(3,1)點(diǎn)為最大值,z=4.

目前,常用的求解整數(shù)規(guī)劃的方法有：分枝定界法和割平面法；對(duì)于特別的0－1規(guī)劃問(wèn)題采用隱枚舉法和匈牙利法。3分枝定界法因此,可將集合內(nèi)的整數(shù)點(diǎn)一一找出,其最大目0－1整數(shù)規(guī)劃求解隱枚舉法求解舉例0－1整數(shù)規(guī)劃求解解:(1)先用試探的方法找出一個(gè)初始可行解,如x1＝x2＝0,x3＝1.滿(mǎn)足約束條件,選其作為初始可行解,目標(biāo)函數(shù)z0＝2. (2)附加過(guò)濾條件,以目標(biāo)函數(shù)作為過(guò)濾約束：

4x1＋3x2＋2x3>=2原模型變?yōu)椋航?(1)先用試探的方法找出一個(gè)初始可行解,如x1＝x2＝（3）求解求解過(guò)程如表4－6所示。點(diǎn)過(guò)濾條件約束z值④①②③

4x1＋3x2＋2x3≥2

（0，0，0）T

×

（0，0，1）T

√√√√2（0，1，0）T

√√×

（0，1，1）T

√√√√5

4x1＋3x2＋2x3≥5

（1，0，0）T

×

（1，0，1）T

√×

（1，1，0）T

√√√√7

4x1＋3x2＋2x3≥7

（1，1，1）T

√√√√9（3）求解求解過(guò)程如表4－6所示。點(diǎn)過(guò)濾條件約束z值④

基本思路

考慮純整數(shù)問(wèn)題整數(shù)問(wèn)題的松弛問(wèn)題3分枝定界法容易求解基本思路考慮純整數(shù)問(wèn)題整數(shù)問(wèn)題的松弛問(wèn)題3分第一步:先不考慮整數(shù)約束,解A的松弛問(wèn)題B,可能得到以下情況之一:若B沒(méi)有可行解,則A也沒(méi)有可行解,停止計(jì)算.若B有最優(yōu)解,并符合A的整數(shù)條件,則B的最優(yōu)解即為A的最優(yōu)解,停止計(jì)算.若B有最優(yōu)解,但不符合A的整數(shù)條件,轉(zhuǎn)入下一步.為討論方便,設(shè)B的最優(yōu)解為：

3分枝定界法第一步:先不考慮整數(shù)約束,解A的松弛問(wèn)題B第二步:定界

記A的目標(biāo)函數(shù)最優(yōu)值為z*,以z(0)作為z*

的上界,記為

=z(0).再用觀察法找的一個(gè)整數(shù)可行解X′,并以其相應(yīng)的目標(biāo)函數(shù)值z(mì)′作為z*的下界,記為z＝z′,也可以令z＝－∞,則有:4分枝定界法第二步:定界4分枝定界法第三步:分枝在以上界

所對(duì)應(yīng)的解中,任選一個(gè)不符合整數(shù)條件的變量,例如(不為整數(shù)),以表示不超過(guò)的最大整數(shù).構(gòu)造兩個(gè)約束條件將這兩個(gè)約束條件分別加入問(wèn)題B中,形成兩個(gè)子問(wèn)題B1和B2,再對(duì)這兩個(gè)子問(wèn)題進(jìn)行求解.3分枝定界法第三步:分枝3分枝定界法

第四步:修改上、下界,按照以下兩點(diǎn)規(guī)則進(jìn)行在各分枝問(wèn)題中,找出目標(biāo)函數(shù)值最大者作為新的上界;從已符合整數(shù)條件的分枝中,找出目標(biāo)函數(shù)值最大者作為新的下界.3分枝定界法第四步:修改上、下界,按照以下兩點(diǎn)規(guī)則進(jìn)行3分如此反復(fù)進(jìn)行,直到得到

為止,即得最優(yōu)解X*.第五步：比較與剪枝

各分枝的目標(biāo)函數(shù)值中,若有小于

者,則剪掉此枝,表明此子問(wèn)題已經(jīng)探清,不必再分枝了;否則繼續(xù)分枝。3分枝定界法如此反復(fù)進(jìn)行,直到得到用分枝定界法解整數(shù)規(guī)劃問(wèn)題（圖解法）例：考慮下面的整數(shù)規(guī)劃問(wèn)題3分枝定界法用分枝定界法解整數(shù)規(guī)劃問(wèn)題（圖解法）例：考慮下面的整數(shù)規(guī)劃問(wèn)用圖解法求解上述線性規(guī)劃問(wèn)題B,轉(zhuǎn)下頁(yè).第一步：尋找替代問(wèn)題并求解.容易求解用圖解法求解上述線性規(guī)劃問(wèn)題B,轉(zhuǎn)下頁(yè).第一步：尋找替代問(wèn)圖解法分析：

、、、、、、、、、、、0123456789108-7-6-5-4-3-2-1-B不是A問(wèn)題解但圖解法分析：、、、、、、、、分枝：

012345674321B分枝：0123接下來(lái)求出（B1）和（B2）的最優(yōu)解即可。分枝后原B問(wèn)題轉(zhuǎn)化成B1和B2兩個(gè)子問(wèn)題.接下來(lái)求出（B1）和（B2）的最優(yōu)解即可。分枝后原B問(wèn)題轉(zhuǎn)圖解法分析：

012345674321圖解法分析：0123再分枝：

4321

01234567是問(wèn)題A解但不是問(wèn)題A解而

剪枝

再分枝：0123

分枝后原B1問(wèn)題轉(zhuǎn)化成B11和B12兩個(gè)子問(wèn)題.分枝后原B1問(wèn)題轉(zhuǎn)化成B11和B12兩個(gè)子問(wèn)題.圖解法分析：

012345674321圖解法分析：0123分枝定界的全過(guò)程：分枝定界的全過(guò)程：分支定界的全過(guò)程：分支定界的全過(guò)程：練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題

（圖解法）

練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題

（圖解法）

B1x1=1,x2=7/3z(1)

＝10/3Bx1=3/2,x2=10/3z(0)

＝29/6B2x1=2,x2=23/9z(2)

＝41/9x1≤1x1≥2B21x1=33/14,x2=2z(21)

＝61/14B22無(wú)可行解x2≤2x2≥3B211x1=2,x2=2z(211)

＝4B212x1=3,x2=1z(212)

＝4x1≤2x1≥3B1BB2x1≤1x1≥2B21B22x2≤2x2≥3B21解:用單純形法解上述問(wèn)題,如表所示,獲得最優(yōu)解：初始表最終表

用分枝定界法求解整數(shù)

規(guī)劃問(wèn)題(單純形法)解:用單純形法解上述問(wèn)題,如表所示,獲得最優(yōu)解：初始表最終表

x1=13/4

x2=5/2z(0)=59/4≈14.75

選x2進(jìn)行分枝,即增加兩個(gè)約束,2≥x2≥3有下式:分別在(LP1)和(LP2)中引入松弛變量x5和x6

,將新加約束條件加入上表計(jì)算.即x2+x5=2,－x2+x6=－3

得下表:上例續(xù)：x1=13/4x2=5/2z(0)=59/x1=7/2,x2=2

z(1)=29/2=14.5繼續(xù)分枝,加入約束

3≥x1≥4

考慮LP1：x1=7/2,x2=2考慮LP1：

考慮LP2：x1=5/2,x2=3

Z(2)=27/2=13.5∵

Z(2)<Z(1)∴先不考慮分枝考慮LP2：x1=5/2,x2=3接(LP1)繼續(xù)分枝,加入約束4≤x1≤3,有下式：分別引入松弛變量x7和x8，然后進(jìn)行計(jì)算。上例續(xù)：接(LP1)繼續(xù)分枝,加入約束4≤x1≤3,有下式：

x1=3,x2=2

z(3)=13找到整數(shù)解,問(wèn)題已探明,停止計(jì)算.

考慮LP3：x1=3,x2=2考慮LP3：

x1=4,x2=1

z(4)=14找到整數(shù)解,問(wèn)題已探明,停止計(jì)算.

考慮LP4：x1=4,x2=1考慮LP4：樹(shù)形圖如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=13/4,x2=5/2Z(0)

＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)

＝13LP4x1=4,x2=1Z(4)

＝14x2≤2x2≥3x1≤3x1≥4╳╳╳樹(shù)形圖如下：LP1LPLP2LP3LP4x2≤2x2≥3x1練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題

（單純形法）先將問(wèn)題轉(zhuǎn)化成標(biāo)準(zhǔn)型：練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題

（單純形法上述松弛問(wèn)題的單純形表：上述松弛問(wèn)題的單純形表：LP1x1=1,x2=3w(1)

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

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

＝18.5LP3x1=12/5,x2=3w(3)

＝17.4LP4無(wú)可行解LP5x1=2,x2=3w(5)

＝17LP6x1=3,x2=5/2w(6)

＝15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3╳╳╳╳LP1LPLP2LP3LP4LP5LP6x1≤1x1≥2x21958由Gomory提出的一種求解整數(shù)規(guī)劃問(wèn)題的方法基本思想：依次引進(jìn)線性約束條件(稱(chēng)Gomory約束或割平面)切割掉問(wèn)題的部分非整數(shù)解直到使問(wèn)題的目標(biāo)函數(shù)值達(dá)到最優(yōu)的整數(shù)點(diǎn)成為縮小后可行域的一個(gè)頂點(diǎn)4割平面法1958由Gomory提出的一種求解整數(shù)規(guī)劃問(wèn)題的方法4第一步：把問(wèn)題中所有約束條件的系數(shù)均化為整數(shù),用單純形法求解該整數(shù)規(guī)劃對(duì)應(yīng)的松弛問(wèn)題.若松弛問(wèn)題沒(méi)有可行解,則原整數(shù)問(wèn)題也沒(méi)有可行解,停止計(jì)算.若松弛問(wèn)題有最優(yōu)解,并符合原整數(shù)問(wèn)題的整數(shù)條件,則該最優(yōu)解即為原整數(shù)問(wèn)題的最優(yōu)解,停止計(jì)算.若松弛問(wèn)題有最優(yōu)解,但不符合原整數(shù)問(wèn)題的整數(shù)條件,轉(zhuǎn)入下一步.4割平面法第一步：把問(wèn)題中所有約束條件的系數(shù)均化為整數(shù),用單純第二步：從松弛問(wèn)題的最優(yōu)解中,任選一個(gè)不為整數(shù)的分量xr,,將最優(yōu)單純形表中該行的系數(shù)和分解為整數(shù)部分和小數(shù)部分之和,并以該行為源行,按下式作割平面方程：的小數(shù)部分的小數(shù)部分4割平面法第二步：從松弛問(wèn)題的最優(yōu)解中,任選一個(gè)不為整數(shù)的分量xr,,第三步：將所得的割平面方程作為一個(gè)新的約束條件置于最優(yōu)單純形表中（同時(shí)增加一個(gè)單位列向量）,用對(duì)偶單純形法求出新的最優(yōu)解。若表中得到的解仍為非整數(shù)解,重復(fù)第二步.4割平面法第三步：將所得的割平面方程作為一個(gè)新的約束條件置于最優(yōu)單純形例1：用割平面法求解整數(shù)規(guī)劃問(wèn)題解：將上述問(wèn)題的松弛問(wèn)題記為例1：用割平面法求解整數(shù)規(guī)劃問(wèn)題解：將上述問(wèn)題的松弛問(wèn)題記續(xù)：增加松弛變量x3和x4,得到LP1的初始單純形表和最優(yōu)單純形表：續(xù)：增加松弛變量x3和x4,得到LP1的初始單純形表和最系數(shù)和常數(shù)項(xiàng)分解成整數(shù)和小數(shù)部分此題的最優(yōu)解為：,但不是整數(shù)最優(yōu)解,需引入割平面.以x2為源行生成割平面:例1續(xù)：系數(shù)和常數(shù)項(xiàng)分解此題的最優(yōu)解為：現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中：現(xiàn)將生成的割平面條件加入