物流運(yùn)籌學(xué)——整數(shù)規(guī)劃(更新版)
【正文】 ，則以 為效率矩陣的新的指派問題與原指派問題的最優(yōu)解相同。 （ 3）若是整數(shù)解，但最優(yōu)值，則取為新的下界，該枝關(guān)閉。 分枝定界法 ? 基本思想：求原問題的對應(yīng)的松弛問題，其最優(yōu)解若不是原問題的可行解，則通過附加線性不等式約束（整型），將松弛問題分枝變?yōu)槿舾勺訂栴}，即對每一個非整變量附加兩個互相排斥（不交叉）的整型約束，即得兩個子問題，繼續(xù)求解定界，重復(fù)下去，直到得到最優(yōu)解為止。 技能目標(biāo) ? 能夠結(jié)合實際情況建立整數(shù)規(guī)劃模型，并可利用分枝 定界法求解； ? 能夠應(yīng)用 0— 1規(guī)劃建模并求解，安排人員工作。任選的一個不為整的分量，設(shè)為（其中為整數(shù)部分，為小數(shù)部分），據(jù)此得兩個約束條件，這樣就將 LP的可行域分割成兩個不相交的子集。 步驟 5：各分枝均已查清，對應(yīng)最優(yōu)目標(biāo)值的解即是原問題的最優(yōu)解。216。 （ 5）對未打 √的每一行劃一直線，如第 5行。 1 3 11 80 6 6 21 2 1 01 0 5 41 2 3 4??????????◎◎◎◎◎1 3 0 11 80 0 6 6 20 1 2 1 01 0 5 0 41 2 3 4 0???????????????????????????61012961081476781296101417971215784C最優(yōu)指派方案是：讓小組 1完成任務(wù) 3；小組 2完成任務(wù) 2；小組 3完成任務(wù) 1；小組 4完成任務(wù) 4；小組 5完成任務(wù) 5 總成本 7＋ 9＋ 6＋ 6＋ 6=34 非標(biāo)準(zhǔn)形式的指派問題 ? 最大化指派問題 ? 人數(shù)和工作數(shù)不等 ? 某事一定不能由某人來做 ? 一個人可做幾件事 第五節(jié) 物流資源分配問題 本章小結(jié) ? 本章在線性規(guī)劃的基礎(chǔ)上，結(jié)合物流問題實際，提出了決策變量部分或者全部限制為整數(shù)時的一般線性整數(shù)規(guī)劃問題，通過與相應(yīng)的線性規(guī)劃進(jìn)行比較，說明了整數(shù)規(guī)劃問題需要探求新的求解方法，接著重點(diǎn)闡述了求解整數(shù)規(guī)劃問題的兩類基本方法：割平面法與分枝定界法。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1