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

在現(xiàn)實(shí)生活中，有各種性質(zhì)的指派問題。例如，有若干項(xiàng)工作需要分配給若干人（或部門）來完成；有若干項(xiàng)合同需要選擇若干個投標(biāo)者來承包；有若干班級需要安排在若干教室上課等等。諸如此類的問題，它們的基本要求是在滿足特定的指派要求條件下，使指派方案的總體效果最佳。

【例1】

某廠擬派4個維修小組去維修4臺機(jī)車，他們相應(yīng)的完成工作所需時間cij(i,j=1,2,

3,4)由右表給出。如何給每個

小組安排工作才能使完成任務(wù)

的總時間最少。4指派問題

指派問題也稱分配或配置問題，是資源合理配置或最優(yōu)匹配問題。指派問題通常劃分為標(biāo)準(zhǔn)和非標(biāo)準(zhǔn)的指派問題。4.1指派問題的引入

機(jī)車1234小組12151342104141539141613478119

解：該指派問題是安排維修小組去維修機(jī)車，其決策變量為4指派問題

機(jī)車1234小組1x11x12x13x142x21x22x23x243x31x32x33x344x41x42x43x44該問題的數(shù)學(xué)模型為：任務(wù)約束

人員約束

4指派問題

【例2】

某商業(yè)

公司計劃開辦五家新商

店。為了盡早建成營業(yè)，

商業(yè)公司決定由5家建

筑公司分別承建。已知

建筑公司Ai(i=1,2,3,4,5)

對新商店Bj(j=1,2,3,4,5)

的建造費(fèi)用的報價（萬

元）為cij

，見下表。商

業(yè)公司應(yīng)當(dāng)對5家建筑公司怎樣分派建筑任務(wù)，才能使總的建筑費(fèi)用最少？商店B1B2B3B4B5建公A14871512A279171410A3691287A46714610A56912106

解：該指派問題是安排建筑公司承建商店，其決策變量為4指派問題

該問題的數(shù)學(xué)模型為：商店B1B2B3B4B5建公A1x11x12x13x14x15A2x21x22x23x24x25A3x31x32x33x34x35A4x41x42x43x44x45A5x51x52x53x54x55

顯然指派問題與運(yùn)輸問題相類似，該問題的指派平衡表如下：4指派問題

商店B1B2B3B4B5任務(wù)建公A148715121x11x12x13x14x15A2791714101x21x22x23x24x25A36912871x31x32x33x34x35A467146101x41x42x43x44x45A569121061x51x52x53x54x55公司數(shù)111114指派問題

4.2標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型

一般地，指派問題的一般提法是：有n項(xiàng)任務(wù)，需分配給n個人員（或設(shè)備）去完成，已知每個人員完成某項(xiàng)工作的效率（或成本等）為cij，如何給每個人員指派一項(xiàng)工作，使得完成任務(wù)的總效率最高（或總成本最少），見下表。任務(wù)1…j…n人1c11…c1j…c1n………………ici1…cij…cin………………ncn1…cnj…cnn解：4指派問題

稱矩陣C為效率矩陣（在其他問題中，可根據(jù)實(shí)際意義稱為費(fèi)用矩陣等），其元素cij體現(xiàn)了第i個人完成第j項(xiàng)工作時的效率，即

決策變量xij排成的n×n矩陣X稱為決策變量矩陣,其中4指派問題

分析：指派問題解的特征是它有n個1，其它都是0，且這n個1位于決策變量矩陣的不同行、不同列，每一種情況為指派問題的一個可行解，共n!個解。指派問題是：把這n個1放到的n

2個位置的什么地方可使耗費(fèi)的總資源最少？（解最優(yōu)）【例3】

對于效率矩陣決策變量矩陣都是指派問題的最優(yōu)解。4指派問題

4.3指派問題的求解

指派問題既是一類特殊的整數(shù)規(guī)劃問題，又是特殊的運(yùn)輸問題，因此可以用多種相應(yīng)的解法來求解，然而這些解法都沒有充分利用指派問題的特殊性質(zhì)，有效地減少計算量，直到1955年庫恩（W.W.Kuhn）提出的匈牙利法才有效地解決了指派問題。匈牙利法的理論基礎(chǔ)

定義2

獨(dú)立零元素組在效率矩陣中，有一組在不同行不同列的零元素，稱為獨(dú)立零元素組，其每個元素稱為獨(dú)立零元素?！纠?】

已知效率矩陣求其獨(dú)立零元素組。4指派問題

解：可行解｛c12=0，c24=0，c31=0，c43=0｝是一個獨(dú)立零元素組，c12=0，c24=0，c31=0，c43=0分別稱為獨(dú)立零元素；

｛c12=0，c23=0，c31=0，c44=0｝也是一個獨(dú)立零元素組，而｛c14=0，c23=0，c31=0，c44=0｝就不是獨(dú)立零元素組.

根據(jù)上述對效率矩陣中零元素的分析，將效率矩陣中出現(xiàn)的獨(dú)立零元素組中零元素所處的位置，在決策變量矩陣中令相應(yīng)的xij=1，其余的xij=0，就可找到指派問題的一個最優(yōu)解,如例14。

問題：在有的問題中效率矩陣中獨(dú)立零元素的個數(shù)不夠n個，這樣就無法求出最優(yōu)指派方案，需作進(jìn)一步的分析，首先給出下述定理。4指派問題

定理3

設(shè)指派問題的效率矩陣為C=[cij]n×n，若將該矩陣的某一行（或某一列）的各個元素都減去同一常數(shù)k（k可正可負(fù)），得到新的效率矩陣C’=[c’ij]n×n

，則以C’為效率矩陣的新的指派問題與原指派問題的最優(yōu)解相同。

推論若將指派問題的效率矩陣每一行或每一列分別減去各行或各列的最小元素，則得到新指派問題與原指派問題有相同的最優(yōu)解。

定理4

效率矩陣中獨(dú)立零元素的最多個數(shù)等于能覆蓋所有零元素的最少直線數(shù)。4指派問題

匈牙利法求解步驟

第一步：變換效率矩陣，將各行各列都減去當(dāng)前各行、各列中最小元素。

第二步：標(biāo)記新矩陣的獨(dú)立零元素。1）行檢驗(yàn)對變換后的效率矩陣進(jìn)行逐行檢驗(yàn)，若某行只有一個未標(biāo)記的零元素時，用“*”將該零元素做標(biāo)記，然后將被標(biāo)記的零元素所在的列的其它未標(biāo)記的零元素用“×”將該零元素標(biāo)記。2）列檢驗(yàn)與行檢驗(yàn)過程類似，對進(jìn)行了行檢驗(yàn)的矩陣逐列進(jìn)行檢驗(yàn)，對每列只有一個未被標(biāo)記的零元素，用“*”將該零元素做一標(biāo)記，然后將該元素所在行的其他未被標(biāo)記的零元素打“×”將該零元素標(biāo)記。重復(fù)上述列檢驗(yàn)，直到每一列都沒有未被標(biāo)記的零元素或有兩個未被標(biāo)記的零元素為止。

這時可能出現(xiàn)以下三種情況：

①每一行均有標(biāo)記“*”出現(xiàn)，“*”的個數(shù)m恰好等于n；

②存在未標(biāo)記的零元素，但他們所在的行和列中，未標(biāo)記過的零元素均至少有兩個；

③不存在未被標(biāo)記過的零元素，“*”的個數(shù)m<n。4指派問題

3）試指派

若情況①出現(xiàn)，則可進(jìn)行試指派：令“*”記號的決策變量取值為1，其他決策變量取值均為零，得到一個最優(yōu)指派方案，停止計算。

若情況②出現(xiàn)，則對每行、每列的其它未被標(biāo)記的零元素任選一個，加上標(biāo)記“*”，即給該零元素標(biāo)記“*”，然后給同行、同列的其它未被標(biāo)記的零元素加標(biāo)記“×”，然后再進(jìn)行行、列檢驗(yàn)，可能出現(xiàn)情況①或③，出現(xiàn)情況①就會得到最優(yōu)指派，停止計算。

若情況③出現(xiàn)，則要轉(zhuǎn)入下一步。

第三步：作最少直線覆蓋當(dāng)前所有零元素。4指派問題

1）對新矩陣中所有不含“*”元素的行打√；2）對打√的行中，所有打×零元素所在的列打√；

3）對所有打√列中標(biāo)記“*”元素所在行打√；4）重復(fù)上述2），3）步，直到不能進(jìn)一步打√為止；5）對未打√的每一行劃一直線，對已打√的每一列劃一縱線，即得到覆蓋當(dāng)前0元素的最少直線數(shù)。

第四步：對矩陣未被直線覆蓋過的元素中找最小元素，將打√行的各元素減去這個最小元素，將打√列的各元素加上這個最小元素（以避免打√行中出現(xiàn)負(fù)元素），這樣就增加了零元素的個數(shù)，返回第二步。【例5】

求解例1和例24指派問題

解：

故可得到指派問題的最優(yōu)解X，這樣安排能使總的維修時間最少，維修時間為z=4＋4＋9＋11=28（小時）。

故可得到指派問題的最優(yōu)解X，這樣安排能使總的建造費(fèi)用最少，建造費(fèi)用為z=7＋9＋6＋6＋6=34（萬元）。4指派問題

4指派問題

4.4非標(biāo)準(zhǔn)指派問題

在實(shí)際應(yīng)用中，常會遇到非標(biāo)準(zhǔn)形式，如求最大值，人數(shù)與工作數(shù)不相等以及不可接受的配置（某人不可完成某項(xiàng)任務(wù)）等特殊指派問題。解決的思路是先化成標(biāo)準(zhǔn)形式，然后再用匈牙利法求解，即對效率矩陣通過適當(dāng)變換使得滿足匈牙利算法的條件再求解。最大化的指派問題

最大化指派問題的一般形式為

解決辦法：設(shè)最大化的指派問題的系數(shù)矩陣為C=[cij]n×n

，M=max{c11,c12,…,cnn}，令B=[bij]n×n=[M-cij]n×n

，則以B為效率矩陣的最小化指派問題和以C為效率矩陣的原最大化指派問題有相同的最優(yōu)解。

4指派問題

【例6】

某工廠有4名工人A1,A2,A3,A4,分別操作4臺車床B1,B2,B3,B4,每小時單產(chǎn)量如

右表，求產(chǎn)值最大的分配方

案。車間B1B2B3B4工人A110987A23456A32112A44356

解：令M=max{10,9,…,6}=10人數(shù)和事數(shù)不等的指派問題4指派問題

B’中有4個獨(dú)立零元素，所以為最優(yōu)解，最大產(chǎn)值為z=10＋6＋1＋5=22。

若人數(shù)小于事數(shù)，添一些虛擬的“人”，此時這些虛擬的“人”做各件事的費(fèi)用系數(shù)取為0，理解為這些費(fèi)用實(shí)際上不會發(fā)生；若人數(shù)大于事數(shù)，添一些虛擬的“事”，此時這些虛擬的“事”被各個人做的費(fèi)用系數(shù)同樣也取為0?！纠?】

現(xiàn)有4個人，5件工作，每人做每件工作所耗時間如下表：4指派問題

工作B1B2B3B4B5工人A11011428A2711101412A35691214A4131511107問指派哪個人去完成哪項(xiàng)工作，可使總耗時最小？

解：添加虛擬人A5，構(gòu)造耗時矩陣C，

應(yīng)用匈牙利法求解，得到最優(yōu)解X，

最少耗時為z=2＋7＋6＋7=22。一個人可做幾件事的指派問題4指派問題

若某人可作幾件事，則可將該人化作相同的幾個“人”來接受指派。這幾個“人”做同一件事的費(fèi)用系數(shù)當(dāng)然一樣?！纠?】

對例13中的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司A4和A5，讓技術(shù)力量較強(qiáng)的建筑公司A1,A2,A3來承建5家商店，其

投標(biāo)費(fèi)用見右表。根據(jù)實(shí)

際情況，允許每家建筑公

司承建一家或兩家商店，

求使總費(fèi)用最少的指派方

案。商店B1B2B3B4B5建公A14871512A279171410A3691287

解：由于每家建筑公

司最多可承建兩家新商店，因此，把每家建筑公司化作Ai’和Ai’’(i=1,2,3)相同的兩家建筑公司因而費(fèi)用矩陣變?yōu)椋?指派問題

上面的系數(shù)矩陣有6行5列，為了使“人”和“事”的數(shù)目相同，引入一件虛擬“事”，使之成為標(biāo)

準(zhǔn)的指派問題，其效率矩