62分枝定界法 思路:切割可行域,去掉非整数点。一次分枝 变成两个可行域,分别求最优解 例1.maxz=2000X1+1000X2 5X1+4X2≤24 21+5x≤13 X1,x2≥0且为整数 解:先不考虑整数要求,解相应的LP问题,得: X1=48x=0Z=9600不是可行解 z=9600是|P问题的上界,记为:Z=9600 OR3
OR3 6 6.2 分枝定界法 思路：切割可行域，去掉非整数点。一次分枝 变成两个可行域，分别求最优解 例1. maxZ=2000x1+1000x2 5x1+4x2≤24 2x1+5x2 ≤13 x1.x2 ≥0且为整数 解：先不考虑整数要求，解相应的LP问题，得： x1=4.8 x2=0 Z=9600 不是可行解 Z=9600是IP问题的上界，记为：Z=9600
分枝定界法(续) X1=4.8不符合要求,切掉45之间的可行域, 可行域变成两块,即原有约束条件再分别附加 约束条件x1≤4和x1≥5 原问题分解为两个 maxz=2000X1+1000X2 maxz=2000X1+1000X2 5X1+4X2≤24 5X1+4x2≤24 2x1+5X2s13(|P1)2×1+5X≤13(P2) X1≤4 X1≥5 X1,x2≥0且为整数 X1,x2≥0且为整数 OR3
OR3 7 分枝定界法（续） X1=4.8不符合要求，切掉4—5之间的可行域， 可行域变成两块，即原有约束条件再分别附加 约束条件x1 ≤4和x1 ≥5 原问题分解为两个 maxZ=2000x1+1000x2 maxZ=2000x1+1000x2 5x1+4x2≤24 5x1+4x2≤24 2x1+5x2 ≤13 ( IP1 ) 2x1+5x2 ≤13 (IP2) x1 ≤4 x1 ≥5 x1.x2 ≥0且为整数 x1.x2 ≥0且为整数