《天津大学运筹学3整数规划课件》由会员分享，可在线阅读，更多相关《天津大学运筹学3整数规划课件（27页珍藏版）》请在金锄头文库上搜索。
1、第三章 整数规划Integer Programming,运 筹 学Operations Research,3.1 整数规划问题与模型 3.2 整数规划解法,3.1 整数规划问题与模型,一、整数规划问题实例,例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运受限制如下表：,问两种货物各托运多少箱，可使获得利润最大？,例2 投资项目选择问题 现有资金总额为B，可供选择的投资项目有n个，项目j所需投资和预期收益分别为aj和cj。此外，有三个附加条件： （1）若选择项目1，就必须同时选择项目2，反之，则不一定； （2）项目3和4中至少选择一个； （3）项目5、6和7中恰好选择两个
2、。 应怎样选择投资项目，才能使总预期收益最大？,例3 运动员选拔问题（指派问题） 甲、乙、丙、丁是4名游泳运动员，他们各种姿势的100m游泳成绩见下表，为组成一个4*100m混合泳接力队，怎样选派运动员，方使接力队的游泳成绩最好？,例4 固定费用问题 某工厂为生产某种产品，有3种不同的生产方式可供选择。设第j种生产方式的固定成本为kj，可变成本为cj。若不考虑其他约束，建立使总成本最小的规划模型。,例5 背包问题 一个徒步旅行者要在背包中选择一些最有价值的物品携带，他最多能携带115kg的物品。现共有5件物品，分别重54kg、35kg、57kg、46kg、19kg，其价值依次为7、5、9、6、
3、3。问该旅行者携带那些物品，使总价值最大?,练习 某钻井队要从s1, s2, s10（相应的钻探费用为c1, c2, c10 ）10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小，且要满足下列限制条件： （1）或选择s1，或选择s8； （2）选择了s3或s4就不能选择s5，反过来也一样； （3）在s5, s6, s7, s8中最多只能选择两个。 建立这个问题的整数规划模型。,二、整数规划模型,一般形式：,整数规划一般可以分为三类：,1）纯整数规划：全部决策变量都限定取整数； 2）混合整数规划：部分决策变量为整数，即规划模型中变量一部分取整数，其余部分是连续变量； 3）0-1整数规划：不
4、仅限定决策变量取整数，而且只允许取0和1两个值。,3.2 整数规划解法,一、整数规划问题的解,松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。,（1）整数规划问题的可行解是松弛问题的可行解吗？ （2）松弛问题的最优解就是整数规划问题的最优解吗？ （3）松弛问题的最优解经过化整处理后就是整数规划问题的最优解吗？,5x1+4x2=24,2x1+5x2=13,20 x1+50 x2=96,分支定界解法：纯整数规划、混合整数规划 割平面解法：基于单纯形法，收敛慢 0-1整数规划求解：枚举法、隐枚举法,最优解不一定在顶点上达到 最优解不一定是松弛问题最优解
5、的邻近整数解 整数可行解远多于顶点，枚举法不可取,二、分支定界法,设有最大化的整数规划问题A， 与它相应的线性规划问题为B， 求解问题B 若B的最优解不符合A的整数条件，则B的最优值一定为A最优值Z*的上界，而A的任意可行解的目标函数值将是Z*的下界。 分支定界法就是将B的可行域分成子区域（称为分支方法）的方法，通过减小最优值的上界和增大最优值的下界最终得到最优值。,分支,边界,例6 求解下列整数规划。,9x1+7x2=56,7x1+20 x2=70,40 x1+90 x2=356,松弛问题B最优解： X0=(4.81，1.82)T， z0=356 整数问题A最优目标： 0 z* 356,对B
6、问题增加两个约束条件：,问题B1,问题B2,0 z* 349,对B1问题增加两个约束条件：,340 z* 341,问题B3,问题B4,对B2问题增加两个约束条件：,z* = 340,问题B6,问题B5,z* = 340,0 z* 356,0z* 349,340z* 341,分支定界法求解步骤总结：,整数规划问题问题A；其松弛问题问题B 分三种情况： （1）B没有可行解，这时A也没有可行解，停止。 （2）B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解。 （3）B有最优解，但不符合A的整数条件，记它目标函数值为最优值上界，观察取下界值。, 分支 在中选择一个不符合整数条件的变量xj，
7、其值为bj， bj 表示小于 bj 的最大整数，构造两个约束条件。,将此两个约束条件加入B，在不考虑整数条件的情况下，求解两个后继问题B1和B2。, 定界 以每个后继问题为一分枝标明求解结果，与其他问题解的结果中，找出目标函数最大者作为新的上界； 从已符合整数条件的各分支中，找出目标函数值最大者作为新的下界，若无，下界仍为零。, 比较与剪支 各分枝的最优目标函数中若有小于下界者，则剪掉这枝，此后无需再考虑； 若大于下界，且不符合整数条件，则重复第一步，直至找到最优解为止。,三、0-1型整数规划问题的求解,方法：,枚举法：将全部解列出，验证约束，比较目标 2n个组合（m个约束+1个目标函数）,隐枚举法：找出一个可行解，计算其目标； 由此确定一个过滤条件，再枚举。,例7 求解下列0-1整数规划。,(0) (1) (2) (3) (4),作业,（1）P131：5.2。 （2）P132：5.4。 （3）P132：5.6（1）。,
