物流運(yùn)籌學(xué)——整數(shù)規(guī)劃(文件)
【正文】 ? ? ?? ? ???? ? ??????????? ?? 或第四節(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)解。 ? ?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。216。 （ 4）重復(fù)上述（ 2）、（ 3）步，直到不能進(jìn)一步打 √為止。 ◎◎ √216。 ◎√在未被直線覆蓋過(guò)的元素中找最小元素，將打 √行的各元素減去這個(gè)最小元素，將打 √列的各元素加上這個(gè)最小元素（以避免打 √行中出現(xiàn)負(fù)元素），這樣就增加了零元素的個(gè)數(shù)。 ? 本章重點(diǎn)和難點(diǎn)是求解一般整數(shù)規(guī)劃的分枝定界法、割平面法原理與具體計(jì)算方法；標(biāo)準(zhǔn)指派問(wèn)題及其匈牙利解法；整數(shù)規(guī)劃在物流領(lǐng)域中的有效運(yùn)用。試確定總花費(fèi)時(shí)間為最少的指派方案。經(jīng)測(cè)算得每人完成各項(xiàng)任務(wù)時(shí)間如表 313所示。作為整數(shù)規(guī)劃的特例，專門討論了決策變量?jī)H取 0、 1兩個(gè)值時(shí)相應(yīng)整數(shù)規(guī)劃及其求解方法。 ◎ 216。對(duì)已打 √的每一列劃一縱線，如第 1列，既得到覆蓋當(dāng)前 0元素的最少直線數(shù)。 （ 2）對(duì)打 √的行中，所有打 零元素所在的列打 √，如第 1列。216。 定理 1 設(shè)指派問(wèn)題的效率矩陣為 ，若將該矩陣的某一行 （或某一列）的各個(gè)元素都減去同一常數(shù) （ 可正可負(fù)），得到 新的效率矩陣 ，則以 為效率矩
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1