數(shù)學(xué)建模指派問題第1頁，課件共20頁，創(chuàng)作于2023年2月設(shè)置變量:z………總成本數(shù)學(xué)模型:每項任務(wù)由一人完成

每人只承擔(dān)一項任務(wù)

總成本最小

第2頁，課件共20頁，創(chuàng)作于2023年2月解矩陣的特征全部元素僅取0或1每行有且僅有一個1每列有且僅有一個1第3頁，課件共20頁，創(chuàng)作于2023年2月性質(zhì)

從原成本矩陣C的任一行(列)中各元素加(減)一個常數(shù),得到新的成本矩陣,則此兩成本矩陣的指派問題的最優(yōu)解是相同的.證明：設(shè)矩陣C的第i行對應(yīng)的常數(shù)為di，

即f與z僅差一個常數(shù),所以兩目標(biāo)在相同的約束條件下，最優(yōu)解是相同的.第4頁，課件共20頁，創(chuàng)作于2023年2月求解的思想方法

若利用以上性質(zhì)，能把成本矩陣變換到存在n個獨立的0元素(在不同行不同列),且保持每個Cij非負(fù).這時讓這n個0元素的位置對應(yīng)的xij=1,其余位置的xij=0，就得最優(yōu)解.因為它是目標(biāo)值為0的可行解，且總有

第5頁，課件共20頁，創(chuàng)作于2023年2月匈牙利數(shù)學(xué)家

康尼格(D.Konig)的定理若在成本矩陣C中最多能找到k個獨立0，則必可畫k條直線把C的全部0覆蓋.第6頁，課件共20頁，創(chuàng)作于2023年2月匈牙利法步驟(1)把成本矩陣的各行每一元素分別減去該行中的最小元素,再檢查每列中是否都有0,若不是，則把沒有0的列的每一元素分別減去該列中的最小元素.(2)如果能在矩陣中找到n個獨立的0元素,就可以進行指派,即對應(yīng)于這n個0元素的位置的xij=1,其余位置的xij=0.結(jié)束.第7頁，課件共20頁，創(chuàng)作于2023年2月(3)當(dāng)獨立的0個數(shù)k<n時,可用k條直線覆蓋全部0.然后從未被覆蓋的各元素中,選出最小的元素a,把未被覆蓋的各元素減去這個最小元素,而兩直線交叉處的元素加上這個最小元素.（這種操作相當(dāng)于：未被覆蓋的行都減a，被覆蓋的列都加a.）(4)重復(fù)第(3)步,直做到能在矩陣中找到n個獨立的0為止,這樣就可以進行指派.第8頁，課件共20頁，創(chuàng)作于2023年2月第9頁，課件共20頁，創(chuàng)作于2023年2月第10頁，課件共20頁，創(chuàng)作于2023年2月最大化指派問題第11頁，課件共20頁，創(chuàng)作于2023年2月第12頁，課件共20頁，創(chuàng)作于2023年2月不平衡時的處理辦法—虛擬法前面講的方法只適用于人數(shù)與任務(wù)數(shù)相等當(dāng)人數(shù)與任務(wù)數(shù)不相等時n----人數(shù),m----任務(wù)數(shù)若n>m,則虛擬n-m個任務(wù)，相應(yīng)Cij=0若n<m,則虛擬m-n個人，相應(yīng)Cij=0這樣就化為人數(shù)與任務(wù)數(shù)相等的情況第13頁，課件共20頁，創(chuàng)作于2023年2月第14頁，課件共20頁，創(chuàng)作于2023年2月第15頁，課件共20頁，創(chuàng)作于2023年2月第16頁，課件共20頁，創(chuàng)作于2023年2月在C中找出最多獨立0的步驟設(shè)Wi表示第i行0的數(shù)目,Lj表示第j列0的數(shù)目.1.統(tǒng)計Wi和Lj（i,j=1,2,…n）.2.按W1，W2，…,Wn,L1,L2,…,Ln順序找出第一個最小正數(shù)，選中該行（列）首個0.3.刪除該0所在的行與列,對應(yīng)的Wi=0,Lj=0.4.重復(fù)步驟1~3，直到全部Wi=0為止.第17頁，課件共20頁，創(chuàng)作于2023年2月這樣就找到4個獨立0第18頁，課件共20頁，創(chuàng)作于2023年2月如果按自上而下從左到右順序找這樣只找到3個獨立0第19頁，課件共20頁，創(chuàng)作于2