解：设在第时段开始上班的人数为x，则minz=x+x+x+x4+xsxi≥10X+x2 ≥8Xi+X2+X ≥9X+X2+x+x4≥11X2+X3+x4+xs ≥13X +4 +xs ≥8X4 +x ≥ 5Xs ≥3Xi,X2,X3,X4,Xs≥0,且为整数
解：设在第j时段开始上班的人数为 ，则 j x + + + + + + + + + + + + = + + + + , , , , 0, 3 5 8 13 11 9 8 10 min 1 2 3 4 5 5 4 5 3 4 5 2 3 4 5 1 2 3 4 1 2 3 1 2 1 1 2 3 4 5 x x x x x x x x x x x x x x x x x x x x x x x x x z x x x x x 且为整数
解的特点整数线性规划及其松弛问题比较，前者的最优解的目标函数值不会优于后者的例：考虑下面的整数规划问题max z = xi +4x,-2xi +3x2 ≤3Xi + 2x2 ≤8Xi,X2 ≥O 且取整数
解的特点 整数线性规划及其松弛问题比较，前者 的最优解的目标函数值不会优于后者的。 例：考虑下面的整数规划问题 + − + = + , 0 2 8 2 3 3 max 4 1 2 1 2 1 2 1 2 x x x x x x z x x 且取整数
从图上分析：整数规划最优解A P A1B012345678
从图上分析： 0 1 2 3 4 5 6 7 8 B P C A1 A2 A3 A4 * A 整数规划 最优解
2.分支定界法分支定界法是枚举法基础上的改进分支定界法的关键是分支和定界思路：利用其松弛问题的最优解（值）来分支定界
2.分支定界法 分支定界法是枚举法基础上的改进。 分支定界法的关键是分支和定界。 思路：利用其松弛问题的最优解（值）来 分支定界
例：求解整数规划问题A整数规划问题A松弛问题Bmax z = 40x, +90x,max z = 40x, +90x,9x +7x2 ≤569x + 7x2 ≤567x + 20x, ≤ 707xi + 20x, ≤ 70xi,x≥0 且为整数Xi,x ≥0设问题A的最优目标函数值为z=Z初始上界
例：求解整数规划问题A + + = + , 0 7 20 70 9 7 56 max 40 90 1 2 1 2 1 2 1 2 x x x x x x z x x 且为整数 松弛问题B 设问题A的最优目标函数值为 z = 。 z * + + = + , 0 7 20 70 9 7 56 max 40 90 1 2 1 2 1 2 1 2 x x x x x x z x x 整数规划问题A 初始上界