物流運籌學——整數(shù)規(guī)劃(參考版)
2025-05-17 21:27本頁面
【正文】 試確定總花費時間為最少的指派方案。經(jīng)測算得每人完成各項任務(wù)時間如表 313所示。 ? 本章重點和難點是求解一般整數(shù)規(guī)劃的分枝定界法、割平面法原理與具體計算方法；標準指派問題及其匈牙利解法；整數(shù)規(guī)劃在物流領(lǐng)域中的有效運用。作為整數(shù)規(guī)劃的特例，專門討論了決策變量僅取 0、 1兩個值時相應(yīng)整數(shù)規(guī)劃及其求解方法。 ◎√在未被直線覆蓋過的元素中找最小元素，將打 √行的各元素減去這個最小元素，將打 √列的各元素加上這個最小元素（以避免打 √行中出現(xiàn)負元素），這樣就增加了零元素的個數(shù)。 ◎ 216。 ◎◎ √216。對已打 √的每一列劃一縱線，如第 1列，既得到覆蓋當前 0元素的最少直線數(shù)。 （ 4）重復上述（ 2）、（ 3）步，直到不能進一步打 √為止。 （ 2）對打 √的行中，所有打 零元素所在的列打 √，如第 1列。216。216。 ? ?ij nnCc ??k()ij n nCc ???? C?k每行減掉其所在行最小值，然后每列再減其所在列最小值 指派 指派方案 最優(yōu)值為 5＋ 6＋ 6＋ 5=22 例 312 ?????????????????61012961081476781296101417971215784C3 11 81 7 7 32 3 2 1542 3 4C??????? ?????216。 定理 1 設(shè)指派問題的效率矩陣為 ，若將該矩陣的某一行 （或某一列）的各個元素都減去同一常數(shù) （ 可正可負），得到 新的效率矩陣 ，則以 為效率矩陣的新的指派問題與原指派問題的最優(yōu)解相同。 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
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1