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 割平面技术 首先放弃变量的整数要求，求线性规划最优解 如果最优解恰是一整数解，则最优解就是整数规划的最优解 如果最优解不是整数解，则要求构造一个新的约束，对线性 规划问题的可行域进行切割，切除已得到的规划的最优解， 但保留原可行域中所有的整数解，求解新的线性规划问题， 如果最优解仍不是整数解，再增加附加的约束将其切除，但 仍保持最初可行域中所有的整数解，如此一直进行，直至得 到一个整数的最优解为止