运筹学第10讲整数规划(一).ppt

第10讲整数规划(一)浙江工业大学经贸管理学院曹柬一、整数规划的概念及其应用整数规划(IntegerProgram):决策变量取整 数的LP问题,简称IP问题纯整数规划(PureIP):全部整数取整0-1规划(Zero-OneIP):变量只能取0或1混合整数规划(MixedIP):部分整数取整运筹学第10讲:整数规划(一)篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高以及擅长的位置如下表所示。队员12345678身高(m):只能有一名中锋上场;至少有一名后卫;如1号和4号均上场,则6号不出场;2号和8号至少有一个不在场。问应选择哪5名队员上场,使队员身高最高。例10-1规划问题解:设0-1变量xi表示第i个队员是否上场,当xi=0时表示该队员不上场;当xi=1时表示该队员上场,建立如下的线性规划模型:目标函数:min∑cixi(ci为第i位队员的身高)约束条件:+x2=1x6+x7+x8≥1 x1+x4+x6≤2x2+x8≤1 ∑xi=5 xi=0或1,i=1,2,…,8最优值::x2=x3=x4=x5=x6=1其余xi=。由于该物资供不应求,故需再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3和B4四个。各厂年生产能力、各地年需求量、各厂到各需求地的单位物资运费如下表所示。BjB1B2B3B4生产能力(kt/年)AiA12934400A28357600A37612200A44525200需求量(kt/年)350400300150运费工厂A3或A4开工后,每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设工厂A3还是A4,才能使今后每年的总费用(即全部物资运费和新工厂生产费用之和)最少。混合整数规划问题二、Ip问题的求解松弛问题(slackproblem):去掉整数性约束的LP问题,或称原问题的LP问题例:maxz=6x1+5x2(1)—+x2≤9(2)5x1+7x2≤35(3) x1,x2≥0(4)—非负条件 x1,x2为整数(5)—整数性约束LP约束运筹学第10讲:整数规划(一)上述IP问题的LP问题的解为:,当松弛问题的所有非整变量值都较大时,例如xj≥100,圆整LP问题的方法是有效的运筹学第10讲:整数规划(一)maxz=6x1++x2≤9,5x1+7x2≤35 x1,x2≥0,x1,x2为整数图解法5x1+7x2=352x1+x2=9ABA为该问题的松弛问题的最优解B为该问题的最优解,x1*=4,x2*=1,z*=29x1x2993366z=6x1+5x2三、0-1规划问题的求解将各变量按系数绝对值由大到小的顺序进行排列,并令系数为负的变量xj=1-xj’;在max型中,从变量最大值开始求算;在min型中,从变量最小值开始求算,并验证约束条件是否成立maxZ=4x1-3x2++2x2-x3≤2 x1+4x2+x3≤4 x1+x2≤3 4x2+x3≤6 2x1+2x2+x3≤5 x1,x2,x3=0或1例4minZ=3x1+7x2-x3+!运筹学第10讲:整数规划(一)