指派問題市公開課一等獎省賽課獲獎課件

指派問題（AssignmentProblem,AP）是一個特殊線性規(guī)劃問題，也屬于0-1整數(shù)規(guī)劃問題.5.5指派問題問題描述：在實際中經(jīng)常會碰到這么問題，有n項不一樣任務，需要n個人分別完成其中一項，但因為任務性質和各人專長不一樣，所以各人去完成不一樣任務效率（或花費時間或費用）也就不一樣。于是產生了一個問題，應指派哪個人去完成哪項任務，使完成n項任務總效率最高（或所需時間最少），這類問題稱為指派問題或分配問題。指派問題第1頁x3x1x2y2y1y3x4x5y4y5

該問題也可用矩陣表示假如xi

會做yj不然1111111111000000000000000

在矩陣中尋找什么？尋找最多不一樣行不同列1元素.指派問題第2頁指派問題數(shù)學模型設n個人被分配去做n件工作，要求每個人只做一件工作，每件工作只有一個人去做。已知第i個人去做第j件工作效率（時間或費用）為Cij(i=1.2…n;j=1.2…n)并假設Cij≥0。問應怎樣分配才能使總效率（時間或費用）最高？指派問題第3頁任務人員EJGRA215134B1041415C9141613D78119

Example

有一份漢字說明書需要譯成英、日、德、俄四種語言，分別記為E、J、G、R.現(xiàn)有A、B、C、D

四人，他們將漢字翻譯成不一樣語言所需時間如表,問應分配何人去完成何任務（一人完成一項任務），使所需總時間最少？指派問題第4頁設決議變量1分配第i個人去做第j件工作

xij=0相反(i,j=1.2.…n)其數(shù)學模型為：指派問題第5頁

顯然，這是一個0-1規(guī)劃問題，

也是一個特殊運輸問題

任務人員EJGRaiA2151341B10414151C91416131D781191bj1111

所以,分配問題可用解IP問題方法（如：分支定界法),或解運輸問題表上作業(yè)法.

因為算法引用了匈牙利數(shù)學家K?nig結論,所以，該算法也稱為匈牙利算法.指派問題第6頁Theorem假如從效益矩陣(cij)第i行中每個元素減去a和第j

列中每個元素加上b，得到一個新效益矩陣(cij)*.則以(cij)*為新目標函數(shù)與原目標函數(shù)指派問題最優(yōu)解相同.指派問題第7頁匈牙利算法：Step1使效益矩陣各行各列出現(xiàn)零元素；詳細：從效益矩陣每行各元素減去該行最小元素；再從所得矩陣每列各元素減去該列最小元素

.指派問題第8頁第二步：畫最少0元素覆蓋線，求維數(shù)r,檢驗是否能找到最優(yōu)解；當維數(shù)r=矩陣階數(shù)時，則已能找到最優(yōu)解，轉第四步；當維數(shù)r<矩陣階數(shù)時，則還不能找到最優(yōu)解，轉第三步；指派問題第9頁=28每行每列有零元素，能確保有n個獨立零元素嗎？

R=4=n,則已得到最優(yōu)解；Zmin=指派問題第10頁第三步：調整0元素分布后，重復第二步。調整0元素分布步驟：（1）在未被直線覆蓋元素中找出最小數(shù)，記a;（2）將未被直線覆蓋元素減去a;（3）僅被一條直線覆蓋元素不變；（4）同時被兩條直線覆蓋元素加上a.第四步：找出n個獨立0元素，確定最優(yōu)解。指派問題第11頁要強調是匈牙利法要求人數(shù)與任務數(shù)相等，且目標函數(shù)必須極小化。當人數(shù)與任務數(shù)不等，目標函數(shù)為極大化時，必須進行適當處理后才能用匈牙利法求解。指派問題第12頁

任務人員ABCD甲15182124乙19232218丙26171619丁19212317例6.11

有4個工人，要指派他們分別完成4項工作，每人做各項工作所消耗時間如表所表示。問指派哪個工人去完成哪項工作，可使總消耗時間最?。?/p>

指派問題第13頁求解過程以下：第一步，變換系數(shù)矩陣：指派問題第14頁

第三步，作最少直線覆蓋全部0元素：

獨立零元素個數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；

第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋全部元素中最小元素為1,指派問題第15頁得到3個獨立零元素，再調整指派問題第16頁線條數(shù)4=階數(shù)4，所以能找到最優(yōu)解：總時間=15+22+16+17=70指派問題第17頁例6.12最大收益最優(yōu)分配問題：有5名工人完成5項不一樣任務收益如表所表示：求使總收益到達最高任務分配方案。指派問題第18頁工人\任務12345110591811213196121433244541891217155116141910指派問題第19頁這是一個尋求總收益為最大值得極大化問題，我們必須把極大化問題轉化成極小化問題后才能用匈牙利法求解。解：設最大總收益問題收益矩陣為B=(bij),假如b=max(bij),則令cij=b-bij組成矩陣C,以C為矩陣最優(yōu)方案就是原最大總收益問題最優(yōu)方案。指派問題第20頁練習：115764戊69637丁86458丙9117129乙118957甲EDCBA費工作用人員指派問題第21頁-1-2指派問題第22頁◎?◎◎◎??指派問題第23頁◎?◎◎◎??√√√l=m=4<n=5指派問題第24頁◎?◎◎◎??指派問題第25頁◎?◎?◎?◎?√√√√√√√指派問題第26頁◎?◎?◎?◎?√√√√√√√l=m=4<n=5指派問題第27頁◎?◎?◎?◎?√√√√√√√