因而不是解x.ppt

* * 3.1 整数规划问题的提出 3.2 分枝定界法 3.3 0-1型整数规划 3.4 指派问题 3 整数规划 3.1 整数规划问题的提出 在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题,称为整数规划(Integer Programming)或简称IP。 例1 某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下： 货物集装箱 体积(米3) 重量(百斤) 利润(百元) 甲 5 2 20 乙 4 5 10 托运限制 24 13 问两种货物各装运多少箱，可使获得利润最大？ 是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢？ 设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型如下： Max z＝20x1+10x2 (1) 5x1+4x2≤24 (2) 2x1+5x2≤13 (3) x1,x2≥0 (4) x1,x2为整数 (5) 它和线性规划问题的区别在于条件(5)。 此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)，因而不是可行解；如截断小数变为x1=4,x2=0，这当然满足所有约束条件，但不是最优解，因为对x1=4,x2=0有z＝80，而对x1=4,x2=1（也是可行解）有z＝90。因此要专门研究整数规划的解法。 分枝定界法是20世纪60年代由Land-Doig和Dakin等人提出的。这种方法既可用于纯整数规划问题，也可用于混合整数规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。 3.2 分枝定界法 设有最大化的整数规划问题R，与它相应的线性规划问题为R0，分枝定界法的做法是： (1)用观察法求R的一个可行解，其目标值便是R的最优目标值z*的一个下界z。 (2)求解R0，得R0的最优解x(0)和最优值z0。若x(0)符合R的整数条件，则显然x(0)也是R的最优解，结束；否则，以R0作为一个分枝标明求解的结果，z0是问题R的最优目标值z*的一个上界z。 (3)分枝。取目标函数值最大的一个枝Rs，在Rs的解中任选一不符合整数条件的变量xj，其值为bj，构造两个约束条件xj≤[bj]和xj≥[bj]+1。将两个约束条件分别加入问题Rs，得两个后继规划问题Rs1和Rs2。不考虑整数条件求解这两个后继问题，以每个后继问题为一分枝标明求解的结果。 (4)定界。在各分枝中找出目标函数值最大者作为新的上界z；从已符合整数要求的各分枝中，找出目标函数值最大者作为新的下界z。 (5)比较与剪枝。各分枝的最优目标函数值中如果有小于z者，则剪掉这一枝（用打×表示），即以后不再考虑了。若已没有大于z的分枝，则已得到R的最优解，结束；否则，转(3)。 例 求解问题 Max z=40x1+90x2 9x1+7x2 ≤ 56 7x1+20x2≤70 x1,x2≥0, 整数 R0: z0=356 x1=4.81 x2=1.82 R1:z1=349 x1=4.00 x2=2.10 R2:z2=341 x1=5.00 x2=1.57 R12: z12=327 x1=1.42 x2=3.00 x2≥3 R11: z11=340 x1=4.00 x2=2.00 R21: z21=308 x1=5.44 x2=1.00 R22: 无可 行解 x1 ≤4 x1 ≤1 x1≥5 x1≥2 问题R0为: Max z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1,x2≥0 问题R2为: Max z=40x1+90x2 9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≥ 5 x1,x2 ≥ 0 问题R1为: Max z=40x1+90x2 9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≤4 x1,x2≥0 x2 ≤2 问题R