数学模型第六讲整数规划模型与求解软件.ppt

主讲人 周大勇E MAIL zhoudy102 理学院应用数学教研室 数学模型 课程教学课件 版权所有 大连交通大学理学院应用数学教研室Copyright 2011DalianJiaotongUniversity Allrightsreserved 2010 2011学年第二学期 第六讲整数规划模型与0 1规划 时间 2011年3月24日主讲人 周大勇E MAIL zhoudy102 整数规划模型及其处理方法0 1规划模型及其处理方法数学软件求解上述模型分析 请各小组思考下列问题 数学规划模型的一般形式是什么 E mail zhoudy102 常用的解决规划模型的软件有哪些 规划模型构成及软件处理 实际问题中的优化模型 x 决策变量 f x 目标函数 gi x 0 约束条件 数学规划 线性规划非线性规划整数规划 重点在模型的建立和结果的分析 E mail zhoudy102 处理软件 LindoLingoMatlabMathematica 设每月生产小 中 大型汽车的数量分别为x1 x2 x3 汽车厂生产计划 模型建立 线性规划模型 LP E mail zhoudy102 模型求解 3 模型中增加条件 x1 x2 x3均为整数 重新求解 OBJECTIVEFUNCTIONVALUE1 632 2581VARIABLEVALUEREDUCEDCOSTX164 5161290 000000X2167 7419280 000000X30 0000000 946237ROWSLACKORSURPLUSDUALPRICES2 0 0000000 7311833 0 0000000 003226 结果为小数 怎么办 1 舍去小数 取x1 64 x2 167 算出目标函数值z 629 与LP最优值632 2581相差不大 2 试探 如取x1 65 x2 167 x1 64 x2 168等 计算函数值z 通过比较可能得到更优的解 但必须检验它们是否满足约束条件 为什么 请写出在Lindo软件的源程序 E mail zhoudy102 IP可用LINDO直接求解 整数规划 IntegerProgramming 简记IP gin3 表示 前3个变量为整数 等价于 ginx1ginx2ginx3 IP的最优解x1 64 x2 168 x3 0 最优值z 632 max2x1 3x2 4x3st1 5x1 3x2 5x3 600280 x1 250 x2 400 x3 60000endgin3 OBJECTIVEFUNCTIONVALUE1 632 0000VARIABLEVALUEREDUCEDCOSTX164 000000 2 000000X2168 000000 3 000000X30 000000 4 000000 IP结果输出 E mail zhoudy102 其中3个子模型应去掉 然后逐一求解 比较目标函数值 再加上整数约束 得最优解 方法1 分解为8个LP子模型 汽车厂生产计划 讨论 若生产某类汽车 则至少生产80辆 求生产计划 x1 x2 x3 0或 80 x1 80 x2 150 x3 0 最优值z 610 LINDO中对0 1变量的限定 inty1inty2inty3 方法2 引入0 1变量 化为整数规划 M为大的正数 可取1000 OBJECTIVEFUNCTIONVALUE1 610 0000VARIABLEVALUEREDUCEDCOSTX180 000000 2 000000X2150 000000 3 000000X30 000000 4 000000Y11 0000000 000000Y21 0000000 000000Y30 0000000 000000 若生产某类汽车 则至少生产80辆 求生产计划 x1 0或 80 最优解同前 E mail zhoudy102 NLP虽然可用现成的数学软件求解 如LINGO MATLAB 但是其结果常依赖于初值的选择 方法3 化为非线性规划 非线性规划 Non LinearProgramming 简记NLP 实践表明 本例仅当初值非常接近上面方法算出的最优解时 才能得到正确的结果 若生产某类汽车 则至少生产80辆 求生产计划 x1 0或 80 E mail zhoudy102 分派问题 接力队选拔和选课策略 若干项任务分给一些候选人来完成 每人的专长不同 完成每项任务取得的效益或需要的资源就不同 如何分派任务使获得的总效益最大 或付出的总资源最少 若干种策略供选择 不同的策略得到的收益或付出的成本不同 各个策略之间有相互制约关系 如何在满足一定条件下作出决择 使得收益最大或成本最小 E mail zhoudy102 丁的蛙泳成绩退步到1 15 2 戊的自由泳成绩进步到57 5 组成接力队的方案是否应该调整 如何选拔队员组成4 100米混合泳接力队 混合泳接力队的选拔 5名候选人的百米成绩 穷举法 组成接力队的方案共有5 120种 E mail zhoudy102 目标函数 若选择队员i参加泳姿j的比赛 记xij 1 否则记xij 0 0 1规划模型 cij 秒 队员i第j种泳姿的百米成绩 约束条件 每人最多入选泳姿之一 每种泳姿有且只有1人 E mail zhoudy102 模型求解 最优解 x14 x21 x32 x43 1 其它变量为0 成绩为253 2 秒 4 13 2 MIN66 8x11 75 6x12 87x13 58 6x14 67 4x51 71x52 83 8x53 62 4x54SUBJECTTOx11 x12 x13 x14 1 x41 x42 x43 x44 1x11 x21 x31 x41 x51 1 x14 x24 x34 x44 x54 1ENDINT20 输入LINDO求解 甲 自由泳 乙 蝶泳 丙 仰泳 丁 蛙泳 E mail zhoudy102 丁蛙泳c43 69 6 75 2 戊自由泳c54 62 4 57 5 方案是否调整 敏感性分析 乙 蝶泳 丙 仰泳 丁 蛙泳 戊 自由泳 IP规划一般没有与LP规划相类似的理论 LINDO输出的敏感性分析结果通常是没有意义的 最优解 x21 x32 x43 x54 1 成绩为4 17 7 c43 c54的新数据重新输入模型 用LINDO求解 指派 Assignment 问题 每项任务有且只有一人承担 每人只能承担一项 效益不同 怎样分派使总效益最大 讨论 E mail zhoudy102 为了选修课程门数最少 应学习哪些课程 选课策略 要求至少选两门数学课 三门运筹学课和两门计算机课 选修课程最少 且学分尽量多 应学习哪些课程 E mail zhoudy102 0 1规划模型 决策变量 目标函数 xi 1 选修课号i的课程 xi 0 不选 选修课程总数最少 约束条件 最少2门数学课 3门运筹学课 2门计算机课 E mail zhoudy102 先修课程要求 最优解 x1 x2 x3 x6 x7 x9 1 其它为0 6门课程 总学分21 0 1规划模型 约束条件 x3 1必有x1 x2 1 模型求解 LINDO E mail zhoudy102 学分最多 多目标优化的处理方法 化成单目标优化 两目标 多目标 规划 讨论 选修课程最少 学分尽量多 应学习哪些课程 课程最少 以学分最多为目标 不管课程多少 以课程最少为目标 不管学分多少 E mail zhoudy102 多目标规划 在课程最少的前提下以学分最多为目标 最优解 x1 x2 x3 x5 x7 x9 1 其它为0 总学分由21增至22 注意 最优解不唯一 LINDO无法告诉优化问题的解是否唯一 可将x9 1易为x6 1 E mail zhoudy102 多目标规划 对学分数和课程数加权形成一个目标 如三七开 最优解 x1 x2 x3 x4 x5 x6 x7 x9 1 其它为0 总学分28 E mail zhoudy102 讨论与思考 最优解与 1 0 2 1的结果相同 学分最多 多目标规划 最优解与 1 1 2 0的结果相同 课程最少 E mail zhoudy102 课程论文二 发布时间 请安静 论文上交时间 2011年9月27日 E mail zhoudy102 注意 1 封面必须是打印版 格式已下发 2 从摘要开始全部为手写稿 课程论文评分标准 方法新颖巧妙 格式非常好20分模型建立 求解合理 格式很好18 19分模型建立 求解合理 格式规范16 17分模型建立 求解基本合理 格式一般14 15分模型建立 求解有问题 格式一般12 13分模型建立不正确 格式糟糕 态度有问题0 6分 E mail zhoudy102 E mail zhoudy102 A题 营养配餐问题每种蔬菜含有的营养素成份是不同的 从医学上知道 每人每周对每种营养成分的最低需求量 某医院营养室在制定下一周菜单时 需要确定表A 1中所列六种蔬菜的供应量 以便使费用最小而又能满足营养素等其它方面的要求 规定白菜的供应一周内不多于20kg 其它蔬菜的供应在一周内不多于40kg 每周共需供应140kg蔬菜 为了使费用最小又满足营养素等其它方面的要求 试建立数学模型 说明在下一周内应当供应每种蔬菜各多少kg 表A 1 E mail zhoudy102 B题 广告竞争计划某市场研究小组考虑下一步如何选择广告竞争计划 在进行大量的调查研究后 制定了各种可供选择的方案 方