人力資源級匈牙利法解題思路.doc

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