交通运筹学教学课件作者张文会第3章节整数规划课件

《交通运筹学教学课件作者张文会第3章节整数规划课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章整数规划IntegerProgramming1主要内容第一节整数规划的性质第二节整数规划的解法第三节分支定界法第四节割平面法第五节0-1规划2第一节整数规划的引出1、引例某公交车队决定，驾驶员每周连续工作5天后，连续休息2天，轮流休息。根据统计，车队每天需要的驾驶员人数如表所示。车队的调度应如何安排每天上班的驾驶员人数，使车队总的驾驶员最少？3表3-1所需驾驶员数统计表星期需要人数星期需要人数一139五132二132六120三138日121四1334解：设xj为休息两天后星期一到星期日开始上班的驾驶员数量，则这个问题的线性规划模型为：52、整数规划的特点与分

2、类（1）在很多实际问题中，全部或部分变量的取值必须是整数，如人或机器设备等不可分割。（2）此外还有一些问题，如要不要在某地建设工厂或指派某人去做某事，可选用一个逻辑变量x，令x=1表示在该地建厂或指派某人做事，x=0表示不在该地建厂或不指派某人做事，逻辑变量也是只允许取整数值的一类变量。63、整数规划的分类（1）纯整数线性规划（IP）：在一个线性规划中要求全部变量取整数值，或简称纯整数规划。（2）混合整数(线性)规划（MIP）：在一个线性规划中只要求一部分变量取整数值。74、用“凑整法”求解是否可行？有同学会认为，对整数规划问题的求解可以先不考虑对变量的整数约束，

3、作为一般线性规划问题来求解，当解为非整数时可用四舍五入或凑整方法寻找最优解。是否合适？是否可行？8例题：求下述整数规划问题的最优解9(3,3)(3,2)(4,3)(4,2)(4,1)，Z=14(3.25，2.5)2x1+3x2=14x1+0.5x2=4.53x1+2x2=0(4,1)，Z=142x1+3x2=1410如果不考虑x1、x2取整数的约束，用图解法求得最优解为(3.25，2.5)。由于x1、x2必须取整数值，实际上问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但(4，3)、(4，2)、(3，3)都不是可行解，(3，2)虽属可

4、行解，但代入目标函数得z=13，并非最优。实际上问题的最优解应该是(4，1)，z*=14。注意：(4，1)不是可行域的顶点，因此直接用图解法或单纯形法都无法找出整数规划问题的最优解来。这就要求研究解整数规划问题的特殊方法。115小结整数规划的可行域包含在其对应的一般线性规划可行域之内；整数规划的最优解可能不是其对应的一般线性规划的顶点；整数规划需要专门的求解方法；整数规划的最优解不会优于其对应的线性规划的最优解；既然不能通过凑整来求解，可以逐步将对应线性规划可行域中的非整数部分舍去。12第2节分枝定界法步骤：1、寻找替代问题并求解2、分枝与定界3、剪枝131、基本

5、思路：整数规划的最优解不会优于相应的线性规划的最优解。对于极大值问题，相应线性规划的最大值成为整数规划目标函数的上界。maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X为整数(B)(B)为(A)的松弛问题。（1）替代问题的确定14（2）替代问题的求解maxZ=CXAX=bX0(B)采用相应的方法（如图解法）求解出替代问题的最优解，观察其是否满足整数解的要求。如其最优解就为整数，则结束；如含有分数，则需要进行分支定界操作。15（3）分支与定界—增加约束如替代问题的解不符合整数条件，则需要对原问题进行分支。分支方法：假设替代问题的解为[i，i+1]之间

6、的一个数，则分成两支：一支增加约束xj≤i，另一支增加约束xj≥i+1；对上述两个问题进行求解：不考虑整数问题时，求解对应的线性规划问题，观察其最优解是否是整数，如不是，则继续分支定界，直到得到全部整数解为止。X*Xj*i+1i(C)(D)(B)Xji+1(B)Xji16maxZ=40X1+90X29X1+7X2567X1+20X270X1,X20X1,X2为整数例1：17解：先解该整数规划对应的松弛问题X*=4.8091.817Z*=355.890，上界Z*选X1分枝问题(2)(1)X14问题(3)(1)X15将[4,5]之间的非整数部分舍去18选

7、(2)继续分枝问题(4)(2)X22问题(5)(2)X23解为X1=4X2=2.1Z=349.0解为X1=5X2=1.571Z=341.39问题2问题319(1)4.8091.817355.890(2)42.1349.0(3)51.571341.39(4)42340(5)1.4283340327.12(6)5.4441340307.76(7)无解X14X15X22X21X22X23分支定界过程20第3节割平面法割平面法的基本思想：在整数规划问题的松弛问题中依次引进线性约束条件(称Gomory约束，高莫雷约束或割平面)，使问题的可行域逐步缩小。但每次

8、切割时，只