1、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 指派问题 求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。n 在整数规划中，如果所有的变量都为整数，则称为 纯整数规划问题 ；如果有一部分变量为整数，另一部分变量可
2、以不取整数，则称之为 混合整数规划问题 。在整数规划中，如果变量的取值只限于 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 purchaseL = 购买的大飞机数 Number of large a
3、irplanes to purchaseMaximize 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)线性规划的决策变量可以在满足一定约束条件下取所有实数，包括小数。因此决策变量不一定是整数，决策变量代表各种可能的方案 (活动水平 ).违背可分性假设当要求决策变量必须取
4、整数时，就不再符合可分性假设 ，图解法 Graphical Method for Integer Programmingn 当一个整数规划问题只有两个决策变量时，可用图解法求解n 首先去掉整数约束，得到松弛规划。确定松弛规划的可行域。根据目标函数确定等值线，将等值线沿着梯度的方向移动。 .n 当等值线平移到可行域内的最后一个整数点，使目标函数取得最优值时，这个整数解即为最优解。用图解法求例 1最优解图解(0, 2)整数规划最优解 ,利润等于 10Max z = S + 5L S.T. 5S + 50L 100 S 2最优解利润 11 S 5L取整解利润 7购买的小飞机数大飞机数1 整数规划的图
5、解法例 1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。 P162甲种货物至多托运 4件，问两种货物各托运多少件，可使获得利润最大。解： 设 x1 、 x2分别为甲、乙两种货物托运的件数，建立模型目标函数： Max z = 2x1 +3 x2 约束条件： s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140x1 4x1， x2 0 为整数。如果去掉最后一个约束，就是一个线性规划问题。利用图解法，货物 每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制 1365 140
6、得到线性规划的最优解为 x1=2.44, x2=3.26,目标函数值为 14.66。由图表可看出，整数规划的最优解为 x1=4, x2=2,目标函数值为 14。性质 1： 任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。1 2 3 4123 2x1+3x2 =14.66x1 x2 2x1+3x2 =142x1+3x2 =6o2 Branch and Bound Technique for Pure IPs整数规划的分枝定界法分枝定界法是
7、求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。分枝定界法步骤第一步 : 将原规划称为问题 A0.去掉整数约束得到相应的松弛规划 B0第二步 ：求解 B0 ，有以下几种情况： (1) B0无解 A0无解，停止计算(2) B0 最优解为整数，则 B0 最优解为 A0最优解，停止计算(3) B0 最优解不是整数解，则转入下一步第三步 ：确定初始上界 和下界 ，记 B0 最优值为用观察法找到 A 0.的一个整数解，此解的目标函数值记为第四步 ：分枝（将问题 B0分枝），在的最优解中，任选一个不符合整数条件变量xj bj 构造两个约束条件， xjbj ； xj bj 1；加到 B0中得到两个子规划 B1和 B2（两支）。第五步 ：比较与剪枝，对 B1和 B2求解，可得到以下情况：(1) 分枝无解 该分枝是树叶，剪枝。(2) 分枝最优解为整数，从该最优解的目标函数值与原来的 值中选最大的值作为新的 ，该分枝为树叶，剪掉
