求解廣義指派問(wèn)題的轉(zhuǎn)換方法(1)

《求解廣義指派問(wèn)題的轉(zhuǎn)換方法(1)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第六屆中國(guó)青年運(yùn)籌與管理學(xué)者大會(huì)論文集秦皇島，2004年7月16-20日，第222—230頁(yè)求解廣義指派問(wèn)題的轉(zhuǎn)換方法余英姿張強(qiáng)(北京理工大學(xué)管理與經(jīng)濟(jì)學(xué)院，北京10008)摘要對(duì)一類廣義指派問(wèn)題建立了數(shù)學(xué)模型，這類問(wèn)題研究的是辨?zhèn)€人執(zhí)行H項(xiàng)任務(wù)，每個(gè)人執(zhí)行的任務(wù)數(shù)、執(zhí)行每項(xiàng)任務(wù)的人數(shù)以及總的指派人項(xiàng)數(shù)均有限制，要求最優(yōu)指派。找到一種轉(zhuǎn)換方法，將這類問(wèn)題轉(zhuǎn)換為平衡指派問(wèn)題，從而用傳統(tǒng)方法。如匈牙利法求解。最后用一個(gè)算例來(lái)說(shuō)明這種轉(zhuǎn)換方法的簡(jiǎn)便和有效性。關(guān)鍵詞指派問(wèn)題廣義轉(zhuǎn)換退化匈牙利法中圖分類號(hào)：02

2、21文獻(xiàn)標(biāo)識(shí)碼：AI引言指派問(wèn)題(又稱分配問(wèn)題)在現(xiàn)實(shí)生活中有著廣泛韻應(yīng)用背景，傳統(tǒng)的平衡指派問(wèn)題(AssignmemProblem，簡(jiǎn)記作AP)Ⅲ研究的是人數(shù)與事數(shù)相等，一人一事且一事一人的情形，但現(xiàn)實(shí)生活還存在著許多更為復(fù)雜的指派問(wèn)題，即廣義指派問(wèn)題(GeneralizedAssignmentProblem，簡(jiǎn)記作GAP)。對(duì)于形形色色的廣義指派問(wèn)題，人們提出了各種解法，而將廣義指派問(wèn)題轉(zhuǎn)換為平衡指派問(wèn)題的轉(zhuǎn)換方法，卻一直是人們的研究重點(diǎn)和首先考慮的方法。這是因?yàn)橛捎谄胶庵概蓡?wèn)題結(jié)構(gòu)的特殊性和簡(jiǎn)單

3、性，已經(jīng)存在許多針對(duì)平衡指派問(wèn)題的專門算法，如匈牙利法I”、削高排除法【2】、縮陣分析法”1和差額法14】(盡管存在著特例使該方法無(wú)效，但在大多數(shù)情況下，該方法仍不失為一種簡(jiǎn)便，有效的好算法)等。因此，如果我們能將廣義指派問(wèn)題——這類非平衡指派問(wèn)題較容易地轉(zhuǎn)換為平衡指派問(wèn)題，然后使用上述專門算法來(lái)求解轉(zhuǎn)換后的平衡指派問(wèn)題，這顯然是一種非常實(shí)用的做法。文獻(xiàn)[5]提出了一類廣義指派問(wèn)題，要求是：允許某些人做多件工作或允許某些工作由多人完成，且當(dāng)人數(shù)Ⅲ不等于工作數(shù)n時(shí)，要求不剩工作和不剩人。文獻(xiàn)[5]以m<

4、n的情形為例，分別討論了以下三種情形下的轉(zhuǎn)換方法：1)n—Ⅲ=1，允許某人做兩件工作：2)求解廣義指派問(wèn)題的轉(zhuǎn)換方法m<"，允許某人做n—"十1件工作；3)m

5、完成一項(xiàng)虛任務(wù)。在文獻(xiàn)[7]中，提出了～類C-A指派問(wèn)題。它要求從Ⅲ個(gè)人中派出}(o

6、次不超過(guò)d，闖如何指派可使該隊(duì)期望的總分最高。這一問(wèn)題的數(shù)學(xué)規(guī)劃模型可表示如下其中maxc=∑∑q·％l—IJ=lH虬t0≤q≤∑％≤《f=1∥2．．，m』寸mO

7、％s彰，21∥2一，月(2)i=1∑∑b≥dJ=l，；lh=0或1Vi，J(3)f～=l，指派人員f去執(zhí)行任務(wù)，；h=o，否則。cg：人員i執(zhí)行任務(wù)，的效率(如時(shí)間，投資等)：c：總效率；“人員i最少執(zhí)行的任務(wù)數(shù)：口!：人員i最多執(zhí)行的任務(wù)數(shù)；豌：執(zhí)行任務(wù)，最少的人數(shù)；b：：執(zhí)行任務(wù)，最多的人數(shù)；d：總的被指派的人項(xiàng)數(shù)。顯然，文獻(xiàn)[5]、[6]和[7]所提出的問(wèn)題都可以看作是這類廣義指派問(wèn)題的特例求解廣義指派問(wèn)題的轉(zhuǎn)換方法因此，找出求解這類問(wèn)題的有效方法，既有實(shí)際價(jià)值又有理論意義。我們將上述廣義指派問(wèn)

8、題記為GAP*。對(duì)于GAP*，文獻(xiàn)[8]將其轉(zhuǎn)化為一個(gè)能閣對(duì)偶運(yùn)輸法求解的容量運(yùn)輸問(wèn)題。但是，用求解運(yùn)輸問(wèn)題的方法來(lái)求解指派問(wèn)題通常是不合算的。本文受文獻(xiàn)[5]、[6]和[7]的啟發(fā)，通過(guò)對(duì)GAP*模型結(jié)構(gòu)的分析和研究，找到了一種轉(zhuǎn)換方法，不但能將GAP*轉(zhuǎn)換為AP，而且統(tǒng)一了文獻(xiàn)[5]、[6]和[7]的特殊轉(zhuǎn)換方法。為求解這一類廣義指派問(wèn)題的轉(zhuǎn)換方法的推廣帶來(lái)便利。從算例可以看出，這種轉(zhuǎn)換方法非常簡(jiǎn)便而有效。2問(wèn)題的轉(zhuǎn)換2．1目標(biāo)最小化GAP*的轉(zhuǎn)換將