第4讲 整数规划与0-1规划.ppt

第四讲 整数规划与0-1规划 数学对经济竞争力至为重要，数学是一种关键的普遍使用的、并授予人能力的技术。 ——格里姆(美国科学院院士) * * * * 基础教研部：夏冰 数学规划模型 x~决策变量 f(x)~目标函数 gi(x)?0~约束条件 分类：线性规划 整数规划与0－1规划 非线性规划 重点：模型的建立和结果的分析 安排生产计划, 满足每周的需求, 使4周总费用最小。 存贮费:每周每千箱饮料 0.2千元。 例3 饮料厂的生产与检修计划 在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周? 周次 需求量(千箱) 生产能力(千箱) 成本(千元/千箱) 1 15 30 5.0 2 25 40 5.1 3 35 45 5.4 4 25 20 5.5 合计 100 135 ? 某种饮料4周的需求量、生产能力和成本 问题分析 除第4周外每周的生产能力超过每周的需求； 生产成本逐周上升； 前几周应多生产一些。 周次 需求 能力 1 15 30 2 25 40 3 35 45 4 25 20 合计 100 135 成本 5.0 5.1 5.4 5.5 ? 饮料厂在第1周开始时没有库存； 从费用最小考虑, 第4周末不能有库存； 周末有库存时需支出一周的存贮费， 存贮费:0.2 (千元/周?千箱) ； 每周末的库存量等于下周初的库存量。 模型假设 x1~ x4：第1~4周的生产量 y1~ y3：第1~3周末库存量 符号说明 目标函数 约束条件 产量、库存与需求平衡 能力限制 非负限制 建立模型 思考：在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周? 约束条件 目标函数 产量、库存与需求平衡条件不变 检修安排在任一周均可，由此引入0-1变量wt ：wt=1表示检修安排在第t周(t=1,2,3,4）。 生产能力限制 检修安排在任一周均可，由此引入0-1变量wt ：wt=1表示检修安排在第t周(t=1,2,3,4）。 检修次数限制 应用Lingo软件计算得:w1=1, w2 , w3, w4=0; x1~ x4：15,45,15,25； y1~ y3：0,20,0 ; max Z=527 如果生产某一类型汽车，则至少要生产80辆， 那么最优的生产计划应作何改变？ 例4 汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。 小型 中型 大型 现有量 钢材（吨） 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 线性规划模型(LP) 模型求解 OBJECTIVE FUNCTION VALUE 1) 632.2581 VARIABLE VALUE REDUCED COST X1