第八章 运筹学课件整数规划.ppt

整数规划(IntegerProgramming)整数规划的模型分枝定界法整数规划的应用§1 整数规划的模型(一)、整数规划问题实例例1、合理下料问题设用某型号的圆钢下零件A1,A2,…,Am的毛坯。在一根圆钢上下料的方式有B1,B2,…Bn种,每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量,如表所示。问怎样安排下料方式,使得即满足需要,所用的原材料又最少?零件方个数式零件零件毛坯数设xj表示用Bj(j=…n)种方式下料根数,可得如下模型:例2、某公司计划在m个地点建厂,可供选择的地点有A1,A2…Am,他们的生产能力分别是a1,a2,…am(假设生产同一产品)。第i个工厂的建设费用为fi(i=…m),又有n个地点B1,B2,…Bn需要销售这种产品,…bn。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂,即满足各地需要,又使总建设费用和总运输费用最省?单销地厂址价生产能力建设费用销量设:xij表示从工厂运往销地的运量(i=…m、j=…n),1在Ai建厂又设Yi=(i=…m)0不在Ai建厂模型:(二)、整数规划的数学模型一般形式依照决策变量取整要求的不同,整数规划可分为纯整数规划、全整数规划、混合整数规划、0-1整数规划。纯整数规划:所有决策变量要求取非负整数(这时引进的松弛变量和剩余变量可以不要求取整数)。全整数规划:除了所有决策变量要求取非负整数外,系数aij和常数bi也要求取整数(这时引进的松弛变量和剩余变量也必须是整数)。混合整数规划:只有一部分的决策变量要求取非负整数,另一部分可以取非负实数。0-1整数规划:所有决策变量只能取0或1两个整数。(三)、整数规划与线性规划的关系从数学模型上看整数规划似乎是线性规划的一种特殊形式,求解只需在线性规划的基础上,通过舍入取整,寻求满足整数要求的解即可。但实际上两者却有很大的不同,通过舍入得到的解(整数)也不一定就是最优解,有时甚至不能保证所得到的解是整数可行解。