指派問題(含非標(biāo)準(zhǔn)指派問題)-文庫吧資料
2025-07-20 21:42本頁面
【正文】 A4 B4 A5 B5這樣按排能使總的建造費最少，為 z=7＋9＋6＋6＋6=34（萬元）四． 一般的指派問題在實際應(yīng)用中，常會遇到非標(biāo)準(zhǔn)形式，解決的思路是：先化成標(biāo)準(zhǔn)形式，然后再用匈牙利法求解。 =Ⅵ）：回到步驟Ⅱ），對已增加了零元素的矩陣，再用圈0法找出獨立零元素組。在未被直線覆蓋過的元素中找最小元素，將打√行的各元素減去這個最小元素，將打√裂的各元素加上這個最小元素（以避免打√行中出現(xiàn)負(fù)元素），這樣就增加了零元素的個數(shù)。見。（5）對未打√的每一行劃一直線，如第1，3，5行。（3）對所有打√列中圈0元素所在行打√，如第2行。 為了確定中的獨立零元素，對加圈，即=由于只有4個獨立零元素，少于系數(shù)矩陣階數(shù)n=5,不能進(jìn)行指派，為了增加獨立零元素的個數(shù)，需要對矩陣作進(jìn)一步的變換，變換步驟如下：（1）對中所有不含圈0元素的行打√，如第3行。ⅳ）：做最少直線覆蓋當(dāng)前所有零元素。然后再進(jìn)行行、列檢驗，可能出現(xiàn)情況或，出現(xiàn)情況則由上述得到一最優(yōu)指派，停止計算。若情況出現(xiàn)，則在對每行、每列的其它未被標(biāo)記的零元素任選一個，加上標(biāo)記○，即圈上該零元素。上例中得到后，出現(xiàn)了情況，可令=1，=1，=1，=1，其余=0。這時可能出現(xiàn)以下三種情況：每一行均有圈0出現(xiàn)，圈0的個數(shù)m恰好等于n,即m=n.存在未標(biāo)記的零元素，但他們所在的行和列中，為標(biāo)記過的零元素均至少有兩個。這是第4行也只有一個未被標(biāo)記的零元素，再用○圈起，見 =（2）進(jìn)行列檢驗 與進(jìn)行行檢驗相似，對進(jìn)行了行檢驗的矩陣逐列進(jìn)行檢驗，對每列只有一個未被標(biāo)記的零元素，用記號○將該元素圈起，然后技改元素所在行的其他未被標(biāo)記的零元素打。本題中第1行此時也只有1個未被標(biāo)記的零元素。因此優(yōu)先指派第i人干第j項工作，而劃去第j列其它未標(biāo)記的零元素，表示第j項工作不再指派其它人去干（即使其它人干該項工作也相對有最好的效率）。如中第2行、第3行都只有一個未標(biāo)記的零元素，用○分別將它們?nèi)ζ?。?）進(jìn)行行檢驗對進(jìn)行逐行檢驗，對每行只有一個未標(biāo)記的零元素時，用○記號將該零元素圈起。min 列變換行變換7942C= = Min 0 0 4 2這樣得到的新矩陣中，每行每列都必然出現(xiàn)零元素。三． 匈牙利法求解步驟：我們以例題來說明指派問題如何求解：例4 給定效率矩陣 C= 求解該指派問題。我們不證它，說一下意思：例3：已知矩陣C1= ，C2= ，C3= 分別用最少直線去覆蓋各自矩陣中的零元素：C1= ， C2= ， C3= 可見，C1最少需要4條線，C2最少需要4條線，C3最少需要5條線，方能劃掉矩陣中所有的零。首先給出下述定理。同理 X（2）= 也是一個最優(yōu)解。就可找到指派問題的一個最優(yōu)解。｛=0，=0，=0，=0｝也是一個獨立零元素組，而｛=0，=0，=0，=0｝就不是一個獨立零元素組，因為=0與=0這兩個零元素位于同一列中。定義：在效率矩陣C中，有一組在不同行不同列的零元素，稱為獨立零元素組，此時每個元素稱為獨立零元素。設(shè)=0，從第i行來看，它表示第i個人去干第j項工作效率（相對）最好。只要反復(fù)運用定理1便可得證。推論：若將指派問題的效率矩陣每一行即每一列分別減去各行及各列的最小元素，則得到新指派問題與原指派問題有相同的最優(yōu)解。1=Zt因此有 Min =
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1