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