1、第四节第四节 指指 派派 问问 题题 assignment problem 在生活中经常遇到这样的问题，某在生活中经常遇到这样的问题，某单位需完成单位需完成n n项任务，恰好有项任务，恰好有n n个人可承个人可承担这些任务。由于每人的专长不同，各担这些任务。由于每人的专长不同，各人完成任务不同人完成任务不同(或所费时间或所费时间)，效率也，效率也不同。于是产生应指派哪个人去完成哪不同。于是产生应指派哪个人去完成哪项任务，使完成项任务，使完成n n项任务的总效率最高项任务的总效率最高(或所需总时间最小或所需总时间最小)。这类问题称为指。这类问题称为指派问题或分派问题。派问题或分派问题。例例1 1
2、 有一份中文说明书，需译成英、日、德、有一份中文说明书，需译成英、日、德、俄四种文字。分别记作俄四种文字。分别记作E E、J J、G G、R R。现有甲、乙、。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表的说明书所需时间如表1 1所示。问应指派何人去所示。问应指派何人去完成何工作，使所需总时间最少完成何工作，使所需总时间最少?表1任务人员 E J G R 甲 乙 丙 丁 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 耗时 类似有：有类似有：有n n项加工任务，怎样指派到项加工任务，怎样指
3、派到n n台机床上分别完成的问题；有台机床上分别完成的问题；有n n条航线，怎样条航线，怎样指定指定n n艘船去航行问题艘船去航行问题。对应每个指派问。对应每个指派问题，需有类似表题，需有类似表1 1那样的数表，称为效率矩阵那样的数表，称为效率矩阵或，其元素或，其元素c cijij0(i,j=1,20(i,j=1,2，n n)表示指派表示指派第第i i人去完成第人去完成第j j项任务时的效率项任务时的效率(或时间、成或时间、成本等本等)。解题时需引入变量。解题时需引入变量x xijij；其取值只能；其取值只能是是1 1或或0 0。并令。并令 项任务人去完成第当不指派第项任务人去完成第当指派第j
4、ijixij,0,1当问题要求极小化时数学模型是：当问题要求极小化时数学模型是：1111min1,1,2,1,1,2,10nnijijijnijinijjijzc xxjnxinx目目标标函函数数约约束束条条件件或或()表 示 每 人 仅 做 一 件 事 情（表示一项工作只能由一个人完成）（xij）是nn矩阵,对应于效率矩阵(cij).111111jniijinnnjnnxxxxxxxxx11,1,2,nijixjn表明各行之和为1。11,1,2,nijjxin表明各列之和为1。满足约束条件的可行解xij构成的可行解矩阵，矩阵中有n个为1,其余都为0,而且这这n个个1必位于矩阵的不必位于矩阵的
5、不同行不同列上。同行不同列上。对应于可行解xij的目标值是这n个cij之和.可行解矩阵可行解矩阵工作工作人人显然，解矩阵(xij)中各行各列的元素之和都是1，但这不是最优。如例1的一个可行解矩阵01000010()10000001ijx E J G R 指派问题是0-1规划的特例，当然可用整数线性规划、0-1规划的解法去求解，但可以利用指派问题的特点设计更简便的解法，下面介绍匈牙利法。定理定理1 设()ijn nBb是效率矩阵,若可行解x*的n个1(在解矩阵的不同行不同列上)对应的n个bij都为0,则x*是最优解.(显然z(x*)=0)因此需对效率矩阵作变换,使变换后效率矩阵()ijn nb含
6、有含有n个不同行不同列个个不同行不同列个0.由此求得最优解矩阵的n个1是对应于效率矩阵的这n个0.如效率矩阵为0*14939200*23230*38012140*令,10000010()01000001ijx则xij是最优解11minnnijijijzb x定理定理2 2 设给定了以C=(cij)为效率矩阵指派问题G，现将C的元素cij 改变为则以B=()为效率矩阵指派问题G与G有相同的最优解。指派问题的最优解有这样性质，若从效率矩阵(cij)的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵(bij)，那么以(bij)为效率矩阵求得的最优解和用原效率矩阵求得的最优解相同。即,iji
7、jijijbc与为常数ijb证:首先效率矩阵的这种变化只是目标值在变换，并不影响约束方程组，其次用z和 z分别记问题G与G的目标函数值,则()ijijijijijijijijijiijjijijijjiijijzb xcxc xxxz即z和 z只相差一个常数,故它们有相同的最优解.利用这个性质，可使原效率矩阵变换变换为含有很多0元素的新效率矩阵，而最优解保持不变，在效率矩阵(bij)中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。若能在效率矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素的元素取值为1，其他元素取值为0。将其代入目标函数中得到 ，
8、它一定是最小。这就是以(bij)为效率矩阵的指派问题的最优解。也就得到了原问题的最优解。0ijijijzb x 以下用例1来说明指派问题的解法。第一步：使指派问题的效率矩阵经变换，在各行各列中都出现0元素。(1)从效率矩阵的每行元素减去该行的最小元素；(2)再从所得效率矩阵的每列元素中减去该列的最小元素。若某行(列)已有0元素，那就不必再减了。例1的计算为min215134210414154()9141613978119701311201370*60101160*69()05740*5320142010*042minijijcb行例如列行列都有零元素最优解为最优解为00010100()1000
9、0010ijx定理定理3 若矩阵C可分成”0”与非”0”两部分,则覆盖”0”元素的最少直线最少直线等于位于不同行不同列的”0”元素的最大个数最大个数.如50*202230*000*105729800*406365覆盖”0”元素的最少直线为4条,位于不同行不同列的”0”元素的最大个数也为4.01370606905320100()ijb再如例1直线数位于不同行不同列的”0”元素的最大个数也为4.第二步第二步:做能覆盖所有零元素的最少数目的直线集合。此时，若直线数等于 n ，则已可得出最优解。否则，转第三步。第三步第三步:变换效率矩阵，使未被直线覆盖的元素中出现零元素。回到第二步。在未被直线覆盖的元
10、素中总有一个最小元素。对未被直线覆盖的元素所在的行（或行）中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必会出现零元素，但同时却又使已被直线覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）中各元素都加上这一最小元素（可以看作减去这一最小元素的相反数）即可。50*202230*000*105729800*406365如-2-250*202230*00283509800*424143+270*202430*0008350*11800*40*4143第四步：进行指派，寻求最优解。需找出n个独立的0元素。若能找出，就以这些独立0元素对应解矩阵(xij)中的元素为1，其余为
11、0，这就得到最优解。当n较小时，可用观察法去找出n个独立0元素。若n较大时，就必须按一定的步骤去找，常用的步骤为：(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作。这表示对这行所代表的人只有一种任务可指派。然后划去所在列(行）的其他0元素，记作。这表示这列所代表的任务已指派完，不必再考虑别人了。如此反复进行，直到所有0元素都被圈出和划掉为止。(2)若遇到同行(列)的0元素至少有两个(表示可以从两项任务中指派其一)，可以任选一行(列)中某一个0元素，再划去同行(列)的其他0元素。现用例1的(bij)矩阵，按上述步骤进行运算。先给b22加圈，然后给b31加圈，划掉b11，b41；给b4
12、3加圈，划掉b44，最后给b14加圈，得到 01370606905320100()ijb137669532101370*60*690*532010*0所以得最优解为00010100()10000010ijx这表示：指定甲译出俄文，乙译出日文，丙译出英文，丁译出德文。所需总时间最少31224314028minminijijijijijijzb xzc xcccc E J GR甲乙丙丁（小时）2151341041415()914161378119ijc例例2 某商业公司设计开办五家新闻商店 。为了尽早建成营业，商业公司通知了 五个建筑公司，以便让每家新商店由一个建筑公司承建。建筑公司 对新商店 的
13、建造费用的投标为 均见表。商业公司应当对五家建筑公司 怎样分配建造任务，才能使总建造费用最少？54321,BBBBB54321,AAAAAiAjBijc2A3A4A5A 487151279171410691287671461069121061B2B3B4B5B1AijcjBiA解：这是一个标准的指派问题。若设0-1变量 则问题的数学模型为 )5,4,3,2,1,(,0,1jiBABAxjijiij时不承建当时承建当5,4,3,2,11015,4,3,2,11.61084min515155541211ixxjxtsxxxxzijjijiij或(一个商店只能由一个公司承建)(一个公司只能建造一个商
14、店)现在，我们来解例2的指派问题的效率矩阵为 61012961061477812910141791215786674C对各行元素分别减去本行的最小元素，对各列也如此，得 0432040501232377181103000004630408112633710281134000061012961061477812910141791215786674 容易看出，可用四条直线覆盖所有零元素，这是最少数直线 集合，由于C的阶数 =5，故需对效率矩阵C继续变换。n0301 1801773023210050402340-4-7-6-6-6 -1 -3为了使未被直线覆盖的元素中出现零元素，将第二行和第三行中各
15、元素减去未被直线覆盖元素中的最小元素1。但这样一来，第一列中出现了负元素，因而再对第一列各元素分别加上1，即043214050012126608110310010432040500121266081103011004320405012323771811030000此时，已不能用少于五条直线来覆盖所有零元素，故已可看得最优指派方案。为了得到最优指派方案，对效率矩阵进行圈零：-1+1也就是说，最优指派方案为：让也就是说，最优指派方案为：让A A1 1 承建承建B B3 3,A A2 2 承建承建B B2 2,A A3 3 承建承建 B B1 1,A A4 4 承建承建 B B4 4,A A5 5
16、承建承建 B B5 5,这样，总的建设费用这样，总的建设费用最少，为最少，为7+9+6+6+6=34万元。万元。130*1180*6620*121150*412340*0 01000 10001 00000 001000001X 所以，本题最优解为所以，本题最优解为先找出零元素最少行列先找出零元素最少行列,然然后对其它行列的零元素进后对其它行列的零元素进行筛选行筛选,保证各行列只有一保证各行列只有一个零元素个零元素.61012961061477812910141791215786674C5A12345AAAAAB1 B2 B3 B4 B5练习：求表所示效率矩阵的指派问题的最小解。表解解 按上述
17、第一步，将这效率矩阵进行变换。按上述第一步，将这效率矩阵进行变换。1279797502028966662300071712149701057215146610 6980044107109406365min经一次运算即得每行每列都有经一次运算即得每行每列都有0 0元素的效率矩阵，元素的效率矩阵，再按上述步骤运算，得到再按上述步骤运算，得到502022300028350980042414350202230000105729800406365可用四条直线覆盖所有零元素，可用四条直线覆盖所有零元素，这是最少数直线集合，由于这是最少数直线集合，由于C的阶数的阶数=5，故需对效率矩阵，故需对效率矩阵C继续
18、变换。继续变换。第三行和第五行减第三行和第五行减2,得得3414040081105380000342020770202430000835011800404143第1列+2此时，已不能用少于五条直线来覆盖所有零元素，故已可看得最优指派方案。72243083511844143为了得到最优指派方案，对效率矩阵进行圈零：为了得到最优指派方案，对效率矩阵进行圈零：70*2024300*008350*1180*040*4143 已具有已具有n n个独立个独立0 0元素。这就得到了最优解，相应元素。这就得到了最优解，相应的解矩阵为：的解矩阵为：由解矩阵得最优指派方案：由解矩阵得最优指派方案：甲甲B B，乙，
19、乙D D，丙，丙E E，丁，丁C C，戊，戊A A本例还可以得到另一最优指派方案：本例还可以得到另一最优指派方案：甲甲B B，乙，乙C C，丙，丙E E，丁，丁D D，戊，戊A A所需总时间为所需总时间为min z=7+6+9+6+4=32min z=7+6+9+6+4=320100000010000010010010000ijx1279798966671712149151466104107109()ijc甲乙丙丁戊 A B C D E 当指派问题的效率矩阵，经过变换得到了同行和同列中都有两个或两个以上0元素时。这时可以任选一行(列)中某一个0元素，再划去同行(列)的其他0元素。这时会出现多重
20、解。一般的指派问题一般的指派问题 1、最大化指派问题、最大化指派问题设最大化指派问题效率矩阵 ，其中最大元素 为 。令矩阵 ，则以B为效率矩阵的最小指派问题和以C为效率矩阵的原最大化指派问题有相同最优解。nnijcC)(mnnijnnijcmbB)()(例例4 矩阵 9118713161491514410413152C 的最大元素为 ，取 ，令1633c16m758930271212612311491611168167161316161614169161516141641610164161316516216B则以C为效率矩阵的最大化指派问题和以B为效率矩阵的最小化指派问题有相同最优解。当效率矩
21、阵为利润矩阵、产量矩阵等时，就产生最大化指派问题。2、人数和事数不等的指派问题、人数和事数不等的指派问题 若人少事多，则添上一些虚拟的“人”。这些虚拟的“人”做各事的费用系数可取0（理解为这些费用实际上不会发生），若人多事少，则添上一些虚拟的“事”，这些“事”被各人做的费用系数同样可取0。3、一个人可做几件事的指派问题、一个人可做几件事的指派问题 若某事一定不能由某人做，则可将相应的费用系数取作足够大的数M。若某人可做几件事，则可将该人化作相同的几个“人”来接受指派，这几个“人”做同一件事的费用系数当然都一样。4、某事一定不能由某人做的指派问题、某事一定不能由某人做的指派问题例例5 对于例2
22、的指派问题，为了加快建造速度，经研究决定，舍弃建筑公司 和 ，而让技术力量较强的建筑公司 和 来承建。根据实际情况，可以允许每家建筑公司承建一个或两个商店。求使总费用最少的指派方案。反映投标费用的效率矩阵为4A5A21,AA3A 12345123487151279171410691287BBBBBAAA由于每家建筑公司最多可承建两个新商店，因此，把每家建筑公司化作相同的两家（和 ）。上面的效率矩阵有六行五列，为了使“人”和“事”的数目相同，引入一件虚事，使之成为标准指派问题的效率矩阵，这样效率矩阵为：iA3,2,1,iAi000750000750311063031106302150002150
23、00C(每列减列中最小值)（3、4行减1）332211654321000000771010121288141415151212171777999988667744AAAAAACBBBBBB110000551122001122555902590270007000000000551122125912590570057000002200从最后的矩阵已能确定最优解，有123101 0 0010 0 0000 1 1AAA0*00*7520*9522150*0*覆盖所有零元素的最少数直线数为612345BBBBB+1所以，最优指派方案是应由所以，最优指派方案是应由A1承建承建B1和和B3,A2承建承建
24、B2,A3承建承建B4和和B5。这样，总的建造费用最省，是。这样，总的建造费用最省，是 4+7+9+8+7=35万元。万元。487151279171410691287ijc例例6 从甲、乙、丙、丁、戊五人中挑选四人去完成从甲、乙、丙、丁、戊五人中挑选四人去完成A、B、C、D四项任务。每人完成各项任务所需的时间如表所示。规定四项任务。每人完成各项任务所需的时间如表所示。规定每项任务只能由一个人单独完成，且每人最多承担一项任务。每项任务只能由一个人单独完成，且每人最多承担一项任务。又假定甲必须保证承担一项任务，丁不能承担任务又假定甲必须保证承担一项任务，丁不能承担任务D。在满。在满足上述条件下，如
25、何分配任务，使完成四项任务总的花费时足上述条件下，如何分配任务，使完成四项任务总的花费时间为最小。间为最小。任务任务人人ABCD甲甲1051520乙乙210515丙丙3151413丁丁15276戊戊94158时间时间 解解 由于人多事少，先增加一项虚设的任务由于人多事少，先增加一项虚设的任务E。因为甲必须保。因为甲必须保证承担一项任务，则甲不能完成虚设的任务证承担一项任务，则甲不能完成虚设的任务E，所以甲完成任，所以甲完成任务务E的时间设为的时间设为M，丁不能承担任务，丁不能承担任务D，所以丁完成任务，所以丁完成任务D的的时间同样设为时间同样设为M。从而得表。从而得表 任任务务人人ABCDE甲
26、甲1051520M乙乙2105150丙丙31514130丁丁1527M0戊戊9415804069M090810138501201M062900-2 -2 -5 -8-35079M080701139501302M0721000覆盖的最少直线数为+1覆盖的最少直线数为51051520M2105150315141301527M0941580-1 -140*68M090*1110*138501201M0*6290*0圈零圈零最优解为最优解为0100000100100000000100010用匈牙利法求解得最优分用匈牙利法求解得最优分配方案为：甲做配方案为：甲做B，乙做，乙做C，丙做丙做A，戊做，戊做D，丁不分配，丁不分配任务（即丁做任务（即丁做E），总时），总时间为间为21。甲甲乙乙丙丙丁丁戊戊ABCD E105152021051531514131527694158Cij=92475689143952474、38293872972642758423599698、习题：求解下列最小化指派问题（每人只能做一项工作，每项工作只能由一人来完成）：
