第四章：特殊的线性规划
整数规划
本章的主要内容：
理解整数规划的基本概念 掌握分枝定界法的思想和方法 掌握0-1变量的含义和用法 掌握指派问题的求解方法
4.1 整数规划问题的提出
整数规划的应用背景
4.1 整数规划问题的提出
决策问题中经常有整数要求，如人数、件 数、机器台数、货物箱数……如何解决？ 四舍五入不行，枚举法太慢
求解整数规划的分枝定界法
思路：分枝和定界两部分： 分枝：切割可行域，去掉非整数点。 一次分枝变成两个可行域，分别求最 优解 定界：松弛问题最优解——上界；IP 问题的任意可行解——下界，不断减 小上界和增加上界，最终的最优解。
对于最大化问题 ZZi≤ Z*≤ Z0Z 对于最小化问题 ZZ0≤ Z*≤ Zi Z
是IP问题的上界,记作 Z 0 Z
x1 0,x2 0 Z=0，是的一个下界 。
分枝定界法（续）
(第一次分枝前）
5
5x1 9x2 ≤44
4
3
Z x1 x2
2
1
6x1 2x2 ≤17
（第一次分枝后）
x2
5
4
5x1 9x2 ≤ 44
3
Z x1 x2
2
1
6x1 2x2 ≤17
x1
0
例1. 求解整数规划A
max Z x1 x2 6x1 2x2 ≤ 17
(1) (2)
5x1 x1, x2
9x2 ≤ ≥0
44
(3) (4)
x1, x2为整数
(5)
解：先不考虑整数要求，解相应的 LP问题，得： x 1 1 .4 7 7 ,x 2 4 .0 6 8 ,Z 0 5 .5 4 5
因子问题B3的解中所有变量均为整数，因 此它的目标函数值Z 3 5 可取为 Z ，由于它 大于Z2 4.5，因此没有必要对子问题B2进行 分枝。于是可以断定Z3 ZZ* 5。子问题B3 的解 x1 1,x2 4为最优整数解。
整数规划图解法
x2
3
2
1
B
A
1 2 3 4 5 6 7 x1
图解法的启示
A（4.8，0）点是LP问题的可行解，不是 IP问题的可行解，B（4，1）才是IP的最 优解
纯整数规划可行解是可行域中的整数点 非整数点不是可行解，对于求解没有意
义，故切割掉可行域中的非可行解，不 妨碍整数规划问题的优化 IP问题的最优解不优于LP问题的最优解
到现场的限制，可得到如下模型
m in Z x1 x2 x3 x4 x5 x6
x1 x 2
≥1
x1
x2
x6 ≥ 1
s
.t
.
x3 x4 x3 x4 x5
≥1 ≥1
x4 x5 x6 ≥ 1
x2
x5 x6 ≥ 1
x i 取 0 或 1， i 1 , , 6
4.2 整数规划的求解方法
所谓整数规划，就是指决策变量有整数要 求的数学规划问题。
问题分类：纯整数规划、混合整数规划、 0-1整数规划
专门方法：分枝定界法、割平面法、隐枚 举法、匈牙利法
应用举例1：投资问题
项目
5个投资项目；600 万元资金，投资受 1
到约束：
2
(1) 项目1、2和3至少一项被
选中；
(2) 项目3和4只能选一项；
费用。条件：
区
必须保证在城区任何地方
四 区
28 32
12
0
发生火警时，消防车能在
15分钟之内赶到现场。各 区之间消防车行驶的时间
五 区
27 17
27
15
0
见右表。
请确定设站方案。
六 20 10 21 25 14 0 区
布点问题的数学模型：
设01为决策变量，当表示i地区设站，表 示i地区不设站。这样根据消防车15分钟赶
210x1 300x2 100x3 130x4 260x5 ≤600
s.t.xx13
x2 x4
x3 1
≥1
x5 ≤x1
xi取0或1，i 1, ,5
应用举例2：背包问题
目标：在不超过一定重量的前提下，使所携 带物品的重要性系数之和最大 。
例：登山队员需携带的物品及每一件物品 的重量和重要性系数见下表。假定允许携带 的最大重量为25千克，试确定一最优方案。
继续对子问题B1和B2进行分枝。
因为Z1 ＞Z2，因此先将B1再分为两枝。增加条 件 x2≤4,x2≥5 。前者称为子问题B3，后者 称为子问题B4。在图中再舍去之间的可行域， 再进行第二次迭代。得到的最优解为
子问题B3， x11,x24,Z35 ； 子问题B4无可行解。
分枝定界法（续2）
分枝定界法、隐枚举法、匈牙利法
4.2 整数规划的求解方法
在一般情况下，单纯形法求得的解并不能
保证是整数最优解。
例：求整数规划
maxZ 20x1 10x2
52xx11
4x2 5x2
≤24 ≤13
x1, x2 ≥0且为整数
求解其松弛问题，很容易得出最优解为 x14.8,x2 0, maxZ96 。
12 3 4
123 4
B1 B2
子问题B1，x 1 1 ,x 2 4 .3 3 3 ,Z 1 5 .3 3 3 子问题B2，x12 ,x22 .5 ,Z 24 .5
分枝定界法（续）
因为Z1 ＞Z2 ，故将 Z 改为5.333，那么必存在最 优整数解，得到Z * ，并且0≤Z*≤5.333 。
可通过计算每一物品的重要性系数和重量 的比值ci/ai来解决。
应用举例3：布点问题
共同目标：满足公共要 求，布点最少，节约投
地一二三四五六 点区区区区区区
资费用。
一0
学校、医院、商业区、消防队 区
等公共设施的布点问题。
二 10 0
例：某市6个区，希望设 区
置最少消防站以便节省 三 16 24 0
数据 物品 项目
食品 氧气
冰镐
绳索
帐篷
照相器材 通信设备
5 重量(千克) 5 2 6 12 2
4
重要系数 20 15 18 14 8 4 10
背包问题的数学模型
解：设01变量表示携带物品i，表示不携 带物品i，则问题可写为
m axZ20x115x218x314x48x54x610x7 s.t. 5x15x2x2 i取 x30 或 6x1 4， 1 i2 x15,2 ,2x,674x7≤ 25
3
(3) 项目5选中的前提是1必
须被选中。
4
问如何投资才能使
收益最大？
5
投资额(万 元)
210
期望收益 (万元)
150
300
210
100
60
130
80
260
180
投资问题的数学模型：0－1规划
设01变量为决策变量，即xi=1表示项目i被选中， xi=0表示项目i被淘汰，则模型可表示为
max Z 150x1 210x2 60x3 80x4 180x5