运筹学整数规划

二、匈牙利法
指派问题的效率矩阵的每一个元素aij≥0
解矩阵是每行或每列只能有一个元素为1，其余 均为 0 的 n 阶方阵。如：
0 0 ( xij ) 1 0 1 0 0 0 0 1 0 0 0 0 0 1
是指派问题的解矩阵。
匈牙利法
匈牙利法源于匈牙利数学家康尼 (D.König) 一个关于矩阵中 0 元素 的定理： 系数矩阵中独立 0 元素的最多个 数等于能覆盖所有 0 元素的最少直 线数. 1955年，库恩（W.W.Kuhn） 引用了0 元素的定理提出了匈牙利 法，用于求解指派问题。
2
1
5 2 2 9 2
0 3 8 8 4
4
2 0 3 0 1
0 0 5 0 4
2 0 0 4 3
3
8。按算法处理列数据减去势值-2，0。 1列减-2，2，3，4，5列减0。得到
2
1
7 4 0 11 0
0 3 8 8 4
1
5 2 0 9 0
0 3 10 8 6
4
2 0 5 0 3
0 0 7 0 6
2 0 2 4 5
3
5。按算法处理行数据减去势值2，0。 3，5行减2，1，2，4行减0
2
1
5 2 0 9 0
0 3 10 8 6
4
2 0 5 0 3
匈牙利法
（5）若 元素的数目 m 等于矩阵的阶数 n ，那 么这个指派问题的最优解已得到。若 m < n ，则转 入上一步：
例 :有一份中文说明书,需要译成英、日、德、俄 四种文字，分别记作 E、J、G、R 。现有 甲、乙、 丙、丁四人，他们将中文说明书翻译成不同文字 说明书所 需要的时间如表4—1所示。问应指派何 人去完成哪一 项工作，使所需的总时间最少？
2 0 5 0 3
0 0 7 0 6
2 0 2 4 5
3。重复。依行，不考虑划去的0，只有一个0的 对0打圈，划去列 2
1
5 2 0 9 0
0 3 10 8 6
2 0 5 0 3
0 0 7 0 6
2 0 2 4 5
3
4。重复。依列，不考虑划去的0，只有一个0的 对0打圈，划去行 2
7 8 11
任务 人员
分派情况
甲 乙 丙
E J G R
丁
4
15
所需时间
13
9
甲 1 1 乙 1 丙 1 丁
对应每个指派问题, 都有类似的表格，我们称之 为效率矩阵或系数矩阵，某元素 cij ( i , j = 1,2, · · · · · · , n ) 表示指派第 i 个人去完成 第 j 项任务时的效率(或
0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0
于是，得到
0 0 1 0
0 1 0 0
0 0 0 1
1 0 0 0
这时我们已经找到了4个不同行不同列的 0 元素，所 以，该问题的最优解矩阵是：
0 0 ( aij ) 1 0
1。第一行找到二个0 元素，转第二行
2。第二行找到一个0 元素，划去第二列。
6。第四列找到一个0 元素，划去第一行。
3。第三行找到一个0 元素，划去第一列。
0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0
5。第三列找到一个0 元素，划去第四行。
4。第四行找到二个0 元素，转向处理列
注：本定理解决了不同问题的等价转换。像我们提 示------可以将复杂的问题转换为简单问题来解
匈牙利法
定理一的解释： 设效率矩阵为：
4 A= 8 6 显然，A的最优解是 2
1 0
0 1
2 1 0 3 B= ( )( )( )( ) 8 2 1 1 2 1 5 0
整数规划问题的求解要比一般的线性规划困难
本章将着重讨论 1。一类特殊的整数规划——指派问题，它的数 学模型和求解。 2。求解整数规划方法——分枝定界法。
一、指派问题的数学模型
1。数学模型
某单位需要指派 n 个人去完成 n 项任务，每个人 只做一项工作，同时，每项工作只由一个人完成。由 于各人的专长不同，每个人完成各项任务的效率也不 同。于是产生了应指派哪一个人去完成哪一项任务， 使完成 n 项任务的总效率最高（如所用的时间为最 少）。我们把这类问题称之为指派问题或分派问题 (Assignment Problem)。
匈牙利法
（3）重复进行（1）、（2）两步，直到所有 0 元 素都被圈出和划掉为止。 （4）若仍然有没有被划圈的 0 元素，且同行列 的 0 元素至少有两个（表示对这个人可以从两项 任务中指派其一），则可用不同的方案去试探。 从所剩 0 元素最少的行或列开始，比较该行或列 各 0 元素所在列或行中 0 元素的数目，选择 0 元 素少的那一列或行的这个 0 元素加圈（表示选择 性多的要“礼让”选择性少的）。然后划掉同行 或列的其它 0 元素。反复进行直到所有 0 元素都 已被圈出和划掉为止。
时间、成本等)。解题时需要引入变量 xij ；其取值只
能是 1 或 0，并令 ：
1 xij 0
当指派第 I 个人去完成第 j 项任务
当不指派第 I 个人去完成第 j 项任务
当问题是要求极小化时的数学模型是：
Min Z
c
i 1 j 1
n
n
ij
xij
n xij 1 i 1, , n j 1 n j 1, , n xij 1 i 1 xij 0 或 1
矩阵A得元素aij 与B矩阵bij的元素满足 bij = aij - ui – vi。 显然可见， A与B的最优解等价。
4 6
2 2
匈牙利法
定理二：
设 (aij)是指派问题的系数矩阵， aij 0，i , j = 1 , 2, · · · · · · , n 。若从(aij)的某一行（列）各 元素中分别减去该行（列）的最小元素而得 到的新矩阵 (bij) ，那么, 以新矩阵 (bij) 为系 数矩阵的指派问题与原问题具有相同的最优 解。
0 0 7 0 6
2 0 2 4 5
3
6。按算法处理行数据减去势值2，0。 3，5行减2，1，2，4行减0。得到
2
1
5 2 2 9 2
0 3 8 8 4
4
2 0 3 0 1
0 0 5 0 4
2 0 0 4 3
3
7。按算法处理列数据减去势值-2，0。 1列减-2，2，3，4，5列减0。
任务 人员
E
2 10 9 7
J
15 4 14 8
G
13 14 16 11
R
4 15 13 9
甲 乙 丙 丁
2 10 ( aij ) 9 7
15 13 4 0 4 14 15 6 14 16 13 0 8 11 9 0
13 11 2 0 10 11 5 7 4 1 4 2
解：按第一、二步将系数矩阵进行变 换：
12 7 9 7 9 5 0 2 0 8 9 6 6 6 2 3 0 0 (cij ) 7 17 12 14 9 0 10 5 7 15 14 6 6 10 9 8 0 0 4 10 7 10 9 0 6 3 6 2 0 2 4 5
4
2 0 3 0 1
0 0 5 0 4
2 0 0 4 3
3
9。按算法要求，得到一个新的矩阵。重新 依行依列划圈，与划线，见下。 2
1
7 4 0 11 0
0 2 0 2 3 0 0 0 8 3 5 0 8 0 0 4 4 1 4 3
0 1 0 0
0 0 0 1
1 0 0 0
这表示： 指定甲翻译俄文，乙翻译日文，丙翻译英 文 ，丁翻译徳文。所需总时间最少为：
Min Z c31 c22 c43 c14 28 (小时)
例：求如下系数矩阵所对应的指派问题：
12 7 9 7 9 8 9 6 6 6 (cij ) 7 17 12 14 9 15 14 6 6 10 4 10 7 10 9
匈牙利法
定理一：分派问题的效率矩阵A的每一行的元素中 分别减去（或加上）一个常数ui （称为该行的位 势）；每一列的元素中分别减去（或加上）一个 常数vi （称为该列的位势）。得到一个新的矩阵 B。如果矩阵A的元素aij与矩阵B的元素bij满足 ： bij = aij - ui - vi , 则， A与B的最优解等价。
wenku.baidu.com
第一行减去2； 第二行减去4； 第三行减去9； 第四行减去7；
（每行减去行的最小值）
0 13 11 2 0 13 7 0 6 0 10 11 6 0 6 9 0 5 7 4 0 5 3 2 0 1 4 2 0 1 0 0
第一列已有0，不减； 第二列已有0，不减； 第三列减4； 第四列减2； （每列减去行的最小值， 如列中已有0，不减）
定理三： 若矩阵A的元素分为“0”与非“0”二 部分，则覆盖0元素的最小直线数是位于 不同行、不同列的“0”元素的最大个数。
注：解决了如何找到解矩阵的“1”元素的 位置。得到最优解。
下面，请阅读教材P114 — 例5.15。 尝试理解匈牙利法解指派问题的过程。
匈牙利法
指派问题的解法: 第一步：使指派问题的系数矩阵，经变换，在各行各
1。依行，只有一个0的对0打圈，划去列
1
5 2 0 9 0
0 3 10 8 6
2 0 5 0 3
0 0 7 0 6
2 0 2 4 5
2。依列，不考虑划去的0，只有一个0的，对0 打圈，划去行 2
1
5 2 0 9 0
0 3 10 8 6
列中都出现 0 元素。为此分如下两步进行：
（1）将系数矩阵的每行元素减去该行的最小元素；
（2）再从所得的系数矩阵中，将每列减去该列的最
小元素。（若该行或列已有 0 元素，则就不必计算）
匈牙利法
第二步：进行试指派以寻求最优解。为此按如下 5 个分步骤进行： （1）从只有一个 0 元素的行（列）开始，给这个 0 元素加圈，记为 。然后划去 所在的列 （行）的其它 0 元素，记为 。这表示该列所 代表的任务已指派 完，不必再考虑别人。 （2）给只有一个 0 元素的列的 0 元素加圈，记 为 ；然后划去 所在行的 0 元素，记为 。
3
9。按算法要求，已无法划圈，与划线。有闭回路 ， 间隔划圈 2 4
例 :有一份中文说明书,需要译成英、日、德、俄 四 种文字，分别记作 E、J、G、R 。现有 甲、乙、 丙、丁四人，他们将中文说明书翻译成不同文字 说明书所 需要的时间如表4—1所示。问应指派何 人去完成哪一 项工作，使所需的总时间最少？
任务 人员
E
2 15 13
J
10 4 14
G
9 14 16
R
第四章 整数规划
整数规划
线性规划问题中，所有的解都假设为具有连续型 的数值，即解可以是整数、分数或带有小数点的实 数。
但对于某些具体的问题，常要求最优解是整数的
情形。
例如：机器台数
完成工作的人数
装货的车数等等。
分数或小数的解，不符合实际要求，要求整数解。
直观上用看起来，似乎对线性规划最优解“舍 入化整” 可以求得解，但这常常得不到可行的解， 即使得到可行的解，也不一定是最优解。 称求解是整数的规划问题为整数规划 (Integer Programming)，简称为 I P 。 因此，对整数规划问题，需要另行研究。 整数规划中，如果所有的变量都要求是（非负） 整数,就称为纯整数规划(Pure Integer Programming); 全整数规划(All Integer Programming)； 如果其中一部分变量取值为整数，则称为混合 整数规划( Mixed Integer Programming )。