【正文】 2 14 14 13 19 15 15 60 30 20 10 3 19 19 20 23 M M 50 20 30 4 M 0 M 0 M 0 50 30 20 30 20 70 30 10 50 210 經(jīng)過(guò)數(shù)次換基后得到問(wèn)題的最優(yōu)解 : 12 22 24 315 , 20 , 40 , x x x? ? ? ? 某類物資有 個(gè)產(chǎn)地 , 產(chǎn)地 的產(chǎn)地為 m,iaiA對(duì)該類物 資有 個(gè)需求點(diǎn) , 第 個(gè)需求點(diǎn)的需求量為 n j.jb 從產(chǎn)地到達(dá)需求點(diǎn)都需經(jīng)過(guò) 個(gè)中轉(zhuǎn)站中的某個(gè)中轉(zhuǎn) p站 . 啟動(dòng)第 個(gè)中轉(zhuǎn)站將發(fā)生固定費(fèi)用 k,kf相應(yīng)的單位 費(fèi)用分別為 ,.ik kjcd 求運(yùn)輸方案 , 使總運(yùn)費(fèi)為最小 . 中轉(zhuǎn)站的最大轉(zhuǎn)運(yùn)量為 .kc 引入 變量 01?,1kkxx ? ,ik kjxy表示啟用第 個(gè)中轉(zhuǎn)站 , k表示經(jīng)過(guò)從 個(gè)產(chǎn)地到第 個(gè)中轉(zhuǎn)站及從第 個(gè)中轉(zhuǎn)站到 i k k第 個(gè)需求點(diǎn)的運(yùn)輸量 , 則問(wèn)題的目標(biāo)函數(shù)為 j1 1 1 1 1,p p pmnk k i k i k k j k jk i k k jz f x c x d y? ? ? ? ?? ? ?? ? ? ? ?產(chǎn)量限制 : ? ?1, 1 , 2 , ,pi k ikx a i m????? ?1, 1 , 2 , ,mi k k kix c x k p???? 中轉(zhuǎn)站能力限制 : 需求量限制： ? ?1, 1 , 2 , ,pk j jky b j n???? 供需平衡限制 : ? ?11. 1 , 2 , ,mni k k jijx y k p?????? 由此得到該問(wèn)題的數(shù)學(xué)模型 : 1 1 1 1 1m i n ,p p pmnk k i k i k k j k jk i k k jz f x c x d y? ? ? ? ?? ? ?? ? ? ? ?? ?? ?? ?? ?11111, 1 , 2 , , 1 , 2 , , 1 , 2 , ,. 1 , 2 , ,pik ikmik k kipk j jkmnik k jijx a i mx c x k py b j nx y k p???????????????????????????????? ?0 1 , 1 , 2 , ,0 , 0.kik k jx k pxy? ? ? ???????四、指派問(wèn)題 問(wèn)題 設(shè)有 項(xiàng)工作 , 交給 個(gè)人去完成 . 每個(gè)人只能 n n 如此的問(wèn)題即稱為 指派問(wèn)題 . 完成其中的一項(xiàng) . 又每人完成其中任何一項(xiàng)工作的代價(jià) 為已知 , 求這樣的任務(wù)分配方案 , 使完成這些工作的總 代價(jià)為最小 . 以 表示第 人完成第 項(xiàng)工作所需的代價(jià) , 由此得 ijc i j1 1 1 2 12 1 2 2 212.nnn n n nc c cc c cCc c c??????????? 如此的矩陣稱為指派問(wèn)題中的 代價(jià)矩陣 . 到矩陣 : 引入決策變量 : ijx10ijx????第 人完成第 項(xiàng)工作 。 i j第 項(xiàng)工作由其他人完成 . j由此得到矩陣 注意到 : 由于每項(xiàng)工作只能由 ? ?.ijXx?一人完成及每人只能完成一項(xiàng)工作 , 故在矩陣中每行和 每列只能有一個(gè) 1, 其余均為 0. 如此的矩陣稱為指派問(wèn)題中的 指派矩陣 . 例 17 設(shè)指派問(wèn)題中的代價(jià)矩陣為 1 5 1 8 1 2 1 11 3 1 6 1 0 9,1 3 1 7 1 0 81 1 1 8 8 9C???????????則下列矩陣 121 0 0 0 0 1 0 00 1 0 0 1 0 0 0,0 0 1 0 0 0 0 10 0 0 1 0 0 1 0XX? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ?? ? ? ?均為指派矩陣 , 其代價(jià)分別為 而矩陣 50,47.31 0 0 00 1 0 0,0 0 0 10 0 0 1X?????????????則不是指派矩陣 . 所謂求解指派問(wèn)題的最小值解 , 即為求解這樣的矩陣 , 使對(duì)應(yīng)的代價(jià)為最小 . 分析 條件 : 矩陣中每行每列的元素只有一個(gè)是 1, 其余均為 11 1 , 2 , , .nijjx i n????行 : 列 : 11 1 , 2 , , .nijix j n????0 1 .ij ijxx? ? ?零的數(shù)學(xué)表達(dá)式為 : ,1.nij ijijz c x?? ?由此得到問(wèn)題的模型為 : 而相應(yīng)的代價(jià)為 111 1 , 2 , , .1 1 , 2 , , .nijjnijix i nx j n???????????????.min,1.nij ijijz c x?? ?0 1 . , 1 , 2 , , .i j i jx x i j n? ? ? ? 設(shè)代價(jià)矩陣為 我們用下面的方法求其最 ? ? ,ij nnCc? ⑴ 每行減去該行的最小數(shù) 。 ⑵ 每列減去該列的最小數(shù) 。 每行每列至少一個(gè)零 . ⑶ 判斷是否有 個(gè)獨(dú)立的零 , 若有 , 則在指派矩陣中 , n小值解 : 相應(yīng)元素取 1, 其余為 0. 所謂有 個(gè)獨(dú)立的零 , 即指這些零應(yīng)分布在不同的行 n判斷方法 : 用最少的橫線和豎線將所有的零劃去 , 若最 列上 . ,n n少的線數(shù)為 則一定有 個(gè)獨(dú)立的零 . 例 18 求下面指派問(wèn)題中的最小值解 . 2 7 2 2 2 52 0 2 8 2 6 .2 8 3 2 3 0C?????????解 2 7 2 2 2 52 0 2 8 2 62 8 3 2 3 0行 5 0 30 8 6042列 5010 8 40 4 0注意到在最后表中 , 每行每列都有零的存在 . 5010 8 40 4 0 在下面矩陣中 , 選獨(dú)立的零 : 則問(wèn)題的最優(yōu)解為 其余 1 2 2 1 3 3 1,x x x? ? ? ?√ √ √ 即相應(yīng)的指派矩陣為 0 1 01 0 0 ,0 0 1X?????????最小代價(jià)為 2 2 2 0 3 0 7 2 .z ? ? ? ?例 19 求下面指派問(wèn)題的最小值解 : 1 4 1 7 1 8 2 01 2 1 5 1 9 2 01 6 1 7 2 0 1 81 9 2 1 2 0 2 3C?????????解 1 4 1 7 1 8 2 01 2 1 5 1 9 2 01 6 1 7 2 0 1 81 9 2 1 2 0 2 3行 0 3 4 60 3 7 80 1 4 20 2 1 4列 0 2 3 40 2 6 60 0 3 00 1 0 2注意到 , 對(duì)表 0 2 3 40 2 6 60 0 3 00 1 0 2可以用 3條線將所有的零劃去 , 因而沒(méi)有 4個(gè)獨(dú)立的零 . 對(duì)此我們有下面的迭代次序 : ⑴ 在所有未劃去的數(shù)中找最小數(shù) 。 ⑵ 未劃去的數(shù)減去該數(shù) 。 ⑶ 交叉點(diǎn)加上該數(shù) , 其余不變 。 ⑷ 繼續(xù)判定 . 在上例中 : 0 2 3 40 2 6 60 0 3 00 1 0 2最小數(shù)為 2, 由此得 : 0 0 1 20 0 4 42 0 3 02 1 0 2此時(shí)有 4個(gè)獨(dú)立的零 , 12 21 34 43 1,x x x x? ? ? ?√ √ √ √ 因而最優(yōu)解為 其余 最小代價(jià)為 ? ?注意到該問(wèn)題的最優(yōu)解是不唯一的 . 但最小值相同 . 2 0 2 4 2 2 2 63 4 3 6 4 0 3 9.3 8 3 1 3 5 3 21 2 1 8 1 7 1 6C???????????例 20 求指派問(wèn)題的最小值解 : 解 0 4 2 60 2 6 57 0 4 10 6 5 4行 20 24 22 2634 36 40 3938 31 35 3212 18 17 16列 0 4 0 50 2 4 47 0 2 00 6 3 30 4 0 50 2 4 47 0 2 00 6 3 3最小數(shù)為 2, 繼續(xù)迭代 2 4 0 50 0 2 29 0 2 00 4 1 1最優(yōu)解為 其余 最小 13 22 34 41 1,x x x x? ? ? ? ?√ √ √ √ 代價(jià)為 ? ⑴ 的指派問(wèn)題 mn? 所謂 的指派問(wèn)題是指工作數(shù)與工人數(shù)不相等的 mn?指派問(wèn)題 . 相應(yīng)的解決方法是虛擬工作數(shù)或工人數(shù) , 以 達(dá)到平衡 . 相應(yīng)的代價(jià)為 0. 例 21 求下面指派問(wèn)題的最小值解 : 25 29 31 4222 19 35 1839 38 26 2034 37 28 4024 42 36 23C???????????解 此時(shí) 故添加 0列 . 有下表 5 , 4 ,mn??25 29 31 42 022 19 35 18 039 38 26 20 034 37 28 40 024 42 36 23 0再由列縮減法 , 得 25 29 31 42 022 19 35 18 039 38 26 20 034 37 28 40 024 42 36 23 0列 3 1 0 5 2 4 00 0 9 0 01 7 1 9 0 2 01 2 1 8 2 2 2 02 2 3 1 0 5 0最小數(shù)為 2, 繼續(xù) , 則有下表 1 8 5 2 2 00 0 1 1 0 21 5 1 7 0 0 01 0 1 6 2 2 0 00 2 1 1 0 3 0最小數(shù)為 2, 繼續(xù)迭代 : 1 6 3 2 0 02 0 1 1 0 41 7 1 7 0 0 21 0 1 4 0 1 8 00 1 9 8 1 0√ 此時(shí)有 個(gè)獨(dú)立的零 . 選擇獨(dú)立的零 : n√ √ √ √ 最優(yōu)解為 最小成本為 2 2 3 4 4 3 5 1 1,x x x x? ? ? ? ? ⑵ 指派問(wèn)題中的最大值解 在某些問(wèn)題中 , 代價(jià)矩陣中的元素表示完成工作的收 矩陣 稱為 收益矩陣 . ? ?ijCc?益 , 此時(shí)問(wèn)題將轉(zhuǎn)化為求相應(yīng)的極大值問(wèn)題 . 問(wèn)題 求收益矩陣中的最大值解 . 解法 令 ? ?m a x ,ijMc? 記 ? ?ijC M c? ??則代價(jià)矩陣 的最小值解即為原問(wèn)題的最大值解 . C?例 22 求下面指派問(wèn)題的最大值解 4 1 0 8 59 8 0 21 2 3 7 4C?????????解 ? ?m a x 1 2 ,ijMc??