chap整数规划.ppt

， ， ，……， 第四节 0-1规划和隐枚举法 二、隐枚举法示例 对变量3（x3 =1） Q1=4 -3≡1 离可行性的距离0 Q2=-3+3=0 离可行性的距离 0 Q3=-1+1=0 离可行性的距离0 离各约束条件可行性的总距离为 0 选取x3转换 ， ， ，……， 第五节 应用实例 【实例3－1】 有3万亩提水灌区拟建两种不同规格的泵站，甲种泵站每站可灌溉0.25万亩．乙种泵站每站可灌溉0.4万亩，但甲种泵站限制不得超过8座，乙种泵站限制不得超过4座，甲种泵站平均增产效益10千元，乙种泵站平均增产效益20干元．间每种泵站各建几座可获效益最大？ ， ， ，……， 第五节 应用实例 * * * * * * * * * * * * * * * * * * * * * * * * * 灌排工程系统分析 Chap 3 整数规划及其应用 内 容 目 录 第一节 整数规划的类型及其数学模型 第二节 割平面法 第三节 分枝定界法 第一节 整数规划的类型及其数学模型 一、纯整数规划 二、混合整数规划 三、0-1整数规划 第一节 整数规划的类型及其数学模型 一、纯整数规划 在整数规划中，如果所有的变量均限制为非负整数，就称为纯整数规划（Pure Integer Programming），或称为全整数规划（All Integer Programming）。 第一节 整数规划的类型及其数学模型 第一节 整数规划的类型及其数学模型 二、混合整数规划 如果模型（3-1）中仅一部分变量限制为非负整数．则称为混合整数规划（Mixed Integer Programming）。 第一节 整数规划的类型及其数学模型 第一节 整数规划的类型及其数学模型 三、0-1整数规划 如果整数规划中所有变量的取值仅限于0或1，则该整数规划就称为0—l型整数规划 第一节 整数规划的类型及其数学模型 ， ， ，……， 目标函数 约束条件 第二节 割平面法 ， ， ，……， 第二节 割平面法 ， ， ，……， 关键：如何构造割平面方程？ cj 1 1 0 0 CB XB b x1 x2 x3 x4 初始计算 0 x3 1 -1 1 1 0 0 x4 4 3 1 0 1 0 1 1 0 0 最终计算 1 x1 3/4 1 0 -1/4 1/4 1 x2 7/4 0 1 3/4 1/4 -5/2 0 0 -1/2 -1/2 第二节 割平面法 ， ， ，……， 关键：如何构造割平面方程？ 第二节 割平面法 ， ， ，……， 关键：如何构造割平面方程？ 第二节 割平面法 ， ， ，……， 将割平面方程作为新的约束 cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 x5 1 x1 3/4 1 0 -1/4 1/4 0 1 x2 7/4 0 1 3/4 1/4 0 0 x5 -3 0 0 -3 -1 1 -5/2 0 0 -1/2 -1/2 0 第二节 割平面法 ， ， ，……， 对偶单纯形法求解 cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 x5 1 x1 1 1 0 0 1/3 1/12 1 x2 1 0 1 0 0 1/4 0 x3 1 0 0 1 -1 - 1/3 -2 0 0 0 -1/3 - 1/6 第二节 割平面法 ， ， ，……， 对偶单纯形法求解 cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 x5 1 x1 1 1 0 0 1/3 1/12 1 x2 1 0 1 0 0 1/4 0 x3 1 0 0 1 -1 - 1/3 -2 0 0 0 -1/3 - 1/6 第二节 割平面法 ， ， ，……， 在求解整数规划时，如果变量很少且可行域是有界的，可以采用穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解，这种方法称为“枚举法”或“穷举法” 第三节 分枝定界法 ， ， ，……， 分枝定界法（Branch and Bound Method）思路： 只须检查可行整数组合中的一部分，就能确定最优整数解的方法。 分枝定界法可用于求解纯整数或混合的整数规划问题，在二十世纪六十年代由Land Doig和Dakin等人提出的。 第三节 分枝定界法 ， ， ，……， 分枝定界法的基本思路为： 设有最大化整数规划问题A，与它对应的线性规划问题B； 从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数值必是A的最优目标函数Z*的上界，记作Z；而 A任意可行解的目标函数值将是 的一个下界Z 。 分枝定界法就是将 A的可行域分成子区域（称为分枝）的方法，逐步减小Z和增大Z（称为定界）。最终求出 的一种迭代解