第四章 整数规划
整数规划
整数规划的分支定界法
0-1整数规划
隐枚举法
匈牙利算法
问题引出
且为整数
引例：
当不要求解为整数时，对应的线性规划问题最优解为：
X1=, x2=
整数解如何获得?
能否用将线性规划问题解中不满足整数的解取整的办法获得整数解呢？
例1.某厂拟用集装箱托运甲乙两种货物，每箱的体积重量可获得的利润及托运所受的限制如表1所示。问每次两种货物各托运多少箱，可使得获得的利润最大？
货物
每箱体积
(米3)
每箱重量
(百斤)
每箱利润(百元)
甲
5
2
20
乙
4
5
10
托运限制
24
13
问题引出
线性规划模型：
整数规划定
义
若在线性规划模型中，变量限制为整数，则称为整数线性规划。
整数规划分类
变量全限制为整数的，为纯(完全)整数规划。
特例：0-1整数规划
变量部分限制为整数的，为混合整数规划。
+
+
+
+
+
(,0)
Z=90
Z=96
作图法求解例1
整数规划解的特点
整数规划的松弛问题是一个线性规划问题，其可行域是一个凸集，任何两个可行解的凸组合都是可行解；
整数规划可行解的集合是其松弛问题可行域的一个子集。任何两个可行解的凸组合不一定满足整数条件，因而不一定为可行解；
整数规划的可行解一定是其松弛问题的可行解，反之，不成立。
所以整数规划的最优解不优于松弛问题的最优解( 引申含义是什么？ )。
定义：去掉整数条件得到的问题为整数规划问题的松弛问题。
原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况；
①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
②原最优解变为非可行解。
整数规划最优解不能按照实数最优解简单取整而获得。
整数规划解的特点
1．割平面法——主要求解纯整数线性规划(不要求掌握)
2．分支定界法——可求纯或混合整数线性规划
3．隐枚举法——求解0-1整数规划
① 过滤隐枚举法
② 分支隐枚举法
4．匈牙利法——解决指派问题(0-1规划特殊情形)
5．蒙特卡洛法——求解各种类型规划(不要求掌握)
6. 分支切割方法(不要求掌握)
7. 启发式算法(不要求掌握)
整数规划求解方法
分支定界法是求整数规划的一种常用的有效的方法，既能解决纯整数规划的问题，也能解决混合整数规划的问题。
问题(A)如下：
Max z = c1 x1 + c2 x2 + … + cn xn
. a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1 ，x2 ，… ，xn ≥ 0 为整数
分支定界法
步骤1. 求解对应的松弛问题
(A)去掉整数条件得到的问题为松弛问题(B)，对(B)进行求解，在应用分支定界法过程中，对应的解应满足以下情况之一：
① (B)无可行解，则(A)亦无可行解，停止对此问题 的计算；
② (B)有最优解，并满足整数约束，即同时为(A)的最优解，那么z*同时是当前问题(A)最优目标值的上界和下界。停止对这个问题的计算；
③ (B)有最优解 x, 但不符合整数条件。
分支定界法的计算过程(以最大化问题为例)：
若情况③发生，得到(A)问题最优值的一个上界。同时可以通过观察的方法任找(A)问题的一个可行解，那么对应的目标函数值是(A)最优值的一个下界 z 。即得到
z ≤ z* ＜z，转2，进行以下一步的迭代；
步骤2.对当前问题进行分支和定界
分支：任取非整数的分量 xr。构造两个附加约束：
xr ≤ [xr] 和 xr ≥ [xr]+1 ，
对(B)分别加入这两个约束，可得到两个子问题:
(B1)(分支xr ≤ [xr] )和(B2)(分支xr ≥ [xr]+1 )，
由于在区域 [xr] < xr< [xr]+1 中不可能有整数规划的可行解，所以整数规划的所有可行解分别含在两个子问题 (分支)中，即只要求出各分支中符合整数要求的最优解进行比较，就可以得到整数规划的最优解；
定界：根据前面分析，对每一个松弛问题(B)，以及(A)的可行解，得到当前问题的上、下界z和 z 。
对于问题(B1)(分支xr ≤ [xr])相应的松弛问题，如果其最优解为x(r), 最优值为z(r), 那么在这个分支中原整数规划所有可行解的目标函数值都不会优于z(r)。
对于问题(B2)分支xr ≥ [xr]+1 可以做同样的分析。
两个分支中较优的目标函数值可以作为新的上界，整数解可作为新的下界。
步骤3.分支后计算子问题的线性规划的最优解——剪支
分情况讨论：
(1) 得到整数解且目标值优于原有定界(下界),则替代原有定界(下界);
比如某个分支得到的整数解对应的目标函数值大于原有的下界。
(2) 得到整数解且目标值劣于原有定界(下界),则删除该分支—剪支(其中无最优解);
比如某个分支得到的整数解对应的目标函数值小于原有的下界。
(3) 得到非整数解且目标值优于原有定界(下界),则继续分支，并回到步骤2;
(4) 得到非整数解且目标值劣于等于原有定界(下界),则剪支(其中无最优解). 为什么？
当所有子问题都剪支了，即没有需要处理的子问题时，达到当前下界z 的可行解即原问题的最优解， 算法结束。
用分支定界法求解整数规划
9x1+7x2=56
(0,)
Z=315
(,) Z=356
2
4
6
8
10
2
4
6
8
7x1+20x2=70
Z=40x1+90x2
x1
x2
等值线
松弛规划问题最优解
选x1来分支
9x1+7x2=56
(0,)
Z=315
2
4
6
8
10
2
4
6
8
7x1+20x2=70
x1
x2
(5,) z=341
(4,) z=349
B1 (x1≤4)
B2
9x1+7x2=56
(0,)
Z=315
2
4
6
8
10
2
4
6
8
7x1+20x2=70
x1
x2
(4,2) z=340
(,3) z=327
(5,) z=341
B3
B4
9x1+7x2=56
(0,)
Z=315
2
4
6
8
10
2
4
6
8
7x1+20x2=70
x1
x2
(4,2) z=340
(,3) z=327
(,1) z=308
(5,) z=341
B6
B5
用分支定界法求解下列整数规划问题：
Max 2x1+3x2
. 195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1,x2≥ 0且x1,x2为整数
线性规划1
Z1=
X1=
X2=
z=13, =
线性规划2
Z2=
X1=2
X2=
线性规划3
Z3=
X1=3
X2=
线性规划4
Z4=
X1=4
X2=2
线性规划5
无可行解
X1≤2
X1≥3
X2≤2
X2≥3
z=13, =
z=14, =14
投资场所的选择问题
例2.京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：
在东区由A1 ， A2 ，A3 三个点至多选择两个；
在西区由A4 ， A5 两个点中至少选一个；
在南区由A6 ， A7 两个点中至少选一个；
在北区由A8 ， A9 ， A10 三个点中至少选两个。
Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见下表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?
0-1整数规划
解：设：0-1变量 xi = 1 (Ai 点被选用) 或 0 (Ai 点没被选用)。
这样我们可建立如下的数学模型：
Max z=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10
. 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
固定成本问题
例3．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示。
每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人月，机器有100台月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。
现在要制定一个生产计划，使获得的利润为最大。
资源
小号容器
中号容器
大号容器
金属板（吨）
2
4
8
劳动力（人月）
2
3
4
机器设备（台月）
1
2
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
. 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
指派问题
有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。
后文，我们将会学习匈牙利求解方法。
例4．有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。
解：引入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
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
.
投资问题
例5．某公司在今后五年内考虑给以下的项目投资。已知：
项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；
项目B：第三年初需要投资，到第五年未能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元；
项目 C：第二年初需要投资，到第五年未能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。
项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。
该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?
解：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
2)约束条件：
第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+ x1D = 100000；
第二年：A次年末才可收回投资故第二年年初的资金为，于是x2A+x2C+x2D = ；
第三年：年初的资金为 +，于是 x3A+x3B+x3D = + ；
第四年：年初的资金为 +，于是 x4A + x4D = + ；
第五年：年初的资金为 +，于是 x5D = + ；
关于项目A的投资额规定:
x1A ≥ 40000y1A ，x1A ≤ 200000y1A，200000是足够大的数；
保证当 y1A = 0时， x1A = 0 ；当y1A = 1时，x1A ≥40000
关于项目B的投资额规定:
x3B ≥ 30000y3B ，x3B ≤ 50000y3B ；
保证当 y3B = 0时， x3B = 0 ；当y3B = 1时，
50000 ≥ x3B ≥ 30000
关于项目C的投资额规定:
x2C = 20000y2C ，y2C = 0，1，2，3，4
3)目标函数及模型：
Max z = + + +
. x1A+ x1D = 100000；
x2A+x2C+x2D = ；
x3A+x3B+x3D = + ；
x4A+x4D = + ；
x5D = + ；
x1A ≥ 40000y1A
x1A ≤ 200000y1A
x3B ≥ 30000y3B
x3B ≤ 50000y3B
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)
对于0-1整数规划，由于变量的取值为0或1，所以一个很自然的求解方法就是：穷举法，即
排出全部变量为0或1的全部组合，比较每一个可能的组合的目标函数值，选择最优解。
该方法存在的问题：当问题较大时，计算时间较长，因而计算效率不高。
比如0-1规划问题有n个决策变量，因而可能的组合(解)为：2n。当n较大时，要比较所有的解几乎不可能。
0-1整数规划的解法
隐枚举法：只检查变量取值组合的一部分，就能求得问题的最优解的方法。
对于最大化问题，一旦发现一个可行解(0,1组合)，代入目标函数，得到的目标函数值就构成了问题的下界，这样就可以产生一个过滤条件
对于目标函数值小于b的组合，就不需要再检验它的可行性。所以在检验过程中，每发现一个比前面更好的可行解(目标函数值更大)就要替换原来的过滤条件，以大大减少检验次数，使最优解能够被较快地发现。
0-1整数规划的解法
例6：
(0)
(1)
(2)
(3)
(4)
(5)
过滤条件
阅读P90例4
(x2,x1,x3)
Z值
约束
条件
Z过滤值
①
②
③
④
（0,0,0)
（0,0,1)
（0,1,0)
（0,1,1)
（1,0,0)
（1,0,1)
（1,1,0)
（1,1,1)
所以，该问题的最有解为（0，1，1），最优值为8
5
3
8
-2
3
1
6
√
0
√
√
√
0
√
√
√
√
5
√
√
√
√
8
5
8
8
8
8
第一步
第二步
第三步
指派问题的数学模型为：
=1 i=1,…,m
=1 j=1,…,m
xij=
匈牙利法主要用于解决指派问题，指派问题是一种特殊的0-1规划。
指派问题的匈牙利解法
.
例7. 指派授课问题，现有A、B、C、D、E五项任务，需由甲、乙、丙、丁、戊五人完成，并且规定：
每人只完成且只完成１项任务。
每项任务必须且只需１人完成。
五人分别完成每项任务所需时间如下表：
A
B
C
D
E
甲
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
求如何安排任务才能使所花费的时间最短？
指派问题最优解的性质
若从价值系数矩阵C=(cij)m×n的某行或某列各元素分别减去一个常数K，得到一个新的矩阵C’=(c’ij)m×n，那么以C’和C为系数矩阵的两个指派问题有相同的最优解
解释：
假设C的第r行的每个元素都减去常熟K，那么以C’作为价值系数矩阵的指派问题目标函数为
Z和Z’具有相同的最优解！！
匈牙利算法的原理：匈牙利数学家康尼格提出该方法
在上述指派问题最优解的性质中，通常，K值取行或列的最小元素，使得新价值矩阵的元素都是非负，且行(列)中都含有零元素。
如果能够找到一个可行解，其非零变量所对应的价值系数全部为0，从而目标函数值Z’也等于0。
由c’ij 和xij的非负性可知，这样的解就是新的指派问题的最优解，同时也是原指派问题的最优解。
也就是说若存在一组位于C’的不同行，不同列的n个零元素，只要令其对应于这些零元素位置的变量为1，其它位置对应的变量取值为0，这样构成的解就是原问题的最优解。
指派问题的关键就是寻求产生这组不同行不同列零元素的方法。匈牙利数学家康尼格发展并证明了这种方法，简称匈牙利算法
矩阵中独立0元素定理(匈牙利数学家康尼格)
矩阵中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。
指派问题的解法
1. 对指派问题的系数矩阵进行变换，使得各行各列都出现0元素
(1) 从系数矩阵的每行元素中找到该行的最小元素；
(2) 再从所得的系数矩阵的每列元素中减去该列的最小元素。
－4
－7
－6
－6
－6
－1
－3
例8
min
min
2. 进行指派，以寻求最优解
(1) 从只有1个0元素的行(列)开始，给该0元素加圈记作○，然后划去○所在的列(行)的其他0元素记作"\"
(2) 给只有1个0元素的列(行)的0元素加圈○，然后划去○所在的行(列)的其他0元素，记作"\"
(3) 反复进行(1)(2)直到所有的0元素都被加圈或划掉为止
(4) 若○元素的数目等于矩阵的阶数，则指派问题的最优解已经找到，加圈的0对应的最优指派，若小于则转入下第三步
所以最优解为：
例9
圈的个数：5
矩阵阶数：5
3. 作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的0元素，可以按照下面的步骤进行
(1)对没有○的行打√；
(2)对已打√的行中所含的"\" 元素的列打√；
(3)再对打有√的列中含○元素的行打√；
(4)重复(2)(3)直到得不出新的打√的行列为止
(5)对没有打√的行划一横线，有√的列画一条纵线；如果直线数等于矩阵阶数则已得到最优解，如小于则必须变换当前的系数矩阵，为此需要转入第4步。
例10
√
√
√
直线数4，矩阵阶数为5：不是最优解
圈的个数4，矩阵阶数为5
4.对系数矩阵变换
对系数矩阵进行变换的目的是增加0元素，所以在没有被划去的元素中找出最小的元素，将没有被划去的元素都减去该最小元素，划去一次的元素不变，划去两次的元素加上该最小元素，得到新的系数矩阵，转入2，重复进行直到得到最优解为止。
注：指派问题的系数矩阵经过变换后得到的新矩阵中，若存在某些0元素所在的行和列都有两个或者两个以上的0元素，则该指派问题就会有多重解。
最优解：划圈的个数等于矩阵的阶数。
例9
用匈牙利算法求解例8
－4
－7
－6
－6
－6
－1
－3
所以最优解为：
Z=7+9+6+6+6=34
√
√
√
课堂练习：用匈牙利算法求解例7
A
B
C
D
E
甲
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
特殊的指派问题
1. m与n不相等
若m<n，虚设n-m个工人；若m>n，虚设m-n项工作，使工作数与人数相等，相应的系数为0。
B1
B2
B3
B4
A1
12
7
9
7
A2
8
9
6
6
A3
7
17
12
14
A4
15
14
6
6
A5
4
10
7
10
B1
B2
B3
B4
B5
A1
12
7
9
7
0
A2
8
9
6
6
0
A3
7
17
12
14
0
A4
15
14
6
6
0
A5
4
10
7
10
0
2.最大化问题
转化成最小化指派问题，对目标函数系数变为M-cij，求对应的最小化指派问题。
因此，Z最大时，Z‘最小。从而Z’最小时的解即为原问题的最优解
3.一个人可做几项工作的指派问题
若某人可做几件事，则可将该人化作相同的几个"人"来接受指派，这几个“人”做同一件事的费用系数当然都一样。
B1
B2
B3
B4
A1
12
7
9
7
A2
8
9
6
6
A3
7
17
12
14
B1
B2
B3
B4
A1
12
7
9
7
A2
8
9
6
6
A3
7
17
12
14
A1'
12
7
9
7
A1"
12
7
9
7
A1可以同时做三件事
4. 某项工作一定不能由某人做的指派问题
若某事一定不能由某人做，则可将相应的费用系数取作
足够大的数M。
B1
B2
B3
B4
A1
12
7
-
7
A2
-
9
6
6
A3
7
17
12
14
B1
B2
B3
B4
A1
12
7
M
7
A2
M
9
6
6
A3
7
17
12
14
A1不能做B3
A2不能做B1
4. 某项工作一定不能由某人做的指派问题
若某事一定不能由某人做，则可将相应的费用系数取作
足够大的数M。
B1
B2
B3
B4
A1
12
7
-
7
A2
-
9
6
6
A3
7
17
12
14
B1
B2
B3
B4
A1
12
7
M
7
A2
M
9
6
6
A3
7
17
12
14
A1不能做B3
A2不能做B1
