指派問題及其應(yīng)用石家莊學院畢業(yè)論文16-17-1引言指派問題是現(xiàn)實生活中經(jīng)常遇到的一類組合優(yōu)化問題，應(yīng)用十分廣泛．在生活中經(jīng)常遇到這樣的問題，某單位需完成n項任務(wù)，恰好有個人可承擔這些任務(wù)．由于每人的專長不同，各人完成任務(wù)不同(或所費時間)，效率也不同．于是產(chǎn)生應(yīng)指派哪個人去完成哪項任務(wù)，使完成項任務(wù)的總效率最高(或所需總時間最小)．這些問題的解決都涉及到指派問題．它們的基本要求是在滿足特定的指派要求條件下，使指派方案的總體效果最佳．通常的指派問題多是求項目的總工時最少，而很多情況下人們并不關(guān)心項目總工時多少，而只關(guān)心項目能否在最短時間完成，即歷時最少的指派問題．1955年，美國運籌學家H．W．Kuhn依據(jù)匈牙利數(shù)學家Konig的0元素覆蓋定理首次建立了人事指派問題求解的匈牙利法．1992年，建立了關(guān)于人事指派問題求解的指派矩陣同解變換與同解改造理論及削高排除法．1994年，北京大學張立昂教授依據(jù)指派矩陣同解變換理論設(shè)計出人事指派問題的周良澤算法．在本文中給出了一類人員招聘問題，建筑中以及圖書館資源配置的數(shù)學模型，利用運籌學中線性規(guī)劃中的指派問題進行決策，建立量化的分配模型，應(yīng)用匈牙利算法解決了實際生活中遇到的這些問題．2指派問題的相關(guān)知識線性規(guī)劃是運籌學的一大分支，是目前管理中經(jīng)常使用而又卓有成效的優(yōu)化技術(shù)．線性規(guī)劃在運用過程中主要可以解決兩類問題，一類問題是在任務(wù)確定后，如何統(tǒng)籌安排，做到用盡量少的人力和物力資源來完成任務(wù)；另一類問題是在一定量的人力、物力資源條件下，如何安排、使用它們，使完成的任務(wù)最多，在這樣的條件下常常解決的是指派問題．2.1數(shù)學模型的介紹為了建立標準指派問題的數(shù)學模型，引入個0-1變量：（=1，2，．．．，n)這樣，問題的數(shù)學模型可寫成其中，第一個式子表示每件事必有且只有一個人去做．第二個式子表示每個人必做且只做一件事．2.2匈牙利法指派問題是一類特殊的運輸問題，也是0-1型整數(shù)規(guī)劃問題，因此可以有多種解法求解．但是由于指派問題的數(shù)學結(jié)構(gòu)的特殊性，可用比求解運輸問題或者0-1型整數(shù)規(guī)劃更簡便有效的方法來求解指派問題，這就是所謂的匈牙利法．該算法于1955年由庫恩提出．因其關(guān)鍵定理由匈牙利數(shù)學家康尼格予以證明，故稱為匈牙利法．定理1設(shè)是效率矩陣,若可行解的個1(在解矩陣的不同行不同列上)對應(yīng)的個都為0,則x*是最優(yōu)解．(顯然=0)．則是最優(yōu)解．因此需對效率矩陣作變換,使變換后效率矩陣．含有個不同行不同列個0．由此求得最優(yōu)解矩陣的個1是對應(yīng)于效率矩陣的這個0．指派問題的最優(yōu)解有這樣性質(zhì)，若從效率矩陣()的一行(列)各元素中分別減去該行(列)的最小元素，得到新矩陣()，那么以()為效率矩陣求得的最優(yōu)解和用原效率矩陣求得的最優(yōu)解相同．定理2設(shè)給定了以()為效率矩陣指派問題，現(xiàn)將的元素改變?yōu)椋瑸槌?shù)．則以=()為效率矩陣指派問題與有相同的最優(yōu)解．證明首先效率矩陣的這種變化只是目標值在變換，并不影響約束方程組，其次用和分別記問題與的目標函數(shù)值,則即和只相差一個常數(shù),故它們有相同的最優(yōu)解．利用這個性質(zhì)，可使原效率矩陣變換為含有很多0元素的新效率矩陣，而最優(yōu)解保持不變，在效率矩陣()中，我們關(guān)心位于不同行不同列的0元素，以下簡稱為獨立的0元素．若能在效率矩陣()中找出個獨立的0元素；則令解矩陣()中對應(yīng)這個獨立的0元素的元素取值為1，其他元素取值為0．將其代入目標函數(shù)中得，它一定是最?。@就是以()為效率矩陣的指派問題的最優(yōu)解．也就得到了原問題的最優(yōu)解．2.3匈牙利法的解法步驟第一步：使指派問題的效率矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素．(1)從效率矩陣的每行元素減去該行的最小元素；(2)再從所得效率矩陣的每列元素中減去該列的最小元素．若某行(列)已有0元素，那就不必再減了．第二步:做能覆蓋所有零元素的最少數(shù)目的直線集合．此時，若直線數(shù)等于,則可得出最優(yōu)解，否則，轉(zhuǎn)到第三步．第三步:變換效率矩陣，使未被直線覆蓋的元素中出現(xiàn)零元素．回到第二步．在未被直線覆蓋的元素中總有一個最小元素．對未被直線覆蓋的元素所在的行（或行）中各元素都減去這一最小元素，這樣，在未被直線覆蓋的元素中勢必會出現(xiàn)零元素，但同時卻又使已被直線覆蓋的元素中出現(xiàn)負元素．為了消除負元素，只要對它們所在的列（或行）中各元素都加上這一最小元素（可以看作減去這一最小元素的相反數(shù)）即可．第四步：進行指派，尋求最優(yōu)解．需找出個獨立的0元素．若能找出，就以這些獨立0元素對應(yīng)解矩陣()中的元素為1，其余為0，這就得到最優(yōu)解．當較小時，可用觀察法去找出個獨立0元素．若較大時，就必須按一定的步驟去找，常用的步驟為：(1)從只有一個0元素的行(列)開始，給這個0元素加圈，記作◎．這表示對這行所代表的人只有一種任務(wù)可指派．然后劃去◎所在列的其他0元素，記作Φ．這表示這列所代表的任務(wù)已指派完，不必再考慮別人了．如此反復(fù)進行，直到所有0元素都被圈出和劃掉為止．(2)若遇到同行(列)的0元素至少有兩個(表示可以從兩項任務(wù)中指派其一)，可以任選一行(列)中某一個0元素，再劃去同行(列)的其他0元素．3應(yīng)用舉例隨著科學技術(shù)的不斷進步，指派問題已經(jīng)越來越多地出現(xiàn)在我們生活中．為解決一個實際問題，建立數(shù)學模型是一種有效的重要方法．對于建立起來的數(shù)學模型，還需要用一定的技術(shù)手段（如匈牙利法等）求解數(shù)學問題，以達到解決實際問題的目的．這在現(xiàn)在的生活中是常用．3.1平衡指派問題的應(yīng)用在實際生活和生產(chǎn)安排中，經(jīng)常遇到要指派不同的工作人員去完成數(shù)目相同的工作．由于每個人的專長不同，不同的人去完成各項任務(wù)的效率(或所花時間或成本等)一般地也不同．這樣，就產(chǎn)生了指派何人去完成何任務(wù)，使總效率最高(或所花時間最少或成本最低等)的問題．這就是在運籌學中的所謂的平衡指派問題，下面就運用以上介紹的知識到實際問題中．3.1.1建筑中的應(yīng)用例某商業(yè)公司設(shè)計開辦五家新聞商店．為了盡早建成營業(yè)，商業(yè)公司通知了五個建筑公司，以便讓每家新商店由一個建筑公司承建．建筑公司對新商店的建造費用的投標均見表．商業(yè)公司應(yīng)當對五家建筑公司怎樣分配建造任務(wù)，才能使總建造費用最少？解這是一個標準的指派問題．若設(shè)0-1變量（=1,2,3,4,5)則問題的數(shù)學模型為其效率矩陣為對各行元素分別減去本行的最小元素，對各列也如此，得容易看出，可用四條直線覆蓋所有零元素，這是最少數(shù)直線集合，由于的階數(shù)=5，故需對效率矩陣繼續(xù)變換．為了使未被直線覆蓋的元素中出現(xiàn)零元素，將第二行和第三行中各元素減去未被直線覆蓋元素中的最小元素1．但這樣一來，第一列中出現(xiàn)了負元素，因而再對第一列各元素分別加上1，即此時，已不能用少于五條直線來覆蓋所有零元素，故已可看得最優(yōu)指派方案．為了得到最優(yōu)指派方案，對效率矩陣進行圈零：先找出零元素最少行列,然后對其它行列的零元素進行篩選,保證各行列只有一個零元素．所以，本題最優(yōu)解為也就是說，最優(yōu)指派方案為：讓承建,承建,承建,承建,承建,這樣總的建設(shè)費用最少,為7+9+6+6+6=34萬元．圖書館資源優(yōu)化配置中的應(yīng)用長期以來圖書館決策以多年來積累的管理經(jīng)驗為基礎(chǔ)進行微調(diào)或不調(diào)，這種決策方式缺乏科學性，難以實現(xiàn)資源的最優(yōu)配置．因此，以建立科學合理的定量管理辦法為基礎(chǔ)，輔之以多年經(jīng)驗進行決策既能滿足圖書館資源優(yōu)化的需求，又能為領(lǐng)導決策節(jié)省大量時間．目前，高校圖書館經(jīng)費緊張已是不爭的事實，如何合理、有效地利用有限資源已成為高校圖書館當前工作的重要任務(wù)．利用運籌學中線性規(guī)劃中的指派問題進行決策，建立量化的模型．例圖書加工流程一般分為：分類、編目、統(tǒng)計、入庫．而不同的工作人員，由于性格、專業(yè)背景等的不同對各項工序的執(zhí)行效率不同．如何合理指派任務(wù)使整體工作能快速、高效地完成?解若能對不同工作人員對于不同工序的完成情況進行合理評價，給出合理的效率數(shù)，從而得出效率矩陣，進而可以運用匈牙利法進行工作指派．建立效率系數(shù)表，如下圖所示．表1 工序人員甲乙丙丁分類30254032編目32353036統(tǒng)計35403427入庫28433238其中表示第名人員分配到第個崗位；表示第名人員分配到第個崗位．運用運籌學中指派問題的知識可以建立如下數(shù)學模型：所以（=1,2,3,4）可建立如下效率矩陣：記作因為中未被直線覆蓋元素的最小值是1，因此將中的第3，4行減去1，將第2列加上1，可得：記作此時m=n=4，因此決策變量矩陣為：即指派丙來完成分類，丁來完成編目，甲來完成統(tǒng)計，乙來完成入庫才能使工作效率最大，才使圖書加工速度最快，其總效率為f=40+36+35+43=154．3.2一般指派問題的應(yīng)用在現(xiàn)實中還會遇到人數(shù)與任務(wù)數(shù)不等的問題，也就是說有可能任務(wù)數(shù)多于人數(shù)或人數(shù)多于任務(wù)數(shù)．遇到這種情況需要處理一下，否則就不滿足指派問題的求解模型．具體方法如下：狀況方法人數(shù)少于任務(wù)數(shù)添加若干虛擬人任務(wù)數(shù)多于人數(shù)添加若干虛擬事一人可做件事加邊補小法某事不能由某人做加邊補零()法3.2.1人數(shù)多于事數(shù)或事數(shù)多于人數(shù)人數(shù)多于任務(wù)數(shù)的不平衡指派問題，可以采用添加虛擬任務(wù)的方法，使之轉(zhuǎn)化為平衡指派問題，即添加“虛擬”的事，各人做這些事的費用為零．最優(yōu)指派方案中，完成虛設(shè)的任務(wù)的那個人就不指派給任務(wù)，虛擬任務(wù)不會增加目標函數(shù)的值，所以，在上面轉(zhuǎn)化為平衡指派問題時每個人完成虛擬任務(wù)的效率設(shè)為0即可．添加虛擬任務(wù)后的新的平衡指派問題的匈牙利求解如下；同樣，對人數(shù)少于事數(shù)的情況，只需添加“虛擬”的人，這些人做各種事的費用為零．例一家企業(yè)崗位聘任，有甲乙丙丁四個人要競聘三個崗位，如何安排，才會使得工作的效率最大?最后四位競聘者對三個崗位的綜合效率數(shù)為表所示．表2職位甲乙丙丁崗位一75818667崗位二80747785崗位三83728583解當前的情況是競爭者多，崗位少，所以需要添加一個虛擬崗位四，得到其效益矩陣為：，所以（=1,2,3,4)．可建立如下效率矩陣：進行求解得到：于是得到結(jié)果為：競聘者甲競聘到崗位三，競聘者丙競聘到崗位一，競聘者乙競聘到崗位二．例現(xiàn)在有4個人，5件工作，每人做每件工作所耗時間見下表所示．表3工人工作 10114287111014125691214131511107問指派哪個人去完成哪項工作，可使總消耗時間最少?(每人只能做一件事）解添加虛擬人（戊），構(gòu)造效率矩陣：=從未劃去的元素中找最小者：｛4，3，7，5，1，4，7，9｝=1．未劃去的行減去此最小者1，劃去的列加上次最小者1，得 從而得到最優(yōu)指派矩陣:指定甲做工作4，乙做工作1，丙做工作2，丁做工作5，從而最小耗時為z=2+7+6+7=22．3.2.2一人可做件事考慮一人可做件事的指派問題作為多目標決策問題，首先要求指派給各人的任務(wù)數(shù)目相差不能超過1；其次要求所需總費用最少．這就用到加邊補小法，即一人化成P人法，當該人完成一項任務(wù)后，剩下的任務(wù)實際是交給完成此項任務(wù)用時間最少得人去完成，如以下例子．例某商業(yè)公司計劃開辦五家新商店．為了盡早建成營業(yè)，商業(yè)公司決定由3家建筑公司分別承建，每家最多可以承建2家商店．已知建筑公司（=1，2，3）對新商店（=1，2，3，4，5）的建造費用的報價（萬元）為（=1，2，3，4，5）．見下表所示，商業(yè)公司應(yīng)當對3家建筑公司怎樣分派建筑任務(wù)，才能使總的建筑費用最少？建筑商店487151279171410691287表4解系數(shù)矩陣為由于每家建筑公司最多可承建兩家新商店，因此，把每家建筑公司化作相同的兩家建筑公司（和，=1，2，3）．這樣，系數(shù)矩陣變?yōu)椋荷厦娴南禂?shù)矩陣有6行5列，為了使“人”和“事”的數(shù)目相同，引入一件虛擬事，使之稱為標準的指派問題，其系數(shù)矩陣為：這是一個方陣，用匈牙利解法可得最優(yōu)指派：亦即公司承建商店，公司承建商店，公司承建商店，可使總的建造費用最省，最小建造費用為（萬元）．3.2.3某事不能由某人做單位一般有若干個部門需要招聘，每個部門需要的職員有限，這些部門按工作性質(zhì)對職員也有些要求，這就對具有不同技能的人員有所限制，具體的辦法都有很大的區(qū)別，所以需要考慮一個適合不同分配方法的人才評價模型．評價模型建立的基礎(chǔ)是對職員特長等級評分的量化工作．方法是在指派方案中，某事的任務(wù)由虛擬的人完成，然后用匈牙利算法得到的指派最優(yōu)．例某單位分配甲、乙、丙、丁四個人去完成、、、、五項任務(wù)，每人完成各項任務(wù)的時間（單位：小時）見表所示．由于任務(wù)重，人數(shù)少，考慮：（1）只需完成4項任務(wù)．任務(wù)必須完成，其他4項任務(wù)可選3項完成，但是甲不能做項工作．（2）5件任務(wù)必須都完成，其中有一人完成兩項，其他人每人完成一項．試就（1）、（2）兩種情況分別確定最優(yōu)分配方案，使完成任務(wù)的時間最少．表5人人任務(wù)甲2529314237乙3938262033丙3427284032丁2442362345解這是人數(shù)與工作不等的指派問題，若用匈牙利解法求解，需作一定的處理．（1）由于任務(wù)數(shù)大于人數(shù)，所以需要一個虛擬的人，設(shè)為戊．因為必須完成故設(shè)戊完成的時間為（為非常大的數(shù)），即戊不能做工作，其余的假想時間為0，見下表所示表6人任務(wù)甲29314237乙3938262033丙3427284032丁2442362345戊0000用匈牙利解法求解過程如下：行變換 ，第2、4行減去1，第4列加上1得：從而得到最優(yōu)指派:得到表7甲乙丙丁即甲完成任務(wù)，乙完成任務(wù)，丙完成任務(wù)，丁完成任務(wù)．最少的耗時數(shù)（小時）可以考慮將其中某一人看作兩人，共有4種可能，然后一一求解最佳時間，再分別比較找出最少時間，但是該方法比較繁瑣，考慮下述解法：設(shè)有虛擬人戊，它集五人優(yōu)勢為一身，即戊完成每件任務(wù)的時間是每個人該完成任務(wù)的最低者．戊所完成的任務(wù)即由完成此項任務(wù)時間最低者來完成，見下表所示．表8人任務(wù)甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032下面用匈牙利解法求解如下：行變換列變換對做最少直線覆蓋:直線數(shù)3小于5，未被直線覆蓋的元素最少者為1，用未被直線劃去的行都減去1，被直線劃去的列都加上1，有對做最少直線覆蓋：直線數(shù)3小于5，未被直線覆蓋的元素最小者為4，用未被直線劃去的行都減去4，被直線劃去的列都加上4，有由于0數(shù)為5，等于方陣階數(shù)5，故可得最優(yōu)指派矩陣相應(yīng)指派見下表所示：表9甲乙