您好,欢迎访问三七文档
上页下页返回指派问题在现实生活中,有各种各样的指派问题(assignmentproblem)。例如,有若干项任务需要分配给若干人来完成,有若干项合同需要选择若干个投标者来承包。这类问题的基本要求是在满足特定的指派要求下,使指派方案的总体效果最佳。上页下页返回例1(指派问题)欲指派n个人去做n件事。已知第i人做第j件事的费用为cij(i,j=1,2,..,n),要求拟定一个指派方案,使每个人做一件事、且使总费用最小。解:设件事人不做第,第件事人做第,第jijixij01上页下页返回第i人做一件事表示为:njijnix1,...,2,1,1第j件事由一人去做:niijnjx1,...,2,1,1目标函数为:ninjijijxcz11min上页下页返回则模型为:ninjijijxcz11minniijnjijnjxnixts11,...,2,1,1,...,2,1,1..0-1规划问题njixij,...,2,1,10,或上页下页返回从数学模型来看,指派问题是一种特殊的0-1规划问题。可采用整数规划的方法求解,但由于其独特的结构,采用前面的方法求解时,要么计算复杂,要么需要的计算时间较长。本节介绍的匈牙利法依据指派问题的特点较好地解决了这个问题。算法1(匈牙利法)上页下页返回库恩(W.W.Kuhn)于1955年提出了求解指派问题的一个解法,他利用了匈牙利数学家尼格(konig)提出的一个关于0元素的定理。故这个解法称为指派问题的匈牙利解法上页下页返回0-1规划问题的标准形式为:niiiTxcxcz1minnixbAxtsi,...,2,1,10..或其中:TnTnTnnmijxxxxbbbbccccaA),...,,(),...,,(),...,,()(212121上页下页返回而指派问题的标准形式为:ninjijijxcz11min这是一种特殊的0-1规划问题niijnjijnjxnixts11,...,2,1,1,...,2,1,1..njixij,...,2,1,10,或上页下页返回在指派问题中,记:njicccijnnij,...,1,,0,)(称距阵c为系数距阵,它可以是费用距阵,也可以是成本距阵、时间距阵等。问题的每一个可行解可以用距阵表示为:nnijxX)(其中X的每一行元素之和都是1,每一列元素之和也都是1,且xij=0或1,i,j=1,2,…,n上页下页返回基本原理:定理1:设指派问题的系数距阵为C=(cij)nn,若将C的第i行各元素减去ui,将C的第j列减vj,i,j=1,2,…,n,则所得的新的系数距阵nnijcc)(''对应的指派问题的最优解与C=(cij)nn对应的指派问题的最优解一致。证明:因为ninjjinjinjinjiijijijjijinjiijijnjiijijjiijijvuxcxvxuxcxcnjivucc111,1,1,1,1,'',...,1,,所以,上页下页返回ninjjinjinjinjiijijijjijinjiijijnjiijijjiijijvuxcxvxuxcxcnjivucc111,1,1,1,1,'',...,1,,所以,由上可知,结论成立。上页下页返回利用定理1变换系数距阵,使其含有许多零,并保证变换后的距阵元素不为零。若能找到n个位于不同行和不同列的零元素,则在问题的解向量中令这n个零元素对应的分量为1,其余为0,便得到了指派问题的一个最优解。否则,将系数距阵中的0元素作适当调整,不断地进行下去,直到找到n个位于不同行和不同列的0元素为止。204021240C010100001X例如若上页下页返回定理2(D.konig,匈牙利)若一方阵中的一部分元素为零,另一部分元素非零,则覆盖方阵内所有零元素的最少直线数等于该方阵中位于不同行和不同列的零元素的最多个数。库恩(W.W.Kuhn)利用了匈牙利数学家尼格(konig)提出的关于0元素的上述定理。于1955年提出了求解指派问题的下述解法:第1步:把各行元素分别减去本行元素的最小值;然后在此基础上再把每列元素减去本列中的最小值。48715127917141069128767146106912106C例2系数矩阵4871512030118791714100177369128702321671461000504691210602340CC此时每行及每列中肯定都有0元素了。第2步:用最少的直线覆盖C‘所有零元素,得到030118017730232100504023404871512030118791714100177369128702321671461000504691210602340CCm=45=n怎么办?才能得到更多的0元素?上页下页返回主要步骤为:匈牙利法的主要步骤1。找出(Cij)每行(列)的最小元素,将每行(列)的所有元素减去该行(列)的最小元素,得(Cij')然后转下一步;2。找出(Cij')每行(列)的最小元素,如它们都为零,则转下一步。否则,将每行(列)的所有元素减去该行(列)的最小元素,直至每行每列都含有零元素,这个系数距阵称为简约化的价值系数距阵。上页下页返回3。以最少的m条直线(水平的或竖直的)去覆盖(或称划去)简约化价值系数距阵中的所有零元素。4。若m=n,则可从简约化系数距阵中找到不同行不同列的n个零元素,从而得最优解。若mn,那么,简约化的系数距阵中的元素分为三类:(1)没有被直线覆盖到的元素;(2)被直线覆盖过一次的元素;(3)被直线覆盖过二次的元素;上页下页返回5。继续变换系数距阵。方法是在未被直线覆盖到的所有元素中,找到一个最小的元素。对未被直线覆盖的元素都减去这一最小元素;而同时被直线二次覆盖的元素都加上这一最小元素即可,再转步骤2对于例题2:用最少的直线覆盖C‘所有零元素,得到030118017730232100504023404871512030118791714100177369128702321671461000504691210602340CCm=45=n怎么办?才能得到更多的0元素?第2步:在未被直线覆盖的所有元素中找出一个最小元素(Xmin)0432140501012102660081103103011801773023210050402340未被直线覆盖的所有元素都减去这个数1。被直线二次覆盖元素加上1得到:Xmin=104321405010121026600811031''C最优解为X13=x22=x31=x44=x55=1上页下页返回例如,若一个指派问题的系数距阵为:9118713161491514410413152c由定理1得:上页下页返回0*0102350*76*060*713024104750910062111302410475011100621113079429118713161491514410413152minc上页下页返回由上可知,相应的最优解为143312214xxxx0*0102350*76*060*71302410475091006211130上页下页返回一般指派问题1。最大化指派问题设最大化指派问题的系数距阵为C=(cij)nn,其中最大元素为m。令B=(bij)nn=(m-cij)nn,则B以为系数距阵的最小化指派问题和以C为系数距阵的原最大化指派问题的解相同上页下页返回若人少事多,则添上一些虚拟的“人”,这些虚拟的“人”做各种事的费用为零,理解为这些费用实际上不会发生。若人多事少,则添上一些虚拟的“事”,这些虚拟的“事”被各人做的费用同样为零。2.人数和事数不相等的指派问题上页下页返回3.一人可做几件事的指派问题若某人可做几件事,则可将此人化作相同的几个人“来”接受指派,这几个“人”做同一件事的费用相同。上页下页返回4。某事不能由某人做的指派问题若某事不能由某人来做,则可将相应的费用系数取为足够大的数M上页下页返回例3某商业公司计划开办五家新商店。为了尽早建成营业,商业公司决定由三家公司分别承建。已知建筑公司Ai(I=1,2,3)对新商店Bj(j=1,2,3,4,5)的建筑费用的报价(万元)为Cij(i=1,2,3,j=1,2,3,4,5),见下表。根据实际情况允许每家建筑公司承建一家或二家商店问应当对这五家建筑公司怎样分配建造任务,才能使总的建造费用最少?上页下页返回BjCijAi商店B1商店B2商店B3商店B4商店B5公司A14871512公司A279171410公司A3691287上页下页返回解:B1B2B3B4B5321781296101417971215784AAA投标费用系数距阵为:Cij商店B1商店B2商店B3商店B4商店B5公司A14871512公司A279171410公司A3691287上页下页返回由于每家建筑公司最多可承建两家新商店,因此,把每家建筑公司化做相同的两家建筑公司(Ai和Ai′,I=1,2,3),这样系数距阵变为:'33'22'11781296781296101417971014179712157841215784AAAAAAB1B2B3B4B5B1B2B3B4B5321781296101417971215784AAA上页下页返回上面的系数距阵有6行和5列,为使“人”和“事”的数目相等,引入一虚事件B6,使之变成标准指派问题的系数距阵:'33'22'11078129607812960101417970101417970121578401215784AAAAAAB1B2B3B4B5B6'33'22'11781296781296101417971014179712157841215784AAAAAAB1B2B3B4B5上页下页返回利用匈牙利法解以为系数距阵的最小化指派问题,得最优方案为:A1承建B1和B3A2承建B2A3承建B4和B5这样总的建造费用为:4+7+9+8+7=35'33'22'11078129607812960101417970101417970121578401215784AAAAAAB1B2B3B4B5B6上页下页返回作业2某运输车队有五辆汽车,待驶往五个目的地送货。一地的货物只需一辆汽车运送,其运费(元)如下表所示:汽车目的地12345A100120140110130B140200230150210C803001009070D120160200130250E70140190150220上页下页返回汽车目的地12345A100120140110130B140200230150210C803001009070D120160200130250E70140190150220(1)试求最优调运方案;(2)若表中数字为所得利润,则应如何调运?(3)若目的地只有A、B、C,则(
本文标题:指派问题
链接地址:https://www.777doc.com/doc-3151222 .html