【導(dǎo)讀】個規(guī)劃稱為整數(shù)規(guī)劃。當(dāng)要求全部變量取整數(shù)值的，稱為純整。本章只討論整數(shù)線性。量x，當(dāng)x=1表示投資，x=0表示不投資；xij=0表示不安排第i人去做j工作。邏輯變量也是只允許取整數(shù)。某人有一背包可以裝10公斤重、。問兩種物品各裝多少件，所裝物品的總價值最大？線性規(guī)劃的可行域如圖3-1中的陰影部分所示。用圖解法求得點B為最優(yōu)解：X＝(，)，Z＝。是圖中可行域內(nèi)的那些整數(shù)點。7）雖屬可行解，但代入目標(biāo)函數(shù)得Z=33,并非最優(yōu)。數(shù)規(guī)劃問題的最優(yōu)解需要采用其它特殊方法。置邏輯變量建立起整數(shù)規(guī)劃的數(shù)學(xué)模型。為12公斤，其體積是。背包和旅行箱只能選擇其一，建。引入0－1變量yi，令。i種方式裝載時不采用第，式中M為充分大的正數(shù)。從上式可知，當(dāng)使用背包時(y1=1，作用），yi=0表示第i個約束起作用。當(dāng)約束條件是“≥”符號

　　

【正文】 Page 41 2020年 6月 16日星期二 解 （ 1）目標(biāo)函數(shù)系數(shù)全部非負(fù)，直接對變量重新排序 )()()(4,3,2,110105423243656532m a x1432143214321432cbajxxxxxxxxxxxxxxxxxZj??????????????????????????，或（ 2）求主枝：令 X＝ (1， 1， 1， 1)得到主枝 1，檢查約束條件知 ()不滿足，則進(jìn)行分枝。 （ 3）令 x2=0同時令 x3=0及 x3=1得到分枝 2和分枝 3， X2和 X3是可行解，分枝停止并保留，如表 38及圖 38所示。 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 42 2020年 6月 16日星期二 表 令 x2=1同時令 x3=0得到分枝 4， X4是可行解，分枝停止并保留。令 x2= x3=1， x4取“ 0”和“ 1”得到分枝 5和 6，分枝 5不可行并且 Z5＝ 11小于 Z3和 Z4，分枝停止并剪枝。注意到分枝 6， x4＝ 1時只有 x1＝ 0（ x1＝ 1就是主枝）， X6不可行并且 Z6＝ 10小于 Z3和 Z4，分枝停止并剪枝，分枝過程結(jié)束。整個計算過程可用圖3－ 2和表 。 分枝 (x2, x3, x4, x1) Zj 可行性 1 (1,1,1,1) √ √ 16 不可行 2 (0,0,1,1) √ √ √ 11 可行 3 (0,1,1,1) √ √ √ 14 可行 4 (1,0,1,1) √ √ √ 13 可行 5 (1,1,0,1) 11 不可行 6 (1,1,1,0) 10 不可行 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 43 2020年 6月 16日星期二 搜索到 3個可行解， 3個目標(biāo)值中 Z3最大，因此 X3是最優(yōu)解，轉(zhuǎn)換到原問題的最優(yōu)解為 X＝（ 1， 0， 1， 1），最優(yōu)值 Z＝ 14，計算結(jié)束。 圖 3－ 2 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 44 2020年 6月 16日星期二 【 例 】 用分枝－隱枚舉法求解下列 BIP問題 )()(4,3,2,11010354127264263m i n543215432154321bajxxxxxxxxxxxxxxxxZj??????????????????????，或解 （ 1）令 x2=1－ x39。2及 x5=1－ x39。5，代入模型后整理得 )()(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）求主枝。由于目標(biāo)函數(shù)求最小值，令所有變量等于零，得到主枝的解 X1＝（ 0， 0， 0， 0， 0）， Z1＝－ 7，檢驗約束條件知 X1不可行，進(jìn)行分枝。 （ 4）取 x1=1和 x1=0，分別其它變量等于“ 1”和 “ 0”分枝，判斷可行性，計算過程參見表 3－ 6及圖 3－ 3。 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 46 2020年 6月 16日星期二 分枝 j 上一分枝 Xj=(x1, x4, x39。2, x39。5, x3) Zj 可行性 1 2 3 4 5 主枝 1 1 1 1 (0,0,0,0,0) (0,1,0,0,0) (0,0,1,0,0) (0,0,0,1,0) (0,0,0,0,1) √ √ √ √ √ － 7 － 5 － 4 － 3 － 1 不可行 不可行 不可行 不可行 可行 6 7 8 9 10 1 6 6 6 6 (1,0,0,0,0) (1,1,0,0,0) (1,0,1,0,0) (1,0,0,1,0) (1,0,0,0,1) √ √ √ √ √ － 6 － 4 － 3 － 2 0 不可行 不可行 不可行 不可行 可行 表 3－ 6 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 47 2020年 6月 16日星期二 由表 3－ 6知，分枝 5和分枝 10兩個問題可行，分枝 5優(yōu)于分枝 10，其它不可行子問題盡管目標(biāo)值優(yōu)于分枝 5，由約束 ()知，繼續(xù)分枝不可能得到其它可行解，因此停止分枝，計算結(jié)束。分枝5的解 X5＝ (x1, x4, x39。2, x39。5, x3)＝（ 0， 0， 0， 0， 1），原 BIP的最優(yōu)解為 X＝ (x1, x2, x3, x4, x5)＝ (0， 1， 1， 0， 1),最優(yōu)值 Z＝－ 1。 圖 3－ 3 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 48 2020年 6月 16日星期二 在分枝－隱枚舉法的計算過程中，由于變量已經(jīng)按目標(biāo)函數(shù)系數(shù)從小到大重新排序，因此在選擇子問題分枝的原則是按排序后的變量順序分枝，但變量較多時搜索可行解的過程可能非常漫長。針對轉(zhuǎn)換后的目標(biāo)函數(shù)特征，極大值問題的解中“ 1”越多越優(yōu)，極小值問題的解中“ 0”越多越優(yōu)，因此在選擇變量分枝時盡可能采用避“ 0”或“ 1”的方法，請觀察表 3－ 8及 3－ 6. 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 49 2020年 6月 16日星期二 作業(yè)： P76 T 9， 10 01規(guī)劃的最優(yōu)解 －隱枚舉法求解 01規(guī)劃的最優(yōu)解 0－ 1規(guī)劃的求解 Solving BIP The End of Chapter 3 ???????????????3,2,11072462534m ax321321321jxxxxxxxxxxZj ，或＋??????????????????????????4,3,2,1107423422335434m i n4321432143214321jxxxxxxxxxxxxxxxxxZj，或(1) (2