资源描述：
《整数规划教学课件ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章整数规划(IntegerProgramming)整数规划的模型分支定界法割平面法0－1整数规划指派问题知识回顾：线性规划模型由前面学习可知，线性规划在生产实践中有重要作用，能够解决许多优化问题；用单纯性算法能方便地对线性规划问题求解已知：两种货物装葙每种货物装葙利润体积限制重量限制决策变量:两种货物各多少箱MaxZ=利润最大？货物X1货物X2限量体积5424重量2513利润2010但现在也有另一类现实问题：思考：箱数？实践中的其他问题举例背包问题：背包的容积一定，现有多种物品待装，各物品的价值、体积已知，求最优
2、配装方案，使得在不超过背包的容量的前提下装入物品的价值最大。选址问题：某商场在全市有数个连锁店，拟建立n个仓库对所有连锁店供货，有数个地点作为被选点。问在何处建设仓库使得各仓库到所有连锁店的总距离最小。投资决策问题：现有一定的资金，有数个可以考虑的投资项目。每个项目需要的资金和利润已知。问如何选择投资项目，使得获得的利润最大。分析以上问题的特点是：变量为整数背包问题：对每一件物品进行取舍，装或者不装；选址问题：对每一个被选点有两种选择，在这里建或者不在这里建；投资决策问题：对每一个考虑的项目，投资或者不投资。这类问题
3、无法用线性规划求解！因为线性规划的解可能包含小数部分（一）、整数规划问题实例例一、合理下料问题设用某型号的圆钢下零件A1,A2,…,Am的毛坯。在一根圆钢上下料的方式有B1,B2,…Bn种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？零件方个数式零件零件毛坯数一、整数规划的模型设：xj表示用Bj(j=1.2…n)种方式下料根数模型：例二、某公司计划在m个地点建厂，可供选择的地点有A1,A2…Am，他们的生产能力分别是a1,a2,…am（假
4、设生产同一产品）。第i个工厂的建设费用为fi(i=1.2…m),又有n个地点B1,B2,…Bn需要销售这种产品，其销量分别为b1.b2…bn。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？单销地厂址价生产能力建设费用销量设：xij表示从工厂运往销地的运量(i=1.2…m、j=1.2…n),1在Ai建厂又设Yi＝（i=1.2…m）0不在Ai建厂模型：例三、机床分配问题设有m台同类机床，要加工n种零件。已知各种零件的加工时间分别为a1,a2,…an，问如何分配，
5、使各机床的总加工任务相等，或者说尽可能平衡。设：1分配第i台机床加工第j种零件；xij＝（i=1.2…m,j=1.2…n）0相反。于是，第i台机床加工各种零件的总时间为：又由于一个零件只能在一台机床上加工，所以有因此，求xij，使得（二）、整数规划的数学模型一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划。纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。全整数规划：除了所有决策变量要求取非负整数外，系数aij和常数bi也要求
6、取整数（这时引进的松弛变量和剩余变量也必须是整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0－1整数规划：所有决策变量只能取0或1两个整数。（三）、整数规划与线性规划的关系从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。举例说明。例：设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛
7、问题）。用解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。图因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：
8、分支定界法和割平面法；对于特别的0－1规划问题采用隐枚举法和匈牙利法。（一）、基本思路考虑纯整数问题：整数问题的松弛问题：二、分枝定界法1、先不考虑整数约束，解(IP)的松弛问题(LP)，可能得到以下情况之一：⑴.若(LP)没有可行解，则(IP)也没有可行解，停止计算。⑵.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(I
