引例----一個任務分派問題優化方法----匈牙利法應用和推廣第六章任務分派方案的優化方法工人與任務的廣泛含義最大總收益問題非標準形式的任務分派問題寫出費用矩陣費用矩陣行列縮減畫線蓋0，調整0的布局重復第三步，直至得到最優方案第一節一個任務分派問題安排甲、乙、丙、丁四人完成車、銑、刨、磨床工作。不同工人對不同機床的熟練程度有區別，根據以往的資料，估算出每個工人對各種工種的預制工夾具等準備時間的數據如下表；工種車床銑床刨床磨床甲21057乙154148丙13141211丁415139一個工人擔任一個工種；一個工種工作由一個工人來完成。如何合理的分配任務，使得所有工人化費的準備時間總和盡可能的小？有n項任務，恰好n個人承擔，第i人完成第j項任務的花費(時間或費用等)為cij≥0，如何指派使總花費最省？第j項工作由一個人做第i人做一項工作標準形式的任務分派問題可行的分派方案：每人一項任務，每項任務由一個人承擔。可行解可表示為：例有一份中文說明書，需譯成英、日、德、俄四種文字。分別記作E、J、G、R。現有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種的說明書所需時間如下表。問應指派何人去完成何工作，使所需總時間最少？第二節優化方法階數①寫出費用矩陣已知條件可用系數矩陣（效率矩陣）表示為：其可行解也可用每行僅有一個1，每列也僅有一個1的矩陣表示，如：-2-4-11-4

若某行(列)已有0元素，那就不必再減了。例中的計算為：

根據結論1、結論2進行行列縮減，使系數矩陣各行、各列出現零元素。作法：系數矩陣各行元素減去所在行的最小元素，再從所得矩陣的各列減去所在列最小元素。②費用矩陣行列縮減試求最優解：如能找出n個位于不同行不同列的零元素，獨立0令對應的xij=1，其余xij=0，得最優解，結束；否則下一步。作法：由獨立0元素的行（列）開始，獨立0元素處畫標記，在有的行列中劃去其它0元素；再在剩余的0元素中重復此做法，直至不能標記為止③畫線蓋0，調整0的布局獨立0的個數=n,最優分派。未得到最優分配方案ⅰ以最少的直線數覆蓋所有的0。未被直線覆蓋的最小元素為cij；ⅱ未被直線覆蓋處減去cij；ⅲ僅被一條直線覆蓋的元素不變；ⅳ直線交叉點元素加上cij，。得新效益矩陣。對新矩陣，重新試分配。-2可以分派④求最優解最優分派方案是甲----刨床乙----銑床丙----磨床丁----車床總的準備時間=5+4+11+4=24小時第三節應用和推廣一、工人與任務的廣泛含義166頁例美學文學哲學史學周二50406030周三60303020周四30202030周五30201030工會應怎樣安排，使缺席聽課的職工人數最少？工人任務解：①費用矩陣②費用矩陣行列縮減-30-20-20-10-10③畫線蓋0，調整0的布局④重復上述步驟。標號法分派----多重最優解。周二------美學周三------史學周四------文學周五------哲學總缺席人數：50+20+20+10=100人二、最大總收益問題有六名工人在六個崗位上的效率以百分數表示如下：任務

工人123456192738085979927575989186823809490919980479979682808858476948893726769274867388求使總效率最高的任務分配方案。設最大總收益問題的收益矩陣為B=（bij）（i=1,2,…,n;j=1,2,…,n）。如果則令構成矩陣，那末，以為費用矩陣的最優方案就是原最大總收益問題的最優方案。本例，對C行列縮減，畫線蓋0，調整0的布局。再次調整0的布局，回到原問題，得最優解。工人1-----崗位6，工人2-----崗位3，工人3-----崗位5，工人4-----崗位2，工人5-----崗位1，工人6-----崗位4，最大總效率：99+98+99+97+84+86=563%

三、非標準形式的任務分派問題泳式運動員蛙泳自由泳蝶泳仰泳趙12.011.611.511.2錢12.311.711.611.1孫11.911.411.511.0李11.811.611.711.2周12.111.711.511.1應選哪幾名運動員組成4×