【正文】 得 )()(4,3,2,1103354972674263m i n543215432154321bajxxxxxxxxxxxxxxxxZj?????????????????????????????，或 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 45 2020年 6月 16日星期二 （ 2）目標(biāo)函數(shù)系數(shù)按升序?qū)?yīng)的變量重新排列得到模型 )()(4,3,2,1103534927676432m i n352413524135241bajxxxxxxxxxxxxxxxxZj??????????????????????????，或－－－（ 3）求主枝。 （ 3）令 x2=0同時令 x3=0及 x3=1得到分枝 2和分枝 3， X2和 X3是可行解，分枝停止并保留，如表 38及圖 38所示。當(dāng)目標(biāo)函數(shù)求最小值時，先考慮目標(biāo)函數(shù)系數(shù)最大的變量等于 0。所有變量為整數(shù)， X(1)就是 IP的最優(yōu)解。 新的松弛問題具有特征：當(dāng)原問題是求最大值時 ， 目標(biāo)值是分枝問題的上界；當(dāng)原問題是求最小值時 ， 目標(biāo)值是分枝問題的下界； 4. 檢查所有分枝的解及目標(biāo)函數(shù)值 ， 若某分枝的解是整數(shù)并且目標(biāo)函數(shù)值大于 （ max） 等于其它分枝的目標(biāo)值 ， 則將其它分枝剪去不再計算 ,若還存在非整數(shù)解并且目標(biāo)值大于 （ max）整數(shù)解的目標(biāo)值 ， 需要繼續(xù)分枝 ， 再檢查 ， 直到得到最優(yōu)解 。 （ 1）所裝物品不變； （ 2）如果選擇旅行箱，則只能裝載丙和丁兩種物品，價值分別是 4和 3，載重量和體積的約束為 2121????xxxx【 解 】 此問題可以建立兩個整數(shù)規(guī)劃模型 ， 但用一個模型描述更簡單 。由于 x1， x2必須取整數(shù)值 ， 實際上整數(shù)規(guī)劃問題的可行解集只是圖中可行域內(nèi)的那些整數(shù)點 。如果模型是線性的，稱為整數(shù)線性規(guī)劃。邏輯變量也是只允許取整數(shù)值的一類變量。 即兩種物品各裝 5件 ， 總價值 35元 。 從上式可知 ， 當(dāng)使用背包時 (y1=1，y2=0)， 式 (b)和 (d)是多余的；當(dāng)使用旅行箱時 (y1=0， y2=1)， 式(a)和 (c)是多余的 。 上述分枝過程可用下圖表示 LP0:X=(,),Z0= LP1:X=(3,) Z1= LP2:X=(4,) Z2= x1≤3 x1≥4 LP3:X=(,6) Z3= x2≤6 LP4:X=(4,6) Z4=34 LP5:X=(5,5) Z5=35 x1≤4 x1≥5 無可行解 x2≥7 Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 24 2020年 6月 16日星期二 設(shè)純整數(shù)規(guī)劃 njxbxaxcZ jinjjijnjjj ,10ma x11????? ????且為整數(shù)， 松弛問題 njxbxaxcZ jinjjijnjjj ,10ma x11????? ????，的最優(yōu)解 TmT bbbbBbbBX ),()0,( 2111 ??? ??＝設(shè) xi不為整數(shù)， 為非基變量kkkikii xxabx ??? 求解 IP的割平面法 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 25 2020年 6月 16日星期二 將 分離成一個整數(shù)與一個非負真分?jǐn)?shù)之和： iki ab及? ? 10,10,][ ???????? ikiikikikiii fffaafbb則有 kkikkkijiii xfxafbx ?? ???? ][][kkikikkijii xffxabx ?? ???? ][][等式兩邊都為整數(shù)并且有 1??? ? ikkiki fxff 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 26 2020年 6月 16日星期二 加入松弛變量 si得 ikkiki fxfs ??? ?此式稱為以 xi行為源行（來源行）的割平面，或分?jǐn)?shù)切割式，或 (高莫雷 )約束方程。 Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 32 2020年 6月 16日星期二 作業(yè)：教材 P76 T 7， 8 “ 枝”生“ 枝” “ 枝” ，求出 Gomory約束 Gomory約束，用 對偶單純形法迭代 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming 下一節(jié)： 0－ 1規(guī)劃的求解 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 34 2020年 6月 16日星期二 求解 0－ 1整數(shù)規(guī)劃的隱枚舉法 隱枚舉法的步驟： ，目標(biāo)函數(shù)值為 Z0 2. 原問題求最大值時 ， 則增加一個約束 1 1 2 2 0 ( * )nnc x c x c x Z? ? ? ?當(dāng)求最小值時 ， 上式改為小于等于約束 3. 列出所有可能解，對每個可能解先檢驗式（ *），若滿足再檢驗其它約束，若不滿足式（ *），則認(rèn)為不可行，若所有約束都滿足，則認(rèn)為此解是可行解，求出目標(biāo)值 4. 目標(biāo)函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 35 2020年 6月 16日星期二 【 例 】 用隱枚舉法求解下列 BIP問題 ???????????????????????????????4,3,2,11010542324653103245326m ax43214321432143214321jxxxxxxxxxxxxxxxxxxxxxZj，或【 解 】 （ 1） 不難看出 ， 當(dāng)所有變量等于 0或 1的任意組合時 ，第一個約束滿足 ， 說明第一個約束沒有約束力 ， 是多余的 ，從約束條件中去掉 。計算步驟如下： （ 1）將 BIP問題的目標(biāo)函數(shù)的系數(shù)化為非負，如 332m a x,132m a x 212221 ????????? xxZxxxxZ 令 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 39 2020年 6月 16日星期二 當(dāng)變量作了代換后 ， 約束條件中的變量也相應(yīng)作代換 。注意到分枝 6， x4＝ 1時只有 x1＝ 0（ x1＝ 1就是主枝）， X6不可行并且 Z6＝ 10小于 Z3和 Z4，分枝停止并剪枝，分枝過程結(jié)束。 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 46 2020年 6月 16日星期二 分枝 j 上一分枝 Xj=(x1, x4, x3