【正文】 制作與教學 武漢 理工大學 管理學院 熊偉 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) 。 （ 4）取 x1=1和 x1=0，分別其它變量等于“ 1”和 “ 0”分枝，判斷可行性，計算過程參見表 3－ 6及圖 3－ 3。令 x2= x3=1， x4取“ 0”和“ 1”得到分枝 5和 6，分枝 5不可行并且 Z5＝ 11小于 Z3和 Z4，分枝停止并剪枝。 分枝－隱枚舉法求解 BIP問題 將分枝定界法與隱枚舉法結(jié)合起來用，得到分枝－隱枚舉法。 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming 表 3－ 4 如果在對偶單純形法中原切割方程的松弛變量仍為基變量，則此松弛變量所在列化為單位向量后就可以去掉該行該列，再切割。 ????????????且均取整數(shù),0,34m a x21212121xxxxxxxxZ 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學 武漢 理工大學 管理學院 熊偉 Page 19 2020年 6月 16日星期二 10 21 ?? xx 21 ?? xx松弛問題 LP0的最優(yōu)解X=(,),Z0= x1 x2 o A B C 10 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming 10 10 x1 x2 o A B C ???????????????0,3:134m ax211212121xxxxxxxLPxxZLP1 LP2 3 4 LP1:X=(3,),Z1= LP2:X=(4,),Z2= ???????????????0,4:234m ax211212121xxxxxxxLPxxZ得到兩個線性規(guī)劃及增加約束 43 11 ?? xx① ② 10 10 x1 x2 o A B C LP1 LP3 3 4 LP3:X=(,6),Z3= ????????????????0,64:334m ax2121212121xxxxxxxxLPxxZ，不可行，得到線性規(guī)劃，顯然及進行分枝，增加約束選擇目標值最大的分枝7762222 ??? xxxLP6 ① ② 不可行72 ?xLP1:X=(3,),Z1= 10 10 x1 x2 o A C LP1 3 4 可行域是一條線段即，,40,464:434m a x121121212121??????????????????xxxxxxxxxxLPxxZ：及，到線性規(guī)劃及進行分枝，增加約束，選擇由于545431113LPLPxxLPZZ???6 ① ② ????????????????0,65:534m ax2121212121xxxxxxxxLPxxZ，LP4:X=(4,6),Z4=34 LP5:X=(5,5),Z5=35 5 LP1:X=(3,),Z1= LP3 LP5 盡管 LP1的解中 x1不為整數(shù)，但 Z5Z因此 LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學 武漢 理工大學 管理學院 熊偉 Page 8 2020年 6月 16日星期二 （ 1） 由于所裝物品不變 ， 式 ()約束左邊不變 ， 整數(shù)規(guī)劃數(shù)學模型為 ???????????????????2,110,0134m ax212121212121iyxyyyyxxyyxxxxZii或且取整數(shù)＋（ 2） 由于不同載體所裝物品不一樣 ， 數(shù)學模型為 121 2 21 2 11 2 21 2 11212m a x 4 31 .2 0 .8 1 0 ( )1 .8 0 .6 1 2 ( )2 2 .5 2 5 ( )1 .5 2 2 0 ( )1, 0 , , 0 1Z x xx x My ax x My bx x My cx x My dyyx x y??????? ? ??? ? ? ???? ? ??? ???????＋且 均 取 整 數(shù) 或 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學 武漢 理工大學 管理學院 熊偉 Page 9 2020年 6月 16日星期二 式中 M為充分大的正數(shù) 。 實際上問題的最優(yōu)解是 （ 5， 5） ， Z=35。 很多實際規(guī)劃問題都屬于整數(shù)規(guī)劃問題 1. 變量是人數(shù)、機器設備臺數(shù)或產(chǎn)品件數(shù)等都要求是整數(shù) 2. 對某一個項目要不要投資的決策問題，可選用一個邏輯變量 x，當 x=1表示投資， x=0表示不投資； 3. 人員的合理安排問題，當變量 xij=1表示安排第 i人去做 j工作，xij=0表示不安排第 i人去做 j工作。本章只討論整數(shù)線性規(guī)劃。 用湊整法來解時需要比較四種組合 ， 但 （ 4， 7） 、 （ 4， 8） （ 3， 8） 都不是可行解 ， （ 3，7） 雖屬可行解 ， 但代入目標函數(shù)得 Z=33,并非最優(yōu) 。 引入 0－ 1變量 （ 或稱邏輯變量 ） yi， 令 2,10,1 ????? iiiyi 種方式裝載時不采用第，種方式裝載時采用第i=1,2分別是采用背包及旅行箱裝載 。 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學 武漢 理工大學 管理學院 熊偉 Page 18 2020年 6月 16日星期二 【 例 】 用分枝定界法求解例 【 解 】 先求對應的松弛問題（記為 LP0）： ????????????0,:034m a x21212121xxxxxxLPxxZ用圖解法得到最優(yōu)解 X＝ （ ,） ,Z0=,如下圖所示 。如果不是整數(shù)解，需要繼續(xù)切割，重復上述計算過程。 在表 3－ 7的計算過程中，當目標值等于 14時，將其下界 11改為 14，可以減少計算量。 0－ 1規(guī)劃的求解 Solving BIP Ch3 整數(shù)規(guī)劃 Integer Programming 制作與教學 武漢 理工大學 管理學院 熊偉 Page 42 2020年 6月 16日星期二 表 令