文档介绍：第五章整数规划?第一节整数规划的数学模型及解的特点?第二节解纯整数规划的割平面法?第三节分支定界法?第四节 0-1 型整数规划?第五节指派问题第五章整数规划在求解线性规划问题时,得到的最优解可能是分数或小数,但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题,称为整数线性规划(Integer linear Programming) 。第一节整数规划的数学模型及解的特点例1 某服务部门各时段(每 2h 为一时段)需要的服务员人数见下表。按规定服务员连续工作 8小时为一班。现要求安排服务员的工作时间,使服务部门服务员总数最少。 358 13 11 98 10 服务员最少数目 87654321时段且取整数。,0,,,, 3,5,8 13 , 11 9,8,10 min 54321 554543 5432 4321 321211 54321??????????????????????????xxxxx xxxxxx xxxx xxxx xxxxxx xxxxxz例2 现有资金总额为 B,可供选择的投资项目 n个,项目 j所需投资额和预期收益分别为 a j和c j,此外,由于种种原因,有三个附加条件:( 1) 若选择 1,则必须选择 2,反之则不一定;( 2)项目 3和4至少选择一个;( 3)项目 5、6、7中恰好选择 2个。应该如何选择项目,才能使总预期收益最大? njx xxx xx xx Bxa xczj nj jj nj jj,,2,1,10 2 1 max 765 43 12 1 1???????????????或例3 工厂 A 1和A 2生产某种物资。由于该种物资供不应求,故需再建一家工厂,相应的方案有 A 3和A 4两个。这种物资的需求地有 B 1 ~B 4四个。各工厂的生产能力、各地年需求量、各厂至各需求地的单位运费 c ij见下表。工厂 A3 或 A4 开工后,每年的生产费用估计分别为 1200 万元或 1500 万元。现要决定应该建设 A3 还是 A4 ,才能使每年的总费用(即全部物资运费和新工厂生产费用之和)最少。 150 300 400 350 需求量 200 5254 A4 200 2167 A3 600 7538 A2 400 4392 A1 生产能力 B4 B3 B2 B1例3 10 4,3,2,1;4,3,2,10 )1(200 200 600 400 150 300 400 350 .. )]1(1500 1200 [ min 44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11 44 34 24 14 43 33 23 13 42 32 22 12 41 31 21 11 41 41或, ?????????????????????????????????????????????y jix yxxxx yxxxx xxxx xxxx xxxx xxxx xxxx xxxx ts yyxcz ij ij ij ij引例某厂拟用火车装运甲、乙两种货物集装箱,每箱的体积、重量、可获利润以及装运所受限制如下: 13 24 托运限制 10 5 4 乙 20 2 5 甲利润(百元) 重量(百斤) 体积(米 3) 货物集装箱问两种货物各装运多少箱,可使获得利润最大? 是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢? 设甲、乙两种货物装运箱数分别为 x 1和x 2。显然, x 1、x 2 都要求为整数,于是可建立整数规划模型如下: Max z=20x 1 +10 x 2 (1) 5 x 1 +4 x 2≤ 24 (2) 2 x 1 +5 x 2≤ 13 (3) x 1,x 2≥ 0 (4) x 1,x 2为整数(5) 此例可解得 x 1 =, x 2 =0 ,凑整为 x 1 =5, x 2 =0 ,这就破坏了条件(2) ,因而不是可行解;如截断小数变为 x 1 =4, x 2 =0 ,这当然满足所有约束条件,但不是最优解,因为对 x 1 =4, x 2 =0 有z=80 ,而对x 1 =4, x 2 =1 (也是可行解)有 z=90。整数规划的数学模型????????????????njx m ibxats xcxf j nj ij ij nj jj,,2,1,0 ,,2,1,),(.. )( max(min) 1 1??且为整数?若要求所有 x j的解为整数,称为纯整数规划?若要求部分 x j的解为整数,称为混合整数规划?对应没有整数解要求的线性规划称之为松弛问题?整数规划的解是可数