【正文】 變量kkkikii xxabx ??? 求解 IP的割平面法 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 25 2020年 6月 16日星期二 將 分離成一個整數(shù)與一個非負(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行為源行（來源行）的割平面，或分?jǐn)?shù)切割式，或 (高莫雷 )約束方程。選擇表 33的第一行 (也可以選第二行 )為源行 252141431 ??? xxx 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Cj 4 3 0 0 b CB XB x1 x2 x3 x4 4 3 x1 x2 1 0 0 1 1/4 － 1/8 － 1/2 3/4 5/2 15/4 λj 0 0 － 5/8 － 1/4 表 33 Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 30 2020年 6月 16日星期二 分離系數(shù)后改寫成 212)211(41431 ?????? xxx02141212 4341 ?????? xxxx加入松弛變量 x5得到高莫雷約束方程 22 543 ????? xxx將式 ()作為約束條件添加到表 3－ 3中，用對偶單純形法計算，如表 3－ 4所示 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 31 2020年 6月 16日星期二 Cj 4 3 0 0 0 b CB XB x1 x2 x3 x4 x5 4 3 0 x1 x2 x5 1 0 0 0 1 0 1/4 － 1/8 － 1 － 1/2 3/4 [－ 2] 0 0 1 5/2 15/4 － 2→ λj 0 0 － 5/8 － 1/4↑ 0 4 3 0 x1 x2 x4 1 0 0 0 1 0 1/2 － 1/2 1/2 0 0 1 － 1/4 3/8 － 1/2 3 3 1 λj 0 0 － 1/2 0 － 1/8 最優(yōu)解 X(1)＝ (3， 3)，最優(yōu)值 Z＝ 21。 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的任意組合時 ，第一個約束滿足 ， 說明第一個約束沒有約束力 ， 是多余的 ，從約束條件中去掉 。一般地，當(dāng)目標(biāo)函數(shù)求最大值時，首先考慮目標(biāo)函數(shù)系數(shù)最大的變量等于 1，如例 。計算步驟如下： （ 1）將 BIP問題的目標(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)作代換 。 【 例 】 用分枝－隱枚舉法求解下列 BIP問題 )()()(4,3,2,110105423246535326m a x4321432143214321cbajxxxxxxxxxxxxxxxxxZj?????????????????????????，或 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 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)行分枝。注意到分枝 6， x4＝ 1時只有 x1＝ 0（ x1＝ 1就是主枝）， X6不可行并且 Z6＝ 10小于 Z3和 Z4，分枝停止并剪枝，分枝過程結(jié)束。2及 x5=1－ x39。 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學(xué) 武漢 理工大學(xué) 管理學(xué)院 熊偉 Page 46 2020年 6月 16日星期二 分枝 j 上一分枝 Xj=(x1, x4, x39。2, x3