(ppt)第04章 整数规划与分配问题-运筹学.ppt

2002-03-01 2002ZLZK-PM-KICKOFF 运筹学 4.2 分配问题与匈牙利法 例 4.5 练习： 0－1 整数规划与隐枚举法 练习：用隐枚举法求解0—1规划问题 分枝问题解可能出现的情况 练习：用分枝定界法求解整数规划问题（图解法） 例4.10 用分枝定界法求解整数规划问题（单纯形法） 练习：用分枝定界法求解整数规划问题（单纯形法） LP1 x1=1, x2=7/3 Z(1) ＝10/3 LP x1=3/2, x2=10/3 Z(0) ＝29/6 LP2 x1=2, x2=23/9 Z(2) ＝41/9 x1≤1 x1≥2 LP5 x1=1, x2=2 Z(5) ＝3 LP6 无可 行解 ＃ ＃ x2≤2 x2≥3 LP3 x1=33/14, x2=2 Z(3) ＝61/14 LP4 无可 行解 x2≤2 x2≥3 ＃ LP7 x1=2, x2=2 Z(7) ＝4 LP8 x1=3, x2=1 Z(8) ＝4 x1≤2 x1≥3 ＃ ＃ LP1 x1=1, x2=7/3 Z(1) ＝10/3 LP x1=2/3, x2=10/3 Z(0) ＝29/6 LP2 x1=2, x2=23/9 Z(2) ＝41/9 LP3 x1=33/14, x2=2 Z(3) ＝61/14 LP4 无可 行解 LP7 x1=2, x2=2 Z(7) ＝4 LP8 x1=3, x2=1 Z(8) ＝4 x1≤1 x1≥2 x2≤2 x2≥3 x1≤2 x1≥3 ＃ ＃ ＃ ＃ 0 0 2 3 0 -Z 14/2 1 0 3 2 14 x4 0 9/2 0 1 1 2 9 x3 0 x4 x3 x2 x1 b XB CB 0 0 2 3 -1/4 -5/4 0 0 -59/4 -Z 1/2 -1/2 1 0 5/2 x2 2 -1/4 3/4 0 1 13/4 x1 3 x4 x3 x2 x1 b XB CB 0 0 2 3 解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。 初始表 最终表 x1=13/4 x2=5/2 Z(0) =59/4≈14.75 选 x2 进行分枝，即增加两个约束，2 ≥ x2 ≥3 有下式： 分别在(LP1)和(LP2)中引入松弛变量x5和x6 ，将新加约束条件加入上表计算。即 x2+ x5= 2 , －x2+x6=－3 得下表: -1/4 0 1/2 -1/4 x4 0 0 -1/2 1 0 5/2 x2 2 0 -5/4 0 0 -59/4 -Z 1 0 1 0 2 x5 0 0 3/4 0 1 13/4 x1 3 x5 x3 x2 x1 b XB CB 0 0 2 3 -1/4 -1/2 1/2 -1/4 0 -1/2 1 0 5/2 x2 2 0 -5/4 0 0 -59/4 -Z 1 1/2 0 0 -1/2 x5 0 0 3/4 0 1 13/4 x1 3 0 1 0 0 1 0 1 0 2 x2 2 -1/2 -3/2 0 0 -29/2 -Z -2 -1 0 0 1 x4 0 -1/2 1/2 0 1 7/2 x1 3 x1=7/2, x2=2 Z(1) =29/2=14.5 继续分枝，加入约束 3≥ x1 ≥4 LP1 -1/4 0 1/2 -1/4 x4 0 0 -1/2 1 0 5/2 x2 2 0 -5/4 0 0 -59/4 -Z 1 0 -1 0 -3 x6 0 0 3/4 0 1 13/4 x1 3 x6 x3 x2 x1 b XB CB 0 0 2 3 -1/4 1/2 1/2 -1/4 0 -1/2 1 0 5/2 x2 2 0 -5/4 0 0 -59/4 -Z 1 -1/2 0 0 -1/2 x6 0 0 3/4 0 1 13/4 x1 3 -3/2 -1 0 1/2 -1 0 1 0 3 x2 2 -5/2 0 0 0 -27/2 -Z -2 1 0 0 1 x3 0 3/2 0 0 1 5/2 x1 3 LP2 x1=5/2, x2=3 Z(2) =27/2=13.5 ∵ Z(2) Z(1) ∴ 先不考虑分枝 接(LP1)继续分枝，加入约束 4 ≤ x1≤ 3，有下式： 分别引入松弛变量x7 和 x8 ，然后进行计算。 -1/2 0 -2 1 -1/2 x5 0 0 1 0 0 x4 0 -1 0 0 1 x4 0 0 -3/2 0 0 -29/2 -Z 1 0 0 1 3 x7 0 0 0 1 0 2 x2 2 0 1/2 0 1 7/2 x1 3 x7 x3 x2 x1 b XB CB 0 -2 1 -1 0 0 1 x4 0 -1/2 1/2 1 -1/2 0 0 0 0 0 0