整數(shù)規(guī)劃 割平面法 分枝定界法-文庫吧
2025-04-22 15:38 本頁面
【正文】 分枝定界法 。 167。 2 割平面法 割平面法是 1958年美國學者 純 整數(shù)規(guī)劃的一種比較簡便的方法，其基本思想是：先不考慮變量的整數(shù)限制求解線性規(guī)劃，如果得到的解不是整數(shù)解，則不斷增加適當?shù)募s束，割掉原可行域不含整數(shù)解的一部分，最終得到一個具有若干整數(shù)頂點的可行域，而這些頂點中恰有一個頂點是原問題的整數(shù)解。 割平面法的基本步驟： 步驟 1 不考慮變量的整數(shù)限制，求解相應的線性規(guī)劃問題，如果該問題無解，或最優(yōu)解已是整數(shù)解，則停止計算，否則轉(zhuǎn)下一步。 步驟 2 對上述線性規(guī)劃的可行域進行 “ 切割 ” ，去掉不含整數(shù)解的一部分可行域，即增加適當?shù)木€性約束，然后轉(zhuǎn)步驟 1。 割平面法的關(guān)鍵在于如何確定切割方程，使之能對可行域進行真正的切割，而且切去部分不含有整數(shù)解點。 下面討論切割方程的求法。 設(shè)與整數(shù)規(guī)劃相對應的線性規(guī)劃最優(yōu)解中基變量 XBi=（ B1b)i不是整數(shù)，將最優(yōu)單純形表中該基變量對應的行還原成約束方程，即 XBi +ΣaijXj=（ B1b)i ⑴ 將（ B1b)i， aij都分解成整數(shù)與非負真分數(shù)之和的形式，即 （ B1b)i=Ni+fi 其中 0＜ fi ＜ 1 ⑵ aij=Nij+fij 其中 0≤ fij ＜ 1 ⑶ 這里 Ni、 Nij是整數(shù)，將⑵、 ⑶代入 ⑴， 得 XBi +Σ（ Nij+fij） Xj=Ni+fi 即 XBi +ΣNijXjNi=fiΣfijXj ⑷ 當諸 Xi都是整數(shù)時， ⑷ 式左端是整數(shù)，所以右端亦應是整數(shù)，但右端是兩個正數(shù)之差，且 ∵ 0＜ fi ＜ 1， ∴ fiΣfijXj是小于 1的整數(shù)，從 從而 fiΣfijXj≤0 ⑸ ?、墒阶鳛榍懈罘匠?。因為任何整數(shù)可行解都滿足這個方程，所以把它加到原問題的約束中，它能夠?qū)υ尚杏蜻M行切割，而不會切割掉整數(shù)解。 例 3 用割平面法求解 maxZ=x1+x2 x1+x2≤1 3x1+x2≤4 x1,x2≥0， 整數(shù) 解：將問題標準化得 maxZ=x1+x2 ⑴ x1+x2+x3 =1 ⑵ 3x1+x2+x4=4 ⑶ x1,x2≥
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1