4.3-分枝定界法和割平面法.ppt

3 2 0 0 0 CB XB b x1 x2 x3 x4 x6 3 x1 13/4 1 0 3/4 -1/4 0 2 x2 5/2 0 1 -1/2 1/2 0 0 x6 -3 0 -1 0 0 1 Z 59/4 0 0 -5/4 -1/4 0 3 x1 13/4 1 0 3/4 -1/4 0 2 x2 5/2 0 1 -1/2 1/2 0 0 x6 -1/2 0 0 -1/2 1/2 1 Z 59/4 0 0 -5/4 -1/4 0 3 x1 5/2 1 0 0 1/2 3/2 2 x2 3 0 1 0 0 -1 0 x3 1 0 0 1 -1 -2 Z 27/2 0 0 0 -3/2 -5/2 考虑LP2： x1=5/2, x2=3 Z(2) =27/2=13.5 ∵ Z(2) Z(1) ∴ 先不考虑分枝 接(LP1)继续分枝,加入约束 4 ≤ x1≤ 3,有下式： 分别引入松弛变量x7 和 x8 ，然后进行计算。 上例续： CB XB b x1 x2 x3 x4 x5 x7 3 x1 7/2 1 0 1/2 0 -1/2 0 2 x2 2 0 1 0 0 1 0 0 x4 1 0 0 -1 1 -2 0 0 x7 3 1 0 0 0 0 1 Z 29/2 0 0 -3/2 0 -1/2 0 3 x1 7/2 1 0 1/2 0 -1/2 0 2 x2 2 0 1 0 0 1 0 0 x4 1 0 0 -1 1 -2 0 0 x7 -1/2 0 0 -1/2 0 1/2 1 Z 29/2 0 0 -3/2 0 -1/2 0 3 x1 3 1 0 0 0 0 1 2 x2 2 0 1 0 0 1 0 0 x4 2 0 0 0 1 -3 -2 0 x3 1 0 0 1 0 -1 -2 Z 13 0 0 0 0 -2 -3 x1=3,x2=2 z(3) =13 找到整数解,问题已探明,停止计算. 考虑LP3： CB XB b x1 x2 x3 x4 x5 x8 3 x1 7/2 1 0 1/2 0 -1/2 0 2 x2 2 0 1 0 0 1 0 0 x4 1 0 0 -1 1 -2 0 0 x8 -4 -1 0 0 0 0 1 Z 29/2 0 0 -3/2 0 -1/2 0 3 x1 7/2 1 0 1/2 0 -1/2 0 2 x2 2 0 1 0 0 1 0 0 x4 1 0 0 -1 1 -2 0 0 x8 -1/2 0 0 1/2 0 -1/2 1 Z 29/2 0 0 -3/2 0 -1/2 0 3 x1 4 1 0 0 0 0 -1 2 x2 1 0 1 1 0 0 2 0 x4 3 0 0 -3 1 0 -4 0 x5 1 0 0 -1 0 1 -2 Z 14 0 0 -2 0 0 -1 x1=4, x2=1 z(4) =14 找到整数解,问题已探明,停止计算. 考虑LP4： 树形图如下： LP1 x1=7/2, x2=2 Z(1)＝29/2=14.5 LP x1=13/4, x2=5/2 Z(0) ＝59/4=14.75 LP2 x1=5/2, x2=3 Z(2)＝27/2=13.5 LP3 x1=3, x2=2 Z(3) ＝13 LP4 x1=4, x2=1 Z(4) ＝14 x2≤2 x2≥3 x1≤3 x1≥4 ╳ ╳ ╳ 练习：用分枝定界法求解整数规划问题 （单纯形法） 先将问题转化成标准型： cj 1 5 0 0 0 cB xB b x1 x2 x3 x4 x5 0 x3 2 -1 1 1 0 0 0 x4 30 5 6 0 1 0 0 x5 4 1 0 0 0 1 w 0 1 5 0 0 0 5 x2 40/11 0 1 1/11 5/11 0 1 x1 18/11 1 0 1/11 -6/11 0 0 x5 26/11 0 0 -1/11 6/11 1 w 218/11 0 0 -6/11 -19/11 0 上述松弛问题的单纯形表： LP1 x1=1, x2=3 w(1) ＝16 LP x1=18/11, x2=40/11 w(0) ＝19.8 LP2 x1=2, x2=10/3 w(2) ＝18.5 LP3 x1=12/5, x2=3 w(3) ＝17.4 LP4 无可 行解 LP5 x1=2, x2=3 w(5) ＝17 LP6 x1=3, x2=5/2 w(6) ＝15.5 x1≤1 x1≥2 x2≤3 x2≥4 x1≤2 x1≥3 ╳ ╳ ╳ ╳ 1958由Gomory提出的一种求解整数规划问题的方法 基本思想： 依次引进线性约束条件(称Gomory约束或割平面) 切割掉问题的部分非整数解 直到使问题的目