分配问题
假定有 m 项任务分配给 m 个人去完成,并指定每人完成其中一项,每项只交给其中一个人去完成,应如何分配使总的效率为最高。
也称指派问题(assignment problem),是一种特殊的整数规划问题。
解法
效率表 (已知)
利用不同资源完成不同计划活动的效率通常用表格形式表示
1、效率矩阵
表格中数字组成
2、定义逻辑变量
3、建立数学模型
4、匈牙利法
匈牙利法
第一步:找出效率矩阵每行的最小元素,并分别从每行中减去。
第二步:找出矩阵每列的最小元素,分别从各列中减去。
第三步:确定能否找出 m 个位于不同行不同列的零元素的集合 (m:行列数)
圈0划行列 (先行后列)
看行,有0打上( )并划去该列
看列,有0打上( )并划去该行
若该行没有零元素或者有两个以上零元素 (已划去的不算在内) 则转下一行,依次进行到最后一行
第四步:若打括号的零元素少于 m ,这时转入第四步。进行如下变换
1. 从矩阵未被直线覆盖的数字中找出一个最小的k ;
2. 对矩阵中的每行,当该行有直线覆盖时,令 ui=0,无直线覆盖的,令 ui= k ;
3. 对矩阵中有直线覆盖的列,令 vj= -k,对无直线覆盖的列,令 vj= 0 ;
4. 从原矩阵的每个元素 aij中分别减去 ui 和 vj
第五步:再找m个打()的0元素变1得到最优解
简洁版
找最小元素k
确定位势 无:ukv0,有:u0v-k
ui:看行
无直线k
有直线0
vj:看列
无直线0
有直线-k
减去位势得新矩阵
练习题
分配问题
-
1、效率矩阵
-
- 2、定义逻辑变量
3、建立数学模型
- 2、定义逻辑变量
4、匈牙利法
最优值为:4+4+9+11=28
-