人力資源級(jí)匈牙利法解題思路.doc

匈牙利法假定甲單位有甲、乙、丙、丁、戊五個(gè)員工，需要在一定的生產(chǎn)技術(shù)組織條件下，完成A、B、C、D、E五項(xiàng)任務(wù)，每個(gè)員工完成每項(xiàng)工作所需要耗費(fèi)的工作時(shí)間，如表26所示。請(qǐng)求出：?jiǎn)T工與任務(wù)之間應(yīng)當(dāng)如何進(jìn)行配置，才能保證完成工作任務(wù)的時(shí)間最短？表26 各員工完成任務(wù)時(shí)間匯總表 單位：小時(shí) 員工任務(wù)甲乙丙丁戊A10591811B131961214C32445D189121715E116141910注意：由于存在以下兩種情況，匈牙利法的計(jì)算過程不唯一，最終矩陣的形式也不唯一，但最終配置結(jié)果一定相同，1約減時(shí)，可先進(jìn)行行約減，再進(jìn)行列約減；也可先進(jìn)行列約減，再進(jìn)行行約減。2“蓋0”線的畫法不唯一?，F(xiàn)列舉兩種解法如下：解法一：1以各個(gè)員工完成各項(xiàng)任務(wù)的時(shí)間構(gòu)造矩陣一。表27 矩陣一10591811131961214324451891217151161419102對(duì)矩陣一進(jìn)行行約減，即每一行數(shù)據(jù)減去本行數(shù)據(jù)中的最小數(shù)，得矩陣二。表28 矩陣二50413671306810223903865081343檢查矩陣二，若矩陣二各行各列均有“0”，則跳過此步，否則進(jìn)行列約減，即每一列數(shù)據(jù)減去本列數(shù)據(jù)中的最小數(shù)，得矩陣三。表29 矩陣三40411361304500200803634081114畫“蓋0”線。即畫最少的線將矩陣三中的0全部覆蓋住，得圖25。4041136130450020080363408111圖25 矩陣四操作技巧：從含“0”最多的行或列開始畫“蓋0”線。5數(shù)據(jù)轉(zhuǎn)換。若“蓋0”線的數(shù)目等于矩陣的維數(shù)則跳過此步，若“蓋0”線得數(shù)目小于矩陣得維數(shù)則進(jìn)行數(shù)據(jù)轉(zhuǎn)換，本例屬于后一種情況，應(yīng)進(jìn)行轉(zhuǎn)換，操作步驟如下：（1）找出未被“蓋0”線覆蓋的數(shù)中的最小值，例中1。（2）將未被“蓋0”線覆蓋住的數(shù)減去。（3）將“蓋0”線交叉點(diǎn)的數(shù)加上。本例結(jié)果見表210 矩陣五。表210 矩陣五3041025130340130070352308100 6重復(fù)4步和5步（計(jì)算過程見矩陣五a和矩陣五b），直到“蓋0”線的數(shù)目等于矩陣的維數(shù)。本例最終矩陣見表211。3041025130340130070352308100矩陣五a00472213004046034032200870矩陣五b表211 矩陣六004722130040460340322008707求最優(yōu)解。對(duì)n維矩陣，找出不同行、不同列的n個(gè)“0”，每個(gè)“0”的位置代表一對(duì)配置關(guān)系，具體步驟如下：（1）先找只含有一個(gè)“0”的行（或列），將該行（或列）中的“0”打“”。（2）將帶“”的“0”所在列（或行）中的“0”打“”。（3）重復(fù)（1）步和（2）步至結(jié)束。若所有行列均含有多個(gè)“0”，則從“0”的數(shù)目最少的行或列中任選一個(gè)“0”打“”。其結(jié)果如表212矩陣七所示，即員工甲負(fù)責(zé)任務(wù)A，員工乙負(fù)責(zé)任務(wù)D，員工丙負(fù)責(zé)任務(wù)B，員工丁負(fù)責(zé)任務(wù)C，員工戊負(fù)責(zé)任務(wù)E，參照表26各員工完成任務(wù)時(shí)間匯總表，得出表213所示的員工配置最終結(jié)果。表212 矩陣七0 0 4722130 0 40 460 3 40 3220 0 870 表213 員工配置最終結(jié)果 單位：小時(shí) 員工任務(wù)甲乙丙丁戊A10B6C4D9E10解法二：1以各個(gè)員工完成各項(xiàng)任務(wù)的時(shí)間構(gòu)造矩陣一。表27 矩陣一10591811131961214324451891217151161419102對(duì)矩陣一進(jìn)行行約減，即每一行數(shù)據(jù)減去本行數(shù)據(jù)中的最小數(shù)，得矩陣二。表28 矩陣二50413671306810223903865081343檢查矩陣二，若矩陣二各行各列均有“0”，則跳過此步，否則進(jìn)行列約減，即每一列數(shù)據(jù)減去本列數(shù)據(jù)中的最小數(shù)，得矩陣三。表29 矩陣三40411361304500200803634081114畫“蓋0”線。即畫最少的線將矩陣三中的0全部覆蓋住，得圖25。4041136130450020080363408111圖25 矩陣四操作技巧：從含“0”最多的行或列開始畫“蓋0”線。5數(shù)據(jù)轉(zhuǎn)換。若“蓋0”線的數(shù)目等于矩陣的維數(shù)則跳過此步，若“蓋0”線得數(shù)目小于矩陣得維數(shù)則進(jìn)行數(shù)據(jù)轉(zhuǎn)換，本例屬于后一種情況，應(yīng)進(jìn)行轉(zhuǎn)換，操作步驟如下：（1）找出未被“蓋0”線覆蓋的數(shù)中的最小值，例中1。（2）將未被“蓋0”線覆蓋住的數(shù)減去。（3）將“蓋0”線交叉點(diǎn)的數(shù)加上。本例結(jié)果見表210 矩陣五。表210 矩陣五3041025130340130070352308100 6重復(fù)4步和5步（計(jì)算過程見矩陣五a和矩陣五b），直到“蓋0”線的數(shù)目等于矩陣的維數(shù)。本例最終矩陣見表211。3041025130340130070352308100矩陣五a00172516037043034002200570矩陣五b表211 矩陣六001725160370430340022005707求最優(yōu)解。對(duì)n維矩陣，找出不同行、不同列的n個(gè)“0”，每個(gè)“0”的位置代表一對(duì)配置關(guān)系，具體步驟如下：（1）先找只含有一個(gè)“0”的行（或列），將該行（或列）中的“0”打“”。（2）將帶“”的“0”所在列（或行）中的“0”打“”。（3）重復(fù)（1）步和（2）步至結(jié)束。若所有行列均含有多個(gè)“0”，則從“0”的數(shù)目最少的行或列中任選一個(gè)“0”打“”。其結(jié)果如表212矩陣七所示，即員工甲負(fù)責(zé)任務(wù)A，員工乙負(fù)責(zé)任務(wù)D，員工丙負(fù)責(zé)任務(wù)B，員工丁負(fù)責(zé)任務(wù)C，員工戊負(fù)責(zé)任務(wù)E，參