指派問(wèn)題(含非標(biāo)準(zhǔn)指派問(wèn)題)-資料下載頁(yè)
2025-07-14 21:42本頁(yè)面
【正文】 =的◎數(shù)=5 6=n,下找0元素的最少直線覆蓋?！? 1√ 1= =從而得一最優(yōu)指派：B4B5A3B2B6=ψψA2B1B3A1承建商店公司 = 總費(fèi)用為z=7＋4＋9＋7＋8=35(萬(wàn)元)4．某事不能由某人去做的指派問(wèn)題某事不能由某人去做，可將此人做此時(shí)的費(fèi)用取作足夠大的M。例7：分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)，每人完成各項(xiàng)任務(wù)的時(shí)間如下表。由于任務(wù)重，人數(shù)少，考慮：a). 任務(wù)E必須完成，其它4項(xiàng)任務(wù)可選3項(xiàng)完成。但甲不能做A項(xiàng)工作。b) 其中有一人完成兩項(xiàng)，其他人每人完成一項(xiàng)。試分別確定最優(yōu)分配方案，使完成任務(wù)的總時(shí)間最少。任務(wù)人A B C D E甲乙丙丁25 29 31 42 3739 38 26 20 3334 27 28 40 3224 42 36 23 45解：這是一人數(shù)與工作不等的指派問(wèn)題，若用匈牙利法求解，需作一下處理。a) 由于任務(wù)數(shù)大于人數(shù)，所以需要有一個(gè)虛擬的人，設(shè)為戊。因?yàn)楣ぷ鱁必須完成，故設(shè)戊完成E的時(shí)間為M（M為非常大的數(shù)），即戊不能做工作E，其余的假想時(shí)間為0，建立的效率矩陣表如下：任務(wù)人A B C D E甲乙丙丁戊M 29 31 42 3739 38 26 20 3334 27 28 40 3224 42 36 23 45 0 0 0 0 M用匈牙利法求解過(guò)程如下：行變換C= 列變換由于◎數(shù)=4 5=階數(shù)，下找最少覆蓋0的直線√ 1√ 1=m=｛19,1,19,13,22｝=1,第4行減去1，第4列加上1得：A丁E丙乙B甲D= 從而得最優(yōu)指派：最少的耗時(shí)數(shù)z=29＋20＋32＋24=105.b) 思路：方案1：甲，乙，丙，丁。 方案2：甲，乙，丙，丁。 方案3：甲，乙，丙，丁。 方案4：甲，乙，丙，丁。 方案5：甲，乙，丙，丁。此為人；而工作：A，B，C，D，E，虛擬工作：F，G，H。這些思路都比較煩，請(qǐng)看下面的思路：設(shè)有虛擬人戊，它集五人優(yōu)勢(shì)為一身。即戊的費(fèi)用是每人的最低。戊所做的工作即為此項(xiàng)工作的費(fèi)用最低者的工作。任務(wù)人A B C D E甲乙丙丁戊25 29 31 42 3739 38 26 20 3334 27 28 40 3224 42 36 23 45 24 27 26 20 32以下用匈牙利法求解：行變換C= =列變換對(duì)加圈確定獨(dú)立0元素，◎個(gè)數(shù)=35=n,作0元素的最少直線覆蓋：√√√=在未劃去的數(shù)中選最小者1，未劃取得行都減去1，劃去的列都加上1得：= 再圈0且試指派：◎個(gè)數(shù)=3 5，再作0元素的最少直線覆蓋。從未劃取的元素中找最小者4，未劃取得行都減去這個(gè)4，劃去的列都加上這個(gè)4，得：BEDA丙丁乙甲= 再圈0試指派，結(jié)果為：C戊其中戊是虛擬人，不能真作，它作C工作是借乙（此列最小時(shí)數(shù)26是C所創(chuàng)業(yè)績(jī)）優(yōu)勢(shì)，應(yīng)由C來(lái)作。即C做兩件工作：D，C。15
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1