指派问题_匈牙利算法

2x1 4x2 13
2x1 x2 7
x1, x2 0 且为整数
解：松弛问题的最优解为 x1=2.5, x2=2, OBJ=23 由 x1=2.5 得到两个分枝如下：
max f ( x) 6x1 4x2
max f ( x) 6x1 4x2
2x1 4x2 13
问题I
2x1 x2 7 x1 2
• 整数规划的最优解不会优于其松弛问题的最优解
n
max(min) f (x) c j x j
j 1
s.t.
n
aij
j 1
x
j
(,)bi ,
i 1,2, ,m
x j 0 且为整数 , j 1,2, ,n
2
4.2 整数规划的分枝定解法
4.2.1 思路与解题步骤
• 只解松弛问题
1、在全部可行性域上解松弛问题
– 行变换：找出每行最小元素，从该行各元素中减去之 – 列变换：找出每列最小元素，从该列各元素中减去之
10 9 (7) 8 行 3 2 0 (1) 列 3 2 0 0
ห้องสมุดไป่ตู้
变
变
(5) 8
5 (2)
(4) 3
7 6 4
7 5 5
换
0 1 0
3 0 1
2 2 2
2 1 3
换
2、逐列检查，若该列只有一个未标记的零，对其加( )标记，将( )标
记元素同行同列上其它的零打上*标记。若该列有二个以上未标记的
零，暂不标记，转下一列检查，直到所有列检查完；
逐
逐
行 检
3
x1, x2 0 且为整数
2x1 4x2 13
问题II
2x1 x2 7 x1 3
x1, x2 0 且为整数
5
表4.2.3 分枝问题的松弛解
问题 I
x1
2
x2
9/4
f(x)
21
问题 II 3 1 22
问题II的解即原整数问题的最优解
可能存在两个分枝都是非整数解的情况，则需要两边同时继续 分枝，直到有整数解出现，就可以进行定界过程 当有很多变量有整数约束时，分枝即广又深，在最坏情况下相 当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，NP-complete，只有 少数特殊问题有好的算法，如任务分配问题、匹配问题
证明：略
清华算法的基本思路：
• 根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若 矩阵中存在 m 个不同行不同列的零，就找到了最优解
• 若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚 未找到最优解，设法进一步变换矩阵，增加新的零
9
清华算法的步骤：例4.6.1
第一步：变换效率矩阵，使每行每列至少有一个零
mm
min f ( x) aij xij
i1 j1
m
xij
1
i 1,2, ,m
imj11xij 1 j 1,2, , m
xij 0,1
7
任务分配问题的数学模型
模型中：xij 为第 i 个工人分配去做第 j 项任务； aij 为第 i 个工人为完成第 j 项任务时的工时消耗； {aij}mm 称为效率矩阵
函数优于问题 1 枝)，其整数解为界，
对问题 2 继续分枝
情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后 续分枝所得到的整数解进行比较，结论如情况 4
4
4.2.2 分枝定界法举例
例4.1.1 max f ( x) 6x1 4x2
– 若松弛问题最优解为整数解，则其也是整数规划的 最优解
2、分枝过程
– 若松弛问题最优解中某个 xk=bk 不是整数，令 bk 为 bk 的整数部分
– 构造两个新的约束条件 xk bk 和 xk bk +1，分 别加于原松弛问题，形成两个新的整数规划
3、求解分枝的松弛问题 — 定界过程
– 设两个分枝的松弛问题分别为问题 1 和问题 2 ，它
们的最优解有如下情况
3
表4.2.1 分枝问题解可能出现的情况
序号
问题 1
问题 2
说明
1
无可行解
无可行解
整数规划无可行解
2
无可行解
整数解
此整数解即最优解
3
无可行解
非整数解
对问题 2 继续分枝
4
整数解
整数解
较优的一个为最优解
5 整数解，目标函 非整数解
问题 1 的解即最优解
数优于问题 2
6
整数解
非整数解，目标 问 题 1 停 止 分 枝 (剪
下面介绍一种适合手算的算法(出自清华教科书) 8
4.6.1 清华算法
定理 1 如果从效率矩阵{aij}mm中每行元素分别减去一个常数 ui， 从每列元素分别减去一个常数 vj ，所得新的效率矩阵{bij}mm 的任务分配问题的最优解等价于原问题的最优解。
证明：略
定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方 阵内所有零元素的最少直线数等于位于不同行、不同列的零 元素的最多个数。
©管理与人文学院 忻展红
1999，4
第四章 整数规划
整数规划的难度远大于一般线性规划
4.1 整数规划简介
• 要求所有 xj 的解为整数，称为纯整数规划 • 要求部分 xj 的解为整数，称为混合整数规划 • 对应没有整数解要求的线性规划称之为松弛问题
• 整数规划的解是可数个的，最优解不一定发生在极点
1 当第i个工人分配去做第j项任务 xij 0 当第i个工人未分配去做第j项任务
i, j 1,2, , m
运输问题是任务分配问题的松弛问题 任务分配问题不但是整数规划，而且是01规划
任务分配问题有2m个约束条件，但有且只有m个非零解， 是自然高度退化的 任务分配是两部图的匹配问题，有著名的匈牙利算法
0 1 0
3 0 1
2 2 2
1
0 2
第二步：检查覆盖所有零元素的直线是否为m条
划线规则
1、逐行检查，若该行只有一个未标记的零，对其加( )标记，将 ( )标记元素同行同列上其它的零打上*标记。若该行有二个以上 未标记的零，暂不标记，转下一行检查，直到所有行检查完；
10
清华算法的步骤：例4.6.1
6
4.6 任务分配问题
例4.6.1 有四个熟练工人，他们都是多面手，有四项任务要他 们完成。若规定每人必须完成且只完成一项任务，而每人 完成每项任务的工时耗费如表4.6.1，问如何分配任务使完 成四项任务的总工时耗费最少？
任务
工时 A B C D 人员 人员
甲 10 9 7 8 1 乙 5877 1 丙 5465 1 丁 2345 1 任务 1 1 1 1