2-5最优化.ppt

–整数规划主要是指整数线性规划。一个线性规划问题,如果要求部分决策变量为整数,则构成一个整数规划问题。–所有变量都要求为整数的称为纯整数规划或称全整数规划; –仅有一部分变量要求为整数的称为混合整数规划; –有的变量限制其取值只能为 0或1,这类特殊的整数规划称为 0-1规划。§5 整数线性规划整数规划问题及其数学模型例1某工厂生产甲、乙两种设备,已知生产这两种设备需要消耗材料 A、材料 B,有关数据如下, 问这两种设备各生产多少使工厂利润最大? 设备材料甲乙资源限量材料 A( kg )2314 材料 B( kg ) 利润(元/件) 32 解: 设生产甲、乙这两种设备的数量分别为 x 1、x 2, 由于是设备台数,则其变量都要求为整数,建立模型如下: Maxz =3x 1 +2 x 22x 1 +3 x 2≤14 x 1 + x 2≤ x 1、x 2≥0,且为整数图4-1 要求该模型的解,不考虑整数约束条件,用单纯形法对相应线性规划求解,其最优解为: x 1= x 2= max z= ---- 凑整得到的(3,3)(4,2)不在可行域范围内。--(3,2)点尽管在可行域内,但没有使目标达到极大化。--(4,1)使目标函数达到最大,即 z=14。 Maxz =3x 1 +2 x 22x 1 +3 x 2≤14 x 1 + x 2≤ x 1、x 2≥0,且为整数例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 +5X 5 ? 10 X i为0, 1 例3、选址问题 A 1A 3B 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商店运货量 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 ???????? 31 31 41 min iij ij ijiiyCxbZ混合整数规划 A 1A 3B 2B 4B 3B 1A 2 指派问题( Assignment problem ) ?指派问题是 0-1整数规划问题。在实践中经常会遇到:有 m项任务要 m个人去完成(每人只完成一项工作),在分配过程中要充分考虑各人的知识、能力、经验等,应如何分配才能使工作效率最高或消耗的资源最少?这类问题就属于指派问题。引入 0-1变量 x ij ????项任务个人完成第不指派第项任务个人完成第指派第 ji jix ij0 1 ij ij mj mixcz????? 11 min ????????????????????10 ,,2,11 ,,2,11. 1 1或 ij ij mi ij mjx mjx mixts??二、整数规划数学模型的一般形式由上述例子可得出整数规划数学模型的一般形式: Min z =CX AX=b X ≥0,且为整数或部分为整数若称该整数规划问题为原问题,则线性规划问题: Min z =CX A