数学建模-整数规划ppt课件.ppt

《数学建模-整数规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模整数规划IntegerProgramming数信学院任俊峰2012-4-15整数规划模型（IP）如果一个数学规划的某些决策变量或全部决策变量要求必须取整数，则称这样的问题为整数规划问题，其模型称为整数规划模型。如果整数规划的目标函数和约束条件都是线性的，则称此问题为整数线性规划问题.整数规划问题实例例1合理下料问题例2建厂问题例1、合理下料问题设用某型号的圆钢下零件A1,A2,…,Am的毛坯。在一根圆钢上下料的方式有B1,B2,…Bn种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？零

2、件方个数式零件零件毛坯数设：xj表示用Bj(j=1.2…n)种方式下料根数.模型：例2、（建厂问题）某公司计划在m个地点建厂，可供选择的地点有A1,A2…Am，他们的生产能力分别是a1,a2,…am（假设生产同一产品）。第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＝（

3、i=1.2…m）0不在Ai建厂模型：整数规划的数学模型一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划。纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。全整数规划：除了所有决策变量要求取非负整数外，系数aij和常数bi也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0－1整数规划：所有决策变量只能取0或1两个整数。整数规划与线性规划的关系整数规划松弛的线性规划整数规划可行解是松弛问题可行域中的整

4、数格点ILP最优值小于或等于松弛问题的最优值松弛问题无可行解，则整数规划无可行解；松弛问题最优解满足整数要求，则该最优解为整数规划最优解；整数线性规划的求解方法从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。例：设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题或伴随问题）。用图解法求出最优解x1＝3/2,x2=10/3且有=29/6x1x2⑴⑵33(3/2,10/3

5、)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，=4。目前，常用的求解整数规划的方法有：分枝定界法和割平面法；对于特别的0－1规划问题采用隐枚举法和匈牙利法。x1x2⑴⑵33(3/2,10/3)不考虑整数限制先求出相应松弛问题的最优解，若松弛问题无

6、可行解，则ILP无可行解；若求得的松弛问题最优解符合整数要求，则是ILP的最优解；若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束添加到松弛问题中形成两个子问题依次在缩小的可行域中求解新构造的线性规划的最优解，并重复上述过程，直到子问题无解或有整数最优解（被查清）。分枝定界法在分支的过程中，若当前已经得到的满足整数要求的最优值为，则该就可是作为一个过滤条件，对于最优值小于或等于的子问题无需再分支，则这样的子问题称为被剪枝。未被剪枝的子问题需继续分支。分支定界法的最终子问题要么被查清要么被剪枝。分支定界法求解举例012312301231230123123x1

7、≥2x1≤1x2≥3x2≤2x1≤2x1≥3割平面法的基本思想如果松弛问题(P0)无解，则(P)无解；如果(P0)的最优解为整数向量，则也是(P)的最优解；如果(P0)的解含有非整数分量，则对(P0)增加割平面条件：即对(P0)增加一个线性约束，将(P0)的可行区域割掉一块，使得非整数解恰好在割掉的一块中，但又没有割掉原问题(P)的可行解，得到问题(P1)，重复上述的过程。x1x2例3投资问题有600万元投资5个项目，收益如表，求利润最大的方案？0-1变量的使用例4、互斥约束问题例如某种工序的约束条件为：企业也可以考虑一种新的加工工