分支定界法
什么是三角形-led显示屏报价
2023年2月21日发(作者：国内免费b2b网站大全)分支定界法原理简介
分支定界法是一种广义搜索算法，人工使用非常繁琐，但由于计算机的运
算速度快的特点，这种算法十分适合计算机进行。分支定界法是计算机最擅长
的广义搜索穷举算法。
基本思想：
1.松弛模型的最优解要优于其相应的整数规划的解
由于松弛模型可行解的区域（多边形）包含了对应的整数规划的可行解的集
合（多边形内的整数点），因而松弛模型的解要优于整数规划的解。这就是说，
如果问题是求最大值的，则松弛模型最优解对应的目标函数值必大于或等于整数
规划最优解对应的目标函数值；如果问题是求最小值的，则松弛模型的最优解对
应的目标函数值必小于或等于整数规划最优解对应的目标函数值。由此可以推
出：
2.松弛模型的最优解如果是整数解，则必然也是整数规划的最优解。
3.松弛模型的最优解如果不是整数解，则如果问题是求最大值的，松弛模
型最优解的目标函数值是整数规划最优解目标函数值的一个上界；如果问题是求
最小值的，则松弛模型最优解的目标函数值是整数规划最优解目标函数值的一个
下界。
我们用例子来说明用分支定界法求解整数规划的步骤。
例求下面整数规划的最优解
12
12
12
12
12
max4090
s.t.9756
72070
,0
x,
Zxx
xx
xx
xx
x
=+
+≤
+≤
≥
为整数
解从上述各约束条件可见，是一个可行解，对应的松弛模型目标函
数值。本问题是一个求最大值的问题，因而整数规划最优解的目标函数的
下界可以取为0，即取整数规划模型最优值的下界
(0,0)
0Z=
0Z=
。
先考虑此整数规划问题的线性松弛模型0：
其解为
松弛模型0
0
1
2
356
4.81
1.82
Z
x
x
=
=
=
由于松弛模型解的目标函数值是整数规划模型最优值的一个上界，可以取此
处的
0
Z
为整数规划模型最优值的一个上界
356Z=
。由于该松弛模型解不是整数
解，分原问题为和两个子模型：子模型
1和子模型2。
1
4x≤
1
5x≥
1
子模型1子模型2
1
4≤x
1
5≥x
1
1
2
349
4.00
2.10
Z
x
x
=
=
=
2
1
2
349
5.00
1.57
Z
x
x
=
=
=
子模型1的形式：
12
12
12
1
12
max4090
s.t.9756
72070
4
x,0
Zxx
xx
xx
x
x
=+
+≤
+≤
≤
≥
子模型2的形式：
12
12
12
1
12
max4090
s.t.9756
72070
5
x,0
Zxx
xx
xx
x
x
=+
+≤
+≤
≥
≥
所求整数规划模型的最优值不会超过这两个子模型的最优值中大的那个，即
349。这个值小于原来的上界
356Z=
，因而可以改取整数规划模型最优值的上
界为
349Z=
。
由于子模型1和子模型2的解中
2
x
都不是整数，我们按
2
x
最接近的整数分
别分解子模型1为子模型3、子模型4；分解子模型2为子模型5、子模型6（具
体形式略）。分别求解，得
子模型3子模型4子模型5子模型6
2
2≤x
2
3≥x
2
1≤x
2
2≥x
3
1
2
340
4.00
2.00
Z
x
x
=
=
=
4
1
2
327
1.42
3.00
Z
x
x
=
=
=
5
1
2
308
5.44
1.00
Z
x
x
=
=
=
无可行解
因为子模型3有整数解，因而所求整数规划的最优值不会比这个值更差。我
们可以改记目标函数值的下界为
340Z=
。子模型4、子模型5在不考虑整数的
2
情况下最优（大）值都小于340，在整数约束下的最优值更要小于340，所以尽
管这两个子模型的解不是整数，我们也不再继续分支，即剪去这两支。子模型6
无解。因而最优解就是，对应的最优值为
12
4,2xx==340Z=
。
我们把上述应用分支定界法求解整数规划的过程用下面的图表示出来：
3