第四章-指派問題

信息處理中的組合優(yōu)化

第四章指派問題CombinatorialOptimizationinInformationProcessing

指派問題（AssignmentProblem,AP）是一種特殊的線性規(guī)劃問題，也屬于0-1整數(shù)規(guī)劃問題.在圖論中稱為最佳匹配問題（OptimalMatching）.問題描述：有n

項(xiàng)任務(wù)需要去完成，恰好有

n

個(gè)人可以去完成這n項(xiàng)任務(wù)，而每個(gè)人完成各項(xiàng)任務(wù)的效率是不同的，如果要求每人完成其中一項(xiàng)，且每項(xiàng)任務(wù)只交給其中一人去完成，應(yīng)如何分配，使總的效率最高.第四章指派問題§1最大基數(shù)匹配問題§2指派問題§3指派問題的應(yīng)用§4瓶頸分配問題第四章指派問題§1最大基數(shù)匹配問題人員工作分配問題：某公司有工作人員x1,x2,…,xn,他們?nèi)プ鰊

項(xiàng)工作y1,y2,…,yn

，每人會(huì)做其中的一項(xiàng)或幾項(xiàng)，要求每人至多做一項(xiàng)，每項(xiàng)工作至多由一人來做，問能否每人都分配到一項(xiàng)會(huì)做的工作？x3x1x2y2y1y3如果不那么最多幾人有會(huì)做的工作可做？且如何安排？可用圖和矩陣給出它的數(shù)學(xué)模型及求解方法

.§1最大基數(shù)匹配問題Definition4.1設(shè)圖

G=(V，E)GraphVertexEdge1、如果，且對(duì)，與

無公共頂點(diǎn)，則稱邊子集M是G的一個(gè)匹配；2、M中的每條邊的兩個(gè)頂點(diǎn)稱為關(guān)于

M是飽和的，否則稱為非飽和的；3、G中每個(gè)頂點(diǎn)都關(guān)于

M是飽和的，則稱M

是

G的一個(gè)完備匹配；4、如果M

是一匹配，而不存在其他匹配M1，使得5、如果M

是一匹配，而對(duì)不是G

的匹配，則稱

M

是G的一個(gè)極大匹配

.Note:最大匹配與極大匹配的邊數(shù)是不同的x3x1x2y2y1y3，則稱M

是G的最大（基數(shù)）匹配；第四章指派問題6、如果G的頂點(diǎn)V可分成兩個(gè)滿足如下條件的子集X，Y

：②對(duì)，則與ej

關(guān)聯(lián)的兩個(gè)頂點(diǎn)分屬X

Y，稱G=(X,Y,E)為二部圖或偶圖

.x3x1x2y2y1y3x4x5y4y5①人員工作分配問題就是在二部圖中尋找最大匹配.§1最大基數(shù)匹配問題x3x1x2y2y1y3x4x5y4y5該問題也可用矩陣表示如果xi

會(huì)做yj否則1111111111000000000000000

在矩陣中尋找什么？

尋找最多的不同行不同列的1元素.(二部圖G的鄰接矩陣)

稱為獨(dú)立元（素）第四章指派問題如何尋找？禮讓原則

從每行、每列中，1

最少的行或列先取，一樣多時(shí)隨意

.×××××

遺憾的是這是錯(cuò)的××××××××ק1最大基數(shù)匹配問題

1965年匈牙利著名數(shù)學(xué)家Edmonds

為之設(shè)計(jì)了命名為“匈牙利算法”的有效算法，計(jì)算復(fù)雜性為O(n).就二部圖的鄰接矩陣，先給出幾個(gè)概念：

在第i

行第j列上的①（1被加圈）表示xi(或yj

)已被分配，或該行（或列）已被分配；

此時(shí)，由于所在行和列的1元素不能再取，用1表示;×不同行不同列的①，稱為A的一個(gè)分配，用M

表示;第四章指派問題×××設(shè)M為已知分配，xi

未被分配，而該行沒有1，則xi

不能被分配；若有1，選擇一個(gè)1(aij),如果第j列沒有加圈1，則對(duì)該1加圈，得到一新的分配M′,有，如果有加圈1（ai1j），則對(duì)aij,ai1j打√,√√√且劃去第j列，再看第i1

行有否沒有被劃去的1，

沒有，結(jié)束；有，再重復(fù)上述過程，直至不能繼續(xù)為止.這時(shí)所得序列，稱為關(guān)于M

的交互鏈

.如果在交互鏈中，最后得到的是無圈1，則稱該交互鏈為可增廣鏈

.把可增廣鏈中的加圈1與沒圈的1，互換標(biāo)記，得到一新的分配M′,有.上述過程稱之為增廣過程.交互鏈、可增廣鏈可在圖G中描述§1最大基數(shù)匹配問題Theorem4.1(Berge,1957)

M

是A的最大分配的充要條件是不存在可增廣鏈

.匈牙利算法：Step1任給一初始分配

M

，設(shè)S為未被M分配的行集合；Step2如果，則此時(shí)已得到最大分配，End否則，?。籗tep3尋找xi

出發(fā)的可增廣鏈，如果存在，則進(jìn)行增廣；且令GotoStep2;否則xi不能被分配，令GotoStep2;對(duì)圖G的最大匹配，結(jié)論也成立proofTheorem4.1的證明Proof:必要性：若M是A

的最大分配，顯然A

中無關(guān)于M

的可增廣鏈，不然

M

還可以增廣成獨(dú)立元更多的分配，與M是最大分配相違；充分性：反證，若M

不是最大分配，則存在分配

M1,作

由于M2

是由M，M1

中非公共部分組成，而M,M1

都是分配，所以從M2

的任一1出發(fā)，按交互鏈得到方法，得到的鏈必是M,M1

中的1交替出現(xiàn).√√√√√√√

由于，所以在所有的交互鏈中，必有一條鏈屬于M1

的1多于屬于M

的1，且以M1

的

1出發(fā)、結(jié)束，這是關(guān)于M

的可增廣鏈.與條件矛盾.證畢√√√√第四章指派問題Example1

求G的最大匹配，G的鄰接矩陣如右所示：√Solution:不妨設(shè)初始匹配取x3，從x3y2

出發(fā)，√√√得一增廣鏈：增廣得：√√√√√取x4，得一增廣鏈：增廣得：取x5，從x5y3出發(fā)，√得一交互鏈，但不是增廣鏈

.從x5y4

出發(fā)，因y4未被分配，所以對(duì)x5y4

加圈，得：所以，M

是最大匹配，且是完備匹配.§2指派問題在第一節(jié)的人員工作安排問題中，分配工作時(shí)，只考慮人員有工作做.但事實(shí)上，由于工作的性質(zhì)和個(gè)人的特長不同，在完成不同的任務(wù)時(shí)，其效益是不同的（成本、時(shí)間、利潤、費(fèi)用etc.）.

§2指派問題設(shè)有n

個(gè)人員去完成n項(xiàng)任務(wù)，第i人完成第j

項(xiàng)任務(wù)的效益為，要求每人完成且僅完成一項(xiàng)，問如何分配，使完成n

項(xiàng)任務(wù)的總效益最佳

.可以是max、min先考察min稱C=(cij)n×n

為效益矩陣.

第四章指派問題Example2

任務(wù)人員EJGRA215134B1041415C9141613D78119有一份中文說明書需要譯成英、日、德、俄四種語言，分別記為E、J、G、R.現(xiàn)有A、B、C、D

四人，他們將中文翻譯成不同語言所需時(shí)間如表,問應(yīng)分配何人去完成何任務(wù)（一人完成一項(xiàng)任務(wù)），使所需總時(shí)間最少？Solution:當(dāng)分配第i

人完成第j項(xiàng)任務(wù)否則設(shè)s.t.§2指派問題

顯然，這是一個(gè)0-1

規(guī)劃問題，

任務(wù)人員EJGRA215134B1041415C9141613D78119

任務(wù)人員EJGRaiA2151341B10414151C91416131D781191bj1111

也是一個(gè)特殊的運(yùn)輸問題

.所以,分配問題可用解IP問題方法（如：分支定界法),或解運(yùn)輸問題的表上作業(yè)法.但是，1、IP

是NP-C問題；2、有基變量2n-1個(gè)，而有n-1個(gè)為零，高度退化.

1955年，Kuhn-Munkras

提出了解AP

的算法，將求AP

轉(zhuǎn)化為求完備匹配問題，其計(jì)算復(fù)雜性為O(n3).

由于算法引用了匈牙利數(shù)學(xué)家

K?nig

的結(jié)論,所以，該算法也稱為匈牙利算法.第四章指派問題Theorem4.2(K?nig,1931)

Definition4.2圖G=(V，E)，一個(gè)頂點(diǎn)在C中，稱C

為G的一個(gè)點(diǎn)（對(duì)邊的）覆蓋

.點(diǎn)集若G中每條邊至少有點(diǎn)數(shù)最少的點(diǎn)覆蓋C稱為G的最小點(diǎn)覆蓋

.二部圖G=(X，Y，E)，M為最大匹配，C為最小點(diǎn)覆蓋，則有監(jiān)測(cè)點(diǎn)的設(shè)置等是最小點(diǎn)覆蓋的應(yīng)用

.

點(diǎn)覆蓋在二部圖G的鄰接矩陣上如何表示？Proof

Theorem4.2的證明Proof:顯然，若，則若，設(shè)X1為在M

中沒有獨(dú)立元的行的集合.如右

令Z是X1中行出發(fā)的關(guān)于M

的交互鏈上的所有點(diǎn)，如右

記則

表示S中的行的所有1對(duì)應(yīng)的列取則B

是A

的一個(gè)覆蓋，如果不是，則有1元素行在S

列在

Y-T

中，這與矛盾.而，顯然所以B

是最小覆蓋.證畢§2指派問題顯然，Ex.2的可行解可用一個(gè)0-1矩陣表示

.表示：因此，求解指派問題可在效益矩陣上進(jìn)行

.Theorem4.3如果從效益矩陣(cij)的第i行中每個(gè)元素減去a和第j

列中每個(gè)元素加上b，得到一個(gè)新的效益矩陣.則以為新的目標(biāo)函數(shù)與原目標(biāo)函數(shù)的指派問題最優(yōu)解相同

.第四章指派問題匈牙利算法：Step1使效益矩陣各行各列出現(xiàn)零元素；具體：從效益矩陣的每行各元素減去該行最小元素；再從所得矩陣的每列各元素減去該列最小元素

.稱各行各列所減的數(shù)值之總和為縮減量，記為

S.S=2+4+9+7+4+2=28§2指派問題Step2試尋求最優(yōu)解；用上節(jié)的求最大匹配的算法

.這時(shí)得到最大匹配

M.如果，則已得到最優(yōu)解；即28=S每行每列有零元素，能保證有n個(gè)獨(dú)立零元素嗎？

如果，則gotostep3

；第四章指派問題Step3作縮減后的效益矩陣的最小覆蓋；具體：a、對(duì)沒有0

的行打√；

b、對(duì)已打√的行中所有含0

元素的列打√；

c、對(duì)打√的列上有

0的行打√；

d、重復(fù)b、c

，直到得不出新的打√的行列為止；

e、對(duì)打√的列畫縱線，沒打√行畫橫線.這就得到最小覆蓋

.§2指派問題Example3求效益矩陣為C

的最小指派.Solution:√√√縮減量S1=26此時(shí)，.第四章指派問題Step4增加零元素√√√具體：a、求出未被直線覆蓋的元素中的最小值k；

顯然，在直線下增加零元素是不增加獨(dú)立零的本例k=2b、對(duì)打√的行減去k

，打√的列加上k

，gotostep2.-2-2+2縮減量為S2=2+2-2=2此時(shí)，所以最優(yōu)解為zmin=

S1+S2=26+2=2828

零元素是增加嗎？§2指派問題考慮極大化問題令可以嗎？匈牙利算法要求矩陣元素非負(fù)作一新矩陣

取則Example4（婚姻問題）取M=28對(duì)人多任務(wù)少，人少任務(wù)多，如何？虛設(shè).第四章指派問題§3指派問題的應(yīng)用Example5現(xiàn)有6項(xiàng)任務(wù)，由4個(gè)工廠來完成，已知各個(gè)工廠完成各項(xiàng)任務(wù)的費(fèi)用矩陣為C，應(yīng)如何分配任務(wù)，使總費(fèi)用最??？具體分別1、無要求；2、一廠至多完成兩項(xiàng)；3、一廠至多完成兩項(xiàng)，至少完成一項(xiàng)

.Solution:1、無要求碰巧，符合2、3的要求Zmin=13§3指派問題的應(yīng)用2、一廠至多完成兩項(xiàng)

設(shè)想每個(gè)工廠由兩個(gè)分廠組成，問題變?yōu)?/p>

8個(gè)工廠完成6項(xiàng)任務(wù),虛設(shè)2個(gè)任務(wù)，費(fèi)用為零.

說明什么？3、一廠至多完成兩項(xiàng)，至少完成一項(xiàng)

.一個(gè)廠不能同時(shí)完成最后兩個(gè)任務(wù).如何做到？MM

MM

MM

MM

Zmin=13第四章指派問題Example6（鐵路列車運(yùn)行分派問題）

A

站與B

站之間擬開7對(duì)客車，客車的運(yùn)行時(shí)間如圖，現(xiàn)在要給列車固定乘務(wù)組.現(xiàn)在假定，哪站的乘務(wù)組換班地點(diǎn)就在那站，乘務(wù)組在對(duì)方折返停留的最短時(shí)間為2小時(shí)，問如何分派任務(wù)使7個(gè)乘務(wù)組在折返點(diǎn)的總耗時(shí)最??？

問題：列車如何配對(duì)，乘務(wù)組由哪個(gè)車站提供？AB0246810121416182022241214108642131197531§3指派問題的應(yīng)用AB0246810121416182022241214108642131197531Solution:24681012142024最大數(shù)與最小數(shù)？217

2468101214221825……24…14構(gòu)造一個(gè)新矩陣

C,2468101214

zmin=20小時(shí)如何考慮A

、B

兩站的均衡？第四章指派問題指派問題的分支與定界算法

因?yàn)?，所以是沒必要使用B.B.M，在此只是對(duì)方法的訓(xùn)練.參見

Ex.3Solution:該問題的可行解僅有24個(gè)，然而若n=20,則可行解超過1018個(gè).指派問題的約束為：考慮去掉約束（*）得一松弛問題.§3指派問題的應(yīng)用

分配人工作時(shí)間

A

E2

BJ4

AG9

AR7

總時(shí)間

=22解松弛問題，得：下界為22.顯然，不是可行解

.考慮最優(yōu)解中，任務(wù)

E

必為A、B、C、D

四人中一人完成.所以分成四支，每支先確定一人完成E

，余下三項(xiàng)按前述松弛問題處理.第一支AE

，

不可行，得

下界為27.

分配人工作時(shí)間

A

E2

BJ4

DG13

BR8

總時(shí)間

=27類似得到：第二支BE

，etc.

分配人工作時(shí)間

B

E15

AJ10

AG9

AR7

總時(shí)間

=41第四章指派問題1222273414336367248341237112813399281031AEEEEDCBDE,524EJJJCBACAGG可行可行*JJJDCB*可行***經(jīng)計(jì)算13次(幾乎是可行解的一半)找到最優(yōu)解，BJAG,CRzmin=28§4瓶頸分配問題§4瓶頸分配問題經(jīng)典分配問題（AP）

任務(wù)人員EJGRA215134B1041415C9141613D78119每人完成一個(gè)任務(wù)每個(gè)任務(wù)一人完成條件：目標(biāo)：總完成時(shí)間最少總效益最佳數(shù)學(xué)模型：求解方法：匈牙利算法s.t.第四章指派問題瓶頸分配問題(BAP)每人完成一個(gè)任務(wù)每個(gè)任務(wù)一人完成條件：目標(biāo)：最大完成時(shí)間最小經(jīng)典分配問題：z=5瓶頸分配問題：z=2數(shù)學(xué)模型：當(dāng)分配第i

人完成第j項(xiàng)任務(wù)否則設(shè)§4瓶頸分配問題

任務(wù)人員EJGRA215134B1041415C9141613D78119第一個(gè)任務(wù)的完成時(shí)間：s.t.這是非線性的第四章指派問題求解方法：首先會(huì)想到什么方法一、化為經(jīng)典分配問題1144413404013求效益矩陣(dij)的經(jīng)典分配：所以，fmin

=2§4瓶頸分配問題對(duì)原效益矩陣C

的元素cij

的不同的值按從小到大的順序排序.

c(k)

為第k

個(gè)值，用s表示不同c(k)