指派問(wèn)題的算法

ID:46444078

大?。?38.01 KB

頁(yè)數(shù):15頁(yè)

時(shí)間:2019-11-23

指派問(wèn)題的算法_第1頁(yè)
指派問(wèn)題的算法_第2頁(yè)
指派問(wèn)題的算法_第3頁(yè)
指派問(wèn)題的算法_第4頁(yè)
指派問(wèn)題的算法_第5頁(yè)
資源描述:

《指派問(wèn)題的算法》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、指派問(wèn)題的算法分析與實(shí)現(xiàn)摘要在企業(yè)、公司的運(yùn)營(yíng)與管理中,管理者總是希望把人員最佳分派以發(fā)揮其最大工作效率,從而降低成本、提高效益。然而,如果沒(méi)有科學(xué)的方法是很難實(shí)現(xiàn)優(yōu)化管理的,由此我們引入了指派問(wèn)題。指派問(wèn)題多是求項(xiàng)目的工時(shí)最少,而很多情況下人們并不關(guān)心項(xiàng)目總工時(shí)的多少,而只關(guān)心項(xiàng)目能否在最短的時(shí)間內(nèi)完成,即歷時(shí)最少的指派問(wèn)題。這類(lèi)問(wèn)題研究的是n個(gè)人執(zhí)行n項(xiàng)任務(wù),執(zhí)行每項(xiàng)任務(wù)的人數(shù)以及總的指派人項(xiàng)數(shù)均有限制,要求最優(yōu)指派。在運(yùn)籌學(xué)中求解整數(shù)規(guī)劃的指派問(wèn)題通常是通過(guò)匈牙利算法來(lái)求解,但指派問(wèn)題也可以歸結(jié)為一個(gè)0-1整數(shù)規(guī)劃問(wèn)題,本文

2、先對(duì)指派問(wèn)題進(jìn)行陳述,引出對(duì)實(shí)際問(wèn)題的求解。在指派問(wèn)題的背景、描述中充分理解該問(wèn)題,先運(yùn)用匈牙利算法實(shí)現(xiàn)指派問(wèn)題,然后再建立一個(gè)0-1整數(shù)規(guī)劃模型,并運(yùn)用matlab和lingo編譯程序?qū)?wèn)題進(jìn)行編譯,運(yùn)用軟件解決模型問(wèn)題,最終實(shí)現(xiàn)指派問(wèn)題在實(shí)際問(wèn)題中的運(yùn)用。通過(guò)運(yùn)用匈牙利算法和0-1整數(shù)規(guī)劃同時(shí)對(duì)指派問(wèn)題求解,我們發(fā)現(xiàn)用0-1整數(shù)規(guī)劃的方法來(lái)求解可以更簡(jiǎn)單,也更方便程序的閱讀和理解。與此同時(shí),我們還對(duì)0-1整數(shù)規(guī)劃問(wèn)題由整數(shù)數(shù)據(jù)深入研究到小數(shù)數(shù)據(jù)。最后通過(guò)實(shí)例來(lái)說(shuō)明運(yùn)用matlab,lingo編譯程序來(lái)解決整數(shù)規(guī)劃問(wèn)題的簡(jiǎn)便和有

3、效性。關(guān)鍵詞:指派問(wèn)題;匈牙利算法;0-1整數(shù)規(guī)劃;matlab模型;lingo模型1.問(wèn)題陳述15指派問(wèn)題又稱(chēng)分配問(wèn)題,其用途非常廣泛,比如某公司指派n個(gè)人去做n件事,各人做不同的事,如何安排人員使得總費(fèi)用最少?若考慮每個(gè)職工對(duì)工作效率(如熟練程度等),怎樣安排會(huì)使總銷(xiāo)量達(dá)到最大?這些都是一個(gè)企業(yè)經(jīng)營(yíng)管理者必須考慮的問(wèn)題,所以該問(wèn)題有重要的應(yīng)用價(jià)值。假設(shè)有n件工作分派給n個(gè)人來(lái)做,每項(xiàng)工作只能由一人來(lái)做,每個(gè)人只能做一項(xiàng)工作。若給出各人對(duì)各項(xiàng)工作所具有的工作效率。問(wèn)應(yīng)該如何安排人選,及發(fā)揮個(gè)人特長(zhǎng)又能使總的效率最大。為此用0-1

4、整數(shù)規(guī)劃來(lái)實(shí)現(xiàn)指派問(wèn)題即如何安排人選。2.背景在現(xiàn)實(shí)生活中,有各種性質(zhì)的指派問(wèn)題(AssignmentProblem)。例如,在生產(chǎn)管理中,總希望把人員進(jìn)行最佳分配,以發(fā)揮最大的工作效率;某部門(mén)有n項(xiàng)任務(wù)要完成,而該部門(mén)正好有n個(gè)人可以分別去完成其中任何一項(xiàng),但由于任務(wù)性質(zhì)和個(gè)人的專(zhuān)長(zhǎng)不同,因此各人完成各項(xiàng)不同任務(wù)的效益(所費(fèi)時(shí)間或所花費(fèi)用)也有差別,如果分配每個(gè)人完成一項(xiàng)任務(wù)且僅為一項(xiàng)任務(wù),則把每項(xiàng)任務(wù)分配給哪個(gè)人去完成,使完成所有n項(xiàng)任務(wù)的總效益為最高(總時(shí)間、總費(fèi)用為最小或創(chuàng)造的價(jià)值最大)?這是典型的分配問(wèn)題或指派問(wèn)題。又如

5、有n項(xiàng)加工任務(wù),怎樣指定n臺(tái)機(jī)器分別去完成,以使總的加工時(shí)間最少或總收入最大;有n條航線,怎樣指定n艘船分別航行,使總收入最大,等等,都屬于指派問(wèn)題。3.指派問(wèn)題的描述3.1指派問(wèn)題的一般形式指派問(wèn)題的標(biāo)準(zhǔn)形式(以人和事為例)如下。有n個(gè)人和n項(xiàng)任務(wù),已知第i個(gè)人做第j件事的費(fèi)用為,要求確定人和事之間的一一對(duì)應(yīng)的指派方案,使完成這n項(xiàng)任務(wù)的費(fèi)用最少。一般把目標(biāo)函數(shù)的系數(shù)寫(xiě)為矩陣形式,稱(chēng)矩陣為系數(shù)矩陣(CoefficientMatrix15),也稱(chēng)為效益矩陣或價(jià)值矩陣。矩陣的元素(i,j=1,2,…n)表示分配第i個(gè)人去完成第j項(xiàng)任

6、務(wù)時(shí)的效益。一般地,以表示給定的資源分配用于給定活動(dòng)時(shí)的有關(guān)效益(時(shí)間,費(fèi)用,價(jià)值等),且3.2問(wèn)題的數(shù)學(xué)模型一般形式在模型中,約束條件式(2)表示每個(gè)人只能做一件事,約束條件式(3)表示每件事只能由一個(gè)人去做。對(duì)于問(wèn)題的每個(gè)可行解,可用解矩陣來(lái)表示:當(dāng)然,作為可行解,矩陣的每列元素中都有且只有一個(gè)1,以滿足約束條件式(3)。每行元素中也有且只有一個(gè)1,以滿足約束條件(2)。指派問(wèn)題n!個(gè)可行解。3.3目標(biāo)函數(shù)極大化的指派問(wèn)題求解時(shí),我們將構(gòu)造一個(gè)新的矩陣,使,其中是一個(gè)足夠大的常數(shù)。一般取中最大的元素作為,求解,所得的解就是原問(wèn)

7、題的解。事實(shí)上,由15可的此結(jié)論。4.指派問(wèn)題實(shí)現(xiàn)4.1匈牙利算法4.1.1匈牙利算法的理論基礎(chǔ)定理1如果從分配問(wèn)題的效率矩陣[]的每一行元素中分別減去(或加上)一個(gè)常數(shù),從每一列中分別減去(或加上)一個(gè)常數(shù),得到一個(gè)新的效率矩陣[],則以[]為效率矩陣的分配問(wèn)題與以[]為效率矩陣的分配問(wèn)題具有相同的最優(yōu)解。定理2若矩陣A的元素可以分為‘0’與‘非0’的兩部分,則覆蓋‘0’元素最少直線數(shù)等于位于不同行不同列的‘0’元素的最大個(gè)數(shù)。4.1.2匈牙利算法的實(shí)現(xiàn)步驟第一步:找出矩陣每行的最小元素,分別從每行中減去這個(gè)最小元素;第二步:再

8、找去矩陣每列的最小元素,分別從各列減去這個(gè)最小元素;第三步:經(jīng)過(guò)這兩步變換后,矩陣的每行每列至少都有了一個(gè)零元素,接著根據(jù)以下準(zhǔn)則進(jìn)行試指派,找出覆蓋上面矩陣中所有零元素至少需要多少條直線;(1)從第一行開(kāi)始,若該行只有一個(gè)零元素打上()號(hào)。對(duì)打(

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫(huà)的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。
关闭