运筹学4.doc

1 第四章整数规划教学目的和要求: 目的:使学生具备整数规划的基本知识,具有求解整数规划的基本能力。要求:理解整数规划的概念, 0-1 规划概念,指派问题概念,掌握分枝定界法,割平面法,匈牙利法。重点:整数规划,指派问题概念,分枝定界法,割平面法,匈牙利法。难点:分枝定界法,割平面法。教学方法:讲授法,习题法。学时分配: 6学时作业安排:见教材 P 102. 决策变量具有非负整数要求的线性规划称为整数规划, 若全部决策变量都要求是整数, 则称为纯整数规划。只有部分要求是整数的,则称混合整数规划。若每个决策变量只能取 0或 1, 则称为 0-1 规划。整数规划是特殊的线性规划,求解整数规划不能采用先求不考虑整数要求的最优解,再通过简单取整而得。第一节分枝定界法对于整数规划, 称不考虑其整数要求的线性规划为其对应的松弛问题, 分枝定界法是求解整数规划和 0-1 规划的常用方法。步骤如下: 1. 求解相应松弛问题: MaxZ=CX,AX=b,X ≥0, 若松弛问题的最优解不满足整数要求, 则从非整数的基变量 Xi =b' i 中任选一个变量,例如选 Xr =b' r 进行分枝。 2. 分枝:因Xr 要取整数, 故必有Xr ≤[b'r ]或Xr ≥[b'r ]+1 将原松弛问题分别增添上约束Xr ≤[b'r ]和Xr ≥[b'r ]+1 形成了两个互不相容的子规划, 也就是关于 Xr 的两个分枝。即① MaxZ=CX,AX=b, Xr ≤[b'r ],X≥0;② MaxZ=CX,AX=b, Xr ≥[b'r ]+1 ,X≥0 因在区域[b'r ]<Xr < [b'r ]+1 中不可能有整数规划的可行解,所以整数规划的所有可行解分别含在两个分枝中,反之只要求出各分枝中符合整数要求的最优解,经比较,就可得整数规划的最优解。 3. 定界:对于分枝 Xr ≤[b'r ] 相应的松弛问题,若其最优解为 X (r) ,最优值为 Zr ,则在这个分枝中,原整数规划的所有可行解目标函数值,都不会优于 Zr , 也就是说, Zr 是分枝 Xr ≤[b'r ] 中整数规划目标函数值的上界,对于分枝 Xr ≥[b'r ]+1 也具有同样的分析。 4. 剪枝:若在分枝 Xr ≤[b'r ] 中已经得到了符合整数要求的最优解 X (0) ,其目标函数值为 Z0 ,而在另一分枝 Xr ≥[b'r ]+1 中其上界不超过 Z0 ,则把这一枝剪掉。当第一次分枝后, 由相应的松弛问题仍不能得到符合整数要求的最优解, 则再任选一个非整数的变量进行分枝,直到查清所有的分枝,得到整数规划的最优解为止。例1 运用分枝定界法求解整数规划 Max Z=3X 1 +5X 2 满足 4X 1 +10X 2 ≤ 50 2X 1 - 5X 2 ≤1X1 、X2 ≥0 且为整数解:相应松弛问题的最优解如表 4-1 所示: Cj3500b CB XB X1 X2 X3 X4 3 X1 10 1/8 1/4 13/2 5 X2 01 1/20 -1/10 12/5 ?j 00 5/8 1/4 63/2 最优解 X * =(13/2 , 12/5) T, 最优值 Z * =63/2 。这个解不满足整数要求,对 X1 ,X2 都可进行分枝,这里选择 X2 =12/5 进行分枝。这两个分枝分别为: ① Max Z=3X 1