物流運籌學(xué)——整數(shù)規(guī)劃-在線瀏覽
2025-07-16 21:27本頁面
【正文】 利解法。 技能目標 ? 能夠結(jié)合實際情況建立整數(shù)規(guī)劃模型，并可利用分枝 定界法求解； ? 能夠應(yīng)用 0— 1規(guī)劃建模并求解，安排人員工作。其本質(zhì)是利用線性規(guī)劃的求解方法逐步縮小可行域，最后找到整數(shù)規(guī)劃的最優(yōu)解。 ? 按某非整分量構(gòu)造的約束條件需滿足以下兩個條件： ? （ 1）當前最優(yōu)解不滿足該約束，即使得該最優(yōu)解不會再出現(xiàn)在松弛問題可行解中； ? （ 2）所有整數(shù)可行解均滿足該約束，即新增約束條件后，仍保留了原松弛問題的所有整數(shù)解。 例 37 用分枝定界法求解： 12121212m a x 4 34 10. . 2 3 8,0z x xxxs t x xxx???????????? 且 均 為 整 數(shù)01 1 6( , )55x ? 0625z ?12121212m a x 4 34 10. . 2 3 8,0z x xxxs t x xxx?????????? ?? 且 均 為 整 數(shù)01 1 6( , )55x ? 0625z ?L PL P 1 1x 1 = 9 / 4x 2 = 1z 2 = 1 2x 1 = 9 / 4x 2 = 1z 1 = 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)解，否則進入下步。任選的一個不為整的分量，設(shè)為（其中為整數(shù)部分，為小數(shù)部分），據(jù)此得兩個約束條件，這樣就將 LP的可行域分割成兩個不相交的子集。 步驟 3：定界。 （ 2）若是整數(shù)解且其最優(yōu)值，則該分枝的解就是原整數(shù)規(guī)劃問題的最優(yōu)解，結(jié)束。 （ 4）若是非整數(shù)解且，則該分枝中不包含原問題的最優(yōu)解，該枝關(guān)閉。 步驟 5：各分枝均已查清，對應(yīng)最優(yōu)目標值的解即是原問題的最優(yōu)解。如果整數(shù)規(guī)劃問題中的部分決策變量為 0— 1變量，則稱為 0— 1混合整數(shù)規(guī)劃。 定義：在效率矩
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1