（P）两个子问题:(P,)MaxZ=4xi+3x2s. t. 3xj+4x2 ≤ 124xi+2x2 ≤ 9X1 ≤ 1X2 ≤ 2X1,X2≥ 0，整数用单纯形法可解得相应的（P，）的最优解（1，2）Z=10
（P1）两个子问题： （P3）Max Z=4x Max Z=4x1+3x2 s.t. 3x1+4x2 ≤ 12 4x1+2x2 ≤ 9 x1 ≤ 1 x2 ≤ 2 x1,x2 ≥ 0 , 整数 用单纯形法可解得相应的 用单纯形法可解得相应的（P3）的最优 解（1，2） Z=10
（P,）两个子问题:(P4) MaxZ=4xi+3x2S.t. 3xi+4x2 ≤ 124xi+2x2 ≤ 9X1 ≤ 1X2 ≥ 3X1,X2 ≥ 0，整数用单纯形法可解得相应的（P）的最优解Z=9(0, 3)
（P1）两个子问题： （P4）Max Z=4x Max Z=4x1+3x2 s.t. 3x1+4x2 ≤ 12 4x1+2x2 ≤ 9 x1 ≤ 1 x2 ≥ 3 x1,x2 ≥ 0 , 整数 用单纯形法可解得相应的 用单纯形法可解得相应的（P4）的最优解 （0，3） Z=9
P2:(2,1/2) Z=19/2X,≥2X,≤P:(6/5,21/10)Z-10(1,2)3:Z=111/10X,≤1Pi:(1,9/4)X,Z=43/4)Z=9(0,3)P4:原问题的最优解（1，2）Z=10
X1 ≥ 2 X2 ≤ 2 X1 ≤ 1 X2 ≥ 3 P1:(1,9/4) Z=43/4) P4: (0,3) Z=9 P2:(2,1/2) Z=19/2 P3: (1,2) Z=10 P:(6/5,21/10) Z=111/10 原问题的最优解 原问题的最优解（1，2） Z=10
nZcxjmaxZ =?j=1n考虑纯整数问题：-Za,x, =b, (i=1.2...m)(IP)jlx,≥0,(j=1.2.·m)且为整数nEcjxjmaxZ= j=1整数问题的松弛问题：[ - , - (-1-2. )(LP)j=1x, ≥0,(j=1.2..m)
⎪ ⎩ ⎪ ⎨ ⎧ ≥ = = = = ∑ ∑ = = 0,( 1.2 )且为整数 ( 1.2 ) ( ) max 1 1 x j m a x b i m IP Z c x j n j ij j i n j j j L 考虑纯整数问题： L ⎪ ⎩ ⎪ ⎨ ⎧ ≥ = = = = ∑ ∑ = = 0,( 1.2 ) ( 1.2 ) ( ) max 1 1 x j m a x b i m LP Z c x j n j ij j i n j j j L L 整数问题的松弛问题：
1、先不考虑整数约束，解（IP)的松弛问题（LP）可能得到以下情况之一：（1).若（LP）没有可行解，则（IP）也没有可行解，停止计算。(2)若（LP）有最优解，并符合（IP）的整数条件，则（LP）的最优解即为（IP）的最优解，停止计算。(3）若（LP）有最优解，但不符合（IP）的整数条件，转入下一步。为讨论方便，设（LP）的最优解为：X(0) = (bi,b.,...,b"....,b",0,..,0)目标函数最优值为Z()其中b(i=1,2..m）不全为整数
1、先不考虑整数约束，解( IP )的松弛问题( LP )， 可能得到以下情况之一： ⑴.若( LP )没有可行解，则( IP )也没有可行解，停止 计算。 ⑵.若( LP )有最优解，并符合( IP )的整数条件，则 ( LP )的最优解即为( IP )的最优解，停止计算。 ⑶.若( LP )有最优解，但不符合( IP )的整数条件，转 入下一步。为讨论方便，设( LP )的最优解为： 目标函数最优值为 Z .其中 ( 1,2, , )不全为整数 ( , , , , , ,0, ,0) (0) 1 2 (0) b i m X b b b b i T r m L L L L ′ = = ′ ′ ′ ′