《运筹学课件ch5整数规划》课件.ppt

谢谢！ 第五章 整 数 规 划 Integer Programming 四个目标: 熟悉 IP规划适用的应用领域 掌握建立好的模型化技巧 使用EXCEL获得模型的结果 说明与分析结果报告 整数规划——变量只能取整数的规划问题。 当变量只能取0或1两个值，称0-1规划。 整数规划分类： 纯整数规划——全部变量为整数。 混合整数规划——部分变量为整数。 典型的整数线性规划问题 一、背包问题 有一徒步旅行者要带一背包，设对背包的总重量限制为b千克，今有n种物品可供选择，已知第j种物品每件重量为aj千克，使用价值为cj，问旅行者应如何选取这些物品，使得总价值最大？ 令决策变量xj表示第j种物品的装入件数 模型建立 整数线性规划模型(IP) 二、 投资场所选址问题(0-1整数规划Binary planning) 计划在东、西、南三个区开设若干商业网点，拟在 A1，…，A7 7个地点中选择。规定：东区在A1，A2，A3中 至多选2个，西区在A4，A5中至少选1个，南区在A6，A7中 至少选1个。已知在Ai建点需投资bi，可获利ci，现共有资 金为B。问应如何布局可使总利润最大？ 分析： 东区在A1，A2，A3中至多选2个 怎样表示？ 问2:如果生产某一类型汽车，则至少要生产80辆， 那么最优的生产计划应作何改变？ 例1 汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。 小型 中型 大型 现有量 钢材（吨） 1.5 3 5 600 劳动时间（小时） 280 250 400 60000 利润（万元） 2 3 4 问1:制订月生产计划，使工厂的利润最大。 整数线性规划 设每月生产小、中、大型汽车的数量分别为x1, x2, x3 汽车厂生产计划 模型建立 小型 中型 大型 现有量 钢材 1.5 3 5 600 时间 280 250 400 60000 利润 2 3 4 线性规划模型(LP) 模型求解 3） 模型中增加条件：x1, x2, x3 均为整数，重新求解。 OBJECTIVE FUNCTION VALUE 1) 632.2581 VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.731183 3) 0.00000 0.003226 结果为小数，怎么办？ 1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。 2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。 但必须检验它们是否满足约束条件。为什么？ IP可用LINDO直接求解 整数规划(Integer Programming,简记IP) “gin 3”表示“前3个变量为整数”，等价于： gin x1 gin x2 gin x3 IP 的最优解x1=64，x2=168，x3=0，最