【正文】 ⑶ 交叉點(diǎn)加上該數(shù) , 其余不變 。 每行每列至少一個(gè)零 . ⑶ 判斷是否有 個(gè)獨(dú)立的零 , 若有 , 則在指派矩陣中 , n小值解 : 相應(yīng)元素取 1, 其余為 0. 所謂有 個(gè)獨(dú)立的零 , 即指這些零應(yīng)分布在不同的行 n判斷方法 : 用最少的橫線和豎線將所有的零劃去 , 若最 列上 . ,n n少的線數(shù)為 則一定有 個(gè)獨(dú)立的零 . 例 18 求下面指派問題中的最小值解 . 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ú)立的零 : 則問題的最優(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 求下面指派問題的最小值解 : 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注意到 , 對表 0 2 3 40 2 6 60 0 3 00 1 0 2可以用 3條線將所有的零劃去 , 因而沒有 4個(gè)獨(dú)立的零 . 對此我們有下面的迭代次序 : ⑴ 在所有未劃去的數(shù)中找最小數(shù) 。 i j第 項(xiàng)工作由其他人完成 . j由此得到矩陣 注意到 : 由于每項(xiàng)工作只能由 ? ?.ijXx?一人完成及每人只能完成一項(xiàng)工作 , 故在矩陣中每行和 每列只能有一個(gè) 1, 其余均為 0. 如此的矩陣稱為指派問題中的 指派矩陣 . 例 17 設(shè)指派問題中的代價(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?????????????則不是指派矩陣 . 所謂求解指派問題的最小值解 , 即為求解這樣的矩陣 , 使對應(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?? ?由此得到問題的模型為 : 而相應(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ù) 。 , 則進(jìn)行解的調(diào)整 。 為非基變量 . 解是退化的 . 對退化問題 , 需要虛擬基變量來補(bǔ)充基變量 的個(gè)數(shù) , 其取值為 0. 例 3 用西北角法求下面問題的初始解 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 11 3 10 7 2 1 9 2 8 4 3 7 4 10 5 9 需求量 3 8 5 4 20 解 由西北角法 , 容易得到問題的初始解 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 11 3 10 7 2 1 9 2 8 4 3 7 4 10 5 9 需求量 3 8 5 4 20 3 4 4 5 4 1 1 1 2 2 2 3 3 3 43 , 4 , 4 , 5 , 4 .x x x x x? ? ? ? ?即 : 問題的初始解為 并注意到該解是退化的 . 此時(shí)可令 23 0x ?來增加基變 量的個(gè)數(shù) . 最小元素法的基本想法是 : 按最小成本進(jìn)行分配 . 例 4 用最小元素法求下面運(yùn)輸問題的初始解 . 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 2 7 6 500 2 7 5 2 3 600 3 1 5 4 6 300 需求量 600 400 200 200 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 2 7 6 500 2 7 5 2 3 600 3 1 5 4 6 300 需求量 600 400 200 200 300 解 由最小元素法 , 最小成本為 故 31 3 0 0 ,x ?31 1,c ?剩下的最小成本分別為 1 2 2 32 , 2 ,cc?? 1 2 2 34 0 0 , 2 0 0 ,xx??銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 2 7 6 500 2 7 5 2 3 600 3 1 5 4 6 300 需求量 600 400 200 200 300 400 200 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 2 7 6 500 2 7 5 2 3 600 3 1 5 4 6 300 需求量 600 400 200 200 300 400 200 最后有 1 1 2 1 2 41 0 0 , 2 0 0 , 2 0 0 .x x x? ? ?100 200 200 由此得到問題的初始解 1 1 1 2 2 11 0 0 , 4 0 0 , 2 0 0 ,x x x? ? ?2 3 2 4 3 12 0 0 , 2 0 0 , 3 0 0 .x x x? ? ?此時(shí)對應(yīng)的運(yùn)輸成本為 ?例 5 用最小元素法求下面運(yùn)輸問題的初始解 . 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 11 3 10 7 2 1 9 2 8 4 3 7 4 10 5 9 需求量 3 8 5 4 20 解 由最小元素法得 : 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 11 3 10 7 2 1 9 2 8 4 3 7 4 10 5 9 需求量 3 8 5 4 20 3 1 4 8 3 1 即 : 初始解為 1 3 1 4 2 1 2 3 3 2 3 44 , 3 , 3 , 1 , 8 , 1 .x x x x x x? ? ? ? ? ? ⑵ 最優(yōu)解的判定 為判斷當(dāng)前解是否為最優(yōu)解 , 需要建立相應(yīng)的位勢 . ? ?, . 1 , 2 , , , 1 , 2 , ,iju v i m j n??.ij i jc u v??ijx 若 為基變量 , 則有 因基變量的個(gè)數(shù)為 故令 由此得到所有 1,mn??1 ?為此定義位勢 的位勢 . 例 6 求下面運(yùn)輸問題的初始解所對應(yīng)的位勢 . 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 2 7 6 500 100 400 2 7 5 2 3 600 200 200 200 3 1 5 4 6 300 300 需求量 600 400 200 200 解 由位勢的定義 , 及 是基變量 , 11x1 0,u ?1 1 1 1 ,c u v??由此得到 同樣有 1 ?1 2 1 2 ,c u v??得 再由 及 得 同理 2 ? 2 1 2 1c u v?? 1 3,v ? 2 ?3 4 32 , 1 , 2 .v v u? ? ? ? ? ?即有下表 : 又 可得其它位勢 : 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 2 7 6 500 100 400 2 7 5 2 3 600 200 200 200 3 1 5 4 6 300 300 需求量 600 400 200 200 1 0u ?1 3v ? 2 2v ?2 4u ?3 2u ??3 2v ?? 4 1v ??例 7 求下面運(yùn)輸問題的初始解所對應(yīng)的位勢 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 11 3 10 7 4 3 2 1 9 2 8 4 3 1 3 7 4 10 5 9 8 1 需求量 3 8 5 4 20 解 由位勢的定義可分別得到 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 11 3 10 7 2 1 9 2 8 4 3 7 4 10 5 9 需求量 3 8 5 4 20 3 1 4 8 3 1 1 0u ?3 3v ? 4 10v ?2 1u ??1 2v ?3 5u ??2 9v ? 下面的例子說明對退化問題的處理方式 例 8 求下面運(yùn)輸問題的初始解所對應(yīng)的位勢 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 11 3 10 7 3 4 2 1 9 2 8 4 4 3 7 4 10 5 9 5 4 需求量 3 8 5 4 20 解 由位勢的定義可分別得到 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 11 3 10 7 3 4 2 1 9 2 8 4 4 3 7 4 10 5 9 5 4 需求量 3 8 5 4 20 1 0u ?2 11v ?1 3v ?2 2u ??此時(shí) , 因基變量的個(gè)數(shù) ? ? ?23 0,x ?計(jì)算下去 . 為此 , 虛擬基變量 勢 : 故位勢無法再繼續(xù) 再進(jìn)一步計(jì)算位 銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 11 3 10 7 2 1 9 2 8 4 3 7 4 10 5 9 需求量 3 8 5 4 20 3 4 4 5 4 1 0u ?2 11v ?1 3v ?2 2u ?? 03 4v ?3 6u ?4 1v ?? 由位勢 , 再定義 影響系數(shù) 其定義關(guān)系為 : 若 為 ,ij? ijx.ij ij i jc u v? ? ? ?非基變量 , 則 例 9 對下面問題求相應(yīng)的影響系數(shù) . 6 4 5 1 3 2 5 7 6 7 2 3 200 200 400 600 需求量 300 3 600 2 500 1 產(chǎn)量 4 3 2 1 銷地 產(chǎn)地 300 400 200 100 200 200 1 0u ?1 3v ? 2 2v ?2 4u ?3 2u ??3 2u ?? 3 1u ??解 因 為非基變量 , 由影響系數(shù)的定義 , 有 13x1 3 1 49 , 7 ,????銷地 產(chǎn)地 1 2 3 4 產(chǎn)量 1 3 2 7 6 500 2 7 5 2 3 600 3 1 5 4 6 300 需求量 600 400 200 200