整数规划1-概念、分支定界法.pptVIP

整数规划 整数规划 整数规划- Integer Programming（IP） 整数规划的数学模型及解的特点 分支定界法、割平面法 0-1整数规划 指派问题 整数规划的数学模型及解的特点 整数规划数学模型的一般形式: 一部分或全部决策变量取整数值的规划问题 ——整数规划 整数规划中不考虑整数条件时对应的规划问题 ——该整数规划的松弛问题 松弛问题为线性规划的整数规划问题 ——整数线性规划 * 整数线性规划一般形式： * 中部分或全部取整数 整数线性规划的几种类型： 纯整数线性规划(pure integer linear programming):全部决策变量都必须取整数值。 混合整数线性规划(mixed integer linear programming)：决策变量中一部分必须取整数值，另一部分可以不取整数值。 0-1型整数线性规划(zero-one integer linear programming)：决策变量只能取值 0 或 1 。 * 整数规划的例子： * 货物 体积(米3/箱) 重量(百公斤/箱) 利润(百元/箱) 甲 5 2 20 乙 4 5 10 装运限制 24 13 例1、集装箱运货 * 解：设X1 , X2 为甲、乙两货物各托运箱数 5X1+4X2 ? 24 2X1+5X2 ? 13 X1 , X2 ?0 X1 , X2为整数 Max Z = 20 X1 + 10 X2 例2、背包问题 一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有个限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个价值以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其价值为cj.问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大? * * 背包可再装入8单位重量，10单位体积物品 物品 名称 重量 体积 价值 1 书 5 2 20 2 摄像机 3 1 30 3 枕头 1 4 10 4 休闲食品 2 3 18 5 衣服 4 5 15 * 解：Xi为是否带第 i 种物品 maxZ=20X1 + 30X2 +10X3+18X4 +15X5 5X1+3X2 +X3 +2X4 +4X5 ? 8 2X1+X2 +4X3 +3X4 +5X5 ? 10 Xi为0, 1 某服务部门各时段（每2小时为一时段）需要的服务员人数见下表。按规定服务员连续工作8小时为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。 * 例3、人员排班 解：设在第j时段开始上班的人数为 ，则 * 且为整数 解的特点 整数线性规划及其松弛问题比较，前者的最优解的目标函数值不会优于后者的。 * 例：考虑下面的整数规划问题 且取整数 从图上分析： * 0 1 2 3 4 5 6 7 8 B P C 整数规划最优解 分支定界法 分支定界法是一种隐枚举方法（implicit enumeration）或部分枚举方法，在20世纪60年代初由是Land Doig和Dakin等人提出，是枚举方法基础上的改进。 分支定界法的关键是分支和定界。 思路：利用其松弛问题的最优解