管理运筹学谢家平 博士 副教授研究领域,系统建模与优化、生产与运作管理、物流与供应链管理讲授课程,管理运筹学、管理系统工程、生产运作管理、
供应链管理、国际物流管理、企业资源计划单 位,上海财经大学 国际工商管理学院 供应链管理研究中心
E-mail,jiaping_xie@sina.com.cn
电 话,55036936(H) 65903541(O)
上海财经大学 国际工商管理学院
SHUFE
2
第 6章 整数规划
线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。
例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。
要求全部或部分决策变量的取值为整数的线性规划问题，
称为整数线性规划，简称整数规划 (Integer
Programming)。
全部决策变量的取值都为整数，则称为全整数规划 (All IP)；
仅要求部分决策变量的取值为整数，则称为混合整数规划
(Mixed IP)；
要求决策变量只能取 0或 1值，则称为 0-1规划 (0-1
Programming)。
上海财经大学 国际工商管理学院
SHUFE
3
第一节 整数规划问题
为了满足整数要求，似乎可以把线性规划的小数最优解进行,舍入化整,以得到与最优解相近的整数解。
,舍入化整,一般是不可行的：
化整后的解有可能成为 非可行解 ；
虽是可行解，却 不是最优解 。
例如一、问题的提出产品资源 甲 乙 现有量
A 2 1 9
B 5 7 35
单台利润 6 3
问如何安排甲、乙两产品的产量，使利润为最大。
上海财经大学 国际工商管理学院
SHUFE
4
第一节 整数规划问题
解,设 x1为甲产品的台数,x2为乙产品的台数。
maxZ= 6x1 +5 x2
2x1 + x2 ≤9
5x1 +7 x2 ≤35
x1,x2 ≥0
x1,x2取整数
不考虑整数约束则是一个 LP问题,称为原整数规划的松弛问题。
不考虑整数约束的最优解,x1 *=28/9,x2 * =25/9,Z * =293/9
舍入化整
x1 =3,x2 =3,Z =33，不满足约束条件 5x1 +7 x2 ≤35，非可行解；
x1 =3,x2 =2,Z =28，满足约束条件，是可行解，但不是最优解；
x1 =4,x2 =1,Z =29，满足约束条件，才是最优解。
上海财经大学 国际工商管理学院
SHUFE
5
步骤：
在线性规划的可行域内列出所有决策变量可能取的整数值，
求出这些变量所有可行的整数解，
比较它们相应的目标函数值，最优的目标函数值所对应的解就是整数规划的最优解。
实用性：
只有两个决策变量，
可行的整数解较少。
5x1 +7 x2 =35
2x1 + x2 =9
(3,3)
第一节 整数规划问题二,整数规划的图解法
x1
x2
1 2 3
1
2
5
3
4
4
)972,913(
上海财经大学 国际工商管理学院
SHUFE
6
第一节 整数规划问题
设备购置问题,某厂拟用 M元资金购买 m种设备，设备 i 的单价为 pi；现有 n个地点可装置这些设备，第 j 处最多可装置 bj 台；设备 i
装置在 j 处可获利 cij元。如何购置，总利润最大？
假设,购买第 i 种设备 yi台数，将第 i 种设备安装在第 j 处的台数 xij
该问题的数学模型三,整数规划问题举例为整数
iij
iij
m
i
ii
m
i
jij
n
j
iij
m
i
n
j
ijij
yx
yx
Myp
njbx
miyx
xcZ
,
0,
,.,,,2,1
,.,,,2,10
m ax
1
1
1
1 1
上海财经大学 国际工商管理学院
SHUFE
7
第一节 整数规划问题
投资决策问题,某厂拟用 b元资金投资 n个项目，项目 j 需资金 aj
元，可获利 cj元。应选择那些项目，获利最大？
假设,xj =1表示投资项目 j ； xj =0表示不投资项目 j
该问题的数学模型
njx
bxa
xcZ
j
n
j
jj
n
j
jj
,...,2,1,01
m ax
1
1
或上海财经大学 国际工商管理学院
SHUFE
8
第一节 整数规划问题
工厂选址问题,某商品有 n个销地，各销地的需求量为 bj吨 /天；
现拟在 m个地点中选址建生产厂，一个地方最多只能建一个工厂；
若选 i 地建厂，生产能力为 ai吨 /天，固定费用为 di元 /天；已知 i 址至销地 j 的运价为 cij元 /吨。如何选址和安排调运，总费用最小？
假设,yi=1，选择第 i 址建厂,yi=0，不选择第 i 址建厂；从厂址 i
至销地 j 运量为 xij 。
该问题的数学模型
01
0
,.,,,2,1
,.,,,2,1
m i n
1
1
11 1
或整数约束：
非负约束：
需求约束：
能力约束：
i
ij
j
m
i
ij
ii
n
j
ij
m
i
ii
m
i
n
j
ijij
y
x
njbx
miyax
ydxcZ
上海财经大学 国际工商管理学院
SHUFE
9
第二节 分枝定界法
分枝定界法 (Branch and Bound Method)
基本思想：
先求出整数规划相应的 LP(即不考虑整数限制 )的最优解,
若求得的最优解符合整数要求,则是原 IP的最优解；
若不满足整数条件,则任选一个不满足整数条件的变量来构造新的约束,在原可行域中剔除部分非整数解 。
然后,再在缩小的可行域中求解新构造的线性规划的最优解,这样通过求解一系列线性规划问题,最终得到原整数规划的最优解 。
上海财经大学 国际工商管理学院
SHUFE
10
第二节 分枝定界法
定界的含义：
整数规划是在相应的线性规划的基础上增加变量为整数的约束条件，整数规划的最优解不会优于相应线性规划的最优解。
对极大化问题来说，相应线性规划的目标函数最优值是原整数规划函数值的上界；
对极小化问题来说，相应线性规划的目标函数的最优值是原整数规划目标函数值的下界。
上海财经大学 国际工商管理学院
SHUFE
11
第二节 分枝定界法例 maxZ= 6x1 +5 x2
2x1 + x2 ≤9
5x1 +7 x2 ≤35
x1,x2 ≥0
x1,x2取整数
第一步,不考虑变量的整数约束,求相应 LP(问题 1)的最优解：
x1=28/9,x2 =25/9,Z1=293/9
第二步,定界过程
这个解不满足整数约束,这时目标函值 Z1是整数规划的目标上界；
因为 x1=x2=0是整数规划问题的可行解,所以下界为 0。
第三步,分枝过程将不 满足整数约束的变量 x1进行分枝,x1称为分枝变量,构造两个新的约束条件：
x1≤ [28/9]=3,x1 ≥ [28/9] +1=4
上海财经大学 国际工商管理学院
SHUFE
12
第二节 分枝定界法这样就把相应的线性规划的可行域分成两个部分，如图所示。
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1 2 3
1
2
5
3
4
4
x1=3 x1=4
问题 2,maxZ= 6x1 +5 x2 问题 3,maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≥4
x1,x2 ≥0 x1,x2 ≥0
x1,x2取整数 x1,x2取整数上海财经大学 国际工商管理学院
SHUFE
13
第二节 分枝定界法
求解相应的线性规划的最优解
问题 2相应的线性规划的最优解,x1=3,x2 =20/7,Z2=226/7
问题 3相应的线性规划的最优解,x1=4,x2 =1,Z3=29
第四步，定界过程
LP3的解满足整数约束，不必再分枝，它的目标函数值是 29，
大于原有下界 0，则新的下界为 29；
现有上界为未分枝子问题中目标函数最大值，即为 226/7。
LP2的解仍不满足整数约束的要求，它的目标函数值 226/7大于现有下界，则应继续分枝。
第五步,分枝过程将不 满足整数约束的变量 x2进行分枝,构造两个新的约束条件：
x2≤ [20/7]=2,x2 ≥ [20/7] +1=3
上海财经大学 国际工商管理学院
SHUFE
14
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1 2 3
1
2
5
3
4
4
x1=4x1=3
第二节 分枝定界法问题 4,maxZ= 6x1 +5 x2 问题 5,maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≤ 3
x2≤2 x2 ≥3
x1,x2 ≥0 x1,x2 ≥0
x1,x2取整数 x1,x2取整数
x2 =2
x2=3
上海财经大学 国际工商管理学院
SHUFE
15
第二节 分枝定界法
求解相应的线性规划的最优解
问题 4相应的线性规划的最优解,x1=3,x2 =2,Z4=28
问题 5相应的线性规划的最优解,x1=14/5,x2 =3,Z5=159/5
第六步，定界过程
LP4的解满足整数约束，不必再分枝，它的目标函数值是 28，
小于原有下界 29，则下界仍为 29；
现有上界为未分枝子问题中目标函数最大值，即为 159/5。
LP5的解仍不满足整数约束的要求，它的目标函数值 159/5大于现有下界 29，则应继续分枝。
第七步,分枝过程将不 满足整数约束的变量 x1进行分枝,构造两个新的约束条件：
x1≤ [14/5]=2,x1≥ [14/5] +1=3
上海财经大学 国际工商管理学院
SHUFE
16
第二节 分枝定界法问题 6,maxZ= 6x1 +5 x2 问题 7,maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≤3
x2 ≥3 x2 ≥3
x1≤2 x1 ≥ 3
x1,x2 ≥0 x1,x2 ≥0
x1,x2取整数 x1,x2取整数
x2 =2
x2=3
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1 2 3
1
2
5
3
4
4
x1=4x1=3x
1=2
上海财经大学 国际工商管理学院
SHUFE
17
第二节 分枝定界法
求解相应的线性规划的最优解：
问题 6相应的线性规划的最优解,x1=2,x2 =25/7,Z6=209/7
问题 7相应的线性规划的最优解,无最优解
第八步，定界过程
LP7的无最优解，不必再分枝，下界仍为 29；
现有上界为未分枝子问题中目标函数最大值，即为 209/7。
LP6的解仍不满足整数约束的要求，它的目标函数值 209/7大于现有下界 29，则应继续分枝。
第九步,分枝过程将不 满足整数约束的变量 x2进行分枝,构造两个新的约束条件：
x2≤ 3,x2≥ 4
上海财经大学 国际工商管理学院
SHUFE
18
第二节 分枝定界法问题 8,maxZ= 6x1 +5 x2 问题 9,maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≤3
x2 ≥3 x2 ≥3
x1≤2 x1≤2
x2≤3 x2 ≥4
x1,x2 ≥0 x1,x2 ≥0
x1,x2取整数 x1,x2取整数
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1 2 3
1
2
5
3
4
4
x1=4x1=3
x2=3
x1=2
x2 =2
x2 =4
上海财经大学 国际工商管理学院
SHUFE
19
第二节 分枝定界法
求解相应的线性规划的最优解
问题 8相应的线性规划的最优解,x1=2,x2 =3,Z8=27
问题 9相应的线性规划的最优解,x1=7/5,x2 =4,Z9=142/5
第十步，定界过程
LP8的最优解，满足整数约束，不必再分枝，下界仍为 29；
现有上界为未分枝子问题中目标函数最大值，即为 29。
虽然 LP9的解仍不满足整数约束的要求，它的目标函数值 142/5
小于现有下界 29，则不再继续分枝。
上界 =下界，得整数规划问题的最优解：
x1=4,x2 =1,Z=29
上海财经大学 国际工商管理学院
SHUFE
20
分枝定界过程
7
232,
7
62,3
2
21 Zxx
：问题
9
532,
9
72,
9
13
1
21 Zxx
：问题
29,1,4
3
21 Zxx
：问题
28,2,3
4
21 Zxx
：问题
5
431,3,
5
42
5
21 Zxx
：问题
7
629,
7
43,2
6
21 Zxx
：问题无可行解
：问题 7
27,3,2 821 Zxx,问题
5
228,4,
5
21
9
21 Zxx
：问题
x1≤3 x1 ≥4
x2≤2 x2 ≥3
x1≤2 x1 ≥3
x2≤3 x2 ≥4
0
9
532
下界：
上界：
29
7
232
下界：
上界：
29
5
431
下界：
上界：
29
7
629
下界：
上界：
2929下界：上界：
第二节 分枝定界法
供应链管理、国际物流管理、企业资源计划单 位,上海财经大学 国际工商管理学院 供应链管理研究中心
E-mail,jiaping_xie@sina.com.cn
电 话,55036936(H) 65903541(O)
上海财经大学 国际工商管理学院
SHUFE
2
第 6章 整数规划
线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。
例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。
要求全部或部分决策变量的取值为整数的线性规划问题，
称为整数线性规划，简称整数规划 (Integer
Programming)。
全部决策变量的取值都为整数，则称为全整数规划 (All IP)；
仅要求部分决策变量的取值为整数，则称为混合整数规划
(Mixed IP)；
要求决策变量只能取 0或 1值，则称为 0-1规划 (0-1
Programming)。
上海财经大学 国际工商管理学院
SHUFE
3
第一节 整数规划问题
为了满足整数要求，似乎可以把线性规划的小数最优解进行,舍入化整,以得到与最优解相近的整数解。
,舍入化整,一般是不可行的：
化整后的解有可能成为 非可行解 ；
虽是可行解，却 不是最优解 。
例如一、问题的提出产品资源 甲 乙 现有量
A 2 1 9
B 5 7 35
单台利润 6 3
问如何安排甲、乙两产品的产量，使利润为最大。
上海财经大学 国际工商管理学院
SHUFE
4
第一节 整数规划问题
解,设 x1为甲产品的台数,x2为乙产品的台数。
maxZ= 6x1 +5 x2
2x1 + x2 ≤9
5x1 +7 x2 ≤35
x1,x2 ≥0
x1,x2取整数
不考虑整数约束则是一个 LP问题,称为原整数规划的松弛问题。
不考虑整数约束的最优解,x1 *=28/9,x2 * =25/9,Z * =293/9
舍入化整
x1 =3,x2 =3,Z =33，不满足约束条件 5x1 +7 x2 ≤35，非可行解；
x1 =3,x2 =2,Z =28，满足约束条件，是可行解，但不是最优解；
x1 =4,x2 =1,Z =29，满足约束条件，才是最优解。
上海财经大学 国际工商管理学院
SHUFE
5
步骤：
在线性规划的可行域内列出所有决策变量可能取的整数值，
求出这些变量所有可行的整数解，
比较它们相应的目标函数值，最优的目标函数值所对应的解就是整数规划的最优解。
实用性：
只有两个决策变量，
可行的整数解较少。
5x1 +7 x2 =35
2x1 + x2 =9
(3,3)
第一节 整数规划问题二,整数规划的图解法
x1
x2
1 2 3
1
2
5
3
4
4
)972,913(
上海财经大学 国际工商管理学院
SHUFE
6
第一节 整数规划问题
设备购置问题,某厂拟用 M元资金购买 m种设备，设备 i 的单价为 pi；现有 n个地点可装置这些设备，第 j 处最多可装置 bj 台；设备 i
装置在 j 处可获利 cij元。如何购置，总利润最大？
假设,购买第 i 种设备 yi台数，将第 i 种设备安装在第 j 处的台数 xij
该问题的数学模型三,整数规划问题举例为整数
iij
iij
m
i
ii
m
i
jij
n
j
iij
m
i
n
j
ijij
yx
yx
Myp
njbx
miyx
xcZ
,
0,
,.,,,2,1
,.,,,2,10
m ax
1
1
1
1 1
上海财经大学 国际工商管理学院
SHUFE
7
第一节 整数规划问题
投资决策问题,某厂拟用 b元资金投资 n个项目，项目 j 需资金 aj
元，可获利 cj元。应选择那些项目，获利最大？
假设,xj =1表示投资项目 j ； xj =0表示不投资项目 j
该问题的数学模型
njx
bxa
xcZ
j
n
j
jj
n
j
jj
,...,2,1,01
m ax
1
1
或上海财经大学 国际工商管理学院
SHUFE
8
第一节 整数规划问题
工厂选址问题,某商品有 n个销地，各销地的需求量为 bj吨 /天；
现拟在 m个地点中选址建生产厂，一个地方最多只能建一个工厂；
若选 i 地建厂，生产能力为 ai吨 /天，固定费用为 di元 /天；已知 i 址至销地 j 的运价为 cij元 /吨。如何选址和安排调运，总费用最小？
假设,yi=1，选择第 i 址建厂,yi=0，不选择第 i 址建厂；从厂址 i
至销地 j 运量为 xij 。
该问题的数学模型
01
0
,.,,,2,1
,.,,,2,1
m i n
1
1
11 1
或整数约束：
非负约束：
需求约束：
能力约束：
i
ij
j
m
i
ij
ii
n
j
ij
m
i
ii
m
i
n
j
ijij
y
x
njbx
miyax
ydxcZ
上海财经大学 国际工商管理学院
SHUFE
9
第二节 分枝定界法
分枝定界法 (Branch and Bound Method)
基本思想：
先求出整数规划相应的 LP(即不考虑整数限制 )的最优解,
若求得的最优解符合整数要求,则是原 IP的最优解；
若不满足整数条件,则任选一个不满足整数条件的变量来构造新的约束,在原可行域中剔除部分非整数解 。
然后,再在缩小的可行域中求解新构造的线性规划的最优解,这样通过求解一系列线性规划问题,最终得到原整数规划的最优解 。
上海财经大学 国际工商管理学院
SHUFE
10
第二节 分枝定界法
定界的含义：
整数规划是在相应的线性规划的基础上增加变量为整数的约束条件，整数规划的最优解不会优于相应线性规划的最优解。
对极大化问题来说，相应线性规划的目标函数最优值是原整数规划函数值的上界；
对极小化问题来说，相应线性规划的目标函数的最优值是原整数规划目标函数值的下界。
上海财经大学 国际工商管理学院
SHUFE
11
第二节 分枝定界法例 maxZ= 6x1 +5 x2
2x1 + x2 ≤9
5x1 +7 x2 ≤35
x1,x2 ≥0
x1,x2取整数
第一步,不考虑变量的整数约束,求相应 LP(问题 1)的最优解：
x1=28/9,x2 =25/9,Z1=293/9
第二步,定界过程
这个解不满足整数约束,这时目标函值 Z1是整数规划的目标上界；
因为 x1=x2=0是整数规划问题的可行解,所以下界为 0。
第三步,分枝过程将不 满足整数约束的变量 x1进行分枝,x1称为分枝变量,构造两个新的约束条件：
x1≤ [28/9]=3,x1 ≥ [28/9] +1=4
上海财经大学 国际工商管理学院
SHUFE
12
第二节 分枝定界法这样就把相应的线性规划的可行域分成两个部分，如图所示。
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1 2 3
1
2
5
3
4
4
x1=3 x1=4
问题 2,maxZ= 6x1 +5 x2 问题 3,maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≥4
x1,x2 ≥0 x1,x2 ≥0
x1,x2取整数 x1,x2取整数上海财经大学 国际工商管理学院
SHUFE
13
第二节 分枝定界法
求解相应的线性规划的最优解
问题 2相应的线性规划的最优解,x1=3,x2 =20/7,Z2=226/7
问题 3相应的线性规划的最优解,x1=4,x2 =1,Z3=29
第四步，定界过程
LP3的解满足整数约束，不必再分枝，它的目标函数值是 29，
大于原有下界 0，则新的下界为 29；
现有上界为未分枝子问题中目标函数最大值，即为 226/7。
LP2的解仍不满足整数约束的要求，它的目标函数值 226/7大于现有下界，则应继续分枝。
第五步,分枝过程将不 满足整数约束的变量 x2进行分枝,构造两个新的约束条件：
x2≤ [20/7]=2,x2 ≥ [20/7] +1=3
上海财经大学 国际工商管理学院
SHUFE
14
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1 2 3
1
2
5
3
4
4
x1=4x1=3
第二节 分枝定界法问题 4,maxZ= 6x1 +5 x2 问题 5,maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≤ 3
x2≤2 x2 ≥3
x1,x2 ≥0 x1,x2 ≥0
x1,x2取整数 x1,x2取整数
x2 =2
x2=3
上海财经大学 国际工商管理学院
SHUFE
15
第二节 分枝定界法
求解相应的线性规划的最优解
问题 4相应的线性规划的最优解,x1=3,x2 =2,Z4=28
问题 5相应的线性规划的最优解,x1=14/5,x2 =3,Z5=159/5
第六步，定界过程
LP4的解满足整数约束，不必再分枝，它的目标函数值是 28，
小于原有下界 29，则下界仍为 29；
现有上界为未分枝子问题中目标函数最大值，即为 159/5。
LP5的解仍不满足整数约束的要求，它的目标函数值 159/5大于现有下界 29，则应继续分枝。
第七步,分枝过程将不 满足整数约束的变量 x1进行分枝,构造两个新的约束条件：
x1≤ [14/5]=2,x1≥ [14/5] +1=3
上海财经大学 国际工商管理学院
SHUFE
16
第二节 分枝定界法问题 6,maxZ= 6x1 +5 x2 问题 7,maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≤3
x2 ≥3 x2 ≥3
x1≤2 x1 ≥ 3
x1,x2 ≥0 x1,x2 ≥0
x1,x2取整数 x1,x2取整数
x2 =2
x2=3
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1 2 3
1
2
5
3
4
4
x1=4x1=3x
1=2
上海财经大学 国际工商管理学院
SHUFE
17
第二节 分枝定界法
求解相应的线性规划的最优解：
问题 6相应的线性规划的最优解,x1=2,x2 =25/7,Z6=209/7
问题 7相应的线性规划的最优解,无最优解
第八步，定界过程
LP7的无最优解，不必再分枝，下界仍为 29；
现有上界为未分枝子问题中目标函数最大值，即为 209/7。
LP6的解仍不满足整数约束的要求，它的目标函数值 209/7大于现有下界 29，则应继续分枝。
第九步,分枝过程将不 满足整数约束的变量 x2进行分枝,构造两个新的约束条件：
x2≤ 3,x2≥ 4
上海财经大学 国际工商管理学院
SHUFE
18
第二节 分枝定界法问题 8,maxZ= 6x1 +5 x2 问题 9,maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≤3
x2 ≥3 x2 ≥3
x1≤2 x1≤2
x2≤3 x2 ≥4
x1,x2 ≥0 x1,x2 ≥0
x1,x2取整数 x1,x2取整数
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1 2 3
1
2
5
3
4
4
x1=4x1=3
x2=3
x1=2
x2 =2
x2 =4
上海财经大学 国际工商管理学院
SHUFE
19
第二节 分枝定界法
求解相应的线性规划的最优解
问题 8相应的线性规划的最优解,x1=2,x2 =3,Z8=27
问题 9相应的线性规划的最优解,x1=7/5,x2 =4,Z9=142/5
第十步，定界过程
LP8的最优解，满足整数约束，不必再分枝，下界仍为 29；
现有上界为未分枝子问题中目标函数最大值，即为 29。
虽然 LP9的解仍不满足整数约束的要求，它的目标函数值 142/5
小于现有下界 29，则不再继续分枝。
上界 =下界，得整数规划问题的最优解：
x1=4,x2 =1,Z=29
上海财经大学 国际工商管理学院
SHUFE
20
分枝定界过程
7
232,
7
62,3
2
21 Zxx
：问题
9
532,
9
72,
9
13
1
21 Zxx
：问题
29,1,4
3
21 Zxx
：问题
28,2,3
4
21 Zxx
：问题
5
431,3,
5
42
5
21 Zxx
：问题
7
629,
7
43,2
6
21 Zxx
：问题无可行解
：问题 7
27,3,2 821 Zxx,问题
5
228,4,
5
21
9
21 Zxx
：问题
x1≤3 x1 ≥4
x2≤2 x2 ≥3
x1≤2 x1 ≥3
x2≤3 x2 ≥4
0
9
532
下界：
上界：
29
7
232
下界：
上界：
29
5
431
下界：
上界：
29
7
629
下界：
上界：
2929下界：上界：
第二节 分枝定界法
