匈牙利法

1、匈牙利法假定甲單位有甲、乙、丙、丁、戊五個(gè)員工，需要在一定的生產(chǎn)技術(shù)組織條件下，完成A、B、C、D、E五項(xiàng)任務(wù)，每個(gè)員工完成每項(xiàng)工作所需要耗費(fèi)的工作時(shí)間，如表2－6所示。請求出：員工與任務(wù)之間應(yīng)當(dāng)如何進(jìn)行配置，才能保證完成工作任務(wù)的時(shí)間最短？表2－6各員工完成任務(wù)時(shí)間匯總表單位：小時(shí)員工任務(wù)甲乙丙丁戊A10591811B131961214C32445D189121715E116141910注意：由于存在以下兩種情況，匈牙利法的計(jì)算過程不

2、唯一，最終矩陣的形式也不唯一，注意：由于存在以下兩種情況，匈牙利法的計(jì)算過程不唯一，最終矩陣的形式也不唯一，但最終配置結(jié)果一定相同，最終配置結(jié)果一定相同，1約減時(shí)，約減時(shí)，可先進(jìn)行行約減，再進(jìn)行列約減；也可先進(jìn)行列約減，再進(jìn)行行約減?？上冗M(jìn)行行約減，再進(jìn)行列約減；也可先進(jìn)行列約減，再進(jìn)行行約減。2“蓋“蓋0”線的畫法不唯一。”線的畫法不唯一?，F(xiàn)列舉兩種解法如下：現(xiàn)列舉兩種解法如下：解法一：解法一：1以各個(gè)員工完成各項(xiàng)任務(wù)的時(shí)間構(gòu)造矩陣一

3、。表2－7矩陣一10591811131961214324451891217151161419102對矩陣一進(jìn)行行約減，即每一行數(shù)據(jù)減去本行數(shù)據(jù)中的最小數(shù)，得矩陣二。表2－8矩陣二50413671306810223903865081343檢查矩陣二，若矩陣二各行各列均有“0”，則跳過此步，否則進(jìn)行列約減，即每一列數(shù)據(jù)減去本列數(shù)據(jù)中的最小數(shù)，得矩陣三。表2－9矩陣三404113矩陣五a00472213004046034032200870矩陣

4、五b表2－11矩陣六004722130040460340322008707求最優(yōu)解。對n維矩陣，找出不同行、不同列的n個(gè)“0”，每個(gè)“0”的位置代表一對配置關(guān)系，具體步驟如下：（1）先找只含有一個(gè)“0”的行（或列），將該行（或列）中的“0”打“√”。（2）將帶“√”的“0”所在列（或行）中的“0”打“?”。（3）重復(fù)（1）步和（2）步至結(jié)束。若所有行列均含有多個(gè)“0”，則從“0”的數(shù)目最少的行或列中任選一個(gè)“0”打“√”。其結(jié)果如表2－