第五章:整敢规划(1) 2整數规划的图解法 最优解非整数 (P118例2) X2 X*={X2 *=4.8 目标函数 等值线 XI 关心可行域 中整数点 2=0≤Z*数≤Z*整数=Z 运学 熊中措教一
运筹学 熊中楷教授 2整数规划的图解法 （P118 例2） Z = 0 Z * 整 数 Z * 非整数 = Z 最优解 非整数 1* 4.81 2* 1.82 * { = = = X X X 目标函数 等值线 X1 X2 第五章：整数规划（1） 关心可行域 中整数点
第五章:整敢规划(1) 2整數规划的图解法 (P118例2) Ⅹ2 X*={X2 *=4.8 目标 函数 等值 线 0 XI 把目标函数等值线向下平行移动,关注等值线 在可行域内部或者可行域边上遇到第1个整数点 运等 熊中措教
运筹学 熊中楷教授 2整数规划的图解法 （P118 例2） 1* 4.81 2* 1.82 * { = = = X X X 目标 函数 等值 线 X1 X2 第五章：整数规划（1） 把目标函数等值线向下平行移动，关注等值线 在可行域内部或者可行域边上遇到第1个整数点 2 1 0
第五章:整敢规划(1) 3图示分枝/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） 3 图示分枝 定界法原理
第五章:整脸规到(1 原来可行域B1变成可行域B3,B4 3图示分枝 定界法原理 XI 可行域B3 9X1+7X2<=56 7X1+20X2<=70 增加约束:X1<=4, X2 2 可行域B4 9X1+7X2 7X1+20X2<=70 增加约束X1<=4 X2>= XI 运学 熊中措教一
运筹学 熊中楷教授 原来可行域B1 变成可行域B3, B4 2 1 第五章：整数规划（1） X1 X1 可行域B3 9X1 + 7X2 <=56 7X1 + 20X2 <=70 增加约束: X1 <= 4 , X2 >= 2 可行域B4 9X1 + 7X2 <=56 7X1 + 20X2 <=70 增加约束X1 <= 4 , X2 >= 1 3 图示分枝 定界法原理
第五章:整脸规划(1 原问题B 3分枝定界法(代数 Max z=40X1+90X2 问题B1: 问题B2: 9X1+7X2 保留原有约束 保留原有约束 7X1+20X2<=70 再增加约束: 再增加约束 X1<=4 X1≥5 X1>=0,X2>=0 目标值 目标值 X1,X2整数 Z1=349 7=341 X1=4 最优解: X1=5(整数) (整数) X1=4.81 X2=2.1 X2=157 X2=1.82 (非整数) (非整数) Z=356 非整数解 等 熊中措教一
运筹学 熊中楷教授 问题B1: 保留原有约束 再增加约束: X1 <= 4 问题B2: 保留原有约束 再增加约束: X1 >= 5 目标值 Z1 = 349 目标值 Z2 = 341 X1 = 4 (整数) X1 = 5 (整数) X2 = 2.1 (非整数) X2 = 1.57 (非整数) 第五章：整数规划（1） 原问题B Max Z = 40X1+90X2 9X1 + 7X2 <=56 7X1 + 20X2 <=70 X1>=0 , X2 >=0 X1, X2 整数 最优解： X1=4.81 X2=1.82 Z=356 非整数解 3分枝定界法(代数)