物流運(yùn)籌學(xué)——整數(shù)規(guī)劃(編輯修改稿)
2025-06-18 21:27 本頁面
【文章內(nèi)容簡介】 1 2L P 2L P 1x 1 = 1 1 / 5x 2 = 6 / 5z 0 = 6 2 / 5無 可 行 解L P 1 2x 1 = 2x 2 = 1z 1 1 = 1 1分枝定界法求解步驟 步驟 1：求解原問題的松弛問題（用 LP表示），得最優(yōu)解，若滿足整數(shù)約束，則即為最優(yōu)解，否則進(jìn)入下步。 步驟 2：分枝。任選的一個不為整的分量，設(shè)為（其中為整數(shù)部分，為小數(shù)部分），據(jù)此得兩個約束條件，這樣就將 LP的可行域分割成兩個不相交的子集。將這兩個約束分別加入 LP得兩個新問題，即兩個分枝 LP1和 LP2。 步驟 3：定界。設(shè) LP的最優(yōu)值為，則它是 IP最優(yōu)值的上界，任取 IP的一個可行解，對應(yīng)目標(biāo)值記為，它是的下界（初次下界可以取“”），即有： 分枝定界法求解步驟 步驟 4：解每一分枝，并根據(jù)不同情況采取以下步驟： （ 1）若無可行解，則將該分枝剪掉，不再考慮。 （ 2）若是整數(shù)解且其最優(yōu)值，則該分枝的解就是原整數(shù)規(guī)劃問題的最優(yōu)解，結(jié)束。 （ 3）若是整數(shù)解，但最優(yōu)值，則取為新的下界，該枝關(guān)閉。 （ 4）若是非整數(shù)解且，則該分枝中不包含原問題的最優(yōu)解，該枝關(guān)閉。 （ 5）若是非整數(shù)解，且又是平行各分枝中的最大目標(biāo)函數(shù)值，則取為新的上界，同時將該枝視為新的 LP，回到步驟 2。 步驟 5：各分枝均已查清，對應(yīng)最優(yōu)目標(biāo)值的解即是原問題的最優(yōu)解。 第三節(jié) 0— 1規(guī)劃 ? 如果整數(shù)規(guī)劃問題中的所有決策變量僅限于取 0或者 1兩個值，則稱此問題為 0— 1整數(shù)規(guī)劃，簡稱 0— 1規(guī)劃，其變量稱為 0— 1變量。如果整數(shù)規(guī)劃問題中的部分決策變量為 0— 1變量，則稱為 0— 1混合整數(shù)規(guī)劃。 0— 1規(guī)劃 的求解 ? 列舉法 ? 隱枚舉法 隱枚舉法 1 2 31 2 31 2 312231 2 3( 0 )( 1)( 2)( 3 ) ( 4 ) m a x 3 2 52 2 4 4 3 4 6 , , 0 1z x x xx x xx x xxxxxx x x? ? ?? ? ???? ? ?????
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1