优化问题及其数学模型五解析.ppt

（四）整数规划问题及其数学模型 回顾： 线性规划 例： 为整数 整数线性规划 在线性规划问题中，有些最优解可能是分数或小数，但对于某些问题，常要求解必须是整数(称为整数解)。例如，所求解是机器的台数、完成工作的人数或装货的车数等。 为满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。 因此，对求最优整数解的问题，有必要另行研究。我们称这样的问题为整数线性规划(integer linear programming)，简称ILP。 例（背包问题）有一个背包(泛指仓库、船舱、卫星仓等)，最大装载质量为50单位，现有A，B, C 3个物品（不可拆卸），每种的数量无限。 A，B, C的质量分别为10, 41, 20；而3种物品的价值分别为17，32, 75。问每种物品各取多少装入背包，可使背包中物品的总价值最高？ 设装入背包的A, B, C 3种物品各为x1,x2,x3件 且x1,x2,x3为整数。 二 怎么解线性整数规划 思考：是否可以求解线性规划来解线性整数规划？ 且x1,x2,x3为整数。 若不考虑整数约束，最优解为 最优解为 一般不可行 (1)整数线性规划问题的求解法一：穷举法 穷举所有可行的整数解，然后比较它们的目标函数值，从而确定最优解。 对于规模较小的问题，变量个数很少，可行解的组合数也较小时，这个方法是可行的，也是有效的。 对于大型问题，可行的整数组合数会很大。显然，穷举法是不可取的。 仅检查可行的整数解的一部分，就能定出最优的整数解的方法。分支定界解法就是其中之一。 分支定界法可用于解纯整数或混合整数线性规划问题。 20世纪60年代初由Land Doig和Dakin等提出，是解整数线性规划的重要方法之一。 (2)整数线性规划问题的求解法二：分支定界法 如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？ 例1 汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。 小型 中型 大型 现有量 钢材（吨） 1.5 3 5 600 劳动时间（小时） 280 250 400 60000 利润（万元） 2 3 4 制订月生产计划，使工厂的利润最大。 设每月生产小、中、大型汽车的数量分别为x1, x2, x3 小型 中型 大型 现有量 钢材 1.5 3 5 600 时间 280 250 400 60000 利润 2 3 4 为非负整数 IP可用LINGO直接求解 整数规划(Integer Programming,简记IP) max=2*x1+3*x2+4*x3; 1.5*x1+3*x2+5*x3=600; 280*x1+250*x2+400*x3=60000; @gin(x1); @gin(x2); @gin(x3); 模型求解 OBJECTIVE FUNCTION VALUE 1) 632.0000 VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000 IP 结果输出 IP 的最优解x1=64，x2=168，x3=0，最优值z=632 其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解： 方法1：分解为8个LP子模型 若生产某类汽车，则至少生产80辆，求生产计划。 x1,x2,, x3=0 或 ?80 ? ? ? x1=80，x2= 150，x3=0