文档介绍：Chapter 6 Integer Programming 整数规划
§1 Graphical Method for Integer Programming
整数规划的图解法
§2 Branch and Bound for Pure IPs
整数规划的分枝定界法
§3 Binary integer programming 0-1整数规划
§4 Assignment Problems 指派问题
求整数解的线性规划问题,不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的,而要用整数规划的方法加以解决。
在整数规划中,如果所有的变量都为整数,则称为纯整数规划问题;如果有一部分变量为整数,另一部分变量可以不取整数,则称之为混合整数规划问题。在整数规划中,如果变量的取值只限于0和1,这样的变量我们称之为0-1变量。在纯整数规划和混合整数规划问题中,如果所有的变量都为0-1变量,则称之为0-1规划。
例1 TBA 航空公司飞机采购问题Airlines Problem
小飞机
大飞机
可用资金
每架飞机的年净利润
$1百万
$5百万
每架飞机的成本
5百万
50百万
$100百万
最大购买量
2
—
线性规划模型
设Let S = 购买的小飞机数 Number of small airplanes to purchase L = 购买的大飞机数Number of large airplanes to purchase Maximize Profit z = S + 5L ($millions) subject to 5S + 50L ≤ 100 ($millions) Capital Available S ≤ 2 Max Small Planes: S ≥ 0, L ≥ 0. 且为整数
可分规划 Separable Programming
线性规划的可分性假设(divisibility Assumption of LP)
线性规划的决策变量可以在满足一定约束条件下取所有实数,包括小数。因此决策变量不一定是整数,决策变量代表各种可能的方案(活动水平).
违背可分性假设
当要求决策变量必须取整数时,就不再符合可分性假设,
图解法 Graphical Method for Integer Programming
当一个整数规划问题只有两个决策变量时,可用图解法求解
首先去掉整数约束,得到松弛规划。确定松弛规划的可行域。根据目标函数确定等值线,将等值线沿着梯度的方向移动。.
当等值线平移到可行域内的最后一个整数点,使目标函数取得最优值时,这个整数解即为最优解。
用图解法求例1最优解
图解
(0, 2)整数规划最优解,利润等于10
Max z = S + 5L
. 5S + 50L ≤ 100
S ≤ 2
最优解
利润=11=S+5L
取整解
利润=7
购买的小飞机数
大飞机数
§1 整数规划的图解法
例1. 某公司拟用集装箱托运甲、乙两种货物,这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。 P162
甲种货物至多托运4件,问两种货物各托运多少件,可使获得利润最大。
解:设x1 、 x2分别为甲、乙两种货物托运的件数,建立模型
目标函数: Max z = 2x1 +3 x2
约束条件: .
195 x1 + 273 x2 ≤1365
4 x1 + 40 x2 ≤140
x1 ≤4
x1,x2 ≥ 0 为整数。
如果去掉最后一个约束,就是一个线性规划问题。利用图解法,
货物
每件体积
(立方英尺)
每件重量
(百千克)
每件利润
(百元)
甲
乙
195
273
4
40
2
3
托运限制
1365
140
得到线性规划的最优解为x1=, x2=,。
由图表可看出,整数规划的最优解为x1=4, x2=2,目标函数值为14。
性质1:任何求最大目标函数值的纯整数规划或混合整数规划的最大目
标函数值小于或等于相应的线性规划的最大目标函数值;任何求最小目
标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相
应的线性规划的最小目标函数值。
1
2
3
4
1
2
3
2x1+3x2 =
x1
x2
2x1+3x2 =14
2x1+3x2 =6
o
§2 Branch and Bound Technique for Pure IPs整数规划的分枝定界法
分枝定界法是求解整数规划的一种常用的有效的方法,它既能解决纯整数规划的问题,又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界