线性规划与整数规划.ppt

线性规划模型 第一节线性规划模型 一 线性规划及其数学模型 1 线性规划问题 在生产管理和经营活动中 经常提出一类问题 既如何合理地 利用有限的人力 物力 财力等资源 以便得到最好的经济效益 问题 拟定生产计划 问题提出某公司生产炊事用具需要两种资源 劳动力和原材 料 某公司计划生产三种不同产品 生产管理部门提供的数据如下 每天可供应原材料为 千克 每天可使用的劳动力为 小 时 问如何安排生产计划 才能是公司总收益最大 模型建立设每天生产 三种产品的件数分别为 最大利润为 则该问题就是在条件 下 求利润 的最大值 问题 运输问题 问题的提出两个煤炭厂 每月进煤分别为60t和100t 联合供应三个居民区 三个居民区每月对煤的需求量依次 为50t 70t 40t 煤厂 离居民区 的距离分别为10km 5km 6km 煤厂 离居民区 的距离分别为4km 8km 12km 如何分配供煤量才能使总运输量 达到最小 模型建立设 表示煤厂 提供给居民区 的煤量 表示总运输量 则所求问题就是在条件 下 求总运输量 的最小值 线性规划问题的特点和数学模型 从以上两个实例可以看出 它们都属于一类优化问题 其共同 特点是 所给问题都用一组决策变量 表示某一方案 这组决策变量的值就代表一个具体方案 一般这些变量的取是非 负的 存在一定的约束条件 这些约束条件可以用一组线性 等式或线性不等式来表示 都有一个要求达到的目标 它可以用决策变量的线性 函数来表示 这个函数称为目标函数 按问题的不同 要求目标 函数实现最大化或最小化 满足以上三个条件的数学模型称为线性规划问题的数学模型 其一般形式为 目标函数 约束条件 3 线性规划模型的标准型 实际问题的线性规划模型是多种多样的 在多种多样的模型中 可规定一种形式为标准型 以便于研究和求解 1 线性规划模型的标准型 如果在线性规划模型中 有n个决策变量m个约束条件 约束 条件为等式约束 决策变量非负 求目标函数的最小值 这种线性 规划模型就叫做标准型 其表达式为 在标准型中 规定 否则等式两端乘以 1 其 矩阵形式为 其中 称为约束条件的系数矩阵 一般有 称为价值向量 向量 称为资源向量 称为决策向量 为零向量 2 任意一线性规划模型都可以化为标准型 若原模型要求目标函数实现最大化 即 则 即目标函数可化为 这就 与标准型的目标函数一致了 若原模型中的约束条件为不等式 有两种情况 若原模型中的约束条件为不等式 左端 右端 则在左端加 上 非负松弛变量 使不等式化为等式 左端 非负松弛变量 右端 若原模型中的约束条件为不等式 左端 右端 则在左端减 去 非负松弛变量 使不等式化为等式 左端 非负松弛变量 右端 例1将问题1的模型 化为标准型 二 应用举例 1 食谱问题 问题提出一饲养场饲养供实验用的动物 已知动物的生长对 饲料中的三种营养成分 蛋白质 矿物质和维生素特别敏感 每个 动物每天至少需要蛋白质 克 矿物质 克 维生素 毫克 该场能买到 种饲料 各种饲料每千克的成本及所含营养成分如下 表所示 请确定既能满足动物需要 又使总成本最低的饲料配方 设每个动物每天食用的混合饲料中所含的第 种饲料 的数量 为 千克 混合饲料的总成本为z 则上述问题的数学模型为 连续投资问题 问题提出某部门在今后五年内考虑给下列四个项目投资 项 目 从第一年到第四年年初需要投资 并于次年末回收本利的 115 项目 第三年年初需要投资 到第五年年末能回收本利 125 但规定最大投资不超过 万元 项目 第二年年初需要 投资 到第五年年末能回收本利140 但规定最大投资不超过 万 元 项目 五年内每年年初购买公债 于当年末归还 并加利息 6 该部门现有资金10万元 问如何分配这些项目每年的投资额 使 到第五年末拥有资金的本利总额最大 问题分析 五年中每年年初该部门拥有的资金是变化的 设 表示第i年年初给第j项项目的投资额 显然 该部门每年的投资额等于部门年初所拥有的资金 下面 分年度讨论 第一年 年初拥有资金 万元 所以有 第二年 年初拥有资金仅为项目 在第一年末回收的本息 所以有 第三年 年初拥有资金为 所以有 第四年 年初拥有资金为 所以有 第五年 年初拥有资金为 所以有 又 由题意知 目标函数 模型建立将上述分析整理 可得此问题的数学模型为 3 下料问题 问题的提出计划做100套钢架 每套用长为2 9米 2 1米 1 5米 的圆钢各一根 设原材料长7 4米 问如何下料 才能使所用原料 最少 分析最简单的做法是在每一根原料上截取三种长度不同的 圆钢各一根组成一套 但浪费较大 若改为套截 则可节省原料 8种套截方案如下表 设按第i种方案下料的原料根数为 表示总余料 则所求问题的数学模型为 注 该问题的数学模型的目标函数也可以为 其中 表示使用原料总根数 第二节整数规划模型 在一般的线性规划模型中 再加上决策变量取整的条件 所得到的 一类规划问题称为整数线性规划 问题1货物托运问题 某公司拟用集装箱托运A B两种货物 每箱的体积 重量 可 获得利润以及托运所受限制如下表所示 问两种货物各运多少箱 可获得最大利润 一 整数规划模型 设 分别表示这两种货物的托运箱数 则该问题的数学模型 为 一般地 某公司拟用集装箱托运n种货物 每箱的体积 重量 可获得利润 以及托运所受限制为V和M 问怎么装箱可获得最大利润 问题2分派问题 分配n个人去完成n项任务 第i个人完成第j 项任务的效率为 每个人恰好完成一项任务 如何分配使总效率 最大 设0 1变量 则此问题的 数学模型为 二 0 1整数规划模型 0 1整数规划模型是整数规划模型中的特殊情形 它的 决策变量 仅取0或1 这时 又叫0 1变量 问题2分派问题就是0 1整数规划模型 问题3选址问题 问题提出某公司欲在城市的东 西 南三区建立门市部 拟 议中有7个位置 可供选择 规定 在东区 由 三个位置中至多选两个 在西区 由 两个个位置中至少选一个 在南区 由 两个个位置中至少选一个 如果选用 则设备投资费用为 每年可获利润为 但投资总额不能超过B元 问应选择哪几个位置 可使年利润最大 模型建立首先引入0 1变量 则此问题的数学模型为 习题 1 某昼夜服务的公交线路每天各时间段内所需要司机和乘务员如 下表 设司机和乘务员分别在各时间区段一开始时上班 并连续工作 8小时 问该公交线路至少要配备多少司机和乘务员 设每人每天只上一轮班 8小时 第i时间段开始时有 名人员上班 则 2 背包问题一个旅行者必须决定在旅途中要携带哪些物品 才 能使携带的总重量不超过b公斤 以使总的 价值 最大 这样的问题称 为背包问题 设有n件物品 第i件物品的重量为 公斤 携带的 价值 为 试建立背包问题的数学模型 首先引入0 1变量 则此问题的数学模型为 3 比赛安排问题已知下列5名运动员各种游泳项目的成绩 各 为50米 如下表所示 问如何从中选拔一个参加200米混合游泳的接 力队 使预期成绩最好 4 加工任务安排 某工厂用 两台机床加工 三种 不同的零件 已知在一个生产周期内 只能工作80机时 只能工作 100机时 一个生产周期内计划加工 三种不同的零件分别为 70件 50件 20件 两台机床加工每个零件的时间和成本分别如下 表所示 加工每个零件的时间 单位 机时 个 加工每个零件的成本 单位 元 个 问怎样安排两台机床一个周期的加工任务 才能是加工成本最低