x2 6及x2 7，显然x2 7不可行，得到线性规划
A 10
x2 7不可行 B
maxZ 4x1 3x2
1.2x1 0.8x2 10
LP22 :
2x1 2.5x2 25 x1 4，x2 7
x1 , x2 0
6
LP21:X=(4.33,6),Z21=35.33
LP1
LP21
环
0’’ 1 .2 .3 .4 足 值
5 (1,0,0) -2
no
6 (1,0,1) 3
no
7 (1,1,0) 1
no
8 (1,1,1) 6
no
最优解(X2,X1,X3) =（0，1，1） Z=8 实际只计算了16次
分配问题与匈牙利法
• 指派问题的数学模型的标准形式：
设n 个人被分配去做n 件工作，规定每个人只做一件工作， 每件工作只有一个人去做。已知第i个人去做第j 件工作的效率 （ 时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij ≥0。问应 如何分配才能使总效率（ 时间或费用）最高？
设决策变量
1 指派第i个人做第j件事 xij 0 不指派第i个人做第j件事 (i, j 1,2,...,n)
分配问题与匈牙利法
• 指派问题的数学模型为：
nn
minZ
c x ij ij
i1 j1
n
xij 1
(i 1.2. .n)
j1
n
xij 1
( j 1.2. .n)
i1
x
i
j
取0或1(i
,
j
1.2.
.n)
分配问题与匈牙利法
•克尼格定理 :
例 求下列问题：
Max Z=3x1- 2x2 + 5x3
s.t. x1+2x2 - x3 2 (1)
x1+4x2 + x3 4 (2)
x1 + x2 3 (3)
4x2 + x3 6 (4)
xj 0或1
(5)
解： 容易看出(1,0,0)满足约束 条件，对应Z=3，对Max Z来说， 希望Z 3,所以增加约束条件：
x2≤6
x2≥7
LP21:X=(4.33,6) Z21=35.33
LP22 无可行解
x1≤4
x1≥5
LP211:X=(4,6) Z211=34
LP212:X=(5,5) Z212=35
小结
学习要点： • 掌握一般整数规划问题概念及模型结构 • 掌握分支定界法原理 • 能够用分支定界法求解一般整数规划问题
循 (X2,X1,X3) s.t. s.t. s.t s.t s.t 满 Z
环
0’ 1 .2 .3 .4 足 值
3 (0,1,0) 3
no
4 (0,1,1) 8 0 2 1 1 ye 8 s
改进过滤性条件Z 8 (0’’)
循 (X2,X1,X3) s.t. s.t. s.t s.t s.t 满 Z
0-1规划
隐枚举法(Implicit Enumeration)
基本上此法可以从所有变量等于零 出发（初始点），然后依次指定一些 变量取值为1，直到获得一个可行解， 于是把第一个可行解记作迄今为止最 好的可行解，再重复，依次检查变量 为0，1的各种组合，对迄今为止最好 的可行解加以改进，直到获得最优解。
C
o
34
maxZ 4x1 3x2
1.2x1 0.8x2 10
LP 21 :
2x1 2.5x2 25 x1 4，x2 6
x1 , x2 0
x1
x2
由于Z21 Z1，选择LP21进行分枝，增加约束
x1 4及x1 5，得线性规划LP211及LP212：
A 10
6 LP1
o
3
Z=3x1- 2x2 + 5x3 3 (0)
称为过滤性条件。初看起来，增 加约束条件需增加计算量，实际 减少了计算量。
最优解（1，0，1） Z=8
循环 (X1,X2,X3)
1 (0,0,0) 2 (0,0,1) 3 (0,1,0) 4 (0,1,1) 5 (1,0,0) 6 (1,0,1) 7 (1,1,0) 8 (1,1,1)
x2 A
10
1.2x1 0.8x2 10
松弛问题LP0的最优解 X=(3.57,7.14),Z0=35.7 B
2x1 2.5x2 25
C
o
10
x1
x2
增加约束x1 3及x1 4得到两个线性规划
A 10
LP1:X=(3,7.6),Z1=34.8
B
maxZ 4x1 3x2
1.2x1 0.8x2 10
s.t. s.t. s.t. s.t. s.t. 满 Z 0 1 2 3 4 足值
0
no
5 -1 1 0 1 yes 5
-2
no
3 15
no
3 1 1 1 0 yes 3
8 0 2 1 1 yes 8
1
no
6 26
no
增加约束条件（0）（Z 3)后实际做了24次运 算，而原问题需要计算 23*4=32次运算（3个变 量，4个约束条件）。
LP1
:
2x1 2.5x2 x1 3
பைடு நூலகம்
25
x1 , x2 0
LP1
LP2:X=(4,6.5),Z2=35.5
LP2
max Z 4x1 3x2
1.2x1 0.8x2 10
LP2
:
2x1 2.5x2 x1 4
25
x1 , x2 0
o
34
C
①
②
x2
选择目标值最大的分枝LP2进行分枝，增加约束
注意：
➢改进过滤性条件，在计算 过程中随时调整右边常数。
➢价值系数按递增排列。
以上两种方法可减少计算量。
循 (X2,X1,X3) s.t. s.t. s.t s.t s.t 满 Z
环
0 1 .2 .3 .4 足 值
1 (0,0,0) 0
no
2 (0,0,1) 5 -1 1 0 1 ye 5 s
改进过滤性条件Z 5 (0’)
LP212
C
45
1.2 x1 0.8 x2 10
LP212 :
2x1 2.5x2 25 x1 5，x2 6
x1 , x2 0
x1
•上述分枝过程可用下图表示：
LP0:X=(3.57,7.14),Z0=35.7
x1≤3
x1≥4
LP1:X=(3,7.6) Z1=34.8
LP2:X=(4,6.5) Z2=35.5
LP211:X=(4,6),
maxZ 4x1 3x2
Z211=34
1.2x1 0.8x2 10
LP211:
2x1 2.5x x1 4，x2
2 25 6，x1
4
LP212:X=(5,5)
x1 , x2 0
,Z212=35
即x1 4,可行域是一条线段
max Z 4x1 3x2