分配問題與匈牙利算法

分配問題與匈牙利法2/6/20241在實(shí)際中經(jīng)常會(huì)遇到這樣的問題，有n項(xiàng)不同的任務(wù)，需要n個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專長不同，因此各人去完成不同的任務(wù)的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。于是產(chǎn)生了一個(gè)問題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少），這類問題稱為分配問題或指派問題。1.分配問題2/6/20242例1任務(wù)人員ABCD甲215134乙1041415丙9141613丁781192/6/202432.匈牙利法第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素第二步：進(jìn)行試分配，以尋求最優(yōu)解。如果得到最優(yōu)解，運(yùn)算結(jié)束，否則轉(zhuǎn)到第三步。第三步：作最少的直線覆蓋所有0元素。第四步：變換矩陣(bij)以增加0元素，轉(zhuǎn)到第二步。2/6/20244例1任務(wù)人員ABCD甲215134乙1041415丙9141613丁781192/6/20245-2-4-9-7求解過程如下：第一步，變換系數(shù)矩陣：2/6/20246-4-2-0-02/6/20247◎?◎??◎◎第二步，試分配：2/6/20248任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119此分配問題的最優(yōu)時(shí)間：4+4+9+11=282/6/20249例2有一份中文說明書，需譯成英、日、德、俄四種文字?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分配任務(wù)，使總時(shí)間最少？任務(wù)人員英語日語德語俄語甲67112乙4598丙31104丁59822/6/202410求解過程如下：第一步，變換系數(shù)矩陣：－5第二步，試指派：◎◎◎??找到3個(gè)獨(dú)立零元素但m=3<n=42/6/202411第三步，作最少的直線覆蓋所有0元素：◎◎◎??√√√獨(dú)立零元素的個(gè)數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打√各行都減去1；打√各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派：2/6/202412000000得到4個(gè)獨(dú)立零元素，所以最優(yōu)解矩陣為：◎◎◎??√√√◎◎◎??◎◎◎??◎2/6/202413任務(wù)人員英語日語德語俄語甲67112乙4598丙31104丁5982此分配問題的最優(yōu)時(shí)間：2+4+1+8=152/6/202414例3115764戊69637丁96458丙9117129乙118957甲EDCBA費(fèi)工作用人員2/6/202415-1-22/6/202416◎?◎◎◎??2/6/202417◎?◎◎◎??√√√l=m=4<n=52/6/202418◎?◎◎◎??2/6/202419◎?◎?◎?◎?√√√√√√√2/6/202420◎?◎?◎?◎?√√√√√√√l=m=4<n=52/6/202421◎?◎?◎?◎?√√√√√√√2/6/202422◎??◎??◎?◎?◎此問題有多個(gè)最優(yōu)解總時(shí)間為282