例2求解下面整数规划 maxZ=40x+90x2 1) 8 9x1+7X2=56 9x+7x≤56 (2) Z=40x+90x2 7x+20x2≤70 (3) X1,X2≥0 (4) X1,X2整数 7x1+20x2=70 (5) 解：先不考虑条件（⑤），求解相 10 X 应的线性规划问题L,得最优解 x=4.81,X2=1.82,Z0=356 （见图) 求解线性规划L1、L2 该解不是整数解。选择其中一个 得最优解为： 非整数变量，如x=4.81,对问题 问题L1: 问题L2: L分别增加约束条件： L+X1≤4 L+X1≥5 X1≤4，X1≥5 x1=4.00 X=5.00 将问题L分解为两个子问题L,L? (分枝)，也就是去掉问题L不含 x2=2.10 x2=1.57 整数解的一部分可行域，将原可 Z=349 Z2=341 行域D变为D1、D2两部分（如图）例2 求解下面整数规划 maxZ=40x1+90x2 ⑴ 9x1+ 7x2 ≤56 ⑵ 7x1 +20x2 ≤70 ⑶ x1 ,x2 ≥0 ⑷ x1 ,x2 整数 ⑸ 解：先不考虑条件⑸，求解相 应的线性规划问题L，得最优解 x1=4.81，x2=1.82，Z0=356（见图） x2 8 0 6 4 10 x1 9x1+ 7x2=56 7x1+20x2=70 Z=40x1+90x2 该解不是整数解。选择其中一个 非整数变量，如x1=4.81，对问题 L分别增加约束条件： x1≤4，x1≥5 将问题L分解为两个子问题L1，L2 （分枝），也就是去掉问题L不含 整数解的一部分可行域，将原可 行域D变为D1、D2两部分（如图）。 4 D1 D2 求解线性规划L1、L2 得最优解为： 问题L1： L+ x1≤4 问题L2： L+ x1≥5 x1=4.00 x2=2.10 Z1=349 x1=5.00 x2=1.57 Z2=341