文档介绍：1
期中考试:4月18日8:00-9:30 4106
2
4月23日(周六)调课
春假后 5月6日(周五)8:00 – 9:30
第二节经典分配(指派)问题与匈牙利法
3
n个员工分配作n项工作,已知第i个员工做第j项工作的成本为cij,i=1,…,n; j=1,…,n。规定:每人完成其中一项,每项只交给一个人完成。求最佳分配方案。
两个基本类型
若完成任务的成本表现为资源的消耗, 则考虑的是如何分配任务, 使目标极小化;
若完成任务的成本表现为生产效率的高低, 则要考虑如何分配, 使目标极大化。
分配问题的数学模型 设决策变量为:
4
.
5
分配问题(基)可行解的结构: 在n2个分量中只有n个分量为1,其余的全部为0; 并且这些为1的分量的位置应位于成本矩阵的不同行不同列上. 即
分配问题的解应对应于成本矩阵的不同行与不同列(为什么?)
分配问题成本(效率)矩阵
例:已知分配A1、A2、A3、A4、A5五人分别完成五项任务, 他们分别完成各任务的时间如下
6
cij
问应如何分配,使这五人分别完成这五项任务的总时间最小?
匈牙利算法基本思想
匈牙利算法适用于极小化且成本矩阵的所有元素都非负的分配问题
如果成本矩阵的所有元素都非负,并且存在一组位于不同行不同列的0元素, 则只要令对应于这些0元素位置的xij=1, 其余的xij=0, 即为所求的最优解. 因为此时必有z=0就是问题的最优值
匈牙利算法的关键: 如何产生并寻找一组位于不同行不同列的0元素
7
分配问题的性质—匈牙利算法的依据
8
定理1:对于分配问题,成本矩阵的任一行(或列)减去(或加上)一个相同的数得到的新指派问题与原问题同解
作用: 如何在效率矩阵中产生零元素
9
证明:
指派问题的性质(续)
定理2: 若成本矩阵C的元素可分成0与非0两部分, 则覆盖0元素的最少直线数等于不同行不同列的0元素的最大个数.
作用: 如何寻找位于不同行不同列的零元素.
10