Chapter 9 Integer Programming 整数规划 Data model and decisions 数据、模型与决策 第九章 nteger programming 整数规划 RuC Information School, Ye Xiang 2007
Chapter 9 Integer Programming 整数规划 RUC Information School ,Ye Xiang ,2007 Data, Model and Decisions 数据、模型与决策 第九章 Integer Programming 整数规划
本章内容P342 Chapter 9 Integer Programming 整数规划 91一般整数规划 92案例分析:加利福尼亚制造公司的例子 93其他一些应用 940-1变量的一些其他描述方法 95一些建模的例子 96小结 案例91能力问题 RuC Information School, Ye Xiang 2007
Chapter 9 Integer Programming 整数规划 RUC Information School ,Ye Xiang ,2007 本章内容 P342 9.1 一般整数规划 9.2 案例分析：加利福尼亚制造公司的例子 9.3 其他一些应用 9.4 0-1变量的一些其他描述方法 9.5 一些建模的例子 9.6 小结 案例9.1 能力问题
本章提示 Chapter 9 Integer Programming 整数规划 如果中文版的“规划求解”经常找不到解或 有其他问题,请安装英文版 Premium Solver 在光盘 Premium solver文件夹下,运行 PremSolⅤ文件安装即可。安装完毕后, Premium solver将代替Exce原来的规划求解 ,界面也变成英文的,具体P429。有三种算 法可供选择 1、标准GRG非线性一一等同于使用没有选择“ 假设线性模型”的选项的标准 Solver 2、标准 Simplex LP-一相当于使用选择了“假设 ,3、标准E、10门新的 RuC Information School, Ye Xiang 2007
Chapter 9 Integer Programming 整数规划 RUC Information School ,Ye Xiang ,2007 本章提示 ➢ 如果中文版的“规划求解”经常找不到解或 有其他问题，请安装英文版Premium Solver 。 ➢ 在光盘Premium Solver文件夹下，运行 PremSolv文件安装即可。安装完毕后， Premium Solver 将代替Excel原来的规划求解 ，界面也变成英文的，具体P429。有三种算 法可供选择 ◆ 1、标准GRG非线性－－等同于使用没有选择“ 假设线性模型”的选项的标准Solver ◆ 2、标准Simplex LP－－相当于使用选择了“假设 线性模型”的选项的标准Solver ◆ 3、标准Evolutionary－－新的
Integer Solutions Chapter 9 整数解 Integer Programming 什么时候需要整数解? 整数规划 得到小数解时如何处理呢? 你有什么绝招吗? The Challenges of rounding舍入解的挑战 舍入解可能不是可行解 ■舍入解与最优解离很远 可能有多个舍入解出现 Some solution Technique一些求解技术 Branch-and- Bound technique分枝定界技术 Branch-and- Cut Technique割平面技术 How Integer Programs are Solved如何求解整数规划 RuC Information School, Ye Xiang 2007
Chapter 9 Integer Programming 整数规划 RUC Information School ,Ye Xiang ,2007 Integer Solutions 整数解 ▪ 什么时候需要整数解？ ▪ 得到小数解时如何处理呢？ ▪ 你有什么绝招吗？ ▪ The Challenges of Rounding 舍入解的挑战 ▪ 舍入解可能不是可行解 ▪ 舍入解与最优解离很远 ▪ 可能有多个舍入解出现 ▪ Some Solution Technique 一些求解技术 ▪ Branch-and-Bound Technique 分枝定界技术 ▪ Branch-and-Cut Technique 割平面技术 ▪ How Integer Programs are Solved 如何求解整数规划
Branch-and-Cut Technique Chapter 9 割平面技术 Integer Programming 整数规划 首先放弃变量的整数要求,求线性规划最优解 如果最优解恰是一整数解,则最优解就是整数规划的最优解 如果最优解不是整数解,则要求构造一个新的约束,对线性 规划问题的可行域进行切割,切除已得到的规划的最优解, 但保留原可行域中所有的整数解,求解新的线性规划问题, 如果最优解仍不是整数解,再增加附加的约束将其切除,但 仍保持最初可行域中所有的整数解,如此一直进行,直至得 到一个整数的最优解为止 RuC Information School, Ye Xiang 2007
Chapter 9 Integer Programming 整数规划 RUC Information School ,Ye Xiang ,2007 Branch-and-Cut Technique 割平面技术 首先放弃变量的整数要求，求线性规划最优解 如果最优解恰是一整数解，则最优解就是整数规划的最优解 如果最优解不是整数解，则要求构造一个新的约束，对线性 规划问题的可行域进行切割，切除已得到的规划的最优解， 但保留原可行域中所有的整数解，求解新的线性规划问题， 如果最优解仍不是整数解，再增加附加的约束将其切除，但 仍保持最初可行域中所有的整数解，如此一直进行，直至得 到一个整数的最优解为止
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均为整数