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

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

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

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

三、非標(biāo)準(zhǔn)形式的任務(wù)分派問題泳式運(yùn)動(dòng)員蛙泳自由泳蝶泳仰泳趙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應(yīng)選哪幾名運(yùn)動(dòng)員組成4×