毕业论文(设计)-指派问题及其应用

ijij1引言指派问题是现实生活中经常遇到的一类组合优化问题，应用十分广泛．在生活中经常遇到这样的问题某单位需完成n项任务恰好有n人可承担这些任务由于每人的专长不同，各人完成任务不同(或所费时间，效率也不同．于是产生应指派哪个人去完成哪项任务，使完n项任务的总效率最高(或所需总时间最小．这些问题的解决都涉及到指派问题．它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳．通常的指派问题多是求项目的总工时最少，而很多情况下人们并不关心项目总工时多少，而只关心项目能否在最短时间完成，即历时最少的指派问题1955年美国运筹学家Kuhn依据匈牙利数学家Konig的0元素覆盖定理首次建立n事指派问题求解的匈牙利法．1992年，建立了关nn事指派问题求解的指派矩阵同解变换与同解改造理论及削高排除法．年，北京大学张立昂教授依据指派矩阵同解变换理论设计出nn事指派问题的周良泽算法．在本文中给出了一类人员招聘问题，建筑中以及图书馆资源配置的数学模型，利用运筹学中线性规划中的指派问题进行决策，建立量化的分配模型，应用匈牙利算法解决了实际生活中遇到的这些问题．2指派问的相关知线性规划是运筹学的一大分支，是目前管理中经常使用而又卓有成效的优化技术．线性规划在运用过程中主要可以解决两类问题，一类问题是在任务确定后，如何统筹安排，做到用尽量少的人力和物力资源来完成任务；另一类问题是在一定量的人力、物力资源条件下，如何安排、使用它们，使完成的任务最多，在这样的条件下常常解决的是指派问题．2.1数模的绍为了建立标准指派问题的数学模型，引个0-1变量：不指派第i人做i件事；Xi,j=1，2指派i人做j件事。这样，问题的数学模型可写成minz

nij

cxijij--ijij指派问题及其应用j,;ijst.i,njj1,2,,n

ij其中第一个式子表示每件事必有且只有一个人去做第二个式子表示每个人必做且只做一件事．2.2匈利指派问题是一类特殊的运输问题是0-1整数规划问题因此可以有多种解法求解．但是由于指派问题的数学结构的特殊性，可用比求解运输问题或者型整数规划更简便有效的方法来求解指派问题，这就是所谓的匈牙利法．该算法于1955年由库恩提出因其关键定理由匈牙利数学家康尼格予以证明故称为匈牙利法．定理1设

ij

是效率矩阵,若可行解*

1(在解矩阵的不同行不同列上对应n都为0,则x*是最优解．(显然ij

z(x*

=0)．则x是最优解此需对效率矩阵作变换使变换后效率矩阵bn个ijij不同行不同列个0．由此求得最优解矩阵n个是对应于效率矩阵的个0．指派问题的最优解有这样性质若从效率矩阵(c)的一行(列)各元素中分别减去该行ij(列)的最小元素得到新矩阵b)那么以(b)为效率矩阵求得的最优解和用原效ijij率矩阵求得的最优解相同．定理

设给定了以c)为效率矩阵指派问G元c改变为ijijb为常数．则以B=()为效率矩阵指派问G有相同ijijijijij的最优解．证明首先效率矩阵的这种变化只是目标值在变换并不影响约束方程组其次用和

分别记问G'

的目标函数值,则'xcxijijijijijijiijij

ji

ij

j

ijijijjiijij即和'只相差一个常数,故它们有相同的最优解利用这个性质可使原效率-2-iij矩阵变换为含有很多0元素的新效率矩阵最优解保持不变效率矩阵)中，ij我们关心位于不同行不同列的0元素，以下简称为独立的元素．若能在效率矩阵()中找n个独立的0元素；则令解矩阵(x)中对应n个ijij独立的0元素的元素取值为1，其他元素取值为．将其代入目标函数中得'bx，它一定是最小．ijij这就是以(b)为效率矩阵的指派问题的最优解．也就得到了原问题的最优解．ij2.3匈利的法骤第一步：使指派问题的效率矩阵经变换，在各行各列中都出现元素．从效率矩阵的每行元素减去该行的最小元素；再从所得效率矩阵的每列元素中减去该列的最小元素．若某行列)已有0元素，那就不必再减了．第二步:做能覆盖所有零元素的最少数目的直线集合．此时，若直线数等n

,则可得出最优解，否则，转到第三步．第三步:变换效率矩阵，使未被直线覆盖的元素中出现零元素．回到第二步．在未被直线覆盖的元素中总有一个最小元素．对未被直线覆盖的元素所在的行（或行）中各元素都减去这一最小元素样未被直线覆盖的元素中势必会出现零元素，但同时却又使已被直线覆盖的元素中出现负元素．为了消除负元素，只要对它们所在的列（或行）中各元素都加上这一最小元素（可以看作减去这一最小元素的相反数）即可．第四步：进行指派，寻求最优解．需找n

个独立的0元素．若能找出，就以这些独立0元素对应解矩阵()中的元素为1，其余为，这就得到最优解．ij

较小时，可用观察法去找常用的步骤为：

个独立0元素．

较大时，就必须按一定的步骤去找，从只有一个0元素的行(列)开始，给这个元素加圈，记作◎．这表示对这行所代表的人只有一种任务可指派．然后划去◎所在列的其他0元素，记作．这表示这列所代表的任务已指派完，不必再考虑别人了．如此反复进行，直到所有元素都被圈出和划掉为止．若遇到同行列)的0素至少有两个(表可以从两项任务中指派其一)以任选一行(列)中某一个元素，再划去同行(列)的其他0素．3应用举随着科学技术的不断进步，指派问题已经越来越多地出现在我们生活中．为解决一个实际问题立数学模型是一种有效的重要方法于建立起来的数学模型，--ijij指派问题及其应用还需要用一定的技术手段（如匈牙利法等）求解数学问题，以达到解决实际问题的目的．这在现在的生活中是常用．3.1平指问的用在实际生活和生产安排中，经常遇到要指派不同的工作人员去完成数目相同的工作由于每个人的专长不同不同的人去完成各项任务的效率或所花时间或成本等一般地也不同．这样，就产生了指派何人去完成何任务，使总效率最高或所花时间最少或成本最低等)的问题这就是在运筹学中的所谓的平衡指派问题面就运用以上介绍的知识到实际问题中．3.1.1建筑中的应用例

某商业公司设计开办五家新闻商店,B,B,B．为了尽早建成营业，3商业公司通知了A,A,A五个建筑公司，以便让每家新商店由一个建筑公司3承建．建筑公司对新商店的建造费用的投标均见表．商业公司应当对五家建筑公司怎样分配建造任务，才能使总建造费用最少？解这是一个标准的指派问题．若设0-1变量当承建B时xij，不承时ij

i,j=1,2,3,4,5)则问题的数学模型为minzxxxx1255st.

j1,2,3,4,5iji1,2,3,4,5ijij其效率矩阵为

47

8917

15121410

6

97

8610

6

9

10

对各行元素分别减去本行的最小元素，对各列也如此，得-4-8362283622111

47

89

15121410

00

43111182773

6

97

610

00

10

00

2310504

6

9

10

0

364

0

230

n

容易看出，可用四条直线覆盖所有零元素，这是最少数直线集合，由于C的阶=5，故需对效率矩继续变换．

00

30173

00

2310504

0

230

为了使未被直线覆盖的元素中出现零元素，将第二行和第三行中各元素减去未被直线覆盖元素中的最小元素1．但这样一来，第一列中出现了负元素，因而再对第一列各元素分别加上1，即

00

301181773

0-1

3011066

10

30118062

00

004

-10

050

01

110004

0

20

0

24

1

20

此时不能用少于五条直线来覆盖所有零元素已可看得最优指派方案了得到最优指派方案，对效率矩阵进行圈零：

82

1

00

先找出零元素最少行列,然后对其它行列的零元素进行筛选,保证各行列只有一个零元素．所以，本题最优解为

00

010100

X

1

000000

0

001

B

也就是说，最优指派方案为：A承B,A承B,A承B,A承建32,A承B,这样总的建设费用最少,为7+9+6+6+6=34元．--4545指派问题及其应用3.1.2图书馆资源优化配置中的应用长期以来图书馆决策以多年来积累的管理经验为基础进行微调或不调，这种决策方式缺乏科学性，难以实现资源的最优配置．因此，以建立科学合理的定量管理办法为基础，辅之以多年经验进行决策既能满足图书馆资源优化的需求，又能为领导决策节省大量时间．目前，高校图书馆经费紧张已是不争的事实，如何合理、有效地利用有限资源已成为高校图书馆当前工作的重要任务．利用运筹学中线性规划中的指派问题进行决策，建立量化的模型．例

图书加工流程一般分为：分类、编目、统计、入库．而不同的工作人员，由于性格、专业背景等的不同对各项工序的执行效率不同．如何合理指派任务使整体工作能快速、高效地完成?解若能对不同工作人员对于不同工序的完成情况进行合理评价，给出合理的效率数，从而得出效率矩阵，进而可以运用匈牙利法进行工作指派．建立效率系数表，如下图所示．表1工序甲

乙

丙

丁人员分类编目统计入库

30323528

25354043

40303432

32362738minfxijijij5xj1,2,ijjstiiji1ijij其中x表示i名人员分配到第j个岗位x表示i名人员分配到第jijij个岗位．运用运筹学中指派问题的知识可以建立如下数学模型：maxX43ijij-6-12010所以i,j=1,2,3,4）可建立如下效率矩阵：ijijB

311869165061305

80

记因为中未被直线覆盖元素的最小值是1因此中的第34行减去1将第2列加上1，可得：08此时m=n=4，因此决策变量矩阵为：

记B

10100

即指派丙来完成分类，丁来完成编目，甲来完成统计，乙来完成入库才能使工作效率最大，才使图书加工速度最快，其总效率为f=40+36+35+43=154．3.2一指问的用在现实中还会遇到人数与任务数不等的问题，也就是说有可能任务数多于人数或人数多于任务数．遇到这种情况需要处理一下，否则就不满足指派问题的求解模型．具体方法如下：状况人数少于任务数任务数多于人数一人可n件事某事不能由某人做

方法添加若干虚拟人添加若干虚拟事加边补小法加边补零(M)法--进行求解得到进行求解得到：3指派问题及其应用3.2.1人数多于事数或事数多于人数人数多于任务数的不平衡指派问题，可以采用添加虚拟任务的方法，使之转化为平衡指派问题，即添加“虚拟”的事，各人做这些事的费用为零．最优指派方案中，完成虚设的任务的那个人就不指派给任务，虚拟任务不会增加目标函数的值，所以，在上面转化为平衡指派问题时每个人完成虚拟任务的效率设为即可．添加虚拟任务后的新的平衡指派问题的匈牙利求解如下样人数少于事数的情况，只需添加“虚拟”的人，这些人做各种事的费用为零．例

一家企业岗位聘任，有甲乙丙丁四个人要竞聘三个岗位，如何安排，才会使得工作的效率最大?最后四位竞聘者对三个岗位的综合效率数为表所示．表2职位岗位一岗位二岗位三

甲758083

乙817472

丙867785

丁678583解当前的情况是竞争者多，岗位少，所以需要添加一个虚拟岗位四，得到其效益矩阵为：

86778586

maxX86所以BXi,j=1,2,3,4)．可建立如下效率矩阵：ijijijijB

0129

19038686

于是得到结果为：竞聘者甲竞聘到岗位三，竞聘者丙竞聘到岗位一，竞聘者乙竞聘到岗位二．例

现在有4个人，5件工作，每人做每件工作所耗时间见下表所示．-8-9C'=000009C'=00000*表3工人工作A

B10

B11

B

B2

B8AA

75

116

109

1412

1214A

13

15

11

10

7问指派哪个人去完成哪项工作，可使总消耗时间最少(每人只能做一件事）解添加虚拟人（戊造效率矩阵：4281014

80

07

65

80

94

07

65

C56912141511107

06

44

73

0

06

18

44

73

90

0

0

0

0

0

0

0

0

0

从未划去的元素中找最小者min｛4，3，7，5，，4，7，9｝=1．未划去的行减去此最小者1，划去的列加上次最小者1，C

"C

0

9308

2

0663

6480

C

"

0

1

0

0

0

0

从而得到最优指派矩阵:X

0010

0000

1000

0001

0

0

1

0

0

指定甲做工作4，乙做工作1，丙做工作2，丁做工作，从而最小耗时为z2+7+6+7=22．--66127指派问题及其应用3.2.2一人可做n件事考虑一人可n件事的指派问题作为多目标决策问题，首先要求指派给各人的任务数目相差不能超过1；其次要求所需总费用最少．这就用到加边补小法，即一人化成P人法，当该人完成一项任务后，剩下的任务实际是交给完成此项任务用时间最少得人去完成，如以下例子．例

某商业公司计划开办五家新商店．为了尽早建成营业，商业公司决定由家建筑公司分别承建，每家最多可以承2家商店．已知建筑公Ai=1，23）i对新商B（j=1，，，，）的建造费用的报价（万元）cij=1，，，jij4，5下表所示，商业公司应当对3家建筑公司怎样分派建筑任务，才能使总的建筑费用最少？表4建筑商店A

B4

B8

B7

B15

B12A

7

9

17

14

10A

6

9

12

87解系数矩阵为

8159171410由于每家建筑公司最多可承建两家新商店，因此，把每家建筑公司化作相同的两家建筑公司AAi，2，3这样，系数矩阵变为：ii

8787917

151215121410

766

917912912

141088

上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚-10拟事，使之称为标准的指派问题，其系数矩阵为：

88917

151201512014100

766

917912912

这是一6方阵，用匈牙利解法可得最优指派：X

000001

01

亦即公司A承建商店B,B，公A承建商B，公A承建商B，，32345可使总的建造费用最省，最小建造费用为z4（元3.2.3某事不能由某人做单位一般有若干个部门需要招聘，每个部门需要的职员有限，这些部门按工作性质对职员也有些要求，这就对具有不同技能的人员有所限制，具体的办法都有很大的区别，所以需要考虑一个适合不同分配方法的人才评价模型．评价模型建立的基础是对职员特长等级评分的量化工作．方法是在指派方案中，某事的任务由虚拟的人完成，然后用匈牙利算法得到的指派最优．例

某单位分配甲、乙、丙、丁四个人去完ABC、项任务，每人完成各项任务的时间（单位：小时）见表所示．由于任务重，人数少，考虑：（1）只需完成4项任务．任必须完成，其他4任务可选3项完成，但是甲不能做项工作．（2）5件任务必须都完成，其中有一人完成两项，其他人每人完成一项．试就（1两种情况分别确定优分配方案，使完成任务的时间最少．表5任

务

人

A

B

C

E

2539

2938

3126

4220

3733--00M0000M0000M00M-500M-指派问题及其应用

3424

2742

2836

4023

3245解

这是人数与工作不等的指派问题用匈牙利解法求解作一定的处理．（1）由于任务数大于人数，所以需要一个虚拟的人，设为戊．因E必须完成故设戊完成的时间为MM为非常大的数戊不能做工其余的假想时间为0，见下表所示表6人任务

AM3934240

B293827420

C312628360

422040230

E37333245用匈牙利解法求解过程如下：

M294237392620

M-29021918013

C342728324223

行变换

71351190-0191860

-292133191860

71

0191317

7101191317

，

第2、4行减去1，第4列加上1C"：-12717114001M-C

"

29141850012016从而得到最优指派:

00

1000

0

0100

0

00

得到表7甲B

乙

丙E

丁A即甲完成任务，乙完成任务，丙完成任务E，丁完成任务．最少的耗时数z（小时）（2）可以考虑将其中某一人看作两人，共有种可能，然后一一求解最佳时间，再分别比较找出最少时间，但是该方法比较繁琐，考虑下述解法：设有虚拟人戊，它集五人优势为一身，即戊完成每件任务的时间是每个人该完成任务的最低者．戊所完成的任务即由完成此项任务时间最低者来完成，见下表所示．表8人任务

A25393424

B29382742

C31262836

42204023

E37333245--701134127701134127004470对"C做最少直线覆盖：C0014C001433320232指派问题及其应用戊2427262032下面用匈牙利解法求解如下：

2539

29314237382033

0417191860

C34

27284032423623

行变换

191322

列变换

24

272032

1718

05719

700130'做最少直线覆盖1912

1217直线数3于5，未被直线覆盖的元素最少者1用未被直线划去的行都减去1，被直线去的列都加上，有

01871807

01871807

""18016180