物流運(yùn)籌學(xué)——整數(shù)規(guī)劃(完整版)
【正文】 ??? 且 為 整 數(shù)其最優(yōu)解為 =（ 1,1）最優(yōu)值為 =1 割平面法的求解步驟 步驟 1：求解原問(wèn)題的松弛問(wèn)題，得最優(yōu)解，若滿足整數(shù)約束，則即為最優(yōu)解，否則進(jìn)入下一步； 步驟 2：分解其中一個(gè)非整分量，構(gòu)造一個(gè)新的線性約束條件，加入原松弛問(wèn)題中，形成新的線性規(guī)劃； 步驟 3：求解新線性規(guī)劃問(wèn)題，得，若為整數(shù)則為原問(wèn)題的最優(yōu)解，否則進(jìn)入步驟 2。設(shè) LP的最優(yōu)值為，則它是 IP最優(yōu)值的上界，任取 IP的一個(gè)可行解，對(duì)應(yīng)目標(biāo)值記為，它是的下界（初次下界可以取“”），即有： 分枝定界法求解步驟 步驟 4：解每一分枝，并根據(jù)不同情況采取以下步驟： （ 1）若無(wú)可行解，則將該分枝剪掉，不再考慮。 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? ? ?? ? ???? ? ??????????? ?? 或第四節(jié) 指派問(wèn)題 ? 指派問(wèn)題的標(biāo)準(zhǔn)形式 ? 價(jià)值系數(shù) ? ?, 1 , 2 , ,ijc i j n?? 效率矩陣 ? 決策變量 指派問(wèn)題求解 —— 匈牙利法 k推論：若將指派問(wèn)題的效率矩陣每一行及每一列分別減去各行及各列的最小元素，則得到的新指派問(wèn)題與原指派問(wèn)題有相同的最優(yōu)解。216。 ◎◎ √216。 ? 本章重點(diǎn)和難點(diǎn)是求解一般整數(shù)規(guī)劃的分枝定界法、割平面法原理與具體計(jì)算方法；標(biāo)準(zhǔn)指派問(wèn)題及其匈牙利解法；整數(shù)規(guī)劃在物流領(lǐng)域中的有效運(yùn)用。經(jīng)測(cè)算得每人完成各項(xiàng)任務(wù)時(shí)間如表 313所示。 ◎ 216。 （ 2）對(duì)打 √的行中，所有打 零元素所在的列打 √，如第 1列。 定理 1 設(shè)指派問(wèn)題的效率矩陣為 ，若將該矩陣的某一行 （或某一列）的各個(gè)元素都減去同一常數(shù) （ 可正可負(fù)），得到 新的效率矩陣
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1