第11讲：整数规划(二).ppt

第11讲整数规划(二) ——指派问题
浙江工业大学经贸管理学院曹柬
一、指派问题的概念
运筹学第11讲:整数规划(二)
例1****题5-2)
甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间如表所示。问应指派何人加工何种工件,使总的加工时间最少?
工件
工人
A
B
C
D
甲
14
11
13
17
乙
9
7
2
9
丙
4
9
10
15
丁
15
10
5
13
指派问题的标准形式(以人和事为例)是:有n 个人和n 件事,已知第i 人做第j 事的付出为cij (i,j =1,2,…,n ),要求确定人与事之间的一一对应的指派方案,使完成这n 件事的总付出最小。
一般称C=(cij )n×n为指派问题的系数矩阵。在实际问题中,cij 可表示费用、时间、距离等。
为建立标准指派问题的数学模型,引入n2 个0-1变量:
指派问题有个可行解
n!
二、指派问题的标准形式
运筹学第11讲:整数规划(二)
指派问题标准形式的特点
模型为min型
系数矩阵C 为方阵
系数cij≥0
运筹学第11讲:整数规划(二)
三、匈牙利法
运筹学第11讲:整数规划(二)
(以****题5-2为例)
甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间如表所示。问应指派何人加工何种工件,使总的加工时间最少?
工件
工人
A
B
C
D
甲
14
11
13
17
乙
9
7
2
9
丙
4
9
10
15
丁
15
10
5
13
运筹学第11讲:整数规划(二)
某商业公司计划开办5家新商店,为尽快建成营业,公司决定由5家建筑公司分别承建。已知建筑公司Ai 对新商店Bj 的建造费用报价如下表所示。问商业公司应对5家建筑公司如何分配建造任务,使得总建造费用最小?
Bj
Ai
B1
B2
B3
B4
B5
A1
4
8
7
15
12
A2
7
9
17
14
10
A3
6
9
12
8
7
A4
6
7
14
6
10
A5
6
9
12
10
6
例2 (P143-例12)
四、非标准形式指派问题的求解
若为max型,可用C中最大元素分别减去C中每一元素
若人数和任务数不同,即C非方阵,可添加虚拟的人或任务,取系数为0
一个人做几项任务,可将该人化为几个人;反之亦然
某任务不能由某人做,取系数为M
运筹学第11讲:整数规划(二)
运筹学第11讲:整数规划(二)
某商业公司计划开办5家新商店,公司决定由3家建筑公司分别承建,允许每家建筑公司承建一家或二家商店。已知建筑公司Ai 对新商店Bj 的建造费用报价如下表所示。求使总费用最小的指派方案。
Bj
Ai
B1
B2
B3
B4
B5
A1
4
8
7
15
12
A2
7
9
17
14
10
A3
6
9
12
8
7
例3 (P147-例13)
采用匈牙利法求得:A1承建B1和B3,A2承建B2,A3承建B4和B5,总造价为35万元。
作业****题5-3****题5-4
思考:案例7
例4
甲
乙
丙
丁
A
3
2
-2
1
B
2
-2
0
/
C
/
-1
1
0
表中的元素表示4人完成3项任务的利润,“/”表示不胜任。由于精力所限,每人只能承担一项任务,求使总利润最大的指派方案。
运筹学第11讲:整数规划(二)