文档介绍：第五章整数规划一、整数规划数学模型及解的特点二、解纯整数规划的割平面法三、分支定界法四、 0-1型整数规划五、指派问题第五章例1、集装箱运货货物体积(米 3/箱) 重量(百公斤/箱) 利润(千元/箱) 甲5 2 20 乙4 5 10 装运限制 24 13 一、数学模型及解的特点第五章解:设 x 1 , x 2 为甲、乙两货物各托运箱数 5x 1 +4x 2 ? 24 2x 1 +5x 2 ? 13 x 1 , x 2 ?0x 1 , x 2为整数 maxZ = 20 x 1 +10 x 2纯整数线性规划一、数学模型及解的特点第五章例2、背包问题背包可再装入 8单位重量, 10单位体积物品物品名称重量体积价值 1 书5 2 20 2 摄像机 3 1 30 3 枕头 1 4 10 4 休闲食品 2 3 18 5 衣服 4 5 15 一、数学模型及解的特点第五章解: x i为是否带第 i 种物品 maxZ =20x 1 +30x 2 +10x 3 +18x 4 +15x 55x 1 +3x 2 +x 3 +2x 4 +4x 5 ? 8 2x 1 +x 2 +4x 3 +3x 4 +5xX 5 ? 10 x i为0, 1 0-1型整数线性规划一、数学模型及解的特点第五章例3、选址问题 A 1A 3 B 2B 4B 3B 1A 2A i : 可建仓库地点,容量 a i,投资费用 b i ,建 2个 B j : 商店,需求 d j ( j=1 …4 )C ij : 仓库 i 到商店 j 的单位运费问:选择适当地点建仓库,在满足商店需求条件下,总费用最小。一、数学模型及解的特点第五章解:设 x i ( i=1,2,3) 为是否在 A i 建仓库 y ij ( i=1,2,3, j=1 …4)由i仓库向 j商店运货量???????? 31 31 41 min iij ij ijiiyCxbZ混合整数规划 y 11 + y 21 = d 1y 12 + y 22 + y 32 = d 2y 23 + y 33 = d 3y 14 + y 24 + y 34 = d 4x 1 + x 2 + x 3= 2y 11 + y 12 + y 14 ?a 1x 1y 21 + y 22 + y 23 + y 24?a 2x 2y 32 + y 33 + y 34 ?a 3x 3x i 为0-1,y ij?0 . 一、数学模型及解的特点第五章整数规线性划数学模型的一般形式: ????????????0 max 1 1 i ni ii ni iiX bXa XCZ,部分或全部为整数一、数学模型及解的特点第五章一、数学模型及解的特点几个概念: 1、整数规划( IP)--- 要求一部分或全部决策变量必须取整数值的规划问题。 2、松弛问题--- 不考虑整数条件,由余下的目标函数和约束条件构成的规划问题,称为该整数规划问题的松弛问题。 3、整数线性规划—若松弛问题是一个线性规划,则称该整数规划为整数线性规划。第五章常用问题: : 0 – 1 规划纯整数规划整数规划…….混合整数规划一、数学模型及解的特点