92g 整数规划(1) 运学 熊中措教一
运筹学 熊中楷教授 整数规划（1）
第五章:整规划(1) Chapters: Integer 第五章:整数规划(1) Programming(l) 整数规划的引例与模型 example and model of Integer programming 2.整数规划的图解法 2. graphic method for integer programming 3.整数规划的求解 分枝定界法(难点) 3. Brand-and-Bound Method for solving 4整数规划的求解一 integer programming 割平面法(难点) 运学 熊中措教一
运筹学 熊中楷教授 第五章：整数规划（1） 第五章：整数规划（1） 1．整数规划的引例与模型 2．整数规划的图解法 3．整数规划的求解------ 分枝定界法（难点） 4 整数规划的求解------ 割平面法（难点） Chapter5:Integer Programming(1) 1. example and model of integer programming 2.graphic method for integer programming 3.Brand-and-Bound Method for solving integer programming
第五章:整敢规划(1) 问题的提出: 货物货物限量 已知:两种货物装葙 X1 X2 每种货物装葙利润 体积5 4 24 体积限制 重量限制 重量25 决策变量:两种货物各多少箱 MaxZ=利润最大? 利润2010 箱数不能为分数 运学 熊中措教一
运筹学 熊中楷教授 第五章：整数规划（1） 1问题的提出: 已知：两种货物装葙 每种货物装葙利润 体积限制 重量限制 决策变量:两种货物各多少箱 Max Z =利润最大？ 箱数不能为分数 货物 X1 货物 X2 限量 体积 5 4 24 重量 2 5 13 利润 20 10
第五章:整敢规划(1) 1问题的提出 X2 甲货物运输的箱数 乙货物运输的箱数 5X1+4X2=24 Max z= 20X1+10X2 2X1+5X2=13 每箱利润 X1+4X2=0,X2>=0 。。。。。。。。。 )) X1,X2整数(箱数不能为分数) XI 目标函数 等值线 运学 熊中措教
运筹学 熊中楷教授 5X1+4X2 = 24 2X1+5X2 =13 第五章：整数规划（1） X1 1问题的提出 X2 甲货物运输的箱数 乙货物运输的箱数 Max Z = 20X1+10X2 每箱利润 5X1 + 4X2 =0 , X2 >=0 X1, X2 整数（箱数不能为分数） 目标函数 等值线
第五章:整敢规划(1) 2整數规划的图解法 (P118例2) Max Z=40X1+90X2 9X1+7X2=0,X2>=0 X1,X2整数 运学 熊中措教一
运筹学 熊中楷教授 Max Z = 40X1+90X2 9X1 + 7X2 =0 , X2 >=0 X1, X2 整数 2整数规划的图解法 （P118 例2） 第五章：整数规划（1）
第五章:整敢规划(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=5 运学 熊中措教一
运筹学 熊中楷教授 1* 4.81 2* 1.82 * { = = = X X X 原来最优解 非整数 原来可行域 变成 两个可行域 即 增加约束: X1 = 5 问题B1 可行域 增加约束 X1 = 5 新最优解有一个 分量为整数 新最优解有一个 分量为整数 X1 X2 第五章：整数规划（1） 3 图示分枝 定界法原理
第五章:整脸规到(1 原来可行域B1变成可行域B3,B4 3图示分枝 定界法原理 XI 可行域B3 9X1+7X2= XI 运学 熊中措教一
运筹学 熊中楷教授 原来可行域B1 变成可行域B3, B4 2 1 第五章：整数规划（1） X1 X1 可行域B3 9X1 + 7X2 = 2 可行域B4 9X1 + 7X2 = 1 3 图示分枝 定界法原理
第五章:整脸规划(1 原问题B 3分枝定界法(代数 Max z=40X1+90X2 问题B1: 问题B2: 9X1+7X2 保留原有约束 保留原有约束 7X1+20X2=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 = 5 目标值 Z1 = 349 目标值 Z2 = 341 X1 = 4 (整数) X1 = 5 (整数) X2 = 2.1 (非整数) X2 = 1.57 (非整数) 第五章：整数规划（1） 原问题B Max Z = 40X1+90X2 9X1 + 7X2 =0 , X2 >=0 X1, X2 整数 最优解： X1=4.81 X2=1.82 Z=356 非整数解 3分枝定界法(代数)