【正文】 x2=1同時令 x3=0得到分枝 4， X4是可行解，分枝停止并保留。由于目標(biāo)函數(shù)求最小值，令所有變量等于零，得到主枝的解 X1＝（ 0， 0， 0， 0， 0）， Z1＝－ 7，檢驗約束條件知 X1不可行，進(jìn)行分枝。 圖 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ù)從小到大重新排序，因此在選擇子問題分枝的原則是按排序后的變量順序分枝，但變量較多時搜索可行解的過程可能非常漫長。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é)束。 分枝 (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é)束。 分枝－隱枚舉法是從非可行解中進(jìn)行分枝搜索可行解，第（ 1）步到第（ 3）步用了隱枚舉法的思路，第（ 4）步用了分枝定界法的思路。 首先判斷式 （ ） 是否滿足 ， 如果滿足 ， 接下來判斷其它約束 ， 否則認(rèn)為不可行 ， 計算過程見表 3－ 7所示 。 0?? ? kkiki xff則 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 27 2020年 6月 16日星期二 ?????????324313322354613651xxxxxx例如， 324653651 1)1( ?????? xxxx1行： 移項： 4653653241 1 xxxx ?????令 046536532 ??? xx加入松弛變量 s1得 324653651 ???? xxs同理，對于 x2行有： 324313312 ???? xxs 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 28 2020年 6月 16日星期二 【 例 】 用割平面法求解下列 IP問題 ????????????且為整數(shù)0,102304634m a x21212121xxxxxxxxZ【 解 】 放寬變量約束，對應(yīng)的松弛問題是 ????????????0,102304634m a x21212121xxxxxxxxZ 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 29 2020年 6月 16日星期二 加入松弛變量 x3及 x4后，用單純形法求解，得到最優(yōu)表 33。 整數(shù)規(guī)劃的數(shù)學(xué)模型 Mathematical Model of IP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 10 2020年 6月 16日星期二 （ 1)右端常數(shù)是 k個值中的一個時，類似式 ()的約束條件為 1111?? ??????kiikiiinjjij yybxa ，（ 2)對于 m組 條件中有 k（ ≤ m）組起作用時， 類似式 ()的約束條件寫成 111??? ????kiiiinjjij yMybxa ，這里 yi=1表示第 i組約束不起作用（如 y1=1式 ()、 ()不起作用）， yi=0表示第 i個約束起作用。 還有些問題用線性規(guī)劃數(shù)學(xué)模型無法描述 ， 但可以通過設(shè)置邏輯變量建立起整數(shù)規(guī)劃的數(shù)學(xué)模型 。 他準(zhǔn)備用來裝甲 、 乙兩種物品 ， 每件物品的重量 、 體積和價值如表 31所示 。 整數(shù)規(guī)劃數(shù)學(xué)模型 Mathematical Model of IP 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming 0－ 1規(guī)劃的求解 Solving Binary Integer Programming Chapter 3 整數(shù)規(guī)劃 Integer Programming 運籌學(xué) Operations Research 整數(shù)規(guī)劃數(shù)學(xué)模型 Mathematical Model of IP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 3 2020年 6月 16日星期二 一個規(guī)劃問題中要求部分或全部決策變量是整數(shù)，則這個規(guī)劃稱為整數(shù)規(guī)劃。 問兩種物品各裝多少件 ， 所裝物品的總價值最大 ？ 表 31 【 解 】 設(shè)甲 、 乙兩種物品各裝 x x2件 ， 則數(shù)學(xué)模型為： ????????????且均取整數(shù),0,34m a x21212121xxxxxxxxZ() 整數(shù)規(guī)劃的數(shù)學(xué)模型 Mathematical Model of IP 物品 重量 （公斤 /每件） 體積 （ m3/每件） 價值 (元 /每件 ) 甲 乙 4 3 Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 5 2020年 6月 16日星期二 如果不考慮 x x2取整數(shù)的約束 （ 稱為 （ ） 的松弛問題 ）