管 理 运 筹 学 1
第八章 整数规划
§ 1 整数规划的图解法
§ 2 整数规划的计算机求解
§ 3 整数规划的应用
§ 4 整数规划的分枝定界法
§ 5 割平面方程管 理 运 筹 学 2
第八章 整数规划
求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。
在整数规划中，如果所有的变量都为非负整数，
则称为 纯整数规划问题 ；如果有一部分变量为负整数，则称之为 混合整数规划问题 。在整数规划中，如果变量的取值只限于 0和 1，这样的变量我们称之为 0-1变量 。在纯整数规划和混合整数规划问题中，如果所有的变量都为 0-1变量，则称之为
0-1规划 。
管 理 运 筹 学 3
§ 1 整数规划的图解法例 1,某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、
重量、可获利润以及托运所受限制如表所示。
甲种货物至多托运 4件，问两种货物各托运多少件，可使获得利润最大。
解：设 x1,x2分别为 甲、乙两种货物托运的件数，建立模型目标函数,Max z = 2x1 +3 x2
约束条件,s.t,
195x1 + 273 x2 ≤1365
4 x1 + 40 x2 ≤140
x1 ≤4
x1,x2 ≥ 0 为整数。
如果去掉最后一个约束，就是一个线性规划问题。利用图解法，
货物 每件体积
（ 立方英尺 ）
每件重量
（ 百千克 ）
每件利润
（ 百元 ）
甲乙
195
273
4
40
2
3
托运限制 1365 140
管 理 运 筹 学 4
得到线性规划的最优解为 x1=2.44,x2=3.26,目标函数值为 14.66。
由图表可看出，整数规划的最优解为 x1=4,x2=2,目标函数值为 14。
性质 1,任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。
1 2 3 4
1
2
3 2x1+3x2 =14.66
x1
x2
2x1+3x2 =14
2x1+3x2 =6
§ 1 整数规划的图解法§ 1 整数规划的图解法管 理 运 筹 学 5
例 2：
Max z = 3x1 + x2 + 3x3
s.t.
-x1 + 2x2 + x3 ≤ 4
4x2 -3x3 ≤2
x1 -3x2 + 2x3 ≤3
x1,x2,x3 ≥ 0 为整数例 3：
Max z = 3x1 + x2 + 3x3
s.t.
-x1 + 2x2 + x3 ≤ 4
4x2 -3x3 ≤2
x1 -3x2 + 2x3 ≤3
x3 ≤1
x1,x2,x3 ≥ 0
x1,x3 为整数 x3 为
0-1变量用,管理运筹学,软件求解得：
x1 = 5 x2 = 2 x3 = 2
用,管理运筹学,软件求解得：
x1 = 4 x2 = 1.25 x3 = 1
z = 16.25
§ 2 整数规划的计算机求解管 理 运 筹 学 6
§ 3 整数规划的应用一、投资场所的选择例 4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有 10个位置 Aj (j＝ 1,2,3,…,10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：
在东区由 A1,A2,A3 三个点至多选择两个；
在西区由 A4,A5 两个点中至少选一个；
在南区由 A6,A7 两个点中至少选一个；
在北区由 A8,A9,A10 三个点中至少选两个。
Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元 )。但投资总额不能超过 720万元，问应选择哪几个销售点，可使年利润为最大?
A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10
投资额 100 120 150 80 70 90 80 140 160 180
利润 36 40 50 22 20 30 25 48 58 61
管 理 运 筹 学 7
§ 3 整数规划的应用解,设,0--1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。
这样我们可建立如下的数学模型：
Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10
s.t,100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10
≤ 720
x1 + x2 + x3 ≤ 2
x4 + x5 ≥ 1
x6 + x7 ≥ 1
x8 + x9 + x10 ≥ 2
xj ≥ 0 且 xj 为 0--1变量,i = 1,2,3,……,10
管 理 运 筹 学 8
§ 3 整数规划的应用二、固定成本问题例 5．高压容器公司制造小、中、大三种尺寸的金属容器，
所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元,5万元,6万元，可使用的金属板有 500吨，劳动力有 300人 /月，机器有 100台 /月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：
小号是 l00万元，中号为 150 万元，大号为 200万元。现在要制定一个生产计划，使获得的利润为最大。
资源 小号容器 中号容器 大号容器金属板 （吨） 2 4 8
劳动力 （人月） 2 3 4
机器设备 （ 台月） 1 2 3
管 理 运 筹 学 9
§ 3 整数规划的应用解：这是一个整数规划的问题。
设 x1,x2,x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设 yi = 1(当生产第 i种容器,即 xi ＞ 0 时 ) 或 0（ 当不生产第 i种容器即 xi = 0 时）。
引入约束 xi ≤ M yi,i =1,2,3,M充分大，以保证当 yi = 0 时,xi
= 0 。
这样我们可建立如下的数学模型：
Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3
s.t,2x1 + 4x2 + 8x3 ≤ 500
2x1 + 3x2 + 4x3 ≤ 300
x1 + 2x2 + 3x3 ≤ 100
xi ≤ M yi,i =1,2,3,M充分大
xj ≥ 0 yj 为 0--1变量,i = 1,2,3
管 理 运 筹 学 10
§ 3 整数规划的应用三、指派问题有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是 指派问题。
例 6．有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。
工作工人
A B C D
甲 15 18 21 24
乙 19 23 22 18
丙 26 17 16 19
丁 19 21 23 17
管 理 运 筹 学 11
§ 3 整数规划的应用解,引入 0— 1变量 xij,并令
xij = 1(当指派第 i人去完成第 j项工作时 )或 0（当不指派第 i人去完成第 j项工作时 ),这可以表示为一个 0--1整数规划问题：
Min
z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33
+19x34+19x41 +21x42+23x43+17x44
s.t,x11+ x12+ x13+ x14= 1 (甲只能干一项工作 )
x21+ x22+ x23+ x24= 1 (乙只能干一项工作 )
x31+ x32+ x33+ x34= 1 (丙只能干一项工作 )
x41+ x42+ x43+ x44= 1 (丁只能干一项工作 )
x11+ x21+ x31+ x41= 1 ( A工作只能一人干 )
x12+ x22+ x32+ x42= 1 ( B工作只能一人干 )
x13+ x23+ x33+ x43= 1 ( C工作只能一人干 )
x14+ x24+ x34+ x44= 1 ( D工作只能一人干 )
xij 为 0--1变量,i,j = 1,2,3,4
* * * 求解可用,管理运筹学,软件中整数规划方法。
管 理 运 筹 学 12
§ 3 整数规划的应用四、分布系统设计例 7．某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2,A3,A4,A5地中再选择几个地方建厂。已知在
A2,A3,A4,A5地建厂的固定成本分别为 175千元,300千元,375千元,500千元，另外,A1产量及 A2,A3,A4,A5建成厂的产量，那时销地的销量以及产地到销地的单位运价 (每千箱运费 )如下表所示。
a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?
b) 如果由于政策要求必须在 A2,A3地建一个厂，应在哪几个地方建厂?
销地产地
B
1
B
2
B
3 产量 ( 千吨 )
A
1
8 4 3 30
A
2
5 2 3 10
A
3
4 3 4 20
A
4
9 7 5 30
A
5
10 4 2 40
销量 ( 千吨 ) 30 20 20
管 理 运 筹 学 13
§ 3 整数规划的应用解,a) 设 xij为从 Ai 运往 Bj 的运输量 (单位千箱 ),yk = 1(当 Ak 被选中时 )或 0
（当 Ak 没被选中时 ),k =2,3,4,5,这可以表示为一个整数规划问题：
Min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+
3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53
其中前 4项为固定投资额，后面的项为运输费用。
s.t,x11+ x12+ x13 ≤ 30 ( A 1 厂的产量限制 )
x21+ x22+ x23 ≤ 10 y2 ( A2 厂的产量限制 )
x31+ x32+ x33 ≤ 20 y3 ( A3 厂的产量限制 )
x41+ x42+ x43 ≤ 30 y4 ( A4 厂的产量限制 )
x51+ x52+ x53 ≤ 40 y5 ( A5 厂的产量限制 )
x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制 )
x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制 )
x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制 )
xij ≥0,i = 1,2,3,4,5； j = 1,2,3,yk 为 0--1变量,k =2,3,4,5。
* * * 求解可用,管理运筹学,软件中整数规划方法。
管 理 运 筹 学 14
§ 3 整数规划的应用五、投资问题例 8．某公司在今后五年内考虑给以下的项目投资。已知：
项目 A,从第一年到第四年每年年初需要投资，并于次年末回收本利 115%，
但要求第一年投资最低金额为 4万元，第二、三、四年不限 ；
项目 B,第三年初需要投资，到第五年末能回收本利 128％，但规定最低投资金额为 3万元，最高金额为 5万元 ；
项目 C：第二年初需要投资，到第五年末能回收本利 140%，但规定其投资额或为 2万元或为 4万元或为 6万元或为 8万元。
项目 D：五年内每年初可购买公债，于当年末归还，并加利息 6%，此项投资金额不限。
该部门现有资金 10万元，问它应如何确定给这些项目的每年投资额，
使到第五年末拥有的资金本利总额为最大?
管 理 运 筹 学 15
§ 3 整数规划的应用解,1) 设 xiA,xiB,xiC,xiD ( i ＝ 1,2,3,4,5)分别表示第 i 年年初给项目
A,B,C,D的投资额；
设 yiA,yiB，是 0— 1变量，并规定取 1 时分别表示第 i 年给 A,B投资，
否则取 0（ i = 1,2,3,4,5）。
设 yiC 是非负整数变量，并规定：第 2年投资 C项目 8万元时,取值为 4；
第 2年投资 C项目 6万元时，取值 3；第 2年投资 C项目 4万元时，取值 2；
第 2年投资 C项目 2万元时，取值 1；第 2年不投资 C项目时，取值 0；
这样我们建立如下的决策变量：
第 1年 第 2年 第 3年 第 4年 第 5年
A x1A x2A x3A x4A
B x3B
C x2C=20000y2C
D x1D x2D x3D x4D x5D
管 理 运 筹 学 16
§ 3 整数规划的应用
2）约束条件：
第一年：年初有 100000元,D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+ x1D = 100000；
第二年,A的投资第二年末才可收回，故第二年年初的资金为 1.06x1D，于是
x2A+x2C+x2D = 1.06x1D；
第三年：年初的资金为 1.15x1A+1.06x2D，于是 x3A+x3B+x3D = 1.15x1A+ 1.06x2D；
第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A + x4D = 1.15x2A+ 1.06x3D；
第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D = 1.15x3A+ 1.06x4D。
关于项目 A的投资额规定,x1A ≥ 40000 y1A,x1A ≤ 200000 y1A,200000是足够大的数；保证当 y1A = 0时,x1A = 0 ；当 y1A = 1时,x1A ≥ 40000 。
关于项目 B的投资额规定,x3B ≥ 30000 y3B,x3B ≤ 50000 y3B ；
保证当 y3B = 0时,x3B = 0 ；当 y3B = 1时,50000 ≥ x3B ≥ 30000 。
关于项目 C的投资额规定,x2C = 20000y2C,y2C = 0,1,2,3,4。
管 理 运 筹 学 17
§ 3 整数规划的应用
3）目标函数及模型：
Max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D
s.t,x1A+ x1D = 100000；
x2A+x2C+x2D = 1.06x1D；
x3A+x3B+x3D = 1.15x1A+ 1.06x2D；
x4A+x4D = 1.15x2A+ 1.06x3D；
x5D = 1.15x3A+ 1.06x4D；
x1A ≥ 40000 y1A,
x1A ≤ 200000 y1A,
x3B ≥ 30000 y3B,
x3B ≤ 50000 y3B ；
x2C = 20000y2C,
yiA,yiB = 0 或 1,i = 1,2,3,4,5
y2C = 0,1,2,3,4
xiA,xiB,xiC,xiD ≥ 0 ( i = 1,2,3,4,5）
管 理 运 筹 学 18
§ 4 整数规划的分枝定界法分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。
分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，
用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。
下面以例 9予以说明。
管 理 运 筹 学 19
§ 4 整数规划的分枝定界法例 9 用分枝定界法求解整数规划
Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1,x2≥ 0且 x1,x2为整数解,
(一 )先求出以下线性规划的解：
Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1,x2≥ 0
得 z1=14.66,x1=2.44,x2=3.26
(二 )确定整数规划的最优目标函数值 z*初始上界 和下界 z。
分析后，知道 =14.66，由观察法得 下界 z=13（当 x1=2,x2=3时）。
z
z
管 理 运 筹 学 20
§ 4 整数规划的分枝定界法
(三 )将一个线性规划问题分为两枝，并求解。
可由 x1≤2 或 x1≥3 中取值。将线性规划 1分解为两支，如下：
线性规划 2：
Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x2 ≤2
x1,x2≥ 0
解得 z2=13.90,x1=2,x2=3.30
线性规划 3：
Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1≥ 3
x1,x2≥ 0
解得 z3=14.58,x1=3,x2=2.86
管 理 运 筹 学 21
§ 4 整数规划的分枝定界法
(四 )修改整数规划的最优目标函数的上下界。
经分析，将上界 =14.66修改为 =14.58,z=13。
(五 )在线性规划 2和线性规划 3中选择一个上界最大的线性规划，即线性规划 3，进行分枝。
线性规划 3分解为线性规划 4和线性规划 5，如下：
线性规划 4,Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1≥ 3
x2 ≤2
x1,x2≥ 0
解得 z4=14,x1=4,x2=2
线性规划 5,Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1≥ 3
x2≥ 3
x1,x2≥ 0 无可行解
z z
管 理 运 筹 学 22
§ 4 整数规划的分枝定界法
(六 )进一步修改整数规划最优目标函数值 z*的上下界。
从线性规划 2,4,5中修改上下界。分析后，可得 =14,z=14。都取线性规划 2,4,5中的整数可行解的目标函数值的最大值。
性质 2：
当整数规划的最优目标函数值 z*的上界 等于其下界 z
时，该整数规划的最优解已经被求出。这个整数的最优解即为其目标函数值取此下界的对应线性规划的整数可行解。
z
z
管 理 运 筹 学 23
§ 4 整数规划的分枝定界法用图 8-2表示例 9的求解过程与求解结果
z
线性规划 1
Z1=14.66
X1=2.44
X2=3.26
z=13,=14.66
线性规划 2
Z2=13.90
X1=2
X2=3.30
线性规划 3
Z3=14.58
X1=3
X2=2.86
线性规划 4
Z4=14.00
X1=4
X2=2
线性规划 5
无可行解
X1≤ 2 X1≥ 3
X2≤ 2 X2≥ 3
z=13,=14.58
z=14,=14
图 8-2
z
z
管 理 运 筹 学 24
§ 4 整数规划的分枝定界法
z
从以上解题过程可得用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为 A，将与其相对应的线性规划问题称为 B：
第一步：求解问题 B，可得以下情况之一：
1.B没有可行解，则 A也没有可行解，求解过程停止。
2.B有最优解，且符合问题 A的整数条件，则 B的最优解即为 A的最优解，求解过程停止。
3.B有最优解，但不符合 A的整数条件，记其目标函数值为 z1。
第二步：确定 A的最优目标函数值 z*的上下界，其上界即为 z1,=z1,
再用观察法找到 A的一个整数可行解，求其目标函数值作为 z*的下界，记为 z 。
第三步：判断 是否等于 z。若相等，则整数规划最优解即为其目标函数值等于 z的 A的那个整数可行解；否则进行第四步。
z
管 理 运 筹 学 25
§ 4 整数规划的分枝定界法
z
第四步：在 B的最优解中选一个最远离整数要求的变量，不妨设此变量为 xj，以 [bj]表示小于 bj的最大整数，构造以下两个约束条件，并加入问题
B，得到 B的两个分枝 B1和 B2。
xj ≤ [bj]和 xj ≥ [bj]+1
第五步：求解 B1和 B2。修改 A问题的最优目标函数值 z*的上下界,和
z 。
第六步：比较和剪枝。各分枝的最优目标函数值中若有小于 z者，则剪掉这枝（用打 Х 表示），即以后不再考虑了。若大于,则不符合整数条件，则重复第三步至第六步，直至 =z，求出最优解为止。
对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。
z
z
管 理 运 筹 学 26
§ 4 整数规划的分枝定界法
【 例 】 用分枝定界法求解
【 解 】 先求对应的松弛问题（记为 LP0）：
0,
255.22
108.02.1
:0
34m a x
21
21
21
21
xx
xx
xx
LP
xxZ
用图解法得到最优解 X＝ （ 3.57,7.14）,Z0=35.7,如下图所示 。
且均取整数,0,
255.22
108.02.1
34m a x
21
21
21
21
xx
xx
xx
xxZ
管 理 运 筹 学 27
§ 4 整数规划的分枝定界法
8.33
10
108.02.1 21 xx
255.22 21 xx
松弛问题 LP0的最优解
X=(3.57,7.14),Z0=35.7
o
A
B
C
10
管 理 运 筹 学 28
10
10
x1
x2
o
A
B
C
0,
3
255.22
108.02.1
:1
34m a x
21
1
21
21
21
xx
x
xx
xx
LP
xxZ
LP1
LP2
3 4
LP1:X=(3,7.6),Z1=34.8
LP2:X=(4,6.5),Z2=35.5
0,
4
255.22
108.02.1
:2
34m a x
21
1
21
21
21
xx
x
xx
xx
LP
xxZ
得到两个线性规划及增加约束 43 11 xx①
②
管 理 运 筹 学 29
10
10
x1
x2
o
A
B
C
LP1
LP3
3 4
LP3:X=(4.33,6),Z3=35.33
0,
64
255.22
108.02.1
:3
34m a x
21
21
21
21
21
xx
xx
xx
xx
LP
xxZ
，
不可行，得到线性规划，显然及进行分枝，增加约束选择目标值最大的分枝
776
2
222 xxx
LP
6
①
②
不可行72?x
LP1:X=(3,7.6),Z1=34.8
管 理 运 筹 学 30
10
10
x1
x2
o
A
C
LP1
3 4
可行域是一条线段即
，，
,4
0,
464
255.22
108.02.1
:4
34m a x
1
21
121
21
21
21
x
xx
xxx
xx
xx
LP
xxZ
：及，到线性规划及进行分枝，增加约束，选择由于
5454
3
11
13
LPLPxx
LPZZ
6
①
②
0,
65
255.22
108.02.1
:5
34m a x
21
21
21
21
21
xx
xx
xx
xx
LP
xxZ
，
LP4:X=(4,6),Z4=34
LP5:X=(5,5),Z5=35
5
LP1:X=(3,7.6),Z1=34.8
LP3 LP5
管 理 运 筹 学 31
§ 4 整数规划的分枝定界法尽管 LP1的解中 x1不为整数，但 Z5>Z因此 LP5的最优解就是原整数规划的最优解。
上述分枝过程可用下图表示
LP0:X=(3.57,7.14),Z0=35.7
LP1:X=(3,7.6)
Z1=34.8
LP2:X=(4,6.5)
Z2=35.5
x1≤3 x1≥4
LP3:X=(4.33,6)
Z3=35.33
x2≤6
LP4:X=(4,6)
Z4=34
LP5:X=(5,5)
Z5=35
x1≤4 x1≥5
无可行解
x2≥7
管 理 运 筹 学
§ 5 整数规划的割平面法设纯整数规划
njxbxaxcZ ji
n
j
jij
n
j
jj,,10m a x
11
且为整数，
松弛问题
njxbxaxcZ ji
n
j
jij
n
j
jj,,10m a x
11
，
的最优解
TmT bbbbBbbBX ),,,()0,( 2111＝
设 xi不为整数,为非基变量
k
k
kikii xxabx
5,求解 IP的割平面法管 理 运 筹 学
§ 5 整数规划的割平面法将 分离成一个整数与一个非负真分数之和：iki ab及
10,10,,][ ikiikikikiii fffaafbb
则有 k
k
ikk
k
ijiii xfxafbx ][][
k
k
ikik
k
ijii xffxabx ][][
等式两边都为整数并且有
1 ik
k
iki fxff
管 理 运 筹 学
§ 5 整数规划的割平面法加入松弛变量 si得
ik
k
iki fxfs
此式称为以 xi行为源行（来源行）的割平面，或分数切割式，
或 R.E.Gomory(高莫雷 )约束方程。
将 Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。
0 k
k
iki xff
则管 理 运 筹 学
§ 5 整数规划的割平面法
3
2
43
1
33
2
2
3
5
46
1
36
5
1
xxx
xxx例如，
324653651 1)1( xxx
x1行：
移项：
4653653241 1 xxxx
令 0
46536532 xx
加入松弛变量 s1得
324653651 xxs
同理，对于 x2行有：
324313312 xxs
管 理 运 筹 学
§ 5 整数规划的割平面法
【 例 】 用割平面法求解下列 IP问题
且为整数0,
102
3046
34m a x
21
21
21
21
xx
xx
xx
xxZ
【 解 】 放宽变量约束，对应的松弛问题是
0,
102
3046
34m a x
21
21
21
21
xx
xx
xx
xxZ
管 理 运 筹 学
§ 5 整数规划的割平面法加入松弛变量 x3及 x4后，用单纯形法求解，得到最优表 3。
最优解 X(0)＝ (5/2,15/4),不是 IP的最优解。选择表 3的第一行
(也可以选第二行 )为源行
2
5
2
1
4
1
431 xxx
Cj 4 3 0 0 b
CB XB x1 x2 x3 x4
4
3
x1
x2
1
0
0
1
1/4
－ 1/8
－ 1/2
3/4
5/2
15/4
λj 0 0 － 5/8 － 1/4
表 3
管 理 运 筹 学
§ 5 整数规划的割平面法分离系数后改写成
2
12)
2
11(
4
1
431 xxx
02141212 4341 xxxx
加入松弛变量 x5得到高莫雷约束方程
22 543 xxx
将上式作为约束条件添加到表 3中，用对偶单纯形法计算，
如表 4所示管 理 运 筹 学
§ 5 整数规划的割平面法
Cj 4 3 0 0 0 b
CB XB x1 x2 x3 x4 x5
4
3
0
x1
x2
x5
1
0
0
0
1
0
1/4
－ 1/8
－ 1
－ 1/2
3/4
[－ 2]
0
0
1
5/2
15/4
－ 2→
λj 0 0 － 5/8 － 1/4↑ 0
4
3
0
x1
x2
x4
1
0
0
0
1
0
1/2
－ 1/2
1/2
0
0
1
－ 1/4
3/8
－ 1/2
3
3
1
λj 0 0 － 1/2 0 － 1/8
最优解 X(1)＝ (3,3)，最优值 Z＝ 21。所有变量为整数,X(1)就是 IP的最优解。如果不是整数解，需要继续切割，重复上述计算过程。
表 4
第八章 整数规划
§ 1 整数规划的图解法
§ 2 整数规划的计算机求解
§ 3 整数规划的应用
§ 4 整数规划的分枝定界法
§ 5 割平面方程管 理 运 筹 学 2
第八章 整数规划
求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。
在整数规划中，如果所有的变量都为非负整数，
则称为 纯整数规划问题 ；如果有一部分变量为负整数，则称之为 混合整数规划问题 。在整数规划中，如果变量的取值只限于 0和 1，这样的变量我们称之为 0-1变量 。在纯整数规划和混合整数规划问题中，如果所有的变量都为 0-1变量，则称之为
0-1规划 。
管 理 运 筹 学 3
§ 1 整数规划的图解法例 1,某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、
重量、可获利润以及托运所受限制如表所示。
甲种货物至多托运 4件，问两种货物各托运多少件，可使获得利润最大。
解：设 x1,x2分别为 甲、乙两种货物托运的件数，建立模型目标函数,Max z = 2x1 +3 x2
约束条件,s.t,
195x1 + 273 x2 ≤1365
4 x1 + 40 x2 ≤140
x1 ≤4
x1,x2 ≥ 0 为整数。
如果去掉最后一个约束，就是一个线性规划问题。利用图解法，
货物 每件体积
（ 立方英尺 ）
每件重量
（ 百千克 ）
每件利润
（ 百元 ）
甲乙
195
273
4
40
2
3
托运限制 1365 140
管 理 运 筹 学 4
得到线性规划的最优解为 x1=2.44,x2=3.26,目标函数值为 14.66。
由图表可看出，整数规划的最优解为 x1=4,x2=2,目标函数值为 14。
性质 1,任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。
1 2 3 4
1
2
3 2x1+3x2 =14.66
x1
x2
2x1+3x2 =14
2x1+3x2 =6
§ 1 整数规划的图解法§ 1 整数规划的图解法管 理 运 筹 学 5
例 2：
Max z = 3x1 + x2 + 3x3
s.t.
-x1 + 2x2 + x3 ≤ 4
4x2 -3x3 ≤2
x1 -3x2 + 2x3 ≤3
x1,x2,x3 ≥ 0 为整数例 3：
Max z = 3x1 + x2 + 3x3
s.t.
-x1 + 2x2 + x3 ≤ 4
4x2 -3x3 ≤2
x1 -3x2 + 2x3 ≤3
x3 ≤1
x1,x2,x3 ≥ 0
x1,x3 为整数 x3 为
0-1变量用,管理运筹学,软件求解得：
x1 = 5 x2 = 2 x3 = 2
用,管理运筹学,软件求解得：
x1 = 4 x2 = 1.25 x3 = 1
z = 16.25
§ 2 整数规划的计算机求解管 理 运 筹 学 6
§ 3 整数规划的应用一、投资场所的选择例 4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有 10个位置 Aj (j＝ 1,2,3,…,10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：
在东区由 A1,A2,A3 三个点至多选择两个；
在西区由 A4,A5 两个点中至少选一个；
在南区由 A6,A7 两个点中至少选一个；
在北区由 A8,A9,A10 三个点中至少选两个。
Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元 )。但投资总额不能超过 720万元，问应选择哪几个销售点，可使年利润为最大?
A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10
投资额 100 120 150 80 70 90 80 140 160 180
利润 36 40 50 22 20 30 25 48 58 61
管 理 运 筹 学 7
§ 3 整数规划的应用解,设,0--1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。
这样我们可建立如下的数学模型：
Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10
s.t,100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10
≤ 720
x1 + x2 + x3 ≤ 2
x4 + x5 ≥ 1
x6 + x7 ≥ 1
x8 + x9 + x10 ≥ 2
xj ≥ 0 且 xj 为 0--1变量,i = 1,2,3,……,10
管 理 运 筹 学 8
§ 3 整数规划的应用二、固定成本问题例 5．高压容器公司制造小、中、大三种尺寸的金属容器，
所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元,5万元,6万元，可使用的金属板有 500吨，劳动力有 300人 /月，机器有 100台 /月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：
小号是 l00万元，中号为 150 万元，大号为 200万元。现在要制定一个生产计划，使获得的利润为最大。
资源 小号容器 中号容器 大号容器金属板 （吨） 2 4 8
劳动力 （人月） 2 3 4
机器设备 （ 台月） 1 2 3
管 理 运 筹 学 9
§ 3 整数规划的应用解：这是一个整数规划的问题。
设 x1,x2,x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设 yi = 1(当生产第 i种容器,即 xi ＞ 0 时 ) 或 0（ 当不生产第 i种容器即 xi = 0 时）。
引入约束 xi ≤ M yi,i =1,2,3,M充分大，以保证当 yi = 0 时,xi
= 0 。
这样我们可建立如下的数学模型：
Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3
s.t,2x1 + 4x2 + 8x3 ≤ 500
2x1 + 3x2 + 4x3 ≤ 300
x1 + 2x2 + 3x3 ≤ 100
xi ≤ M yi,i =1,2,3,M充分大
xj ≥ 0 yj 为 0--1变量,i = 1,2,3
管 理 运 筹 学 10
§ 3 整数规划的应用三、指派问题有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是 指派问题。
例 6．有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。
工作工人
A B C D
甲 15 18 21 24
乙 19 23 22 18
丙 26 17 16 19
丁 19 21 23 17
管 理 运 筹 学 11
§ 3 整数规划的应用解,引入 0— 1变量 xij,并令
xij = 1(当指派第 i人去完成第 j项工作时 )或 0（当不指派第 i人去完成第 j项工作时 ),这可以表示为一个 0--1整数规划问题：
Min
z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33
+19x34+19x41 +21x42+23x43+17x44
s.t,x11+ x12+ x13+ x14= 1 (甲只能干一项工作 )
x21+ x22+ x23+ x24= 1 (乙只能干一项工作 )
x31+ x32+ x33+ x34= 1 (丙只能干一项工作 )
x41+ x42+ x43+ x44= 1 (丁只能干一项工作 )
x11+ x21+ x31+ x41= 1 ( A工作只能一人干 )
x12+ x22+ x32+ x42= 1 ( B工作只能一人干 )
x13+ x23+ x33+ x43= 1 ( C工作只能一人干 )
x14+ x24+ x34+ x44= 1 ( D工作只能一人干 )
xij 为 0--1变量,i,j = 1,2,3,4
* * * 求解可用,管理运筹学,软件中整数规划方法。
管 理 运 筹 学 12
§ 3 整数规划的应用四、分布系统设计例 7．某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2,A3,A4,A5地中再选择几个地方建厂。已知在
A2,A3,A4,A5地建厂的固定成本分别为 175千元,300千元,375千元,500千元，另外,A1产量及 A2,A3,A4,A5建成厂的产量，那时销地的销量以及产地到销地的单位运价 (每千箱运费 )如下表所示。
a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?
b) 如果由于政策要求必须在 A2,A3地建一个厂，应在哪几个地方建厂?
销地产地
B
1
B
2
B
3 产量 ( 千吨 )
A
1
8 4 3 30
A
2
5 2 3 10
A
3
4 3 4 20
A
4
9 7 5 30
A
5
10 4 2 40
销量 ( 千吨 ) 30 20 20
管 理 运 筹 学 13
§ 3 整数规划的应用解,a) 设 xij为从 Ai 运往 Bj 的运输量 (单位千箱 ),yk = 1(当 Ak 被选中时 )或 0
（当 Ak 没被选中时 ),k =2,3,4,5,这可以表示为一个整数规划问题：
Min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+
3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53
其中前 4项为固定投资额，后面的项为运输费用。
s.t,x11+ x12+ x13 ≤ 30 ( A 1 厂的产量限制 )
x21+ x22+ x23 ≤ 10 y2 ( A2 厂的产量限制 )
x31+ x32+ x33 ≤ 20 y3 ( A3 厂的产量限制 )
x41+ x42+ x43 ≤ 30 y4 ( A4 厂的产量限制 )
x51+ x52+ x53 ≤ 40 y5 ( A5 厂的产量限制 )
x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制 )
x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制 )
x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制 )
xij ≥0,i = 1,2,3,4,5； j = 1,2,3,yk 为 0--1变量,k =2,3,4,5。
* * * 求解可用,管理运筹学,软件中整数规划方法。
管 理 运 筹 学 14
§ 3 整数规划的应用五、投资问题例 8．某公司在今后五年内考虑给以下的项目投资。已知：
项目 A,从第一年到第四年每年年初需要投资，并于次年末回收本利 115%，
但要求第一年投资最低金额为 4万元，第二、三、四年不限 ；
项目 B,第三年初需要投资，到第五年末能回收本利 128％，但规定最低投资金额为 3万元，最高金额为 5万元 ；
项目 C：第二年初需要投资，到第五年末能回收本利 140%，但规定其投资额或为 2万元或为 4万元或为 6万元或为 8万元。
项目 D：五年内每年初可购买公债，于当年末归还，并加利息 6%，此项投资金额不限。
该部门现有资金 10万元，问它应如何确定给这些项目的每年投资额，
使到第五年末拥有的资金本利总额为最大?
管 理 运 筹 学 15
§ 3 整数规划的应用解,1) 设 xiA,xiB,xiC,xiD ( i ＝ 1,2,3,4,5)分别表示第 i 年年初给项目
A,B,C,D的投资额；
设 yiA,yiB，是 0— 1变量，并规定取 1 时分别表示第 i 年给 A,B投资，
否则取 0（ i = 1,2,3,4,5）。
设 yiC 是非负整数变量，并规定：第 2年投资 C项目 8万元时,取值为 4；
第 2年投资 C项目 6万元时，取值 3；第 2年投资 C项目 4万元时，取值 2；
第 2年投资 C项目 2万元时，取值 1；第 2年不投资 C项目时，取值 0；
这样我们建立如下的决策变量：
第 1年 第 2年 第 3年 第 4年 第 5年
A x1A x2A x3A x4A
B x3B
C x2C=20000y2C
D x1D x2D x3D x4D x5D
管 理 运 筹 学 16
§ 3 整数规划的应用
2）约束条件：
第一年：年初有 100000元,D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+ x1D = 100000；
第二年,A的投资第二年末才可收回，故第二年年初的资金为 1.06x1D，于是
x2A+x2C+x2D = 1.06x1D；
第三年：年初的资金为 1.15x1A+1.06x2D，于是 x3A+x3B+x3D = 1.15x1A+ 1.06x2D；
第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A + x4D = 1.15x2A+ 1.06x3D；
第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D = 1.15x3A+ 1.06x4D。
关于项目 A的投资额规定,x1A ≥ 40000 y1A,x1A ≤ 200000 y1A,200000是足够大的数；保证当 y1A = 0时,x1A = 0 ；当 y1A = 1时,x1A ≥ 40000 。
关于项目 B的投资额规定,x3B ≥ 30000 y3B,x3B ≤ 50000 y3B ；
保证当 y3B = 0时,x3B = 0 ；当 y3B = 1时,50000 ≥ x3B ≥ 30000 。
关于项目 C的投资额规定,x2C = 20000y2C,y2C = 0,1,2,3,4。
管 理 运 筹 学 17
§ 3 整数规划的应用
3）目标函数及模型：
Max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D
s.t,x1A+ x1D = 100000；
x2A+x2C+x2D = 1.06x1D；
x3A+x3B+x3D = 1.15x1A+ 1.06x2D；
x4A+x4D = 1.15x2A+ 1.06x3D；
x5D = 1.15x3A+ 1.06x4D；
x1A ≥ 40000 y1A,
x1A ≤ 200000 y1A,
x3B ≥ 30000 y3B,
x3B ≤ 50000 y3B ；
x2C = 20000y2C,
yiA,yiB = 0 或 1,i = 1,2,3,4,5
y2C = 0,1,2,3,4
xiA,xiB,xiC,xiD ≥ 0 ( i = 1,2,3,4,5）
管 理 运 筹 学 18
§ 4 整数规划的分枝定界法分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。
分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，
用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。
下面以例 9予以说明。
管 理 运 筹 学 19
§ 4 整数规划的分枝定界法例 9 用分枝定界法求解整数规划
Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1,x2≥ 0且 x1,x2为整数解,
(一 )先求出以下线性规划的解：
Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1,x2≥ 0
得 z1=14.66,x1=2.44,x2=3.26
(二 )确定整数规划的最优目标函数值 z*初始上界 和下界 z。
分析后，知道 =14.66，由观察法得 下界 z=13（当 x1=2,x2=3时）。
z
z
管 理 运 筹 学 20
§ 4 整数规划的分枝定界法
(三 )将一个线性规划问题分为两枝，并求解。
可由 x1≤2 或 x1≥3 中取值。将线性规划 1分解为两支，如下：
线性规划 2：
Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x2 ≤2
x1,x2≥ 0
解得 z2=13.90,x1=2,x2=3.30
线性规划 3：
Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1≥ 3
x1,x2≥ 0
解得 z3=14.58,x1=3,x2=2.86
管 理 运 筹 学 21
§ 4 整数规划的分枝定界法
(四 )修改整数规划的最优目标函数的上下界。
经分析，将上界 =14.66修改为 =14.58,z=13。
(五 )在线性规划 2和线性规划 3中选择一个上界最大的线性规划，即线性规划 3，进行分枝。
线性规划 3分解为线性规划 4和线性规划 5，如下：
线性规划 4,Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1≥ 3
x2 ≤2
x1,x2≥ 0
解得 z4=14,x1=4,x2=2
线性规划 5,Max 2x1+3x2
s.t,195x1+273x2≤1365
4x1+ 40x2≤140
x1≥ 3
x2≥ 3
x1,x2≥ 0 无可行解
z z
管 理 运 筹 学 22
§ 4 整数规划的分枝定界法
(六 )进一步修改整数规划最优目标函数值 z*的上下界。
从线性规划 2,4,5中修改上下界。分析后，可得 =14,z=14。都取线性规划 2,4,5中的整数可行解的目标函数值的最大值。
性质 2：
当整数规划的最优目标函数值 z*的上界 等于其下界 z
时，该整数规划的最优解已经被求出。这个整数的最优解即为其目标函数值取此下界的对应线性规划的整数可行解。
z
z
管 理 运 筹 学 23
§ 4 整数规划的分枝定界法用图 8-2表示例 9的求解过程与求解结果
z
线性规划 1
Z1=14.66
X1=2.44
X2=3.26
z=13,=14.66
线性规划 2
Z2=13.90
X1=2
X2=3.30
线性规划 3
Z3=14.58
X1=3
X2=2.86
线性规划 4
Z4=14.00
X1=4
X2=2
线性规划 5
无可行解
X1≤ 2 X1≥ 3
X2≤ 2 X2≥ 3
z=13,=14.58
z=14,=14
图 8-2
z
z
管 理 运 筹 学 24
§ 4 整数规划的分枝定界法
z
从以上解题过程可得用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为 A，将与其相对应的线性规划问题称为 B：
第一步：求解问题 B，可得以下情况之一：
1.B没有可行解，则 A也没有可行解，求解过程停止。
2.B有最优解，且符合问题 A的整数条件，则 B的最优解即为 A的最优解，求解过程停止。
3.B有最优解，但不符合 A的整数条件，记其目标函数值为 z1。
第二步：确定 A的最优目标函数值 z*的上下界，其上界即为 z1,=z1,
再用观察法找到 A的一个整数可行解，求其目标函数值作为 z*的下界，记为 z 。
第三步：判断 是否等于 z。若相等，则整数规划最优解即为其目标函数值等于 z的 A的那个整数可行解；否则进行第四步。
z
管 理 运 筹 学 25
§ 4 整数规划的分枝定界法
z
第四步：在 B的最优解中选一个最远离整数要求的变量，不妨设此变量为 xj，以 [bj]表示小于 bj的最大整数，构造以下两个约束条件，并加入问题
B，得到 B的两个分枝 B1和 B2。
xj ≤ [bj]和 xj ≥ [bj]+1
第五步：求解 B1和 B2。修改 A问题的最优目标函数值 z*的上下界,和
z 。
第六步：比较和剪枝。各分枝的最优目标函数值中若有小于 z者，则剪掉这枝（用打 Х 表示），即以后不再考虑了。若大于,则不符合整数条件，则重复第三步至第六步，直至 =z，求出最优解为止。
对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。
z
z
管 理 运 筹 学 26
§ 4 整数规划的分枝定界法
【 例 】 用分枝定界法求解
【 解 】 先求对应的松弛问题（记为 LP0）：
0,
255.22
108.02.1
:0
34m a x
21
21
21
21
xx
xx
xx
LP
xxZ
用图解法得到最优解 X＝ （ 3.57,7.14）,Z0=35.7,如下图所示 。
且均取整数,0,
255.22
108.02.1
34m a x
21
21
21
21
xx
xx
xx
xxZ
管 理 运 筹 学 27
§ 4 整数规划的分枝定界法
8.33
10
108.02.1 21 xx
255.22 21 xx
松弛问题 LP0的最优解
X=(3.57,7.14),Z0=35.7
o
A
B
C
10
管 理 运 筹 学 28
10
10
x1
x2
o
A
B
C
0,
3
255.22
108.02.1
:1
34m a x
21
1
21
21
21
xx
x
xx
xx
LP
xxZ
LP1
LP2
3 4
LP1:X=(3,7.6),Z1=34.8
LP2:X=(4,6.5),Z2=35.5
0,
4
255.22
108.02.1
:2
34m a x
21
1
21
21
21
xx
x
xx
xx
LP
xxZ
得到两个线性规划及增加约束 43 11 xx①
②
管 理 运 筹 学 29
10
10
x1
x2
o
A
B
C
LP1
LP3
3 4
LP3:X=(4.33,6),Z3=35.33
0,
64
255.22
108.02.1
:3
34m a x
21
21
21
21
21
xx
xx
xx
xx
LP
xxZ
，
不可行，得到线性规划，显然及进行分枝，增加约束选择目标值最大的分枝
776
2
222 xxx
LP
6
①
②
不可行72?x
LP1:X=(3,7.6),Z1=34.8
管 理 运 筹 学 30
10
10
x1
x2
o
A
C
LP1
3 4
可行域是一条线段即
，，
,4
0,
464
255.22
108.02.1
:4
34m a x
1
21
121
21
21
21
x
xx
xxx
xx
xx
LP
xxZ
：及，到线性规划及进行分枝，增加约束，选择由于
5454
3
11
13
LPLPxx
LPZZ
6
①
②
0,
65
255.22
108.02.1
:5
34m a x
21
21
21
21
21
xx
xx
xx
xx
LP
xxZ
，
LP4:X=(4,6),Z4=34
LP5:X=(5,5),Z5=35
5
LP1:X=(3,7.6),Z1=34.8
LP3 LP5
管 理 运 筹 学 31
§ 4 整数规划的分枝定界法尽管 LP1的解中 x1不为整数，但 Z5>Z因此 LP5的最优解就是原整数规划的最优解。
上述分枝过程可用下图表示
LP0:X=(3.57,7.14),Z0=35.7
LP1:X=(3,7.6)
Z1=34.8
LP2:X=(4,6.5)
Z2=35.5
x1≤3 x1≥4
LP3:X=(4.33,6)
Z3=35.33
x2≤6
LP4:X=(4,6)
Z4=34
LP5:X=(5,5)
Z5=35
x1≤4 x1≥5
无可行解
x2≥7
管 理 运 筹 学
§ 5 整数规划的割平面法设纯整数规划
njxbxaxcZ ji
n
j
jij
n
j
jj,,10m a x
11
且为整数，
松弛问题
njxbxaxcZ ji
n
j
jij
n
j
jj,,10m a x
11
，
的最优解
TmT bbbbBbbBX ),,,()0,( 2111＝
设 xi不为整数,为非基变量
k
k
kikii xxabx
5,求解 IP的割平面法管 理 运 筹 学
§ 5 整数规划的割平面法将 分离成一个整数与一个非负真分数之和：iki ab及
10,10,,][ ikiikikikiii fffaafbb
则有 k
k
ikk
k
ijiii xfxafbx ][][
k
k
ikik
k
ijii xffxabx ][][
等式两边都为整数并且有
1 ik
k
iki fxff
管 理 运 筹 学
§ 5 整数规划的割平面法加入松弛变量 si得
ik
k
iki fxfs
此式称为以 xi行为源行（来源行）的割平面，或分数切割式，
或 R.E.Gomory(高莫雷 )约束方程。
将 Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。
0 k
k
iki xff
则管 理 运 筹 学
§ 5 整数规划的割平面法
3
2
43
1
33
2
2
3
5
46
1
36
5
1
xxx
xxx例如，
324653651 1)1( xxx
x1行：
移项：
4653653241 1 xxxx
令 0
46536532 xx
加入松弛变量 s1得
324653651 xxs
同理，对于 x2行有：
324313312 xxs
管 理 运 筹 学
§ 5 整数规划的割平面法
【 例 】 用割平面法求解下列 IP问题
且为整数0,
102
3046
34m a x
21
21
21
21
xx
xx
xx
xxZ
【 解 】 放宽变量约束，对应的松弛问题是
0,
102
3046
34m a x
21
21
21
21
xx
xx
xx
xxZ
管 理 运 筹 学
§ 5 整数规划的割平面法加入松弛变量 x3及 x4后，用单纯形法求解，得到最优表 3。
最优解 X(0)＝ (5/2,15/4),不是 IP的最优解。选择表 3的第一行
(也可以选第二行 )为源行
2
5
2
1
4
1
431 xxx
Cj 4 3 0 0 b
CB XB x1 x2 x3 x4
4
3
x1
x2
1
0
0
1
1/4
－ 1/8
－ 1/2
3/4
5/2
15/4
λj 0 0 － 5/8 － 1/4
表 3
管 理 运 筹 学
§ 5 整数规划的割平面法分离系数后改写成
2
12)
2
11(
4
1
431 xxx
02141212 4341 xxxx
加入松弛变量 x5得到高莫雷约束方程
22 543 xxx
将上式作为约束条件添加到表 3中，用对偶单纯形法计算，
如表 4所示管 理 运 筹 学
§ 5 整数规划的割平面法
Cj 4 3 0 0 0 b
CB XB x1 x2 x3 x4 x5
4
3
0
x1
x2
x5
1
0
0
0
1
0
1/4
－ 1/8
－ 1
－ 1/2
3/4
[－ 2]
0
0
1
5/2
15/4
－ 2→
λj 0 0 － 5/8 － 1/4↑ 0
4
3
0
x1
x2
x4
1
0
0
0
1
0
1/2
－ 1/2
1/2
0
0
1
－ 1/4
3/8
－ 1/2
3
3
1
λj 0 0 － 1/2 0 － 1/8
最优解 X(1)＝ (3,3)，最优值 Z＝ 21。所有变量为整数,X(1)就是 IP的最优解。如果不是整数解，需要继续切割，重复上述计算过程。
表 4
