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

第八章整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的圖解法第二節(jié)分枝定界法整數(shù)規(guī)劃（IntegerProgramming，簡稱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ī)劃的圖解法對二維ILP問題，圖解法是最簡單的。解法：在LP問題最優(yōu)解基礎(chǔ)上，讓目標函數(shù)等值線逆著其法線方向朝可行域內(nèi)平移，首次碰到的整數(shù)點（ILP的整數(shù)可行解），即為ILP問題的最優(yōu)解。

例、某廠擬用火車裝運甲、乙兩種貨物集裝箱，每箱的體積、重量、可獲利潤以及裝運所受限制如下：貨物集裝箱體積(米3)重量(百斤)利潤(百元) 甲5220乙 4510托運限制24 13 問兩種貨物各裝運多少箱，可使獲得利潤最大？例：設(shè)甲、乙兩種貨物裝運箱數(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ī)劃問題的區(qū)別在于條件(4)。x1x2（4.8，0）O找到的第一個整數(shù)點（4，1），即IP問題的最優(yōu)解解決整數(shù)規(guī)劃的兩種初始想法：1、一一列舉所有可行方案；2、先放棄整數(shù)性要求，求得一個LP問題的最優(yōu)解后，然后用四舍五入法取整數(shù)解。整數(shù)規(guī)劃問題的解法值得探討。第二節(jié)分枝定界法首先，理解一個問題：原問題與松弛問題解的關(guān)系？一般將一個規(guī)劃問題去掉若干約束條件而得到的規(guī)劃問題稱為原問題的松弛問題；例如：S1→S2（松弛問題）

Maxz=6x1+5x2

2x1+x2≤9

5x1+7x2≤35

x1≥0，x2≥0x2≤2s.t.減少條件形成松弛問題S2減少條件x2≤2后，x1、x2的取值范圍（設(shè)為S2）比最初（設(shè)為S1）大，如圖S2S1因為S1S2，所以z=6x1+5x2在S2上的最大值不超過S2上的最大值（因S1上的最大值也是S2上的值）?！葘τ谀繕撕瘮?shù)最小化的問題亦然。意義：松弛問題的目標函數(shù)值比原問題的目標函數(shù)值更優(yōu)。IP問題去掉整數(shù)性約束，一般稱為該IP問題的伴隨LP問題；伴隨LP問題是IP問題的一個松弛問題；對伴隨LP問題的解，可稱之為IP問題的LP解；伴隨LP問題的最優(yōu)值一定比IP問題的更優(yōu)。例求解IP問題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:無可行解x1≤4x2≤1x1≥5x2≥2伴隨問題R0為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0問題R2為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≥5x1,x2≥

0問題R1為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

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

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

70x1≤4x2≥3x1,x2≥

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