分支定界法 B:x1=3.57 35.7 B1:x1=4x1≥4 x2=7.14 x1 35.5 x2=6.5 35.7 B,:x,=3 二1=35.5 x2=7.6 =34.8 B3:x1=4.33 B 无可行解 35.3 35.3 <4 B5:x=4 XI 35 35 x2=5 35 5.x,=5 34 zs=35
35.7 7.14 : 3.57 0 2 1 = = = z x B x 35.5 6.5 : 4 1 2 1 1 = = = z x B x 34.8 7.6 : 3 2 2 2 1 = = = z x B x 35.3 6 : 4.33 3 2 3 1 = = = z x B x 无可行解 B4 z = 0 , z = 35 .7 35 .5 0 = = z z 35 .3 0 = = z z x1 ³ 4 3 x1 £ 6 x 2 £ 7 x 2 ³ 34 6 : 4 5 2 5 1 = = = z x B x x1 £ 4 x1 ³ 5 35 35 = = z z 35 5 : 5 5 2 6 1 = = = z x B x 5, 5 35 1 2 * = = = x x z
割平面解法 整數线性规划问题的可行堿是整教点集,剖平面解 法的思路是:首先不考虑变量x是整数这一条件,仍然 是用解线性规划的方油去解整数线性规划问题,若得到 非整数的最优解,然后增加能剖去非整数解的线性约袁 条件(或称为剖平面)使得由原可行蜮中切割掉一部分, 这部分只包含非整数解,但没有切剖掉任何整数可行解。 这个方渎就是指出怎样找到适当的平面(不见得一次就 找到),使切剖后最终得到这样的可行城,宅的一个有整 數坐标的极点恰好是问题的最优解
整数线性规划问题的可行域是整数点集，割平面解 法的思路是：首先不考虑变量xi是整数这一条件，仍然 是用解线性规划的方法去解整数线性规划问题，若得到 非整数的最优解，然后增加能割去非整数解的线性约束 条件(或称为割平面)使得由原可行域中切割掉一部分， 这部分只包含非整数解，但没有切割掉任何整数可行解。 这个方法就是指出怎样找到适当的割平面(不见得一次就 找到)，使切割后最终得到这样的可行域，它的一个有整 数坐标的极点恰好是问题的最优解
割平面法 倒4-4求解下列整数规划问题 Max f(x =x+ +x,<1 3x+x2≤4 x1,x2≥0,x1,x2整数 3 0 0 X b 0 1/41/4|3/4 3/141/57/4 0 0 1/2 1/2 从最终计算表中,得到非整数的录优解 x1=3/4,x2=714,x3=x4=0,mxz=5/2
st -x1+ x2 ≤ 1 3x1+ x2 ≤ 4 x1，x2 ≥ 0， x1，x2 整数 Max f(x)= x1 + x2 例4-4 求解下列整数规划问题 cj 2 3 0 0 CB XB x1 x2 x3 x4 b θ 1 x1 1 0 -1/4 1/4 3/4 1 x2 0 1 3/4 1/5 7/4 λ 0 0 -1/2 -1/2 从最终计算表中，得到非整数的最优解： x1=3/4，x2=7/4，x3=x4=0，max z=5/2