线性规划中的若干问题.ppt

例一 生产安排模型 用白纸坯生产原稿纸 日记本 练习本 所需要的白纸坯 劳动力 以及产生的利润资料如下 一捆原稿纸 一扎日记本 一箱练习本分别消耗白纸坯10 3 40 3 80 3kg 劳动力的工作效率分别是为每人每月可生产30捆原稿纸 或可生产30扎日记本 或可生产30箱练习本 而每捆原稿纸可获利2元 每扎日记本可获利3元 每箱练习本可获利1元 企业有工人100人 每月供应白纸坯30000kg 问企业每月应该怎样安排生产可获利最大 解 1 确定决策变量 设x1 x2 x3为每月生产原稿纸 日记本 练习本的生产量 2 明确目标函数 获利最大 即求目标函数总利润2x1 3x2 x3的最大值 3 所满足的约束条件 劳动力限制 白纸坯限制 基本要求 x1 x2 x3 0 具体模型为 s t 运输问题是一类特殊的线性规划模型 该模型的建立最初用于解决一个部门的运输网络所要求的最经济的运输路线和产品的调配问题 并取得了成功 然而 在实际问题的应用中 除运输问题外 许多非运输问题的实际问题一样可以建立其相应的运输问题模型 并由此而求出其最优解 下面以 产销平衡模型 对运输问题进行一下简单的概括和描述 设某产品产自m个地方 在n个地方销售 且i产地的产量为ai 在j地的销售量为bj 假设产销平衡 即 总产量 总销量 个地方 在 个地方销售 且 产地的产量为 在 地的销售量为 假设产销平衡 即 总产量 总销量 若从 产地到 销售地的单位运价为 例二 运输问题 若从i产地到j销售地的单位运价为cij 问如何组织运输才能使总的运输费为最小 此为产销平衡类型 解 1 确定决策变量 设xij表示从i产地销往j销售地的销售量 共有m n个决策变量 2 明确目标函数 总运输费最小 即求 的最小值 3 所满足的约束条件 产量限制和销量限制 i产地的产品量等于分销给n个地方的销量总和 j地的接收量等于m个产地销往j地的销量总和 基本要求 xij 0 i 1 2 m j 1 2 n 于是可得模型 s t 比如 下表给出某运输问题的产销平衡表与单位运价表 求其最佳运输方案 只需要建立模型即可 下面看一个产销不平衡的例子 某厂按合同规定须于当年每个季度末分别提供10 15 25 20台同一规格的柴油机 已知该厂各季度的生产能力及生产每台柴油机的成本如下表 如果生产出来的柴油机当季不交货 每台每积压一个季度需储存 维护等费用0 15万元 试求在完成合同 即每个季度的产量不少于合同订货量 供大于求 的情况下 使该厂全年生产总费用为最小的决策方案 而1 2 3 4季度末的合同需求为10 15 25 20台 只需要建立模型即可 提示 设xij为第i季度生产的柴油机在第j季度交货的台数 例三 生产配套问题 设有n个车间要生产m种产品 第j车间每天生产第i种产品至多aij件 假设以一天为制定生产计划的时间单位 则aij表示j车间全天只生产第i种产品而不生产其他产品时的最大产量 假设这m种产品第i种产品需要bi件配成一套 问如何安排生产任务才能使产出的成套产品最多 注 以一天为制定生产计划的时间单位解 1 确定决策变量 因为主要是对一天的时间进行分配 使哪一段时间生产哪种产品 所以令Xij表示j车间安排用于生产i种产品的时间 占全天的比例 那么aij xij表示j车间每天生产i种产 品的数目 例如 车间1每天至多生产某产品6件 若安排1 3天时间去生产 则至多可以产出2件 决策变量共有个 如果令 则表示每天全厂生产i种产品的总数目 此时 取值为非负整数 2 明确目标函数 令Z表示一天生产的成套产品数 即求Z的最大值 3 所满足的约束条件 配套限制 全天生产i种产品的总数目 不小于配套所需 要的i种产品数 共有m个不等式 时间限制 xij表示j车间安排用于生产i种产品的时间 因为要生产m种产品 所以j车间一天的时间被分成了m份 故共有n个不等式 基本要求 如果以yij为决策变量 则yij取值为非负整数 模型为目标函数 比如设有A B C三个车间要生产甲 乙 丙三种零件 下表数据表示各车间在一天内至多生产的零件数目 假设2件甲零件 1件乙零件和3件丙零件配成一套 问如何安排生产才能使三个车间生产出的成套零件最多 只需要建立模型即可 例四指派问题 也称0 1规划 设有n项任务要分给n个人去完成 一人只能完成一项 由于每个人的专长不同 故完成不同任务所需要的成本 或收益 也不同 若第i个人完成第j项任务的成本 或收益 为cij 问题是如何分派这些任务 哪一个人去完成哪一项任务 才能使总成本最小 或总收益最大 这个问题似乎不知道什么是决策变量 但我们可以人为量化 解 1 确定决策变量 令共有个决策变量 2 明确目标函数 总成本最小 或总收益最大 3 所满足的约束条件 一人一件限制 一件一人限制 其中 模型为目标函数 约束为 例 某公司员工甲 乙 丙 丁 由于四人各自技术特点的不同 他们完成A B C D四种工作所带来的效益 单位 千元 如下表所示 应指派何人完成何种工作 能使总的效益最大 建立这个问题的线性规划模型 不求解 运筹学不平衡指派问题有12345项工作 分配给甲 乙 丙 丁四个人完成 每个人完成时间如下 由于工作数多于人数故考虑 每个工人仅能完成一项工作 问如何安排工作使总的工作时间最短 假如工作4必须完成 则又该如何指派使总的工作时间最短 例五 下料问题 下料问题 cuttingstockproblem 是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题 此类问题在工程技术和工业生产中有着重要和广泛的应用 这里的 实用下料问题 则是在某企业的实际条件限制下的单一材料的下料问题 钢管切割问题 某钢管零售商从钢管厂进货 将钢管按照顾客的要求切割后售出 从钢管厂进货时所得到的钢管都是19M 1 现有一客户需要50根4M 20根6M和15根8M的钢管 应如何下料最节省 2 零售商如果采用不同的切割模式太多 将会导致生产过程复杂化 从而增加生产和管理成本 所以该零售商规定采用的不同切割模式不能超过3种 此外该客户需要 1 种的三种钢管外 还需要10根5M的钢管 该如何下料最节省 问题分析对于下料问题首先要确定采用哪些切割模式 所谓切割模式 是指按照顾客要求的长度在原料钢管上安排切割的一种组合 例如 我们可以将19m的钢管切割成3根长4m的钢管 余料为7m 或者将长19m的钢管切割成长4m 6m和8m的钢管各1根 余料为1m 显然 可行的切割模式是很多的 其次 应当明确哪些切割模式是合理的 合理的切割模式通常还假设余料不应大于或等于客户需要钢管的最小尺寸 例如 将长19m的钢管切割成3根4m的钢管是可行的 但余料为7m 可进一步将7m的余料切割成4m钢管 余料为3m 或者将7m的余料切割成6m钢管 余料为1m 经过简单的计算可知 问题1 的合理切割模式一共有7种 如表3所示 于是问题化为在满足客户需要的条件下 按照哪几种合理的模式 每种模式切割多少根原料钢管最为节省 而所谓节省 可以有两种标准 一是切割后剩余的总余料量最小 二是切割原料钢管的总根数最少 下面将对这两个目标分别讨论 表3钢管下料问题1 的合理切割模式 模型问题1 用xi表示按照表3第i种模式 i 1 2 7 切割的原料钢管的根数 若以切割后剩余的总余料量最小为目标 则按照表3最后一列可得模型一 目标函数总余料最少min 3x1 x2 3x3 3x4 x5 x6 3x7 1 约束条件为客户的需求 按照表3应有4x1 3x2 2x3 x4 x5 50 3 x2 2x4 x5 3x6 20 4 x3 x5 2x7 15 5 其中决策变量根数xi显然应当是非负整数若以切割原料钢管的总根数最少为目标 则模型二 总根数Min x1 x2 x3 x4 x5 x6 x7 2 约束条件为客户的需求 与上面一样 不变 2 同问题1 一样 只使用合理的切割模式 其余料不应大于3m 因为客户需要的钢管最小尺寸为4m 而本题中参数都是整数 由于不同切割模式不能超过3种 可以用xi表示按照第i种模式 i 1 2 3 切割的原料钢管的根数 又设使用第i种切割模式下每根原料钢管生产长4m 5m 6m和8m的钢管数量分别为r1i r2i r3i r4i 仅以使用的原料总根数最少为目标 即目标函数Min x1 x2 x3满足客户需求的约束条件为r11 x1 r12 x2 r13 x3 50 8 r21 x1 r22 x2 r23 x3 10 9 r31 x1 r32 x2 r33 x3 20 10 r41 x1 r42 x2 r43 x3 15 11 每一种切割模式必须可行 合理 所以每根原料钢管的成品量不能超过19m 也不能少于16m 余料不能大