Branch-and-Cut Technique Chapter 9 割平面技术 Integer Programming 整数规划 min z= 3x1 +4x2 线性规划 最优解 s t 3x1+x2≥4 整数规划 X1+2x2≥4 最优解 x2≥0 x1,x2为整数 切割约束 RuC Information School, Ye Xiang 2007
Chapter 9 Integer Programming 整数规划 RUC Information School ,Ye Xiang ,2007 Branch-and-Cut Technique 割平面技术
Branch-and-Bound Technique Chapter 9 分枝定界技术 Integer Programming 整数规划 RuC Information School, Ye Xiang 2007
Chapter 9 Integer Programming 整数规划 RUC Information School ,Ye Xiang ,2007 1 2 3 4 5 1 2 3 4 5 x1 x2 1 2 3 4 5 1 2 3 4 5 x1 x2 Branch-and-Bound Technique 分枝定界技术
Chapter 9 Integer Programming 整数规划 整数规划分为两大类P342 I\ integer programming 般整数规划 2 Binary integer programming(BIP) 0-1整数规划(是非决策问题) RuC Information School, Ye Xiang 2007
Chapter 9 Integer Programming 整数规划 RUC Information School ,Ye Xiang ,2007 整数规划分为两大类P342 1、integer programming 一般整数规划 2、Binary integer programming（BIP） 0-1整数规划（是非决策问题）
Chapter 9 91一般整数规划 Integer Programming P343例子:TBA航空公司问题 整数规划 为了获得最大的年利润,公司应该购买多少飞机(小型飞机 和大型飞机),各种型号又该如何组合? 先去掉整数约束 线性规划模型P344和图解法P344,得到的解为S=2、L=1.8,利润 P=11百万美元 ■舍入解,S=2、L=1,利润P=7百万美元,但不是最优整数解 TBA航空公司问题违背了线性规划可分性假设(决策变量值可以是 分数形式)。 添加整数约束: 整数规划模型:P345(多整数约束) ■图解法(整数解)P346 Excel解法(在线性规划求解中,增加整数约束INT即可,P347) RuC Information School, Ye Xiang 2007
Chapter 9 Integer Programming 整数规划 RUC Information School ,Ye Xiang ,2007 9.1 一般整数规划 P343例子：TBA航空公司问题 ▪ 为了获得最大的年利润，公司应该购买多少飞机（小型飞机 和大型飞机），各种型号又该如何组合？ ▪ 先去掉整数约束： ▪ 线性规划模型P344和图解法P344，得到的解为S=2、L=1.8，利润 P=11百万美元 ▪ 舍入解，S=2、L=1，利润P=7百万美元，但不是最优整数解 ▪ TBA航空公司问题违背了线性规划可分性假设（决策变量值可以是 分数形式）。 ▪ 添加整数约束： ▪ 整数规划模型：P345（多整数约束） ▪ 图解法（整数解）P346 ▪ Excel解法(在线性规划求解中，增加整数约束INT即可，P347）
Chapter 9 Integer Programming TBA航空公司问题的 整数规划 整数规划模型P345 假设:购买小型飞机S架,大型飞机I架 总利润最大化MaxP=S+5L 约束条件 资金:5S+50L≤100 小型飞机:S≤2 且 非负:S,L≥0 S,L均为整数 RuC Information School, Ye Xiang 2007
Chapter 9 Integer Programming 整数规划 RUC Information School ,Ye Xiang ,2007 TBA航空公司问题的 整数规划模型 P345 假设：购买小型飞机S架，大型飞机L架 总利润最大化 Max P＝S＋5L 约束条件 资金： 5S + 50L 100 小型飞机：S 2 且 非负： S，L 0 S, L均为整数