指派问题

运筹学课件ch5指派问题[全文]

指派问题

assignmentproblem运筹学课件

一种特殊的线性规划问题，我们也经常遇到指派人员做某项工作的情况。指派

问题的许多应

用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。

其他的一些应

用如为一项任务指派机器、设备或者是工厂。指派问题

运筹学课件

指派问题的形式表述:

给定了一系列所要完成的任务(tasks)以及一系列完成任务的被指派者

(assignees)，所需

要解决的问题就是要确定出哪一个人被指派进行哪一项任务。

指派问题模型

运筹学课件

指派问题的假设:

被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务

每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一

个相关成本目标是要确定怎样进行指派才能使得总成本最小指派问题模型

运筹学课件

指派问题

assignmentproblem【例51>.14】人事部门欲安排四人到四个不同的岗

位工作，每个岗位一个人(经考核四

人在不同岗位的成绩(百分制)如表5-34所示，如何安排他们的工作使总成绩

最好。

88

80

90

86

丁

90

79

83

82

丙

95

78

87

95

乙

90

73

92

85

甲

D

C

B

A

工作

人员

表5-34

【解】设

1数学模型

运筹学课件

数学模型为:

甲

乙

丙

丁

A

B

C

D

图5.3

指派问题

assignmentproblem

运筹学课件

假设m个人恰好做m项工作，第i个人做第j项工作的效率为cij?0，效率矩

阵为[cij](如

表5-34)，如何分配工作使效率最佳(min或max)的数学模型为指派问题

assignmentproblem

运筹学课件

2解指派问题的匈牙利算法

匈牙利法的条件是:问题求最小值、人数与工作数相等及效率非负【定理

5.1】如果从分配问题效率矩阵[cij]的每一行元素中分别减去(或加上)一个常数

ui

(被称为该行的位势)，从每一列分别减去(或加上)一个常数vj(称为该列的位

势)，得到

一个新的效率矩阵[bij]，其中bij=cij,ui,vj,则[bij]的最优解等价于[cij]

的最优解，这里cij、

bij均非负(

指派问题

assignmentproblem

【证】

运筹学课件

【定理5.2】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素

的最少直线

数等于位于不同行不同列的“0”元素(称为独立元素)的最大个数(如果最少

直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其

余变量等于0，这时目标函数值等于零，得到最优解(

两个目标函数相差一个常数u+v,约束条件不变,因此最优解不变。

指派问题

assignmentproblem运筹学课件

匈牙利法

由单纯形法衍生而来

步骤(对min问题):

建立成本表:必须为m*m方阵

简化行:确定每一行最小值，并将该行的每个数字减去该最小值

简化列:确定每一列最小值，并将该列的每个数字减去该最小值

最佳性检验:使用最少的水平或垂直线覆盖所有0。若线条数等于m，则停止，

并进行最适

当的指派;否则继续

进一步简化成本表:

在所有未被直线覆盖的数字中，确定其最小值所有未被直线覆盖的数字，减

去该最小值所有同时被水平与垂直线画到的数字，加上该最小值返回步骤4

运筹学课件

Whichplantsshouldproducewhichproducts?

哪个工厂应该生产哪种产品,

运筹学课件

某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本

(元/件)如表

5-35所示(求最优生产配置方案(280

200

55

82

工厂4

250

170

70

65

工厂3

230

150

50

75

工厂2

260

180

69

58

工厂1

产品4

产品3

产品2

产品1

表5-35

【解】问题求最小值。

第一步:找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有

指派问题

assignmentproblem

运筹学课件

第二步:找出矩阵每列的最小元素，再分别从每列中减去，有指派问题

assignmentproblem

Min00100180运筹学课件

第三步:用最少的直线覆盖所有“0”，得

第四步:这里直线数等于3(等于4时停止运算)，要进行下一轮计算(

从矩阵未被直线覆盖的数字中找出一个最小数k并且减去k，矩阵中k,5(

直线相交处的元素加上k，被直线覆盖而没有相交的元素不变，得到下列矩阵

指派问题

assignmentproblem

第四步等价于第1、3行减去5，同时第1列加上5得到的结果-5

-5

+5

运筹学课件

第五步:覆盖所有零最少需要4条直线，表明矩阵中存在4个不同行不同列的

零元素(容易

看出4个“0”的位置

()

×

×

()

×

()

()

或

()

×

×

()

×

()

()

指派问题

assignmentproblem

运筹学课件

得到两个最优解

有两个最优方案

第一种方案:第一个工厂加工产品1，第二工厂加工产品3，第三个工厂加工产

品4，第四

个工厂加工产品2;

第二种方案:第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产

品3，第四

个工厂加工产品2;

单件产品总成本

Z,58，150，250，55,513指派问题

assignmentproblem

运筹学课件

5.4.3其它变异问题

【例5.16】求例5.14的最优分配方案

【解】

则

求此问题的最小值(求解过程如下最优分配方案是:甲分配到B岗位;乙分配到

A岗位;丙分配到D岗位;丁分配到C岗位;

总成绩为357

指派问题

assignmentproblem

88

80

90

86

丁

90

79

83

82

丙

95

78

87

95

乙

90

73

92

85

甲

D

C

B

A

工作人员

表5-34运筹学课件丁的蛙泳成绩退步到1’15”2;戊的自由泳成绩进步到

57”5,组成接力队的方案是否应该

调整,

如何选拔队员组成4??100米混合泳接力队?

案例混合泳接力队的选拔

甲

乙

丙

丁

戊

蝶泳

1’06”8

57”2

1’18”

1’10”

1’07”4

仰泳

1’15”6

1’06”

1’07”8

1’14”2

1’11”

蛙泳

1’27”

1’06”4

1’24”6

1’09”6

1’23”8

自由泳

58”6

53”

59”4

57”2

1’02”4

5名候选人的百米成绩

穷举法:组成接力队的方案共有5!=120种。

运筹学课件cij(秒)~队员i第j种泳姿的百米成绩

约束条件

每人最多入选泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.278

70

67.4j=275.666

67.874.271

j=387

66.484.669.683.8j=458.653

59.457.262.4每种泳姿有且只有1人

M

M

M

M

M

j=51

1

1

1

1

运筹学课件

模型求解

最优解:

成绩为253.2(秒)=4’13”2

甲

乙

丙

丁

戊

蝶泳

1’06”8

57”2

1’18”

1’10”

1’07”4

仰泳

1’15”6

1’06”

1’07”8

1’14”2

1’11”

蛙泳

1’27”

1’06”4

1’24”6

1’09”6

1’23”8

自由泳

58”6

53”

59”4

57”2

1’02”4

甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.

运筹学课件

丁蛙泳c43=69.6??75.2，戊自由泳c54=62.4??57.5,方案是否调整,

敏感性分析,

乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳

最优解:x21=x32=x43=x51=1,成绩为4’17”7

c43,c54的新数据重新输入模型，再求解

指派(Assignment)问题:每项任务有且只有一人承担，每人只能承担一项，效

益不同，怎样

分派使总效益最大.讨论

甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.

原方案

运筹学课件

某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、

食品、家俱及

计算机等5个类别(通过评估，家具超市不能放在第3个点，计算机超市不能

放在第4个点，

不同类别的商品投资到各点的年利润(万元)预测值见表5-36(该商业集团如何

作出投资

决策使年利润最大。

指派问题的应用,

270

260

220

计算机

180

,

200

90

家具

300

380

160

150

食品

260

420

350

80

服装

400

360

300

120

电器

4

3

2

1

地点

商品

表5-36

利润表

运筹学课件

【解】这是求最大值、人数与任务数不相等、不可接受的配置的一个综合指

派问题，分别

对表5-36进行转换(

(1)令c43=c54=0

(2)转换成求最小值问题，令M,420，

C`ij=M-cij，得到效率表(机会损失表),即转换后得到表5-37

(3)虚拟一个地点5

0

420

150

160

200

计算机

0

240

420

220

330

家俱

0

120

40

260

270

食品

0

160

0

70

340

服装

0

20

60

120

300

电器

5

4

3

2

1

地点商品

表5-37运筹学课件用匈牙利法求解得到最优解

最优投资方案:地点1投资建设计算机超市，地点2投资建设服装超市，地点3

投资建设食

品超市，地点4投资建设电器超市，年利润总额预测值为1350万元

70

390

180

50

0

0

140

380

40

60

0

20

0

100

0

40

100

0

0

110

80

0

100

20

110

运筹学课件

1(指派模型的特征

2(匈牙利法求解指派问题的条件3(匈牙利法的两个基本定理4(指派问题也是

一个特殊的运输问题.

5(将指派(分配)问题的效率矩阵每行分别加上一个数后最优解不变.

指派问题

assignmentproblem

TheEndofChapter5

作业:P135T7运筹学课件