运筹学第5章课件.ppt

第五章 整数规划;第五章 整数规划;§5.1 整数规划问题; 排班要符合每周连续工作五天、休息两天的规定。如何排班可使用人最少?;解：设 xi 为每周第 i 天开始上班的人数： min: z = x1+x2+x3+x4+x5+x6+x7 s.t. x1 +x4+x5+x6+x7 ? 17 x1+x2 +x5+x6+x7 ? 13 x1+x2+x3 +x6+x7 ? 15 x1+x2+x3+x4 +x7 ? 19 x1+x2+x3+x4+x5 ? 14 x2+x3+x4+x5+ x6 ? 16 x3+x4+x5+ x6+x7 ? 11 xi ? 0 i = 1, 2, . . . , 7;LP问题的解： x = (1.3, 3.3, 2, 7.3, 0, 3.3, 5) z = 22.3 一个取整数的解： x = ( 2, 4, 2, 8, 0, 4, 5) z = 25 最优整数解： x = ( 4, 4, 2, 6, 0, 4, 3) z = 23 ;例5.2 max: z = x1 + x2 s.t. x1 + 2x2 ? 8 2x1 - x2 ? 4 x1, x2 取非负整数;整数规划 = 线性规划 + 整数约束； 放松整数约束的线性规划问题为整数规划的线性规划松弛问题; 整数规划是比线性规划松弛问题约束得更紧的问题, 它的可行域是其线性规划松弛问题可行域的一个子集; 整数解的数目远少于线性规划的解，只要可行域有界，整数解的数目有限; 整数规划的求解难度远大于线性规划。;整数规划分类 纯整数规划：所有决策变量取整数值； 混合整数规划：部分决策变量取整数值； 0-1整数规划：整数变量只能取0或1。;1) 穷举法：方法简单，只可解小问题，计算量很大；对0-1整数规划，计算量为2n，按指数增长： ;2) 四舍五入法 例5.3 max: z = 3x1 + x2 s.t. 2x1 + x2 ? 5 2x1 +3x2 = 5 x1, x2 为非负整数 松弛问题解: x = (2.5, 0), 四舍五入无法得到可行解; 整数最优解: x = (1, 1) 。; 例5.4 max: z = x1 + 5x2 s.t. x1 + 10x2 ? 20 x1 ? 2 x1, x2 为非负整数 松弛问题解：x = (2, 1.8) z = 11 四舍五入解：x = (2, 2.0) 不是可行解； x = (2, 1.0) z = 7 整数最优解：x = (0, 2) z = 10 ; ;3) 分支定界法: 计算效率高, 应用广泛; 4) 割平面法: 有理论意义, 但计算效率较低； 5) 启发算法: 效率高, 但不能保证找到最优解, 可解大规模问题。;第五章 整数规划; 分支定界法实质上是一种有哪些信誉好的足球投注网站方法，其基本思想是根据某种有哪些信誉好的足球投注网站策略将原问题的可行域分解为越来越多、但越来越小的子域，并比较各个子域的整数解的大小，直到找到最好的整数解或证明不存在整数解。; 线性规划松弛问题与整数规划问题的界 松弛问题的解是整数规划最优解的一个界; 线性规划松弛问题的最优解值一定不劣于整数规划最优解值; 若松弛问题有整数解, 该解即为整数规划最优解; 最优整数解不会优于松弛问题的解，因此松弛问题的解是整数规划的一个不优界;;整数规划的解与界 如果已经找到一个整数解，最优解一定不劣于该解, 因此该解成为整数规划的一个不劣界。 若 z0 为松弛问题解 ，zi 为其最好整数解， z*为最优解，zL为下界，zU 为上界，则有以下关系： zL = zi ? z* ? z0 = zU （最大化） zL = z0 ? z* ? zi = zU （最小化）;;分枝定界算法举例;;子问题1 max: x1 + x2 s.t. 6x1 + 2x2 ? 17 5x1 + 9x2 ? 44 x1 ? 1