建模培训-线性规划.ppt

一 引言 二 线性规划模型 三 整数线性规划模型 规划理论及模型 四 非线性规划模型 五 多目标规划模型 六 规划模型举例 一 引言 规划模型的应用极其广泛 其作用已为越来越多的人所重视 随着计算机的逐渐普及 它已经渗透于工农业生产 商业活动 军事行为核科学研究的各个方面 为社会节省的财富 创造的价值无法估量 特别是在数模竞赛过程中 规划模型是最常见的一类数学模型 从近十年全国大学生数模竞赛试题的解题方法统计结果来看 规划模型占到了50 也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析 求解 二 线性规划模型 线性规划模型是所有规划模型中最基本 最 简单的一种 它是指在一组线性的等式或不等式的约束条件下 寻求以线性函数的最大 小 值为目标的数学模型 线性规划模型的形式 一般形式 规范形式 标准形式 三种形式的线性规划问题全都是等价的 即一种形式的线性规划可以简单的变换为另一种形式的线性规划 且它们有相同的解 在实际应用中 特别是数学建模过程中 遇到线性规划问题的求解 我们一般都是利用现有的软件进行求解 比较常用的求解线性规划模型的数学软件有LINGO和LINDO及Matlab软件等 线性规划模型的求解 运输问题 运输问题的数学模型为 产量限制 销量限制 非负限制 总运费最省 运输问题举例 设要从甲地调出物资2000吨 从乙地调出物资 1100吨 分别供给A地1700吨 B地1100吨 所示 假定运费与运量成正比 在这种情况下 C地200吨 D地100吨 已知每吨运费如表1 1 采用不同的调拨计划 运费就可能不一样 现在问 怎样才能找出一个运费最省的调拨计划 分析 设甲 乙两地调往A B C D四地的物资 量为 产量限制 销量限制 在运输问题中若各产地的总产量等于各销地的 否则 称为不平衡的运输问题 包括 则称该问题为平衡的运输问题 总产量 总销量和总产量 总销量 显然 运输问题是一个标准的线性规划问题 因而当然可以运用LINGO和LINDO软件求解 总销量 即 对于线性规划问题 如果要求其决策变量取 整数值 则称该问题为整数线性规划问题 0 1整数规划是整数规划的特殊情形 它要求 三 整数线性规划模型 线性规划模型中的决策变量只能取值为0或1 我们可以利用LINGO和LINDO软件包来求解 整数线性规划和0 1整数规划模型 背包问题 有n个物品 编号为1 2 n 第i件物品 重ai千克 价值为ci元 现有一个载重量不超过 大 应如何装载这些物品 a千克的背包 为了使装入背包的物品总价值最 用变量xi表示物品i是否装包 i 1 2 n 并令 解 可得到背包问题的规划模型为 总载重限制 0 1变量 背包中物品总价值 指派问题 有n项任务 由n个人来完成 每个人必须 要cij小时 如何合理安排时间才能使总用时最小 引入状态变量xij 并令 解 则总用时表达式为 且只需完成其中一件 第i个人完成第j项任务需 可得到指派问题的规划模型为 每项任务必有一个人来完成 每个人只能做一项任务 0 1变量 上面介绍的指派问题称为指派问题的标准形式即每项任务有且只有一人承担 每人只能承担一项 针对任务 针对人 总用时最少 四 非线性规划模型 前面介绍了线性规划问题 即目标函数和约束条件都是线性函数的规划问题 但在实际工作中 还常常会遇到另一类更一般的规划问题 即目标函数和约束条件中至少有一个是非线性函数的规划问题 即非线性规划问题 事实上 客观世界中的问题许多是非线性的 给予线性大多是近似的 是在作了科学的假设和简化后得到的 为了利用线性的知识 许多非线性问题常进行线性化处理 但在实际问题中 有一些是不能进行线性化处理的 否则将严重影响模型对实际问题近似的可依赖型 由于非线性规划问题在计算上是有一定困难的 理论上的讨论也不能像线性规划那样给出简洁的结果形式和全面透彻的结论 这点又限制了非线性规划的应用 所以 在数学建模时 要进行认真的分析 对实际问题进行合理的假设 简化 首先考虑用线性规划模型 若线性近似误差较大时 则考虑用非线性规划 非线性规划问题的标准形式为 非线性规划模型按约束条件可分为以下三类 无约束非线性规划模型 等式约束非线性规划模型 不等式约束非线性规划模型 工程造价问题 要建造容积为1500立方米的长方形仓库 已知每平方米墙壁 屋顶和地面的造价分别为4元 6元 12元 基于美学考虑 要求宽度应为高度的2倍 试建立使造价最省的数学模型 解设仓库的宽 高 长分别为 建立模型为 这是一个非线性等式约束规划模型 五 多目标规划模型 在许多实际问题中 衡量一个方案的好坏标准往往不止一个 例如设计一个导弹 既要射程最远 又要燃料最省 还要精度最高 这一类问题统称为多目标最优化问题或多目标规划问题 多目标规划问题与前面讲的规划问题的主要区别在于 目标函数不止一个 而是若干个 多目标规划的求解 规划模型举例 如何装运 使本次飞行获利最大 三个货舱最大载重 吨 最大容积 米3 例1货机装运 三个货舱中实际载重必须与其最大载重成比例 飞机平衡 决策变量 xij 第i种货物装入第j个货舱的重量 吨 i 1 2 3 4 j 1 2 3 分别代表前 中 后仓 模型假设 每种货物可以分割到任意小 每种货物可以在一个或多个货舱中任意分布 多种货物可以混装 并保证不留空隙 模型建立 2 货舱容积 目标函数 利润 约束条件 1 货舱重量 货仓限制 约束条件 4 平衡要求 3 货物重量 货物2 前仓10 后仓5 货物3 中仓13 后仓3 货物4 中仓3 模型求解 最大利润约121516元 货物 供应点货舱 需求点 重量限制空间限制平衡要求 输入Lindo求解 若丁的蛙泳成绩退步到1 15 2 戊的自由泳成绩进步到57 5 组成接力队的方案是否应该调整 如何选拔队员组成4 100米混合泳接力队 例2混合泳接力队的选拔 5名候选人的百米成绩 穷举法 组成接力队的方案共有5 120种 目标函数 若选择队员i参加泳姿j的比赛 记xij 1 否则记xij 0 0 1规划模型 cij 秒 队员i第j种泳姿的百米成绩 约束条件 每人最多入选泳姿之一 每种泳姿有且只有1人 模型求解 最优解 x14 x21 x32 x43 1 其它变量为0 成绩为253 2 秒 4 13 2 输入LINDO求解 甲 自由泳 乙 蝶泳 丙 仰泳 丁 蛙泳 丁蛙泳c43 69 6 75 2 戊自由泳c54 62 4 57 5 方案是否调整 乙 蝶泳 丙 仰泳 丁 蛙泳 戊 自由泳 最优解 x21 x32 x43 x51 1 成绩为4 17 7 c43 c54的新数据重新输入模型 用LINDO求解 讨论 指派问题 人数多于任务数 解决方法 建立0 1规划模型 例3选课策略 要求至少选两门数学课 三门运筹学课和两门计算机课 为了选修课门数最少 应学哪些课程 若选修课程最少 且学分尽量多 应学哪些课程 课程情况 0 1规划模型 决策变量 目标函数 xi 1 选修课号i的课程 xi 0 不选 选修课程总数最少 约束条件 最少2门数学课 3门运筹学课 2门计算机课 先修课程要求 最优解 x1 x2 x3 x6 x7 x9 1 其它为0 6门课程 总学分21 约束条件 x3 1必先有x1 x2 1 模型求解 LINDO 学分最多 多目标优化的处理方法 化成单目标优化 两目标 多目标 规划 讨论 选修课程最少 学分尽量多 应学哪些课程 课程最少 以学分最多为目标 而不管课程多少 以课程最少为目标 而不管学分多少 在课程最少的前提下以学分最多为目标 最优解 x1 x2 x3 x5 x7 x9 1 其它为0 总学分由21增至22 注意 最优解不唯一 可将x9 1易为x6 1 多目标规划的求解 主要目标法 多目标规划的求解 线性加权法 对学分数和课程数加权形成一个目标 如三七开 最优解 x1 x2 x3 x4 x5 x6 x7 x9 1 其它为0 总学分28 讨论与思考 最优解与 1 0 2 1的结果相同 学分最多 最优解与 1 1 2 0的结果相同 课程最少 注意 本题中 先修课程 的约束 类似的对 要选甲必选乙 这样的约束 也可用不等式来描述 生产中通过切割 剪裁 冲压等手段 将原材料加工成所需大小 原料下料问题 按照工艺要求 确定下料方案 使所用材料最省 或利润最大 问题1 如何下料最节省 例4钢管下料 问题2 客户增加需求 节省的标准是什么 由于采用不同切割模式太多 会增加生产和管理成本 规定切割模式不能超过3种 如何下料最节省 按照客户需要在一根原料钢管上安排切割的一种组合 切割模式 合理切割模式的余料应小于客户需要钢管的最小尺寸 钢管下料 为满足客户需要 按照哪些种合理模式 每种模式切割多少根原料钢管 最为节省 合理切割模式 2 所用原料钢管总根数最少 钢管下料问题1 两种标准 1 原料钢管剩余总余量最小 xi 按第i种模式切割的原料钢管根数 i 1 2 7 约束 满足需求 决策变量 目标1 总余量 最优解 x2 12 x5 15 其余为0 最优值 27 整数约束 xi为整数 按模式2切割12根 按模式5切割15根 余料27米 当余料没有用处时 通常以总根数最少为目标 目标2 总根数 约束条件不变 最优解 x2 15 x5 5 x7 5 其余为0 最优值 25 xi为整数 按模式2切割15根 按模式5切割5根 按模式7切割5根 共25根 余料35米 与目标1的结果 共切割27根余料27米 相比 虽余料增加8米 但减少了2根 钢管下料问题2 对大规模问题 用模型的约束条件界定合理模式 增加一种需求 5米10根 切割模式不超过3种 现有4种需求 4米50根 5米10根 6米20根 8米15根 用枚举法确定合理切割模式 过于复杂 决策变量 xi 按第i种模式切割的原料钢管根数 i 1 2 3 r1i r2i r3i r4i 第i种切割模式下 每根原料钢管生产4米 5米 6米和8米长的钢管的数量 满足需求 模式合理 每根余料不超过3米 整数非线性规划模型 目标函数 总根数 约束条件 整数约束 xi r1i r2i r3i r4i i 1 2 3 为整数 增加约束 缩小可行域 便于求解 原料钢管总根数下界 特殊生产计划 对每根原料钢管模式1 切割成4根4米钢管 需13根 模式2 切割成1根5米和2根6米钢管 需10根 模式3 切割成2根8米钢管 需8根 原料钢管总根数上界 13 10 8 31 模式排列顺序可任定 需求 4米50根 5米10根 6米20根 8米15根 每根原料钢管长19米 LINGO求解整数非线