1
整数规划 Integer Programming（ IP）
第五章整数规划
2
整数规划 Integer Programming（ IP）
整数规划的数学模型及解的特点整数规划数学模型的一般形式
（ IP）问题 Max（ min） z = ∑cjxj
∑aijxj ≤（或 =，或 ≥） bi i=1,2,…,m
xj ≥ 0 j=1,2,…,n
xj 中部分或全部取整数
s.t.
松弛问题 Max（ min） z = ∑cjxj
∑aijxj ≤（或 =，或 ≥） bi i=1,2,…,m
xj ≥ 0 j=1,2,…,n
3
整数规划 Integer Programming（ IP）
整数规划的数学模型及解的特点整数规划问题的类型
1,纯整数线性规划 ——pure integer linear programming,全部 决策变量都必须取整数值。
2,混合整数线性规划 ——mixed integer linear programming：
决策变量中 一部分 必须取整数值，另一部分可以不取整数值。
3,0-1型整数线性规划 ——zero-one integer linear
programming：决策变量只能取值 0 或 1 。
4
整数规划 Integer Programming（ IP）
整数规划的例子例 1,Page 130
工作时间和人员安排问题例 2,Page 130
投资项目选择问题例 3,Page 131
建厂选址问题
5
整数规划 Integer Programming（ IP）
整数规划问题的求解方法分支定界法 branch and bound method
分支定界法是一种隐枚举方法（ implicit enumeration）或部分枚举方法，它不是一种有效的算法，是枚举方法基础上的改进。
其关键是分支和定界。
例 ——
Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1,X2 ≥ 0
X1,X2 取整数
s.t.
6
整数规划 Integer Programming（ IP）
整数规划问题的求解方法分支定界法图解整数规划松弛问题 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1,X2 ≥ 0
该整数规划松弛问题的解为：
（ X1,X2 ） = （ 3/2,10/3）
Z1 = 29/6
7
整数规划 Integer Programming（ IP）
整数规划问题的求解方法分支定界法图解整数规划松弛问题 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1,X2 ≥ 0（ 3/2,10/3）
Z1 = 29/6 B1 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 2
X1,X2 ≥ 0
B2 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≤ 1
X1,X2 ≥ 0
B2：解
（ 1,7/3 ）
Z21 = 17/3
B1：解
（ 2,23/9 ）
Z11 = 41/9
8
整数规划 Integer Programming（ IP）
整数规划问题的求解方法分支定界法图解整数规划
（ 3/2,10/3）
Z1 = 29/6
B1 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 2
X1,X2 ≥ 0
B2：解
（ 1,7/3 ）
Z21 = 17/3
B1：解
（ 2,23/9 ）
Z11 = 41/9
B11 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 2
X2 ≥ 3
X1,X2 ≥ 0
B12 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 2
X2 ≤ 2
X1,X2 ≥ 0
B12：解
（ 33/14,2 ）
Z12 = 61/14
9
整数规划 Integer Programming（ IP）
整数规划问题的求解方法分支定界法图解整数规划
（ 3/2,10/3）
Z1 = 29/6
B2：解
（ 1,7/3 ）
Z21 = 17/3
B12 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 2
X2 ≤ 2
X1,X2 ≥ 0
B12：解
（ 33/14,2 ）
Z12 = 61/14
B121 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 3
X2 ≤ 2
X1,X2 ≥ 0
B122 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≤ 2
X2 ≤ 2
X1,X2 ≥ 0
B121：解
（ 3,1 ）
Z121 = 4
B122：解
（ 2,2 ）
Z122 = 4
B1：解
（ 2,23/9 ）
Z11 = 41/9
10
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
割平面法求解整数规划问题时，若其松驰问题的最优解 X* 不满足整数要求时，则从 X* 的非整分量中选取一个，用以构造一个线性约束条件（ Gomory 割平面），将其加入原松驰问题中，形成一个新的线性规划，然后求解之。其关键在于新增加的这个线性约束条件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切割掉了，而 不会切割掉问题的任何整数解 。
11
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
构造切割方程的步骤：
1、令 xi 是相应松驰问题的最优解中为非整数值的一个基变量，由单纯形表最终表得：
xi + ∑aik xk = bi …………………… （ 1 式）
其中 i ∈ Q （ Q 指非基变量下标集）
k ∈ K （ K 指基变量下标集）
12
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
构造切割方程的步骤：
2、将 bi 和 aik 都分解成整数部分 N （不超过 b 的最大整数）与非负真分数部分 f 之和，即：
bi = Ni + fi,其中 0 ＜ fi ＜ 1 ……… （ 2 式）
aik = Nik + fik,其中 0 ≤ fik ＜ 1
例如：若 b = 2.35,则 N = 2,f = 0.35；
若 b = -1.45,则 N = -2,f = 0.55
13
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
构造切割方程的步骤：
2、将（ 2 式）代入（ 1 式）得：
xi + ∑ Nik xk - Ni = fi - ∑ fik xk …………………… （ 3 式）
3、提出变量为整（当然含非负）的条件：
由于（ 3 式）中等式左边需整，而 0 ＜ fi ＜ 1,故有
fi - ∑ fik xk ≤ 0 …………………… （ 4 式）
此即为所需切割方程。
14
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
构造切割方程的步骤：
（ 1）切割方程 fi - ∑ fik xk ≤ 0 真正进行了切割，至少把非整数最优解这一点切割掉了。
证明：（反证法）假设松驰问题的最优解 X* 未被切割掉，则由
fi - ∑ fik x*k ≤ 0,又因为 x*k = 0，（因 x*k 为非基变量）
有 fi ≤ 0,这与 fi ＞ 0 矛盾。
（ 2）不会切割掉任何整数解，因为切割方程是由变量为整的条件提出的。
15
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
例 ——求解
IP Max Z = X1 + X2
- X1 + X2 ≤ 1
3X1 + X2 ≤ 4
X1,X2 ≥ 0
X1,X2 整数
LP Max Z = X1 + X2
- X1 + X2 ≤ 1
3X1 + X2 ≤ 4
X1,X2 ≥ 0
16
整数规划 Integer Programming（ IP）
求解步骤：
1、求解 LP 得到非整数最优解：
X =（ 3/4,7/4,0,0）,Max Z = 5/2
Cj 1 1 0 0
I 表
CB XB B –1 b X1 X2 X3 X4
0 X3 1 - 1 1 1 0
0 X4 4 3 1 0 1
j 0 1 1 0 0
B 表
1 X1 3/4 1 0 -1/4 1/4
1 X2 7/4 0 1 3/4 1/4
j - 5/2 0 0 - 1/2 - 1/2
17
整数规划 Integer Programming（ IP）
求解步骤：
2、构造切割方程：
由 B 表 中的第 2 个方程 ——
X2 + 3/4 X3 + 1/4 X4 = 7/4
有 b2 = 7/4 = 1 + 3/4
a23 = 3/4 = 0 + 3/4,a24 = 1/4 = 0 + 1/4
因此，切割方程为 ——
3/4 – 3/4 X3 – 1/4 X4 ≤ 0
增加松弛变量 X5,并将如下方程的约束条件添加到 B 表中。
- 3 X3 - 1 X4 + X5 = - 3
X5 ≥ 0
18
整数规划 Integer Programming（ IP）
求解步骤：
3、求解新的松弛问题
Cj 1 1 0 0 0
B 表
CB XB B –1 b X1 X2 X3 X4 X5
1 X1 3/4 1 0 -1/4 1/4 0
1 X2 7/4 0 1 3/4 1/4 0
0 X5 - 3 0 0 - 3 - 1 1
j - 5/2 0 0 - 1/2 - 1/2 0
新
B 表
1 X1 1 1 0 0 1/3 - 1/12
1 X2 1 0 1 0 0 1/4
0 X3 1 0 0 1 1/3 - 1/3
j - 2 0 0 0 - 1/3 - 1/6
19
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用
0-1变量作为逻辑变量（ Logical variable），常常被引用来表示系统是否处于某个特定的状态，或者决策变量是否取某个特定的方案。如
xj = 1 当决策取方案 P j 时0 当决策不取方案 P
j 时
20
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用例 1 选址问题某公司在城市的东、西、南三区建立门市部。拟议 中有 7 个位置（地点） Ai（ i=1,2,…,7）可供选择。公司规定在东区，由 A1,A2,A3 三个点中至多选两个；
在南区，由 A4,A5 两个点中至少选一个；
在西区，由 A6,A7 两个点中至少选一个。
如果选用 Ai 点，设备投资估计为 bi 元，每年可获利润估计为
ci 元，但投资总额不能超过 B 元。问公司选择哪几个点可使年总利润最大？
21
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用建立模型引入 0-1 变量 1 当 Ai 点被选用0 当 A
i 没点被选用
xi = （ i=1,2,…,7）
max z = ∑cixi
∑bixi ≤ B
x1 + x2 + x3 ≤ 2
x4 + x5 ≥ 1
x6 + x7 ≥ 1
xi = 0，或 1
22
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用例 7 应用 0-1 变量解决含互斥约束条件问题设：工序 B 有两种方式完成方式（ 1 ）的工时约束为 0.3X1 + 0.5X2 ≤ 150
方式（ 2 ）的工时约束为 0.2X1 + 0.4X2 ≤ 120
问题是完成工序 B 只能从两种方式中任选一种，如何将这两个互斥的约束条件统一在一个线性规划模型中呢？
23
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用例 7 应用 0-1 变量解决含互斥约束条件问题引入 0-1 变量
y1 = 0 若工序 B 采用方式（ 1 ）完成
1 若工序 B 不采用方式（ 1 ）完成
y2 = 0 若工序 B 采用方式（ 2 ）完成
1 若工序 B 不采用方式（ 2 ）完成
24
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用例 7 应用 0-1 变量解决含互斥约束条件问题于是前面两个互斥的约束条件可以统一为如下三个约束条件：
0.3X1 + 0.5X2 ≤ 150 + M1y1
0.2X1 + 0.4X2 ≤ 120 + M2y2
y1 + y2 = 1
其中 M1,M2 都是足够大的正数。
25
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
指派问题的标准形式及其数学模型指派问题的标准形式（以人和事为例）是：
有 n 个人和 n 件事，已知第 i 人做第 j 事的费用为 Cij（ i,j =
1,2,…,n），要求确定人和事之间的一一对应的指派方案，使完成这件事的总费用最少。如任务人员 A B C D
甲乙丙丁
2
10
9
7
15
4
14
8
13
14
16
11
4
15
13
9
26
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
指派问题的标准形式及其数学模型指派问题的标准形式，令
1 当指派第 i 人完成第 j 项任务
0 当不指派第 i 人完成第 j 项任务xij =
min z = ∑∑cijxij
∑xij = 1,j = 1,2,…,n
∑xij = 1,i = 1,2,…,n
xij = 1 或 0
27
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法标准的指派问题是一类特殊的 0-1 整数规划问题，可以用多种相应的解法来求解。但是，这些方法都没有充分利用指派问题的特殊性质来有效减少计算量。 1955年，库恩（ W.W.Kuhn）利用匈牙利数学家康尼格（ D.K?nig）的关于矩阵中独立零元素的定理，提出了指派问题的一种解法，由此，习惯上称之为匈牙利解法。
28
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法匈牙利解法的关键是利用了指派问题最优解的如下性质：
若从指派问题的系数矩阵 C = （ cij ） n× n 的某行（或某列）
各元素分别 减去一个常数 k，得到一个新的系数矩阵 C’ = （ c’ij ）
则以 C 和 C’ 为系数矩阵的两个指派问题有 相同的最优解 。
29
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤步骤一,变换系数矩阵。使其每行及每列至少有一个零元素，同时不出现负元素。
步骤二,进行试指派，即确定独立零元素。
步骤三,继续变换系数矩阵，然后返回步骤二。
30
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤以上例说明步骤
2 15 13 4
10 4 14 15
9 14 16 13
7 8 11 9
0 13 11 2
6 0 10 11
0 5 7 4
0 1 4 2
2
4
9
7
min
（ cij ） =
31
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤以上例说明步骤
0 13 11 2
6 0 10 11
0 4 7 4
0 1 4 2
0 0 4 2min
0 13 7 0
6 0 6 9
0 5 3 2
0 1 0 0
= （ c’ij ）
32
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤以上例说明步骤
0 13 7 0
6 0 6 9
0 5 3 2
0 1 0 0
此时加圈 0 元素的个数 m = n = 4，所以得到最优解
33
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤以上例说明步骤
0 0 0 1
0 1 0 0
1 0 0 0
0 0 1 0
（ xij ） =
34
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤例任务人员 A B C D E
甲乙丙丁戊
12
8
7
15
4
7
9
17
14
10
9
6
12
6
7
7
6
14
6
10
9
6
9
10
9
35
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
12 7 9 7 9
8 9 6 6 6
7 17 12 14 9
15 14 6 6 10
4 10 7 10 9
7
6
7
6
4
5 0 2 0 2
2 3 0 0 0
0 10 5 7 2
9 8 0 0 4
0 6 3 6 5
36
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
5 0 2 0 2
2 3 0 0 0
0 10 5 7 2
9 8 0 0 4
0 6 3 6 5
此时加圈 0 元素的个数
m = 4,而 n = 5，所以解题没有完成。独立零元素（加圈零元素）少于 n 个，表示还不能确定最优 指派方案。此时需确定能覆盖所有 零元素的最少直线数目的直线集合。方法如下：
37
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
1) 对没有加圈零元素的行打 √号；
2) 对所有打 √号行的所有含零元素的列打 √号；
3) 再对已打 √号的列中含零元素的行打 √号；
4) 重复 2）和 3），直到再也不能找到可以打 √号行或列为止；
5) 对没有打 √号的行画一横线，对打 √号的列画一竖线，这样就得到 能覆盖所有 零元素的最少直线数目的直线集合。
38
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
5 0 2 0 2
2 3 0 0 0
0 10 5 7 2
9 8 0 0 4
0 6 3 6 5 √
√
√
39
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤继续变换系数矩阵。其方法是在未被直线覆盖的元素中找出一个最小元素。然后在打 √号 行 各元素都 减 去这一最小元素，而在 打 √
号 列 的各 元素都 加 上这一最小元素，以保证原来的 0 元素不变。
这样得到新系数矩阵（其最优解和原问题相同）。若得到 n 个独立的 0 元素，则已得最优解，否则重复该步骤继续变换系数矩阵。
40
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
5 0 2 0 2
2 3 0 0 0
0 10 5 7 2
9 8 0 0 4
0 6 3 6 5 √
√
√
最小元素 = 2
7 0 2 0 2
4 3 0 0 0
0 8 3 5 0
11 8 0 0 4
0 4 1 4 3
41
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
7 0 2 0 2
4 3 0 0 0
0 8 3 5 0
11 8 0 0 4
0 4 1 4 3
此时加圈 0 元素的个数
m = 5,而 n = 5，独立零元素
（加圈零元素）等于 n 个,此时已得到最优解，其解矩阵为
42
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
（ xij ） =
0 1 0 0 0
0 0 1 0 0
0 0 0 0 1
0 0 0 1 0
1 0 0 0 0
最优指派：
甲 —— B
乙 —— C
丙 —— E
丁 —— D
戊 —— A
43
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
非标准形式的指派问题在实际应用中，常会遇到各种非标准形式的制派问题。一般的处理方法是先将其转化为标准形式，然后再用匈牙利法求解。
1,最大化指派问题 ——设最大化指派问题系数矩阵 C = （ cij ）,
其中最大元素为 m 。令矩阵 B = （ bij ） = （ m - cij ），则以 B 为系数矩阵的最小化指派问题和以 C 为系数矩阵的最大化指派问题有相同最优解。
2,人数和事数不等的指派问题 ——若 人少事多,则添加一些虚拟的“人”，其费用系数取 0,若 人多事少,则添加一些虚拟的
“事”，其费用系数取 0 。
44
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
非标准形式的指派问题
3,一个人可做几件事的指派问题 ——若某个人可以做几件事，则将该人化作几个“人”来接受指派。这几个“人”做同一件事的费用系数当然都一样。
4,某事一定不能由某人做的指派问题 ——若某事一定不能由某人做，则可将相应的费用系数取为足够大的数 M 。
45
整数规划 Integer Programming（ IP）
第五章结束谢谢！
整数规划 Integer Programming（ IP）
第五章整数规划
2
整数规划 Integer Programming（ IP）
整数规划的数学模型及解的特点整数规划数学模型的一般形式
（ IP）问题 Max（ min） z = ∑cjxj
∑aijxj ≤（或 =，或 ≥） bi i=1,2,…,m
xj ≥ 0 j=1,2,…,n
xj 中部分或全部取整数
s.t.
松弛问题 Max（ min） z = ∑cjxj
∑aijxj ≤（或 =，或 ≥） bi i=1,2,…,m
xj ≥ 0 j=1,2,…,n
3
整数规划 Integer Programming（ IP）
整数规划的数学模型及解的特点整数规划问题的类型
1,纯整数线性规划 ——pure integer linear programming,全部 决策变量都必须取整数值。
2,混合整数线性规划 ——mixed integer linear programming：
决策变量中 一部分 必须取整数值，另一部分可以不取整数值。
3,0-1型整数线性规划 ——zero-one integer linear
programming：决策变量只能取值 0 或 1 。
4
整数规划 Integer Programming（ IP）
整数规划的例子例 1,Page 130
工作时间和人员安排问题例 2,Page 130
投资项目选择问题例 3,Page 131
建厂选址问题
5
整数规划 Integer Programming（ IP）
整数规划问题的求解方法分支定界法 branch and bound method
分支定界法是一种隐枚举方法（ implicit enumeration）或部分枚举方法，它不是一种有效的算法，是枚举方法基础上的改进。
其关键是分支和定界。
例 ——
Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1,X2 ≥ 0
X1,X2 取整数
s.t.
6
整数规划 Integer Programming（ IP）
整数规划问题的求解方法分支定界法图解整数规划松弛问题 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1,X2 ≥ 0
该整数规划松弛问题的解为：
（ X1,X2 ） = （ 3/2,10/3）
Z1 = 29/6
7
整数规划 Integer Programming（ IP）
整数规划问题的求解方法分支定界法图解整数规划松弛问题 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1,X2 ≥ 0（ 3/2,10/3）
Z1 = 29/6 B1 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 2
X1,X2 ≥ 0
B2 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≤ 1
X1,X2 ≥ 0
B2：解
（ 1,7/3 ）
Z21 = 17/3
B1：解
（ 2,23/9 ）
Z11 = 41/9
8
整数规划 Integer Programming（ IP）
整数规划问题的求解方法分支定界法图解整数规划
（ 3/2,10/3）
Z1 = 29/6
B1 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 2
X1,X2 ≥ 0
B2：解
（ 1,7/3 ）
Z21 = 17/3
B1：解
（ 2,23/9 ）
Z11 = 41/9
B11 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 2
X2 ≥ 3
X1,X2 ≥ 0
B12 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 2
X2 ≤ 2
X1,X2 ≥ 0
B12：解
（ 33/14,2 ）
Z12 = 61/14
9
整数规划 Integer Programming（ IP）
整数规划问题的求解方法分支定界法图解整数规划
（ 3/2,10/3）
Z1 = 29/6
B2：解
（ 1,7/3 ）
Z21 = 17/3
B12 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 2
X2 ≤ 2
X1,X2 ≥ 0
B12：解
（ 33/14,2 ）
Z12 = 61/14
B121 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≥ 3
X2 ≤ 2
X1,X2 ≥ 0
B122 Max Z = X1 + X2
14X1 + 9X2 ≤ 51
- 6X1 + 3X2 ≤ 1
X1 ≤ 2
X2 ≤ 2
X1,X2 ≥ 0
B121：解
（ 3,1 ）
Z121 = 4
B122：解
（ 2,2 ）
Z122 = 4
B1：解
（ 2,23/9 ）
Z11 = 41/9
10
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
割平面法求解整数规划问题时，若其松驰问题的最优解 X* 不满足整数要求时，则从 X* 的非整分量中选取一个，用以构造一个线性约束条件（ Gomory 割平面），将其加入原松驰问题中，形成一个新的线性规划，然后求解之。其关键在于新增加的这个线性约束条件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切割掉了，而 不会切割掉问题的任何整数解 。
11
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
构造切割方程的步骤：
1、令 xi 是相应松驰问题的最优解中为非整数值的一个基变量，由单纯形表最终表得：
xi + ∑aik xk = bi …………………… （ 1 式）
其中 i ∈ Q （ Q 指非基变量下标集）
k ∈ K （ K 指基变量下标集）
12
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
构造切割方程的步骤：
2、将 bi 和 aik 都分解成整数部分 N （不超过 b 的最大整数）与非负真分数部分 f 之和，即：
bi = Ni + fi,其中 0 ＜ fi ＜ 1 ……… （ 2 式）
aik = Nik + fik,其中 0 ≤ fik ＜ 1
例如：若 b = 2.35,则 N = 2,f = 0.35；
若 b = -1.45,则 N = -2,f = 0.55
13
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
构造切割方程的步骤：
2、将（ 2 式）代入（ 1 式）得：
xi + ∑ Nik xk - Ni = fi - ∑ fik xk …………………… （ 3 式）
3、提出变量为整（当然含非负）的条件：
由于（ 3 式）中等式左边需整，而 0 ＜ fi ＜ 1,故有
fi - ∑ fik xk ≤ 0 …………………… （ 4 式）
此即为所需切割方程。
14
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
构造切割方程的步骤：
（ 1）切割方程 fi - ∑ fik xk ≤ 0 真正进行了切割，至少把非整数最优解这一点切割掉了。
证明：（反证法）假设松驰问题的最优解 X* 未被切割掉，则由
fi - ∑ fik x*k ≤ 0,又因为 x*k = 0，（因 x*k 为非基变量）
有 fi ≤ 0,这与 fi ＞ 0 矛盾。
（ 2）不会切割掉任何整数解，因为切割方程是由变量为整的条件提出的。
15
整数规划 Integer Programming（ IP）
整数规划问题的求解方法割平面法 cutting plane approach
例 ——求解
IP Max Z = X1 + X2
- X1 + X2 ≤ 1
3X1 + X2 ≤ 4
X1,X2 ≥ 0
X1,X2 整数
LP Max Z = X1 + X2
- X1 + X2 ≤ 1
3X1 + X2 ≤ 4
X1,X2 ≥ 0
16
整数规划 Integer Programming（ IP）
求解步骤：
1、求解 LP 得到非整数最优解：
X =（ 3/4,7/4,0,0）,Max Z = 5/2
Cj 1 1 0 0
I 表
CB XB B –1 b X1 X2 X3 X4
0 X3 1 - 1 1 1 0
0 X4 4 3 1 0 1
j 0 1 1 0 0
B 表
1 X1 3/4 1 0 -1/4 1/4
1 X2 7/4 0 1 3/4 1/4
j - 5/2 0 0 - 1/2 - 1/2
17
整数规划 Integer Programming（ IP）
求解步骤：
2、构造切割方程：
由 B 表 中的第 2 个方程 ——
X2 + 3/4 X3 + 1/4 X4 = 7/4
有 b2 = 7/4 = 1 + 3/4
a23 = 3/4 = 0 + 3/4,a24 = 1/4 = 0 + 1/4
因此，切割方程为 ——
3/4 – 3/4 X3 – 1/4 X4 ≤ 0
增加松弛变量 X5,并将如下方程的约束条件添加到 B 表中。
- 3 X3 - 1 X4 + X5 = - 3
X5 ≥ 0
18
整数规划 Integer Programming（ IP）
求解步骤：
3、求解新的松弛问题
Cj 1 1 0 0 0
B 表
CB XB B –1 b X1 X2 X3 X4 X5
1 X1 3/4 1 0 -1/4 1/4 0
1 X2 7/4 0 1 3/4 1/4 0
0 X5 - 3 0 0 - 3 - 1 1
j - 5/2 0 0 - 1/2 - 1/2 0
新
B 表
1 X1 1 1 0 0 1/3 - 1/12
1 X2 1 0 1 0 0 1/4
0 X3 1 0 0 1 1/3 - 1/3
j - 2 0 0 0 - 1/3 - 1/6
19
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用
0-1变量作为逻辑变量（ Logical variable），常常被引用来表示系统是否处于某个特定的状态，或者决策变量是否取某个特定的方案。如
xj = 1 当决策取方案 P j 时0 当决策不取方案 P
j 时
20
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用例 1 选址问题某公司在城市的东、西、南三区建立门市部。拟议 中有 7 个位置（地点） Ai（ i=1,2,…,7）可供选择。公司规定在东区，由 A1,A2,A3 三个点中至多选两个；
在南区，由 A4,A5 两个点中至少选一个；
在西区，由 A6,A7 两个点中至少选一个。
如果选用 Ai 点，设备投资估计为 bi 元，每年可获利润估计为
ci 元，但投资总额不能超过 B 元。问公司选择哪几个点可使年总利润最大？
21
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用建立模型引入 0-1 变量 1 当 Ai 点被选用0 当 A
i 没点被选用
xi = （ i=1,2,…,7）
max z = ∑cixi
∑bixi ≤ B
x1 + x2 + x3 ≤ 2
x4 + x5 ≥ 1
x6 + x7 ≥ 1
xi = 0，或 1
22
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用例 7 应用 0-1 变量解决含互斥约束条件问题设：工序 B 有两种方式完成方式（ 1 ）的工时约束为 0.3X1 + 0.5X2 ≤ 150
方式（ 2 ）的工时约束为 0.2X1 + 0.4X2 ≤ 120
问题是完成工序 B 只能从两种方式中任选一种，如何将这两个互斥的约束条件统一在一个线性规划模型中呢？
23
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用例 7 应用 0-1 变量解决含互斥约束条件问题引入 0-1 变量
y1 = 0 若工序 B 采用方式（ 1 ）完成
1 若工序 B 不采用方式（ 1 ）完成
y2 = 0 若工序 B 采用方式（ 2 ）完成
1 若工序 B 不采用方式（ 2 ）完成
24
整数规划 Integer Programming（ IP）
0-1整数规划问题
0-1 变量及其应用例 7 应用 0-1 变量解决含互斥约束条件问题于是前面两个互斥的约束条件可以统一为如下三个约束条件：
0.3X1 + 0.5X2 ≤ 150 + M1y1
0.2X1 + 0.4X2 ≤ 120 + M2y2
y1 + y2 = 1
其中 M1,M2 都是足够大的正数。
25
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
指派问题的标准形式及其数学模型指派问题的标准形式（以人和事为例）是：
有 n 个人和 n 件事，已知第 i 人做第 j 事的费用为 Cij（ i,j =
1,2,…,n），要求确定人和事之间的一一对应的指派方案，使完成这件事的总费用最少。如任务人员 A B C D
甲乙丙丁
2
10
9
7
15
4
14
8
13
14
16
11
4
15
13
9
26
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
指派问题的标准形式及其数学模型指派问题的标准形式，令
1 当指派第 i 人完成第 j 项任务
0 当不指派第 i 人完成第 j 项任务xij =
min z = ∑∑cijxij
∑xij = 1,j = 1,2,…,n
∑xij = 1,i = 1,2,…,n
xij = 1 或 0
27
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法标准的指派问题是一类特殊的 0-1 整数规划问题，可以用多种相应的解法来求解。但是，这些方法都没有充分利用指派问题的特殊性质来有效减少计算量。 1955年，库恩（ W.W.Kuhn）利用匈牙利数学家康尼格（ D.K?nig）的关于矩阵中独立零元素的定理，提出了指派问题的一种解法，由此，习惯上称之为匈牙利解法。
28
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法匈牙利解法的关键是利用了指派问题最优解的如下性质：
若从指派问题的系数矩阵 C = （ cij ） n× n 的某行（或某列）
各元素分别 减去一个常数 k，得到一个新的系数矩阵 C’ = （ c’ij ）
则以 C 和 C’ 为系数矩阵的两个指派问题有 相同的最优解 。
29
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤步骤一,变换系数矩阵。使其每行及每列至少有一个零元素，同时不出现负元素。
步骤二,进行试指派，即确定独立零元素。
步骤三,继续变换系数矩阵，然后返回步骤二。
30
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤以上例说明步骤
2 15 13 4
10 4 14 15
9 14 16 13
7 8 11 9
0 13 11 2
6 0 10 11
0 5 7 4
0 1 4 2
2
4
9
7
min
（ cij ） =
31
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤以上例说明步骤
0 13 11 2
6 0 10 11
0 4 7 4
0 1 4 2
0 0 4 2min
0 13 7 0
6 0 6 9
0 5 3 2
0 1 0 0
= （ c’ij ）
32
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤以上例说明步骤
0 13 7 0
6 0 6 9
0 5 3 2
0 1 0 0
此时加圈 0 元素的个数 m = n = 4，所以得到最优解
33
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤以上例说明步骤
0 0 0 1
0 1 0 0
1 0 0 0
0 0 1 0
（ xij ） =
34
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤例任务人员 A B C D E
甲乙丙丁戊
12
8
7
15
4
7
9
17
14
10
9
6
12
6
7
7
6
14
6
10
9
6
9
10
9
35
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
12 7 9 7 9
8 9 6 6 6
7 17 12 14 9
15 14 6 6 10
4 10 7 10 9
7
6
7
6
4
5 0 2 0 2
2 3 0 0 0
0 10 5 7 2
9 8 0 0 4
0 6 3 6 5
36
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
5 0 2 0 2
2 3 0 0 0
0 10 5 7 2
9 8 0 0 4
0 6 3 6 5
此时加圈 0 元素的个数
m = 4,而 n = 5，所以解题没有完成。独立零元素（加圈零元素）少于 n 个，表示还不能确定最优 指派方案。此时需确定能覆盖所有 零元素的最少直线数目的直线集合。方法如下：
37
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
1) 对没有加圈零元素的行打 √号；
2) 对所有打 √号行的所有含零元素的列打 √号；
3) 再对已打 √号的列中含零元素的行打 √号；
4) 重复 2）和 3），直到再也不能找到可以打 √号行或列为止；
5) 对没有打 √号的行画一横线，对打 √号的列画一竖线，这样就得到 能覆盖所有 零元素的最少直线数目的直线集合。
38
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
5 0 2 0 2
2 3 0 0 0
0 10 5 7 2
9 8 0 0 4
0 6 3 6 5 √
√
√
39
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤继续变换系数矩阵。其方法是在未被直线覆盖的元素中找出一个最小元素。然后在打 √号 行 各元素都 减 去这一最小元素，而在 打 √
号 列 的各 元素都 加 上这一最小元素，以保证原来的 0 元素不变。
这样得到新系数矩阵（其最优解和原问题相同）。若得到 n 个独立的 0 元素，则已得最优解，否则重复该步骤继续变换系数矩阵。
40
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
5 0 2 0 2
2 3 0 0 0
0 10 5 7 2
9 8 0 0 4
0 6 3 6 5 √
√
√
最小元素 = 2
7 0 2 0 2
4 3 0 0 0
0 8 3 5 0
11 8 0 0 4
0 4 1 4 3
41
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
7 0 2 0 2
4 3 0 0 0
0 8 3 5 0
11 8 0 0 4
0 4 1 4 3
此时加圈 0 元素的个数
m = 5,而 n = 5，独立零元素
（加圈零元素）等于 n 个,此时已得到最优解，其解矩阵为
42
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
匈牙利解法的一般步骤
（ xij ） =
0 1 0 0 0
0 0 1 0 0
0 0 0 0 1
0 0 0 1 0
1 0 0 0 0
最优指派：
甲 —— B
乙 —— C
丙 —— E
丁 —— D
戊 —— A
43
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
非标准形式的指派问题在实际应用中，常会遇到各种非标准形式的制派问题。一般的处理方法是先将其转化为标准形式，然后再用匈牙利法求解。
1,最大化指派问题 ——设最大化指派问题系数矩阵 C = （ cij ）,
其中最大元素为 m 。令矩阵 B = （ bij ） = （ m - cij ），则以 B 为系数矩阵的最小化指派问题和以 C 为系数矩阵的最大化指派问题有相同最优解。
2,人数和事数不等的指派问题 ——若 人少事多,则添加一些虚拟的“人”，其费用系数取 0,若 人多事少,则添加一些虚拟的
“事”，其费用系数取 0 。
44
整数规划 Integer Programming（ IP）
指派问题（ assignment problem）
非标准形式的指派问题
3,一个人可做几件事的指派问题 ——若某个人可以做几件事，则将该人化作几个“人”来接受指派。这几个“人”做同一件事的费用系数当然都一样。
4,某事一定不能由某人做的指派问题 ——若某事一定不能由某人做，则可将相应的费用系数取为足够大的数 M 。
45
整数规划 Integer Programming（ IP）
第五章结束谢谢！
