求解例5.4指派問題的方法：匈牙利算法匈牙利算法是匈牙利數學家克尼格（Konig）證明了下面兩個基本定理，為計算分配問題奠定了基礎。因此，基于這兩個定理基礎上建立起來的解分配問題的計算方法被稱為匈牙利法。假設問題求最小值，m個人恰好做m項工作，第i個人做第j項工作的效率為cij，效率矩陣為[cij]。【定理5.1】如果從分配問題效率矩陣[cij]的每一行元素中分別減去（或加上）一個常數ui（被稱為該行的位勢），從每一列分別減去（或加上）一個常數vj（稱為該列的位勢），得到一個新的效率矩陣[bij]，若其中bij=cij－ui－vj,則[bij]的最優解等價于[cij]的最優解。這里cij、bij均非負。4/8/2025【定理5.2】若矩陣A的元素可分成“0”與非“0”兩部分，則覆蓋“0”元素的最少直線數等于位于不同行不同列的“0”元素（稱為獨立元素）的最大個數。如果最少直線數等于m，則存在m個獨立的“0”元素，令這些零元素對應的xij等于1，其余變量等于0，得到最優解。定理5.1告訴我們如何將效率表中的元素轉換為有零元素，定理5.2告訴我們效率表中有多少個獨立的“0”元素。【例5.7】已知四人分別完成四項工作所需時間如下表，求最優分配方案。進入演示4/8/2025【解】最優分配方案是怎樣安排四人的工作，使得完成工作總時間最少，是求最小值問題。第一步：找出效率矩陣每行的最小元素，并分別從每行中減去最小元素，有Min3408第二步：找出矩陣每列的最小元素，再分別從每列中減去，有Min4/8/2025第三步：用最少的直線覆蓋所有“0”，得第四步：這里直線數等于3（等于4時停止運算），要進行下一輪計算。（1）從矩陣未被直線覆蓋的數字中找出一個最小的數k，表中k＝3。(2)直線相交處的元素加上k，未被直線覆蓋的元素減去k，被直線覆蓋而沒有相交的元素不變，得到下列矩陣4/8/2025回到第三步:用最少的直線覆蓋所有“0”，得未被直線覆蓋元素中最小元素k=2,直線相交處的元素加上2，未被直線覆蓋的元素減去2，被直線覆蓋而沒有相交的元素不變，得到下列矩陣4/8/2025畫線，最少直線數等于4。第五步：最優分配最優解：最優值Z＝73＋87＋82＋88＝330×××4/8/2025不平衡的指派問題當人數m大于工作數n時，加上m－n項工作，例如當人數m小于工作數n時，加上n－m個人，例如4/8/2025求最大值的指派問題匈牙利法的條件是：模型求最小值、效率cij≥0令則與的最優解相同。設C=(cij)m×m對應的模型是求最大值將其變換為求最小值4/8/2025【例】某人事部門擬招聘4人任職4項工作，對他們綜合考評的得分如下表（滿分100分），如何安排工作使總分最多。【解】M＝95，令4/8/2025用匈牙利法求解：最優解：即甲安排做第二項工作、乙做第三項、丙做第四項、丁做第三項。總分為：Z＝92＋95＋90＋80＝3574/8/2025本章介紹了整數規劃的數學模型的特征及其應用；1．整數規劃的最優解是先求相應的線性規劃的最優解然后取整得到.2．部分變量要求是整數的規劃問題稱為純整數規劃.3．求最大值問題的目標函數值是各分枝函數值的上界.4．求最小值問題的目標函數值是各分枝函數值的下界.5．變量取0或1的規劃是整數規劃.求解方法有：解一般整數規劃用分枝定界法、割平面法；解0－1規劃用隱枚舉法；解指派問題用匈牙利法。試一試，下例結論是否正確：4/8/20256．整數規劃的可行解集合是離散型集合.7．將指派（分配）問題的效率矩陣每行分別加上一個數后最優解不變.8．匈牙利法求解指派問題的條件是效率矩陣的元素非負.9．匈牙利法可直接求解極大化的指派問題.10．高莫雷（R..E.Gomory）約束是將可行域中一部分非整數解切割掉.11．指派問題也是一個特殊的運輸問題.12．指派問題也可用運輸問題求其最優解.