指派問題(含非標準指派問題)(編輯修改稿)
2024-08-10 21:42 本頁面
【文章內(nèi)容簡介】 用記號劃去。如中第2行、第3行都只有一個未標記的零元素，用○分別將它們?nèi)ζ?。然后用劃去?列其它未被標記的零元素（第2列沒有），見 =在第i行只有一個零元素=0時，表示第i人干第j件工作效率最好。因此優(yōu)先指派第i人干第j項工作，而劃去第j列其它未標記的零元素，表示第j項工作不再指派其它人去干（即使其它人干該項工作也相對有最好的效率）。重復行檢驗，直到每一行都沒有未被標記的零元素或至少有兩個未被標記的零元素時為止。本題中第1行此時也只有1個未被標記的零元素。因此圈起中第1行第4列的零元素，然后用劃去第4列中未被標記的零元素。這是第4行也只有一個未被標記的零元素，再用○圈起，見 =（2）進行列檢驗 與進行行檢驗相似，對進行了行檢驗的矩陣逐列進行檢驗，對每列只有一個未被標記的零元素，用記號○將該元素圈起，然后技改元素所在行的其他未被標記的零元素打。重復上述列檢驗，直到每一列都沒有未被標記的零元素或有兩個未被標記的零元素為止。這時可能出現(xiàn)以下三種情況：每一行均有圈0出現(xiàn)，圈0的個數(shù)m恰好等于n,即m=n.存在未標記的零元素，但他們所在的行和列中，為標記過的零元素均至少有兩個。不存在未被標記過的零元素，當圈0的個數(shù)m n.ⅲ) 進行試指派若情況出現(xiàn)，則可進行試指派：令圈0為止的決策變量取值為1，其他決策變量取值均為零，得到一個最優(yōu)指派方案，停止計算。上例中得到后，出現(xiàn)了情況，可令=1，=1，=1，=1，其余=0。即為最優(yōu)指派。若情況出現(xiàn)，則在對每行、每列的其它未被標記的零元素任選一個，加上標記○，即圈上該零元素。然后給同行、同列的其它未被標記的零元素加標記。然后再進行行、列檢驗，可能出現(xiàn)情況或，出現(xiàn)情況則由上述得到一最優(yōu)指派，停止計算。若情況出現(xiàn)，則要轉入下一步。ⅳ）：做最少直線覆蓋當前所有零元素。我們還以例12來說明過程：已知例12指派問題的系數(shù)矩陣為： 先對各行元素分別減去本行的最小元素，然后對各列也如此，即列變換行變換C =此時，中各行各列都已出現(xiàn)零元素。 為了確定中的獨立零元素，對加圈，即=由于只有4個獨立零元素，少于系數(shù)矩陣階數(shù)n=5,不能進行指派，為了增加獨立零元素的個數(shù)，需要對矩陣作進一步的變換，變換步驟如下：（1）對中所有不含圈0元素的行打√，如第3行。（2）對打√的行中，所有零元素所在的列打√，如第1列。（3）對所有打√列中圈0元素所在行打√，如第2行。（4）重復上述（2），（3）步，直到不能進一步打√為止。（5）對未打√的每一行劃一直線，如第1，3，5行。對已打√的每一列劃一縱線，如第1列，既得到覆蓋當前0元素的最少直線數(shù)。見。= =Ⅴ）：對矩陣作進一步變換，以增加0元素。在未被直線覆蓋過的元素中找最小元素，將打√行的各元素減去這個最小元素，將打√裂的各元素加上這個最小元素（以避免打√行中出現(xiàn)負元素），這樣就增加了零元素的個數(shù)。如中未被直線覆蓋過的元素中，最小元素為==1，對打√的第2，3行各元素都減去2，對打√的第1列各元素都加上1，得到矩陣。 =Ⅵ）：回到步驟Ⅱ），對已增加了零元素的矩陣，再用圈0法找出獨立零元素組。=中已有5個獨立零元素，故可確定指派問題的最優(yōu)方案。本例的最優(yōu)解為承建X*=也就是說，最優(yōu)指派方案是：讓A1 B3 A2 B2 A3 B1
規(guī)章制度相關推薦
鄂ICP備17016276號-1