整数线性规划问题
❖ 整数线性规划（ILP）具有下述形式
min c x
Ax b
s.t .
x
0,
x为
整数
❖ 0-1整数线性规划模型
min c x
Ax b
s.t.
xi
0或1; i
1,2,...,
n
❖ 混合整数线性规划
min c x
Ax b s.t.x 0,i 1,2,...,n
xi为整数,i 1,2,...,p
LP的可行集合
费用下降方向 LP问题的最优解
ILP问题的最优解
2. 解整数线性规划问题的困难性续
• 最优解不一定在顶点上达到 • 最优解不一定是松弛问题最优解的邻近整数解 • 整数可行解远多于松弛问题的顶点，枚举法不
可取
• 解ILP问题要远难于解松弛的LP问题 • 如果松弛的LP问题无解，显然原ILP问题无解。
1. 整数线性规划问题举例
❖ 例 某3.财1.团1有 B 万元的资金，有 n(n 2) 个可以考
虑的投资项目，假定每个项目最多投资一次。其中
第 j 个项目需投资金额为 b j 万元，将会获得的利润
为 c j 万元，问应如何选择项目才能使得获得的总 利润最大？
例3.1.1 投资决策问题
❖ 分析
• 变量—每个项目是否投资 x j 0或1 j 1,2...,n
• 约束—总金额不超过限制

bjxj B
j 1
• 目标—总收益最大
n
max c j x j j 1
例3.1.1 投资决策问题
❖ 数学模型
n
maxz c j x j j 1
s.t.
0
n
bj x j
j 1
B
x
j
0或1; j
1, 2..., n
旅行售货员问题
❖ 此外，运筹学还有一个著名的问题：
旅行售货员问题（TSP）
显示问题
旅行售货员问题（TSP）
2. 解整数线性规划问题的困难性
整数规划
min z c x Ax b
s.t.x 0, x为整数
松弛的线性规划问题
min z c x
s.t. xA x
0
b
可行解是松弛问题的可行解 最优值大于等于松弛问题的最优值
2. 解整数线性规划问题的困难性
反之，不一定成立。
• 如果松弛的LP问题无界呢？可以证明原ILP问题 也无界