整數(shù)規(guī)劃割平面法分枝定界法-資料下載頁
2025-05-12 15:38本頁面
【正文】 行域，將原可行域 D變?yōu)?D D2兩部分（如圖）。 4 D1 D2 求解線性規(guī)劃 L L2 得最優(yōu)解為： 問題 L1： L+ x1≤4 問題 L2： L+ x1≥5 x1= x2= Z1=349 x1= x2= Z2=341 因為沒有得到整數(shù)解，所以繼續(xù)對 L1進行分解，增加約束： x2≤2 ， x2≥3 將 L1分解成問題 L3與 L4，并求得最優(yōu)解如下： 問題 L3： L1+ x2≤2 問題 L4： L1+x2≥3 x1=， x2= Z3=340 x1=， x2= Z4=327 問題 L3的解已是整數(shù)解，它的目標值 Z3=340， 大于問題 L4的目標值，所以問題 L4已無必要再分枝。但由于問題 L2的目標值 Z2大于 Z3， 分解L2還有可能產(chǎn)生更好的整數(shù)解，因此繼續(xù)對 L2分枝。增加約束 x2≤1 ， x2≥2 將 L2分解成問題 L5與 L6，并求解，結(jié)果如下： 問題 L5： L2+ x2≤1 問題 L6： L2+x2≥2 x1=， x2= Z5=308 無可行解 問題 L5的 Z5 =308＜ Z3=340 ，所以不必分解了；問題 L6無可行解，于是可以斷定問題 L3的解： x1=， x2=。 整個分枝定界過程如下圖所示： 356,0 ?? ZZ問題 L Z0=356 x1== 問題 L1 Z1=349 x1=， x2= 問題 L2 Z2=341 x1=， x2= 問題 L3 Z3=340 x1= x2= 問題 L4 Z4=327 x1= x2= 問題 L5 Z5=308 x1=， x2= 問題 L6 無可行解 349,0 ?? ZZ341,340 ?? ZZx1≤4 x1≥5 x2≤2 x2≥3 x2≤1 x2≥2 Z※ =340 用分枝定界法求解整數(shù)規(guī)劃的步驟可總結(jié)如下： 步驟 1：求解與整數(shù)規(guī)劃相對應(yīng)的線性規(guī)劃 L， 若 L無可行解，則整數(shù)規(guī)劃也沒有可行解，計算停；若 L的最優(yōu)解是整數(shù)解，則該解即為整數(shù)規(guī)劃的最優(yōu)解，計算停；若 L的最優(yōu)解不是整數(shù)解，則轉(zhuǎn)步驟 2。 步驟 2（分枝）在 L的最優(yōu)解中任選一個不符合整數(shù)條件的變量XBi， 其值為（ B1b)i， [（ B1b)i ]為小于（ B1b)i的最大整數(shù)，構(gòu)造兩個約束條件 XBi ≤ [（ B1b)i ]和 XBi≥ [（ B1b)i ] +1 將這兩個約束條件分別加在問題 L的約束條件上，形成兩個子問題L1和 L2， 并求解 L1和 L2 。 步驟 3（定界 ）取整數(shù)解中最大目標值為界限值 Z(下界 )，如果計算中尚無整數(shù)解，則取 Z=∞ 。 檢查分枝 Li， 若它的最優(yōu)解不是整數(shù)解，且 Zi＞ Z， 則重復(fù)步驟 2，若 Zi≤Z ， 則 Li不再分枝。 重復(fù)步驟 步驟 3，直至所有分枝都不能再分解為止，這時界限值 Z對應(yīng)的整數(shù)解即為原問題的最優(yōu)解。 用分枝定界法可解純整數(shù)規(guī)劃問題和混合整數(shù)規(guī)劃問題。它比窮舉法優(yōu)越，因為它僅在一部分可行的整數(shù)解中尋求最優(yōu)解，計算量比窮舉法小。若變量數(shù)目很大，其計算工作量也是相當可觀的。
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1