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