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

第八章整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的圖解法第二節(jié)分枝定界法整數(shù)規(guī)劃（IntegerProgramming，簡(jiǎn)稱IP）整數(shù)規(guī)劃中要求部分或全部決策變量取整數(shù)值。根據(jù)規(guī)劃模型是否為線性，可分為整數(shù)線性規(guī)劃（ILP）和整數(shù)非線性規(guī)劃（INLP）。根據(jù)受整數(shù)約束的變量范圍，可分為純整數(shù)規(guī)劃（PureIP）、混合整數(shù)規(guī)劃（MixedIP）和0－1規(guī)劃。第一節(jié)整數(shù)規(guī)劃的圖解法對(duì)二維ILP問(wèn)題，圖解法是最簡(jiǎn)單的。解法：在LP問(wèn)題最優(yōu)解基礎(chǔ)上，讓目標(biāo)函數(shù)等值線逆著其法線方向朝可行域內(nèi)平移，首次碰到的整數(shù)點(diǎn)（ILP的整數(shù)可行解），即為ILP問(wèn)題的最優(yōu)解。

例、某廠擬用火車裝運(yùn)甲、乙兩種貨物集裝箱，每箱的體積、重量、可獲利潤(rùn)以及裝運(yùn)所受限制如下：貨物集裝箱體積(米3)重量(百斤)利潤(rùn)(百元) 甲5220乙 4510托運(yùn)限制24 13 問(wèn)兩種貨物各裝運(yùn)多少箱，可使獲得利潤(rùn)最大？例：設(shè)甲、乙兩種貨物裝運(yùn)箱數(shù)分別為x1和x2。顯然，x1、x2都要求為整數(shù),于是可建立整數(shù)規(guī)劃模型如下：

Maxz＝20x1+10x2

s.t.5x1+4x2≤24(1)2x1+5x2≤13(2)x1,x2≥0(3)x1,x2為整數(shù)(4)它和線性規(guī)劃問(wèn)題的區(qū)別在于條件(4)。x1x2（4.8，0）O找到的第一個(gè)整數(shù)點(diǎn)（4，1），即IP問(wèn)題的最優(yōu)解解決整數(shù)規(guī)劃的兩種初始想法：1、一一列舉所有可行方案；2、先放棄整數(shù)性要求，求得一個(gè)LP問(wèn)題的最優(yōu)解后，然后用四舍五入法取整數(shù)解。整數(shù)規(guī)劃問(wèn)題的解法值得探討。第二節(jié)分枝定界法首先，理解一個(gè)問(wèn)題：原問(wèn)題與松弛問(wèn)題解的關(guān)系？一般將一個(gè)規(guī)劃問(wèn)題去掉若干約束條件而得到的規(guī)劃問(wèn)題稱為原問(wèn)題的松弛問(wèn)題；例如：S1→S2（松弛問(wèn)題）

Maxz=6x1+5x2

2x1+x2≤9

5x1+7x2≤35

x1≥0，x2≥0x2≤2s.t.減少條件形成松弛問(wèn)題S2減少條件x2≤2后，x1、x2的取值范圍（設(shè)為S2）比最初（設(shè)為S1）大，如圖S2S1因?yàn)镾1S2，所以z=6x1+5x2在S2上的最大值不超過(guò)S2上的最大值（因S1上的最大值也是S2上的值）。∪對(duì)于目標(biāo)函數(shù)最小化的問(wèn)題亦然。意義：松弛問(wèn)題的目標(biāo)函數(shù)值比原問(wèn)題的目標(biāo)函數(shù)值更優(yōu)。IP問(wèn)題去掉整數(shù)性約束，一般稱為該IP問(wèn)題的伴隨LP問(wèn)題；伴隨LP問(wèn)題是IP問(wèn)題的一個(gè)松弛問(wèn)題；對(duì)伴隨LP問(wèn)題的解，可稱之為IP問(wèn)題的LP解；伴隨LP問(wèn)題的最優(yōu)值一定比IP問(wèn)題的更優(yōu)。例求解IP問(wèn)題Maxz=40x1+90x29x1+7x2≤

567x1+20x2≤70x1,x2≥0,整數(shù)R0:z0=356x1=4.81x2=1.82R1:z1=349x1=4.00x2=2.10R2:z2=341x1=5.00x2=1.57R12:z12=327x1=1.42x2=3.00x2≥3R11:z11=340x1=4.00x2=2.00R21:z21=308x1=5.44x2=1.00R22:無(wú)可行解x1≤4x2≤1x1≥5x2≥2伴隨問(wèn)題R0為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0問(wèn)題R2為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≥5x1,x2≥

0問(wèn)題R1為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x1,x2≥0x2≤2問(wèn)題R11為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≤2x1,x2≥0問(wèn)題R12為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≥3x1,x2≥

0三點(diǎn)說(shuō)明1、分支順序：目標(biāo)值大的先分支；2、下級(jí)分支問(wèn)題的最優(yōu)值一定比上級(jí)分支問(wèn)題的最優(yōu)值小。3、各分支的取舍：若已取得一整數(shù)可行解，凡是目標(biāo)函數(shù)值小于該整數(shù)可行解的分支都可以舍去。對(duì)目標(biāo)函數(shù)最大化的IP問(wèn)題R，其伴隨LP問(wèn)題為R0，分枝定界法的步驟為：(1)用觀察法求R的一個(gè)可行解。其目標(biāo)值便是R的最優(yōu)目標(biāo)值z(mì)*的一個(gè)下界z。(2)求解R0，得R0的最優(yōu)解x(0)和最優(yōu)值z(mì)0。若x(0)符合R的整數(shù)條件，則顯然x(0)也是R的最優(yōu)解，結(jié)束；否則，以R0作為一個(gè)分枝標(biāo)明求解的結(jié)果，z0是問(wèn)題R的最優(yōu)目標(biāo)值z(mì)*的一個(gè)上界z。(3)分枝。取目標(biāo)函數(shù)值最大的一個(gè)枝Rs，在Rs的解中任選一不符合整數(shù)條件的變量xj，其值為bj，構(gòu)造兩個(gè)約束條件xj≤[bj]和xj≥[bj]+1。將兩個(gè)約束條件分別加入問(wèn)題Rs，得兩個(gè)后繼規(guī)劃問(wèn)題Rs1和Rs2。不考慮整數(shù)條件求解這兩個(gè)后繼問(wèn)題，以每個(gè)后繼問(wèn)題為一分枝標(biāo)明求解的結(jié)果。(4)定界。在各分枝中找出