《第5章整数规划第1-2节-运筹学课件.ppt》由会员分享，可在线阅读，更多相关《第5章整数规划第1-2节-运筹学课件.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第5章 整数规划l第1节 整数规划的数学模型及解的特点l第2节 分支定界法l第3节 割平面法l第4节 0-1整数规划l第5节 指派问题 第1节 整数规划的数学模型及解的特点l整数规划数学模型的一般形式整数规划数学模型的一般形式 全部决策变量取整数值的规划问题全部决策变量取整数值的规划问题:纯整数规划（纯整数规划（Pure Interger Programming,PIP）部分变量取整数的规划问题部分变量取整数的规划问题:混合整数规划（混合整数规划（Mixed Interger Programming,MIP）全部决策变量取全部决策变量取0或或1的规划问题的规划问题:0-1规划（规划（Binar
2、y Interger Programming,BIP）整数规划中不考虑整数条件所对应的规划问题整数规划中不考虑整数条件所对应的规划问题:该整数规划的松弛问题该整数规划的松弛问题l整数线性规划一般形式：中部分或全部取整数整数线性规划的几种类型l纯整数线性规划l混合整数线性规划l0-1型整数线性规划例：设整数规划问题如下例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。为松弛问题）。用图解法求出最优解用图解法求出最优解x13/2,x2=10/3且有且有Z=29/6x1x233(3/2,10/3)现求整数解（最优解）：现求整
3、数解（最优解）：如用如用“舍入取整法舍入取整法”可得到可得到4个点即个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能。显然，它们都不可能是整数规划的最优解。是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。图所示。1212(1)(2)因此，可将集合内的整数点一一找出，其最因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。大目标函数的值为最优解，此法为完全枚
4、举法。如上例：其中如上例：其中（2，2）（）（3，1）点为最点为最大值，大值，Z=4。目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：分支定界法和割平面法；分支定界法和割平面法；对于特别的对于特别的0 01 1规划问题采用隐枚举法和匈规划问题采用隐枚举法和匈牙利法。牙利法。（一）、基本思路（一）、基本思路 考虑纯整数问题：考虑纯整数问题：整数规划问题的整数规划问题的线性问题：线性问题：1、先不考虑整数约束，解、先不考虑整数约束，解(IP)的线性规划问题的线性规划问题(LP)，可能得到以下情况之一：，可能得到以下情况之一：若若(LP)没有可行解，则没有可行解，则(IP)也没有
5、可行解，停也没有可行解，停止计算。止计算。若若(LP)有最优解，并符合有最优解，并符合(IP)的整数条件，则的整数条件，则(LP)的最优解即为的最优解即为(IP)的最优解，停止计算。的最优解，停止计算。若若(LP)有最优解，但不符合有最优解，但不符合(IP)的整数条件，的整数条件，转入下一步。为讨论方便，设转入下一步。为讨论方便，设(LP)的最优解为：的最优解为：如此反复进行，直到得到如此反复进行，直到得到ZZ*为止，即得最优解为止，即得最优解 X*。将这两个约束条件分别加入问题将这两个约束条件分别加入问题(IP)，形成两个子，形成两个子问题问题(IP1)和和(IP2)，再解这两个问题的松弛问
6、题，再解这两个问题的松弛问题(LP1)和和(LP2)。4、修改上、下界：按照以下两点规则进行。修改上、下界：按照以下两点规则进行。在各分枝问题中，找出目标函数值最大者作为新在各分枝问题中，找出目标函数值最大者作为新的上界；的上界；从已符合整数条件的分枝中，找出目标函数值最从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。大者作为新的下界。5、比较与剪枝比较与剪枝：各分枝的目标函数值中，若有小于各分枝的目标函数值中，若有小于Z 者，则剪掉此者，则剪掉此枝，表明此子问题已经探清，不必再分枝了枝，表明此子问题已经探清，不必再分枝了;否则继续否则继续分枝。分枝。l图解法分析：、0 1 2 3 4 5 6 7 8 9 108-7-6-5-4-3-2-1-B不是问题A的解但 l图解法分析：0 1 2 3 4 5 6 7 4321l图解法分析：4321 0 1 2 3 4 5 6 7 是问题A解但 不是问题A解而 剪枝 l图解法分析：0 1 2 3 4 5 6 7 4321l分支定界的全过程：l分支定界的全过程：谢 谢！