整数规划3-指派问题.ppt

第三节指派问题
一、指派问题及其模型
1、指派问题
指派问题
某企业一部门有A1、A2、A3、A4四个人,该部门有
B1、B2、B3、B4 四项工作需要做,要求每人只能做一
项工作,每项工作只能一人去做。已知:每人做每项工作
的单位消耗如下表 -1 所示。试问:应如何分配工作
使总消耗最少?
重庆大学经济与工商管理学院肖智
1
§ 指派问题
-1 单耗信息表
模型:

(-1)
单耗工作
人
B1
B2
B3
B4
A1
6
2
1
5
A2
3
12
8
16
A3
2
9
7
13
A4
5
11
9
12
重庆大学经济与工商管理学院肖智
2
§ 指派问题
2、一般指派问题
有n项任务,有m种资源,要求每种资源只能用于一
项任务,每项任务只能拥有一种资源。已知,第 j项任务
需消耗第 i 种资源Cij。试问:应如何配备资源使总消耗
最少?
3、一般模型:
(-2)
重庆大学经济与工商管理学院肖智
3
§ 指派问题
4、基本特征:
1)特殊的线性规划;
2)特殊的整数规划;
3)特殊的0-1整数规划;
4)特殊的运输问题;
5、常用求解方法分类
1)线性规划的求解方法;
2)整数规划的求解方法;
3)0-1整数规划的求解方法;
4)运输问题的求解方法;
5)特殊的求解方法——匈牙利算法
重庆大学经济与工商管理学院肖智
4
§ 指派问题
二、指派问题的求解方法
1、计算机方法
:。
2、匈牙利算法
1)适用范围:指派问题的标准型问题。
指派问题的标准型问题必须满足以下3个条件:
(1)目标要求为极小化(min);
(2)效益矩阵(目标系数矩阵)A=(aij)n×n为方阵;
(3)A中所有元素均为非负常数(aij≥0,i,j=1,2,…,n)
2)基本理论
(1)定理1:设一个指派问题的效益矩阵为(aij)n 。若
重庆大学经济与工商管理学院肖智
5
§ 指派问题
从(aij)n的第 i 行元素中减去一个常数ui (i=1,2,…,n),
从第j 行元素中减去一个常数vj(j=1,2,…,n),得到一
个新的效益矩阵(bij)n,其中每一元素bij=aij-ui-vj,则
(bij)n问题的最优解也是(aij)n问题的最优解。
(2)定理2:若一方阵中的一部分元素为0,一部分元素为非0,则覆盖方阵内所有0元的最少直线数恰好等于那些位于不同行、不同列的0元的最多个数。
3)基本步骤:
(1)效益矩阵的初始变换——零元素的获取
①行变换:效益矩阵A0的每行减去该行的最小元素得
新效益矩阵A1;
②列变换:对A1的每列减去该列的最小元素得新效益
矩阵A2;
重庆大学经济与工商管理学院肖智
6
§ 指派问题
(2)最优性检验:
①用最少的直线覆盖A2所有的0元素,记其直线数为K,
②若k=n,则转(4);否则转(3)。
(3)调整:
①在覆盖有直线的A2中,对线外的所有元素减去这些
元素中的最小a;
②对线上交叉的元素加上a,得一新的效益矩阵,仍
记为A2;转(2)。
(4)输出最优解:
①确定位于不同行不同列的0元素;
②将确定的位于不同行不同列的0元素对应的决策变
量取1,其余决策变量取0,得最优解(方案)。
重庆大学经济与工商管理学院肖智
7
§ 指派问题
4):。
解:(1)效益矩阵的初始变换——零元素的获取

(2)最优性检验
1
3
2
5
0
1
0
4
即有:k=2<4=n
重庆大学经济与工商管理学院肖智
8
§ 指派问题
(3)调整:

转(2)最优性检验
即有:k=3<4=n
重庆大学经济与工商管理学院肖智
9
§ 指派问题
(3)调整:

转(2)最优性检验
即有:k=4=n
重庆大学经济与工商管理学院肖智
10
§ 指派问题