第八章整數規(guī)劃

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

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

Maxz＝20x1+10x2

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

Maxz=6x1+5x2

2x1+x2≤9

5x1+7x2≤35

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

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