第4章 線性整數(shù)規(guī)劃-指派問題

1§4.5指派問題及其應(yīng)用

在實(shí)際工作中，我們經(jīng)常會(huì)遇到這樣的問題：有n項(xiàng)工作要由n個(gè)人去完成，要求每人剛好承擔(dān)一項(xiàng)工作。由于任務(wù)性質(zhì)和各個(gè)人的專長不同，不同的人完成同一項(xiàng)工作所需的資源（或工作效率）不同。那么，到底應(yīng)分配哪一個(gè)人去完成哪一項(xiàng)工作才能使所需的資源總量最少（或總的效率最高）？這類問題就稱為指派問題或分配問題。指派問題不僅僅是指人力資源的分配，也可以是其他資源（如物力資源）的分配問題。2一、指派問題的數(shù)學(xué)模型

例：某一單位，有4個(gè)工作人員，有4項(xiàng)任務(wù)。如果每個(gè)工作人員都有能力去完成n項(xiàng)任務(wù)中的任一項(xiàng)，只是完成任務(wù)所需時(shí)間cij不同(見下表)，問應(yīng)如何合理分配人力，才能使完成任務(wù)所需的總工時(shí)最少？

任務(wù)人員B1B2B3B4A15886A24658A361074A499733指派問題的數(shù)學(xué)模型這是一個(gè)有4個(gè)人和4項(xiàng)任務(wù)的完整指派問題，上表中的數(shù)據(jù)反映了每個(gè)人完成各項(xiàng)任務(wù)的效率（或效應(yīng)），通常稱為效率（或效應(yīng)）矩陣。指派問題的所有原始數(shù)據(jù)均包含在其效率（或效應(yīng)）矩陣中。

這個(gè)指派問題的特點(diǎn)是：每一項(xiàng)任務(wù)必須且只能由一個(gè)工作人員去完成，每一個(gè)工作人員也只能分配一項(xiàng)任務(wù)。引入0-1變量xij

4指派問題的數(shù)學(xué)模型S表示完成所有任務(wù)所需的總工時(shí)，則該問題的數(shù)學(xué)模型為：5對(duì)于將n項(xiàng)資源分配給n項(xiàng)任務(wù)的完整指派問題，設(shè)資源i分配給任務(wù)j所產(chǎn)生的效應(yīng)為cij，S表示總效應(yīng)，引入0-1變量

指派問題的數(shù)學(xué)模型6指派問題的數(shù)學(xué)模型則數(shù)學(xué)模型為：7討論：

1、問題中的效應(yīng)系數(shù)cij可以有多種不同的實(shí)際意義，例如可以為時(shí)間、價(jià)值、資源消耗量或工作效率等。根據(jù)效應(yīng)系數(shù)的具體含義，指派問題的目標(biāo)函數(shù)可以取最小值，也可以取最大值，但最大化問題可以轉(zhuǎn)化為最小化問題求解。2、指派問題的數(shù)學(xué)模型是一個(gè)線性規(guī)劃數(shù)學(xué)模型，約束系數(shù)矩陣的元素不是1就是0，且約束方程的右端常數(shù)均為1，其基本可行解必滿足0-1變量的取值要求，故可以直接用單純形法求解，但求解工作量較大。指派問題的數(shù)學(xué)模型83、指派問題的數(shù)學(xué)模型是一個(gè)特殊的運(yùn)輸問題數(shù)學(xué)模型，各個(gè)產(chǎn)地的產(chǎn)量和各個(gè)銷地的銷量均為1，可以采用運(yùn)輸問題的表上作業(yè)法求解。但由于該問題的特殊性，用表上作業(yè)法求解時(shí)效率很低。4、指派問題的數(shù)學(xué)模型是一個(gè)0-1線性規(guī)劃問題，可以用上一節(jié)介紹的隱枚舉法求解。但由于指派問題的變量和約束條件都較多，采用隱枚舉法求解計(jì)算量很大。5、指派問題可以推廣到資源數(shù)和任務(wù)數(shù)不等的情況。為了把這類推廣的指派問題轉(zhuǎn)化為常規(guī)指派問題，只需對(duì)問題增加若干個(gè)虛擬的資源或若干個(gè)虛擬的任務(wù)即可。指派問題的數(shù)學(xué)模型9⑴資源數(shù)多于任務(wù)數(shù)的情況。這時(shí)可引入若干個(gè)虛擬任務(wù)，并令效應(yīng)矩陣中虛擬任務(wù)對(duì)應(yīng)的列全為0元素。這種情況下，實(shí)際上將有某些資源分配不出去（某些人分配不到工作）。⑵任務(wù)數(shù)多于資源數(shù)。這時(shí)可引入若干個(gè)虛擬的資源，并令效應(yīng)矩陣中虛擬資源對(duì)應(yīng)的行全為0元素。這種情況下，實(shí)際上將有某些任務(wù)分配不到資源（某些任務(wù)無人承擔(dān)）。指派問題的數(shù)學(xué)模型10匈牙利法是求解指派問題的有效算法。它是匈牙利數(shù)學(xué)家柯尼格(Konig)根據(jù)指派問題的獨(dú)特性質(zhì)而提出的一種巧妙而有效的算法，故稱匈牙利法。指派問題的數(shù)學(xué)模型11二、用匈牙利法求解指派問題1、匈牙利法的基本思路

與大多數(shù)整數(shù)規(guī)劃算法不同，求解指派問題的匈牙利法不是采用解迭代方式而采用了問題迭代的方式，其基本思路是：根據(jù)指派問題的性質(zhì)對(duì)原問題做一系列同解變換，從而得到一系列等價(jià)(同解)的指派問題，最后可得到一個(gè)只需直接觀察其效率矩陣就可得到最優(yōu)解的派生指派問題，該問題的最優(yōu)解即為原指派問題的最優(yōu)解（但目標(biāo)函數(shù)值不同）。12匈牙利法在介紹匈牙利法之前，我們先介紹指派問題的幾個(gè)重要性質(zhì)。定理1：如果效率矩陣[cij]n×n中的所有元素非負(fù)，且其中存在n個(gè)位于不同列、不同行的零元素，則只要令對(duì)應(yīng)于這些零元素位置的xij=1，其余的xij＝0，這樣得到的解即為指派問題的最優(yōu)解。

這是因?yàn)?，在目?biāo)函數(shù)表達(dá)式中xij=1的系數(shù)為0，可使目標(biāo)函數(shù)達(dá)到最??；另外，還可以保證在約束方程組的每個(gè)方程中只有一個(gè)變量為1，故可滿足約束條件的要求。因此，這樣得到的解就是指派問題的最優(yōu)解。13定理2：如果從效率矩陣的每一行元素中分別減去一個(gè)常數(shù)ui，從每一列元素中分別減去一個(gè)常數(shù)vj，由此得到一個(gè)新的效率矩陣，匈牙利法證：由于由確定的指派問題的目標(biāo)函數(shù)為：則的最優(yōu)解等價(jià)于的最優(yōu)解。14匈牙利法由于上式后面兩項(xiàng)均為常數(shù)，且指派問題的約束條件與效率矩陣無關(guān)，故由確定的指派問題與的指派問題有相同的最優(yōu)解。證畢。15匈牙利法該定理是對(duì)指派問題進(jìn)行同解變換的依據(jù)。

定理3：若矩陣A的元素可分成0與非0兩部分，則覆蓋0元素的最少直線數(shù)等于位于不同行、不同列的0元素的最大個(gè)數(shù)。

所謂用直線覆蓋是指用一條橫線劃去矩陣的一行元素或用一條豎線劃去一列元素，劃去的元素就稱為被覆蓋。這個(gè)定理實(shí)際上回答了這樣一個(gè)問題：至少要多少條直線(橫線和豎線)才能覆蓋矩陣A中的所有0元素?16匈牙利法根據(jù)定理3，可以采用最少直線覆蓋所有0元素的方法確定效率矩陣中位于不同行、不同列的0元素的最大數(shù)目。如果剛好有n個(gè)0元素位于不同行、不同列，則由定理1即可得到指派問題的最優(yōu)解。否則應(yīng)按定理2繼續(xù)對(duì)效率矩陣作同解變換。以上3個(gè)定理是匈牙利法的基礎(chǔ)，但要實(shí)施這個(gè)算法還要解決以下兩個(gè)問題：①對(duì)于給定的效率矩陣，如何用最少的直線覆蓋所有0元素？

②若效率矩陣中位于不同行、不同列的0元素的最大數(shù)目小于n，如何對(duì)效率矩陣進(jìn)一步作同解變換？

17匈牙利法例：數(shù)學(xué)教研室有四名教師講四門不同的課，由于各位教師的專長、教學(xué)水平和教學(xué)經(jīng)驗(yàn)不同，所需備課時(shí)間也分別不同，問教研室主任應(yīng)如何分配這些教學(xué)任務(wù)，才能使總的備課時(shí)間最省。各教師備各門課所需時(shí)間見下表。

課程教師B1微積分B2數(shù)理方程B3線性代數(shù)B4概率論A121097A2154148A313141611A441513918匈牙利法匈牙利法的變換方法如下：(1)第一步：變換效應(yīng)矩陣C(即備課時(shí)間陣)，使每行每列至少有一個(gè)元素為零，以期從這些對(duì)應(yīng)的零元素能得到完整的分配方案，使總的備課時(shí)間為最省。為此，可先在每行中減去各行的最小元素，根據(jù)表中數(shù)據(jù)，第一、二、三、四行分別減去2、4、11、4，可得新一矩陣為：19匈牙利法加減常數(shù)的代數(shù)和為：S1＝2+4+11+4＝21因第三列中無零元素，因而再在第三列中減去其最小元素5，加減常數(shù)的代數(shù)和為：S1+S2＝21+5＝2620匈牙利法(2)第二步：為了給每個(gè)教師分配一個(gè)任務(wù)，以實(shí)現(xiàn)完整的任務(wù)分配，希望每行每列只有一個(gè)零元素，現(xiàn)在有的行或列多于一個(gè)零元素，如何分配呢？這需要用檢驗(yàn)的辦法決定取舍。先進(jìn)行行檢驗(yàn)，如圖l所示。碰到每行只有一個(gè)0元素的先打△，有兩個(gè)0元素不作記號(hào)，例如第一行只有一個(gè)0，就在0處打△，這就表示把第一門課(微積分)分配給教師Al，因此，對(duì)第一列其它的0元素打×；同理第二行打一個(gè)△；第三行有兩個(gè)0，不作記號(hào)。21匈牙利法然后進(jìn)行列檢驗(yàn)，如圖2所示，第一、二列已沒有未作記號(hào)的0；第三列有一個(gè)0，打△，表示教師A3已接受第三門課，因此對(duì)同一行的0打×。(3)第三步，從檢驗(yàn)出的矩陣可以看出，第四門課還未分配出去，教師A4也未分到任務(wù)?？梢娺@不是最優(yōu)方案。22匈牙利法為過渡到最優(yōu)方案，需對(duì)以上的矩陣再進(jìn)行變換，如圖3所示。變換規(guī)則如下：(a)對(duì)所有沒有分配任務(wù)的行打√。如第四行。(b)在已打√的行中，找出打×的列打√。如第一列。(c)在已打√的列中找出打△的行，打√，如第一行。(d)再進(jìn)行上述(b)、(c)項(xiàng)檢驗(yàn)，直至無法打√為止。并用以下調(diào)整辦法找最優(yōu)解。23匈牙利法(e)對(duì)所有打√的列和未打√的行劃線，這些線至少可以把所有0覆蓋一次。一般講，如果是n×n陣，又要使最優(yōu)分配均在0上，最少線數(shù)就應(yīng)等于n。而此例中現(xiàn)只有三根直線，因此，這不是最優(yōu)解。還需進(jìn)一步進(jìn)行變換。24(f)在變換后的檢驗(yàn)矩陣中，從未經(jīng)劃線的元素中可以找出一個(gè)最小元素c13=2，從未全部劃線的第一行和第四行中各減去2，可得一新矩陣：S1+S2+S3＝26+2+2=30加減常數(shù)的代數(shù)和為：25匈牙利法由于此矩陣中第一列有負(fù)數(shù)，因此再在第一列上加2，于是得一個(gè)所有元素均≥0的矩陣。S1+S2+S3+S4＝30-2=28

加減常數(shù)的代數(shù)和為：

26對(duì)新得的矩陣進(jìn)行行檢驗(yàn)和列檢驗(yàn)，如圖4所示。第二、四行和第四列均只有一個(gè)0，很快打上△，并對(duì)同列或同行的0打×，剩下一個(gè)c13處為0，打△。于是得一完整分配方案，也即最優(yōu)分配方案。得最優(yōu)解為：x13=1，x22=1，x34=1，x41=1，而其余的xij均等于0。27匈牙利法對(duì)于這個(gè)完整分配方案，可得：再看一下打△處原效應(yīng)矩陣的元素值，得由此可見，最優(yōu)分配方案所對(duì)應(yīng)的原效應(yīng)矩陣中元素值之和，等于進(jìn)行變換過程中行和列所加減數(shù)字的代數(shù)和(加為負(fù)，減為正)。此例中目標(biāo)函數(shù)S的最小值即為：28匈牙利法2、匈牙利法的算法步驟如有m個(gè)資源(如人力、機(jī)車或設(shè)備均為一種資源)分配到n個(gè)活動(dòng)領(lǐng)域(如生產(chǎn)任務(wù)、運(yùn)輸路線或地區(qū)等均為一種活動(dòng)對(duì)象或領(lǐng)域)上去。若對(duì)應(yīng)的效應(yīng)cij均已知，那么，分配問題就是要確定各個(gè)資源如何分配到各個(gè)活動(dòng)對(duì)象上去，才能使全局的效應(yīng)最優(yōu)。29匈牙利法若資源的個(gè)數(shù)m大于分配對(duì)象的個(gè)數(shù)n，則在n個(gè)活動(dòng)對(duì)象的列向量后加上m-n個(gè)虛構(gòu)的列向量，而且這些列向量的所有元素cij均為0，這樣效應(yīng)矩陣C就是一個(gè)包含0列向量的m×m階方陣。m-n列m>n30匈牙利法同理，若資源個(gè)數(shù)m小于分配對(duì)象個(gè)數(shù)n，則在m個(gè)資源的行向量下面加上n-m個(gè)虛構(gòu)的行向量，這些行向量的元素也均為0，使效應(yīng)矩陣C成為包含0行向量的n×n方陣。n-m行m<n31匈牙利法我們用方陣進(jìn)行匈牙利算法的運(yùn)算，找出完整分配方案的最優(yōu)解。若所得的結(jié)果中某一1元素在虛行或虛列上，這個(gè)結(jié)果可以不考慮，而其他行和列的結(jié)果就是最優(yōu)解。具體算法步驟如下：

第1步：如果是求目標(biāo)函數(shù)S＝f(X)的極大值，則應(yīng)將所有效應(yīng)矩陣的元素改為負(fù)值，然后進(jìn)行第2步。如果求目標(biāo)函數(shù)S＝f(X)的極小值，則直接進(jìn)行第2步。第2步：若第i行的最小元素不是0，則從該行的每個(gè)元素中減去此最小元素。(i＝1～m)。32匈牙利法第3步：若第j列的最小元素不是0，則從該列的每個(gè)元素中減去此最小元素。(j=1～n)。第4步：逐個(gè)檢查每一行，看是否每一行只有一個(gè)未標(biāo)注的0，如只有一個(gè)0存在，則在此元素上注以符號(hào)△，表示一種分配，同時(shí)，對(duì)同一列的0元素打×，以便下一個(gè)分配不落在此列上。重復(fù)這一過程，直到所有行上沒有未標(biāo)注△的0或至少有兩個(gè)0。第5步：逐個(gè)檢查每一列，查出單一的未標(biāo)注的0，打上△，對(duì)同一行的0元素打×。重復(fù)這一過程，直到所有列上沒有未標(biāo)注△的0或至少有兩個(gè)0。33匈牙利法第6步：反復(fù)進(jìn)行第4、5步，直到下面三種情況之一發(fā)生為止：(a)每行均標(biāo)注有△；(b)至少有兩個(gè)未標(biāo)注的0在各行或各列中；(c)沒有剩下未標(biāo)注的0，但還未形成一完整的分配。

第7步：如果上述(a)發(fā)生，則得一完整的分配方案；且是一最優(yōu)分配方案，可停機(jī)。如果是(b)發(fā)生，可任意作一分配記號(hào)△到一個(gè)0上，而將同行或同列的另一個(gè)0打×，然后轉(zhuǎn)到第4步。如果是(c)發(fā)生，則轉(zhuǎn)到第8步。34匈牙利法第8步：對(duì)所有沒有標(biāo)注△的行打√。第9步：在打√的行中如包含一個(gè)0元素，則給該元素所對(duì)應(yīng)的(沒有打√的)列打上√。第10步：在打√的列上，如有△記號(hào)，則這些△記號(hào)的對(duì)應(yīng)的行均打√。第11步：重復(fù)第9、10步；直到所有能打√的行和列都打完。第12步：對(duì)所有未打√的行和已打√的列劃線，這些線至少有一次蓋過每一個(gè)0元素，這是覆蓋0元素所需的最少線數(shù)。35匈牙利法第13步：檢查所有沒有線通過的元素，選擇出其中最小者。在未完全劃線的行中，對(duì)每一元素減去此最小數(shù)，再在有線通過的列上，對(duì)每一元素加上此最小數(shù)，得一新矩陣，再回到第4步。36三、匈牙利法的FORTRAN程序

該程序用于解n個(gè)資源、n個(gè)活動(dòng)對(duì)象的分配問題，要求使目標(biāo)函數(shù)f(X)為最優(yōu)?？捎靡郧竽繕?biāo)函數(shù)的極大值；也可用以求目標(biāo)函數(shù)的極小值。但要求其效應(yīng)矩陣C的各元素cij必須是整數(shù)。該程序由主程序和子程序組成。主程序包括數(shù)據(jù)輸入、輸出。子程序即為匈牙利算法，稱為HUNGRY。使用下面所列程序至多可解決15個(gè)資源、15個(gè)對(duì)象的問題。若所要求解的問題中資源的個(gè)數(shù)、對(duì)象的個(gè)數(shù)大于15，即n＞15，只需改變主程序中DIMENSION語句中的維數(shù)即可。37匈牙利法的FORTRAN程序使用該程序時(shí)，應(yīng)輸入下列數(shù)據(jù)：

N──資源、對(duì)象的個(gè)數(shù)。KODE──對(duì)于最小化問題，KODE=0；對(duì)于最大化問題，KODE=1。MATRIX(I,J)──初始效應(yīng)矩陣。該程序?qū)⒂?jì)算并打印出：IASMAT──分配矩陣(ASSIGNMENTMATRIX)。NCOST──目標(biāo)函數(shù)的最優(yōu)值。38匈牙利法的FORTRAN程序具體程序如下：CCCC用于求解資源分配問題的匈牙利算法程序CCCC需要輸入的數(shù)據(jù)為：CCCCN──資源、對(duì)象的個(gè)數(shù)。CCCCKODE──對(duì)于極小值問題，KODE=0；對(duì)于極大值問題，KODE=1。CCCCMATRIX(I,J)──初始效應(yīng)矩陣，按行輸入。

DIMENSIONMATRIX(15,15),IASMAT(15) OPEN(21,FILE='HUN.IN') OPEN(22,FILE='HUN.OUT') READ(21,*)N,KODE DO2I=1,N2 READ(21,*)(MATRIX(I,J),J=1,N) CLOSE(21) WRITE(22,*)'初始效應(yīng)矩陣為：' DO6I=1,N6 WRITE(22,5)(MATRIX(I,J),J=1,N)395 FORMAT(1X,10I8)

CALLHUNGRY(N,MATRIX,IASMAT,NCOST,KODE) WRITE(22,120)NCOST120 FORMAT(/1X,'最優(yōu)目標(biāo)函數(shù)值為：',I8) WRITE(22,*)'最優(yōu)分配方案為:' DO130I=1,N130 WRITE(22,135)I,IASMAT(I)135 FORMAT(1X,'資源',I2,'分配給對(duì)象',I2) CLOSE(22) STOP END匈牙利法的FORTRAN程序40匈牙利法的FORTRAN程序 SUBROUTINEHUNGRY(N,IIF,IROW,TOTAL,KODE) DIMENSIONIIF(15,15),IEFF(15,15),IROW(15),ICOL(15) DIMENSIONICHECK(15),JCHECK(15) INTEGERTOTAL IF(KODE.EQ.1)GOTO100 DO110I=1,N DO110J=1,N110 IEFF(I,J)=IIF(I,J) GOTO200100 DO120I=1,N DO120J=1,N120 IEFF(I,J)=-IIF(I,J)200 DO210I=1,N MINROW=IEFF(I,1) DO220J=1,N IF(IEFF(I,J).LE.MINROW)MINROW=IEFF(I,J)220 CONTINUE41匈牙利法的FORTRAN程序 DO210J1=1,N IEFF(I,J1)=IEFF(I,J1)-MINROW210 CONTINUE DO300J=1,N MINCOL=IEFF(1,J) DO310I=1,N IF(IEFF(I,J).LE.MINCOL)MINCOL=IEFF(I,J)310 CONTINUE DO300I1=1,N IEFF(I1,J)=IEFF(I1,J)-MINCOL300 CONTINUE400 DO410I=1,N IROW(I)=0410 ICOL(I)=0 NOMADE=0420 LOOP=0 NZEROS=0 DO430I=1,N NOZR=0 IF(IROW(I).NE.0)GOTO43042匈牙利法的FORTRAN程序 DO440J=1,N IF(ICOL(J).NE.0)GOTO440 IF(IEFF(I,J).NE.0)GOTO440 NOZR=NOZR+1 NZEROS=NZEROS+1 NRPT=J NREFF=I440 CONTINUE IF(NOZR.NE.1)GOTO430 IROW(I)=NRPT ICOL(NRPT)=1 NOMADE=NOMADE+1 LOOP=LOOP+1430 CONTINUE DO500I=1,N NOZC=043匈牙利法的FORTRAN程序 IF(ICOL(I).NE.0)GOTO500 DO510J=1,N IF(IROW(J).NE.0)GOTO510 IF(IEFF(J,I).NE.0)GOTO510 NOZC=NOZC+1 NZEROS=NZEROS+1 IRPT=J510 CONTINUE IF(NOZC.NE.1)GOTO500 ICOL(I)=1 IROW(IRPT)=I NOMADE=NOMADE+1 LOOP=LOOP+1500 CONTINUE IF(NOMADE.EQ.N)GOTO1500 IF(LOOP.NE.0)GOTO420 IF(NZEROS.EQ.0)GOTO800700 IROW(NREFF)=NRPT NOMADE=NOMADE+1 ICOL(NRPT)=1 GOTO42044匈牙利法的FORTRAN程序800 DO810I=1,N ICHECK(I)=0 JCHECK(I)=0 IF(IROW(I).NE.0)GOTO810 ICHECK(I)=I810 CONTINUE900 NCHECK=0 DO910I=1,N IF(ICHECK(I).EQ.0)GOTO910 DO920J=1,N IF(JCHECK(J).NE.0)GOTO920 IF(IEFF(I,J).NE.0)GOTO920 JCHECK(J)=J NCHECK=NCHECK+1920 CONTINUE910 CONTINUE

IF(NCHECK.EQ.0)GOTO1300

45匈牙利法的FORTRAN程序 DO1010I=1,N IF(JCHECK(I).LE.0)GOTO1010 DO1020J=1,N IF(JCHECK(I).NE.IROW(J))GOTO1020 ICHECK(J)=J NCHECK=NCHECK+11020 CONTINUE1010 CONTINUE IF(NCHECK.NE.0)GOTO9001300 MINELM=99999999 DO1310I=1,N IF(ICHECK(I).EQ.0)GOTO1310 DO1320J=1,N IF(JCHECK(J).NE.0)GOTO1320 IF(IEFF(I,J).GE.MINELM)GOTO1320 MINELM=IEFF(I,J)1320 CONTINUE1310 CONTINUE46匈牙利法的FORTRAN程序 DO1400I=1,N DO1400J=1,N IF(ICHECK(I).LT.0)GOTO1400 IF(ICHECK(I).EQ.0)GOTO1410 IF(JCHECK(J).NE.0)GOTO1400 IEFF(I,J)=IEFF(I,J)-MINELM GOTO14001410 IF(JCHECK(J).LE.0)GOTO1400 IEFF(I,J)=IEFF(I,J)+MINELM1400 CONTINUE GOTO4001500 TOTAL=0 DO1510I=1,N K=IROW(I)1510 TOTAL=TOTAL+IIF(I,K) RETURN END47匈牙利法的FORTRAN程序

數(shù)據(jù)輸入文件hun.in：

4,02,10,9,715,4,14,813,14,16,114,15,13,9結(jié)果輸出文件hun.out：初始效應(yīng)矩陣為：

2109715414813141611415139給教師分配教學(xué)任務(wù)例題計(jì)算結(jié)果48匈牙利法的FORTRAN程序最優(yōu)目標(biāo)函數(shù)值為：28最優(yōu)分配方案為:

x(1,3)=1

x(2,2)=1

x(3,4)=1

x(4,1)=149四、指派問題的推廣應(yīng)用指派問題的一種很有意義的推廣是：設(shè)有m個(gè)人和n項(xiàng)任務(wù)，其中每個(gè)人可承擔(dān)的任務(wù)總數(shù)是給定的，應(yīng)如何給每個(gè)人分配任務(wù)才能既保證完成n項(xiàng)任務(wù)，又使總體效率最高？這里沒有限定一個(gè)人必須而且只能承擔(dān)一項(xiàng)任務(wù)，但要求一項(xiàng)任務(wù)只能由一人完成，而且m個(gè)人必須完成n項(xiàng)任務(wù)。設(shè)第i個(gè)人完成第j項(xiàng)任務(wù)所需的時(shí)間為cij，則以上推廣指派問題的數(shù)學(xué)模型為：50指派問題的推廣應(yīng)用51顯然該問題有解的充要條件是指派問題的推廣應(yīng)用經(jīng)以下兩步轉(zhuǎn)換后，該問題可化成常規(guī)的指派問題。①增加項(xiàng)虛設(shè)任務(wù)，并令每個(gè)人完成虛設(shè)任務(wù)所需的時(shí)間均為0；②如果第i個(gè)人最多可承擔(dān)ai項(xiàng)任務(wù)，則將其等價(jià)為ai個(gè)人，其中每個(gè)人剛好承擔(dān)一項(xiàng)任務(wù)，且每個(gè)人完成各項(xiàng)任務(wù)（包括虛設(shè)任務(wù)）所需的時(shí)間與第i個(gè)人相同。52指派問題的推廣應(yīng)用轉(zhuǎn)換后得到的常規(guī)指派問題將包括個(gè)人和項(xiàng)任務(wù)。下面以油氣集輸系統(tǒng)中油井與計(jì)量站的最優(yōu)連接問題為例說明以上推廣的指派問題的應(yīng)用。該問題已在運(yùn)輸問題的拓廣應(yīng)用中討論過，其數(shù)學(xué)模型與上面列出的推廣的指派問題的數(shù)學(xué)模型完全相同。53指派問題的推廣應(yīng)用例：某油田在調(diào)整一個(gè)區(qū)塊的開發(fā)計(jì)劃時(shí)，決定在這個(gè)區(qū)塊打5口調(diào)整井，井的位置及計(jì)劃產(chǎn)量已定?？紤]到這個(gè)區(qū)塊原有的3個(gè)計(jì)量站尚有富裕的處理能力，故決定不再新建計(jì)量站，而是將調(diào)整井分配給原有的計(jì)量站管理。