选X1分枝 问题(2) (1) X1 4 问题(3) (1) X1 5
7
将[4,5]之间的非整数部分舍去
问题2
解为 X1 =4 Z=349.0 解为
问题3 X1 =5 Z=341.39
X2 =2.1
X2 =1.571
选(2)继续分枝
(2) (2)
问题(4)
X2 2
问题(5)
X2 3
实际含义：从事情的角度来考虑，表示此事分配给此人效率最高。
24
min
步骤二：继续产生零元素 方法：再找出矩阵每列的最小元素，再分 别从各列中减去它。
0 8 7 5 0 8 11 0 10 4 11 0 2 3 5 0 2 3 0 11 9 5 0 11
max Z=CX
maxZ=CX (B) AX=b X 0
AX=b
(A) X 0
X为整数 (B)为(A)的松弛问题。
3
（2）替代问题的求解 max Z=CX
(B)
AX=b X 0
采用相应的方法（如图解法）求解出替代问题的 最优解，观察其是否满足整数解的要求。如其最 优解就为整数，则结束；如含有分数，则需要进 行分支定界操作。
28


例：从行开始的独立零元素的寻找与判断 （0 ）
2 5 11 （ 0 5 4 ） 2 3 0 0 0 11 4 5 8
(0) 8 2 5 11 (0) 5 4 2 3 0 0 0 11 4 5
从行开始标定独立零元 素时，只能找到两个独 立的零元素。
29
非直观法-步骤2


(2) <从人的角度>在行寻找的基础上，从第一 列开始，若该列只有一个零元素就对这个 零元素打上( )号(同样不考虑已划去的零元 素)， 对打( )号零元素所在行画一条直线（任务分
配完毕，不能再分配给其他人）。

若该列没有零元素或有两个以上零元素， 则转下一列，依次进行到最后一列；
1 0 1 2
2 0 0 2 0 3 2 4 0 0 3 0
1 0 0 2
2 0 0 2 0 3 2 4 0 2 3 1
19

若矩阵A的元素可分成“0”与非“0”两 部分，则覆盖“0”元素的最少直线数等 于位于不同行、不同列的“0”元素的最 大个数。 将确定一个效率矩阵中最大独立零元素的 个数，转化为寻找覆盖所有零元素所需的 最少直线数。
31
问
题
2 5 (0) 8 11 (0) 5 4 2 3 (0) 0 0 11 4 5
只能对三个零元素进行标定（代表独立的零 元素只有三个），后续如何操作？
32
非直观法-步骤3（第一种情形）


(3) 重复(1)、(2)两个步骤，可能出现三种 情况： ① 效率矩阵每行都有一个打( )号的零元 素，很显然，按上述步骤得到的打( )号 的零元素都位于不同行不同列，只要令 对应打( )号零元素对应的决策变量xij=1 就找到了问题的最优解；
人
从人的 角度看 从任务 角度看
工作 译成英文 译成日文 译成德文 译成俄文
甲 2 15 13 4
乙 10 4 14 15
丙 9 14 16 13
丁 7 8 11 9
12
指派问题的一般模型


假设： [aij]表示指派问题的效率矩阵 xij表示决策变量，决策变量的取值：
1, 分配第i个人去完成第j项任务 xij 0, 不分配第i个人去完成第j项任务 (i 1,..., m; j 1,...,m)
8
(1)
4.809 355.890 1.817
分支定界过程
X1 5
(3)
X1 4
(2)
4 2.1
X2 2 (4) 4 2 340
349.0 X2 3 (5) 340 (6) 5.444 1
5 341.39 1.571
X2 1 340 X2 2 (7) 无解
9
1.428 327.12 3
只能给两个零元素打括号， 还有四个零元素不能打上括 号。剩下的未被划去和未打 括号的零元素存在闭回路。
4
（3）分支与定界—增加约束
•如替代问题的解不符合整数条件，则需要对原问题进行分支。
•分支方法：假设替代问题的解为[i，i+1]之间的一个数，则分成两支：
一支增加约束xj≤i，另一支增加约束xj ≥ i+1； •对上述两个问题进行求解：不考虑整数问题时，求解对应的线性规划 问题，观察其最优解是否是整数，如不是，则继续分支定界，直到得到 全部整数解为止。 i+1
13
指派问题的一般模型

指派问题的一般数学模型
min z aij xij
i 1 j 1 m m
m xij 1 (i 1,...,m) j 1 m xij 1 (j 1,...,m) i 1 xij 0 或 1
14
2、指派问题的求解方法


如何让效率矩阵中产生零元素； 如何让产生的零元素位于不同行和不同列。
17

（2）零元素的产生方法： 匈牙利法的基本定理1

如果从分配问题效率矩阵[aij]的每一行元 素中分别减去(或加上)一个常数ui (被称 为该行的位势)，从每一列分别减去(或 加上)一个常数vj (称为该列的位势)，得 到一个新的效率矩阵[bij]，若其中 bij aij ui v j
33
第一种情形
甲
任务一
任务二 任务三 任务四
乙
丙
丁 x11=1，x22=1， x33=1，x44=1。
2 3 (0) 1 1 (0) 3 4 1 2 (0) 5 8 2 (0) 3
任务一→甲；二 →乙；三→丙； 四→丁
34
非直观法-4（第二种情形）

② 打( )号的零元素个数小于m，但未被划去的 零元素之间存在闭回路（全以0为拐点），这 时可顺着闭回路的走向，对每个间隔的零元素打 一( )号，然后对所有打( )号的零元素，或所在 行，或所在列画一条直线（一般会出现多种方 案）。如：
10
4.5.3 整数规划的解法——匈牙利法
应用于分配问题或指派问题

分配问题也称指派问题，是一种特殊的 整数规划问题。 假定有m项任务分配给m个人去完成，并 指定每人完成其中一项，每项只交给其 中一个人去完成，应如何分配使总的效 率为最高。
11

1、指派问题一般模型的引出

例：有一份说明书，要分别译成英、日、德、俄四种文字， 交甲、乙、丙、丁四个人去完成。因各人专长不同，他们 完成翻译不同文字所需的时间(h)如表所示。问：如何分 配任务使效率最高（所需总时间最短）？

非直观法：m很大时，根据一定规则寻找。
26
直观法
0 8 11 0 2 3 0 11
2 5 0 4
5 4 0 5
只有3个0元素 位于不同行、 不同列
27
非直观法-步骤1（试指派过程）

(1) <从任务的角度来挑选>从第一行开始，若该行 只有一个零元素，就对这个零元素打上( )号。< 表示该0元素处在单独的一行> 同时，对打( )号零元素所在列画一条直线，表示 此列已经确定（人员确定），不能再从事其他行 的工作（任务） 。 若该行没有零元素或有两个以上零元素(已划去的 零元素不计在内)，则转下一行，按照上述方法依 次进行到最后一行；
30
例：从列开始的独立零元素的寻找与判断
(0) 8 2 5 11 (0) 5 4 ） 2 3 （ 0 0 0 11 4 5
2 5 (0) 8 11 (0) 5 4 2 3 (0) 0 0 11 4 5
在行标定后的基础上， 从第一列开始标定独立 零元素时，只能找到一 独立的零元素。
4.5 整数规划的解法
分支定界法 割平面法 匈牙利法
1
4.5.1 整数规划解法 ——分枝定界法
步骤： 1、寻找替代问题并求解 2、分枝与定界 3、剪枝

2
1、基本思路：整数规划的最优解不会优于相应
的线性规划的最优解。对于极大值问题，相应线性 规划的最大值成为整数规划目标函数的上界。
（1）替代问题的确定
22
效率矩阵
2 10 15 4 A 13 14 4 15
7 14 8 16 11 13 9 9
23
步骤一：零元素的产生。 方法：找出效率矩阵每行的最小元素，并 分别从每行中减去它。
2 10 9 7 2 0 8 7 5 15 4 14 8 4 11 0 10 4 13 14 16 11 11 2 3 5 0 4 15 13 9 4 0 11 9 5
20

匈牙利法的计算步骤


基本步骤：在效率矩阵中产生零元素→ 判断独立的零元素个数是否等于任务数 或人数？→如是，则对效率矩阵中独立 零元素所处的位置进行指派（对应的决 策变量为1），完成→如否，则要继续产 生足够的独立零元素。 通过实例来说明匈牙利法求解指派问题 的过程。
21
例：

有一份说明书，要分别译成英、日、德、俄四种文 字，交甲、乙、丙、丁四个人去完成。因各人专长 不同，他们完成翻译不同文字所需的时间(h)如表所 示。问：如何分配任务使效率最高？ 人 工作 译成英文 译成日文 译成德文 译成俄文 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9
307.76
4.5.2 整数规划解法2——割平面法