數(shù)學(xué)建模培訓(xùn)材料2005摸型指派模型

1、指派模型宋海洲一：指派問題設(shè)有n個(gè)人被分配去做n件工作，規(guī)定每個(gè)人只做一件工作，每件工作只由一個(gè)人做。已知第i個(gè)人做第j件工作的效率（時(shí)間或費(fèi)用)為 ，并假設(shè) 。問：應(yīng)如何分配才能使總效率（總時(shí)間或總費(fèi)用）最高？ 引進(jìn)變量設(shè)建立模型分析這是線性規(guī)劃模型；也是整數(shù)規(guī)劃模型；0-1規(guī)劃模型；更是運(yùn)輸模型。共有n*n個(gè)變量，實(shí)際上只需找n個(gè)變量為1即可，因此這是高度退化的線性規(guī)劃模型。例1設(shè)有5個(gè)人被分配去做5件工作，規(guī)定每個(gè)人只做一件工作，每件工作只由一個(gè)人做。已知第i個(gè)人做第j件工作的費(fèi)用如下表所示。問：應(yīng)如何分配工作才能使總費(fèi)用最省？二：匈牙利法定義：指派問題的效益矩陣：效益矩陣的性質(zhì)定理1：

2、從效益矩陣C的第k行（或第k列）的每一個(gè)元素中減去一個(gè)常數(shù)a得到的矩陣C所表示的指派問題具有相同的最優(yōu)解。（ C稱縮減效益矩陣）定義：如果這些0元素分布在效益矩陣的不同的行和不同的列上，則稱這些0元素為獨(dú)立的0元素。定理2：若方陣的一部分元素為0，一部分元素不為0，則覆蓋方陣內(nèi)所有0元素的最少直線數(shù)，等于矩陣中獨(dú)立的0元素的最多個(gè)數(shù)（匈牙利：konig）積和式定義：積和式的性質(zhì)按行展開性；轉(zhuǎn)置不變性；換行不變性；倍法變換增倍性；單行可加性；Laplace法則。補(bǔ)矩陣定義：匈牙利法解指派模型算法第一步：將原指派問題的效益矩陣C進(jìn)行變換得矩陣CC，使得CC的各行各列均出現(xiàn)0元素，其方法是：（1）從

3、效益矩陣C的每行元素減去該行最小元素；（2）在從所得的效益矩陣的每列元素減去該列最小元素。第二步：計(jì)算CC的補(bǔ)矩陣D,計(jì)算D的積和式per(D)。判斷per(D)是否不等于0，如果per(D)不等于0，轉(zhuǎn)第五步；如果per(D)等于0，轉(zhuǎn)第三步。第三步：（1）在CC中找0元素最少的一排（行或列），選中其中一個(gè)0，記為0，將該0所在的行及列劃去。（2）對(duì)上述劃去一行及一列的矩陣，重復(fù)（1）的做法。.一共得到m個(gè)0 。(mn)記下這m個(gè)0 所在的行號(hào)i1,i2,im及列號(hào)j1,j2,jm.(則CC所有的0或0必在i1,i2,im行中或在j1,j2,jm中）(3)：在 CC中找出不在i1,i2,im

4、行的0，記下他們的列號(hào)r1,r2,;并將這些列劃豎線；：在劃去豎線的CC中找出不含0的列的0，記下他們的行號(hào)s1,s2,;并將這些列劃?rùn)M線；重復(fù) ，則這些直線構(gòu)成覆蓋方陣CC內(nèi)所有零元素的最少直線。第四步：調(diào)整CC ,使之增加一些0，為此按如下方法進(jìn)行：（1）在沒有直線覆蓋的元素中，找出最小元素x;（2）在未劃線的行減去最小元素x；（3）在劃線的列加上最小元素x；得到新的CC，返回第二步。第五步：（1）在CC中找0元素最少的一排（行或列），選中其中一個(gè)0，記為0，將該0所在的行及列劃去。（2）對(duì)上述劃去一行及一列的矩陣，重復(fù)（1）的做法。.一共得到n個(gè)0 。（3）將n個(gè)0 所在位置對(duì)應(yīng)的變量賦

5、“1”，其他變量賦“0”，得到最優(yōu)解。例2：用匈牙利法求解例1第一步：將原指派問題的效益矩陣C進(jìn)行變換第二步：計(jì)算CC的補(bǔ)矩陣D,計(jì)算D的積和式per(D)。第三步：（1）在CC中找0元素最少的一排（行或列），選中其中一個(gè)0，記為0，將該0所在的行及列劃去。（2）對(duì)上述劃去一行及一列的矩陣，重復(fù)（1）的做法。.。一共得到4個(gè)0 。(4n=5)記下這4個(gè)0 所在的行號(hào)1，2，3，5。（3）在 CC中找出不在1，2，3，5行的0(不是0 ）的列號(hào)2，并將第2列劃豎線，在CC劃去豎線后剩下的0劃?rùn)M線；則這些直線構(gòu)成覆蓋方陣CC內(nèi)所有零元素的最少直線:（下一頁(yè)） 第四步：調(diào)整CC ,使之增加一些0，為此按如下方法進(jìn)行：（1）在沒有直線覆蓋的元素中，找出最小元素x=1;（2）在未劃線的行減去最小元素x；（3）在劃線的列加上最小元素x；得到新的CC，返回第二步。返回第二步：計(jì)算CC的補(bǔ)矩陣D,計(jì)算D的積和式per(D)=0。再進(jìn)行第三步得：返回第四步：調(diào)整CC ,使之增加一些0，為此按如下方法進(jìn)行：（1）在沒有直線覆蓋的元素中，找出最小元素x=1;（2）在未劃線的行減去最小元素x；（3）在劃線的列加上