第五章:整敢规划(1) 对应代数 X2 新最优解有一个 原来最优解非整数 分量为整数 X*={ X1*=4.81 X2*=1.82 新最优解有一个 分量为整数 问题2、可行域 问题B1 增加约束X1>=≤ 可行域 增加约束 X1<=4 XI 原来可行域变成两个可行域 即增加约束:X1<=4X1>=5 运学 熊中措教一
运筹学 熊中楷教授 1* 4.81 2* 1.82 * { = = = X X X 原来最优解 非整数 原来可行域 变成 两个可行域 即 增加约束: X1 <= 4 X1 >= 5 问题B1 可行域 增加约束 X1 <= 4 问题B2 可行域 增加约束 X1 >= 5 新最优解有一个 分量为整数 新最优解有一个 分量为整数 X1 X2 第五章：整数规划（1） 对应代数
第五章:整故观劍(1) 原问题B1 3分枝定界法(代数) Max Z=40X1+90X2 问题B3 问题B4 9X1+7X2 保留原有约束 保留原有约束 再增加约束 再增加约束 7X1+20X2<=70 X X2>=2X>=5,X2 X1>=0,X2>=0 目标值 目标值 X1,X2整数 X 最优解: X1=(整数) (整数) XI X X ZE (非整数) (非整数) 非整数解 运学 熊中措教一
运筹学 熊中楷教授 问题B3: 保留原有约束 再增加约束: X1 <= 4， X2 >=2 问题B4: 保留原有约束 再增加约束: X1 >= 5, X2 <=1 目标值 Z3 = 目标值 Z4 = X1 = (整数) X1 = (整数) X2 = (非整数) X2 = (非整数) 第五章：整数规划（1） 原问题B1 Max Z = 40X1+90X2 9X1 + 7X2 <=56 7X1 + 20X2 <=70 X1>=0 , X2 >=0 X1, X2 整数 最优解： X1= X2= Z= 非整数解 3分枝定界法(代数)
第五章:整脸规到(1 原来可行域B1变成可行域B3,B4 3图示分枝 定界法原理|/X2 可行域B3 增加约束: X1<=4 X2>=2 可行域B4 增加约束 XI X2<=1 运学 熊中措教一
运筹学 熊中楷教授 第五章：整数规划（1） 原来可行域B1 变成可行域B3, B4 2 1 X1 X2 可行域B3 增加约束: X1 <= 4 , X2 >= 2 可行域B4 增加约束 X1 <= 4 , X2 <= 1 3 图示分枝 定界法原理
第五章:整数妮到(1 非整数解A 增加约束 增加约束 整数解B1 非整数解B2,比B1好 增加约束 增加约束 非整数解B4,比B1,B3好 整数B3, 增加约束 1若分枝后得到整数解,则这枝不必再分枝 2若分枝后得到非整数解,如果比整数解更好,则这枝继续分枝 3若分枝后得到非整数解,如果比整数解更差,则这枝不必再分枝 这里解的好坏是指对应目标函数值的大小 运学 熊中措教一
运筹学 熊中楷教授 第五章：整数规划（1） 非整数解A 整数解B1 增加约束 增加约束 非整数解B2, 比B1好 非整数解B4, 比B1,B3好 整数B3 ， 1 若分枝后得到整数解，则这枝不必再分枝。 2 若分枝后得到非整数解, 如果比整数解更好，则这枝继续分枝 3 若分枝后得到非整数解, 如果比整数解更差，则这枝不必再分枝 这里解的好坏是指对应目标函数值的大小 增加约束 增加约束 增加约束
第五章:整敢规划(1) 问题B 由于这时不是整数解|X1=481 取Z=349=Z1 X2=1.82 可题B5 问题B6 Z1>Z) Z=356 X1=544 题B 问题B3 X2=0 无可行解 X1=5.0 Z5=308 X1=4.0 X2=2.1 X2=1.57 不再分枝 Z1=349 Z2=341 B的解还不如 题B3 问题B4 X1=4 X1=142/的解还不好B整数解再分 的整数解再枝更坏,不再 X2=2 X2=30分解会更坏 2=34023=327圆技不分线分枝 已经得到整数解,Z=340--剪枝依据
运筹学 熊中楷教授 . 356 1.82 4.81 * 0 2 1 = = = Z X X 问题B 349 2.1 4.0 1 2 1 1 = = = Z X X 问题B 341 1.57 5.0 2 2 1 2 = = = Z X X 问题B 340 2 4 3 2 1 3 = = = Z X X 问题B 327 3.0 1.42 4 2 1 4 = = = Z X X 问题B 308 0 5.44 B5 5 2 1 = = = Z X X 问题 无可行解 问题B6 Z = Z 整 数 Z 非整数 = Z * * 0 X1 4 X1 5 ( ) 349 1 2 1 Z Z Z Z 取 = = 由于这时不是整数解 X 2 2 X2 3 Z = 340 剪枝不再分枝 分解会更坏 的整数解再 的解还不好 3 4 B B 不再分枝 分枝 枝更坏，不再 整数解再分 的解还不如 3 5 B B X 2 1 X 2 2 第五章：整数规划（1） 已经得到整数解，Z=340---剪枝依据