【正文】 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 46 2020年 6月 16日星期二 分枝 j 上一分枝 Xj=(x1, x4, x39。計(jì)算步驟如下： （ 1）將 BIP問(wèn)題的目標(biāo)函數(shù)的系數(shù)化為非負(fù)，如 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)作代換 。 上述分枝過(guò)程可用下圖表示 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 無(wú)可行解 x2≥7 Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 24 2020年 6月 16日星期二 設(shè)純整數(shù)規(guī)劃 njxbxaxcZ jinjjijnjjj ,10ma x11????? ????且為整數(shù)， 松弛問(wèn)題 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日星期二 將 分離成一個(gè)整數(shù)與一個(gè)非負(fù)真分?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行為源行（來(lái)源行）的割平面，或分?jǐn)?shù)切割式，或 (高莫雷 )約束方程。 即兩種物品各裝 5件 ， 總價(jià)值 35元 。如果模型是線性的，稱為整數(shù)線性規(guī)劃。 （ 1）所裝物品不變； （ 2）如果選擇旅行箱，則只能裝載丙和丁兩種物品，價(jià)值分別是 4和 3，載重量和體積的約束為 2121????xxxx【 解 】 此問(wèn)題可以建立兩個(gè)整數(shù)規(guī)劃模型 ， 但用一個(gè)模型描述更簡(jiǎn)單 。所有變量為整數(shù)， X(1)就是 IP的最優(yōu)解。 （ 3）令 x2=0同時(shí)令 x3=0及 x3=1得到分枝 2和分枝 3， X2和 X3是可行解，分枝停止并保留，如表 38及圖 38所示。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－ 2 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 44 2020年 6月 16日星期二 【 例 】 用分枝－隱枚舉法求解下列 BIP問(wèn)題 )()(4,3,2,11010354127264263m i n543215432154321bajxxxxxxxxxxxxxxxxZj??????????????????????，或解 （ 1）令 x2=1－ x39。 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 37 2020年 6月 16日星期二 j Xj Zj j Xj Zj 1 (0,0,0,0) 9 (1,0,0,0) 2 (0,0,0,1) 10 (1,0,0,1) √ √ √ √ 11 3 (0,0,1,0) 11 (1,0,1,0) 4 (0,0,1,1) 12 (1,0,1,1) √ √ √ √ 14 5 (0,1,0,0) 13 (1,1,0,0) 6 (0,1,0,1) 14 (1,1,0,1) √ √ √ √ 13 7 (0,1,1,0) 15 (1,1,1,0) √ 8 (0,1,1,1) 16 (1,1,1,1) √ √ √ 表 3－ 5 (3) 由表 35知， BIP問(wèn)題的最優(yōu)解： X＝（ 1， 0， 1， 1），最優(yōu)值 Z＝ 14 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 38 2020年 6月 16日星期二 選擇不同的初始可行解，計(jì)算量會(huì)不一樣。當(dāng)約束條件是“ ≥ ” 符號(hào)時(shí)右端常數(shù)項(xiàng)應(yīng)為 iib My?（ 3) 對(duì)于 m個(gè) 條件中有 k（ ≤ m）個(gè)起作用時(shí)，約束條件寫(xiě)成 kmyMybxa kiiiinjjij ???? ???? 11， 整數(shù)規(guī)劃的數(shù)學(xué)模型 Mathematical Model of IP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 11 2020年 6月 16日星期二 【 例 】 試引入 0－ 1變量將下列各題分別表達(dá)為一般線性約束條件 （ 1） x1+x2≤6或 4x1+6x2≥10或 2x1+4x2≤20 （ 2）若 x1≤5，則 x2≥0，否則 x2≤8 （ 3） x2取值 0， 1， 3， 5， 7 【 解 】 （ 1） 3個(gè)約束只有 1個(gè)起作用 1 2 11 2 21 2 31 2 364 6 102 4 2020 1 1 , 2 , 3jx x y Mx x y Mx x y My y yyj? ? ? ??? ? ???? ? ???? ? ??? ???或 ， 整數(shù)規(guī)劃的數(shù)學(xué)模型 Mathematical Model of IP ??????????????????????????3,2,1101)1(2042)1(1064)1(6321321221121jyyyyMyxxMyxxMyxxj，或或 Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教