1-1LP模型的结构及建模步骤及标准型.ppt

2020年2月22日12时34分 1 第一章线性规划模型和单纯形法1 1线性规划模型的结构及建模步骤 主讲 郑来运机械工程学院 2020年2月22日12时34分 光华食品厂主要生产葱油饼干 型 和苏打饼干 型 根据销售部门提供的信息可知 目前这两种饼干在市场上都很畅销 该厂能生产多少 市场就能卖出多少 但从生产部门得知 有三种关键设备即搅拌机 成型机 烘箱的生产能力 限制了该厂的饼干生产 该公司每天生产这两种饼干的量应为多少 可使其利润最大 2020年2月22日12时34分 2020年2月22日12时34分 光华食品厂主要生产葱油饼干 型 和苏打饼干 型 销售利润分别为500元 吨和400元 吨 根据销售部门提供的信息可知 目前这两种饼干在市场上都很畅销 该厂能生产多少 市场就能卖出多少 但从生产部门得知 有三种关键设备即搅拌机 成型机 烘箱的生产能力 限制了该厂的饼干生产 该公司每天生产这两种饼干的量应为多少 可使其利润最大 其具体数据如表所示 例1资源利用问题 2020年2月22日12时34分 例1资源利用问题 即 生产葱油饼干 型 1吨苏打饼干 型 3吨企业利润 1700元 2020年2月22日12时34分 本节重点和难点及教学目标 重点与难点 如何建立线性规划问题的数学模型 建模条件 步骤及相应的技巧 教学目标 掌握建模的步骤和方法 能根据实际背景抽象和建立适当的线性规划模型 LinearProgrammingproblemanditsModels 2020年2月22日12时34分 例1资源利用问题 光华食品厂主要生产葱油饼干 型 和苏打饼干 型 销售利润分别为500元 吨和400元 吨 根据销售部门提供的信息可知 目前这两种饼干在市场上都很畅销 该厂能生产多少 市场就能卖出多少 但从生产部门得知 有三种关键设备即搅拌机 成型机 烘箱的生产能力 限制了该厂的饼干生产 该公司每天生产这两种饼干的量应为多少 可使其利润最大 其具体数据如表所示 2020年2月22日12时34分 设 Step1 确定决策变量 未知量 可由决策者决定和控制 x1为饼干I的生产数量x2为饼干II的生产数量 Step 1 2020年2月22日12时34分 问题 目标 光华食品厂每天生产这两种饼干的量应为多少 可使其利润最大 目标函数 maxZ 5x1 4x2 Step2 定义目标函数 Step 2 2020年2月22日12时34分 2020年2月22日12时34分 光华食品厂主要生产葱油饼干 型 和苏打饼干 型 根据销售部门提供的信息可知 目前这两种饼干在市场上都很畅销 该厂能生产多少 市场就能卖出多少 但从生产部门得知 有三种关键设备即搅拌机 成型机 烘箱的生产能力 限制了该厂的饼干生产 该公司每天生产这两种饼干的量应为多少 可使其利润最大 其具体数据如表所示 设备 现有工时受限制 如何利用现有资源才最好 辨认哪些是决策的关键影响因素 在选取这些关键因素时存在哪些资源和环境的限制 2020年2月22日12时34分 搅拌机的工时限制 3x1 4x2 15 成型机的工时限制 2x1 x2 5 烘箱的工时限制 2x1 2x2 11 非负约束 产量非负x1 0 x2 0 Step3 表示约束条件 Step 3 2020年2月22日12时34分 1 决策变量 x1为饼干I的生产数量 x2为饼干II的生产数量 2 目标函数 目标是企业利润最大化maxZ 5x1 4x2 3 约束条件 生产受设备能力制约 能力需求不能突破有效供给量 搅拌机的工时限制的约束条件表达为3x1 4x2 15同理 成型机的工时限制约束条件表达为2x1 x2 5烘箱的工时限制 其约束条件为2x1 2x2 11非负约束 产品的产量为非负x1 0 x2 0 LP模型 例1中建模的过程 小结 2020年2月22日12时34分 解 用变量x1和x2分别表示光华食品厂生产饼干I和饼干II的数量 目标函数约束条件 用数学语言完整描述 2020年2月22日12时34分 决策变量问题中要确定的未知量 表明规划中的用数量表示的方案 措施 可由决策者决定和控制 一般取值要求非负目标函数目标函数是决策变量的线性函数有的目标要实现极大 有的则要求极小约束条件指决策变量取值时受到的各种资源条件的限制通常把各种限制条件表达为一组等式或不等式称约束条件约束条件是决策变量的线性函数 线性规划模型的三要素 总结 当数学模型的目标函数为线性函数 约束条件为线性等式或不等式时称此数学模型为线性规划模型 2020年2月22日12时34分 线性规划问题 LinearProgrammingproblem 研究内容 在一定的人力 财力 资源条件下 如何合理安排使用 使得效益最高 某项任务确定后 如何安排人 财 物 使之最省 线性规划问题的共同点 要求达到某些数量上的最大化或最小化 在一定的约束条件下追求其目标最优 2020年2月22日12时34分 确定约束条件由决策变量所受的限制条件确定决策变量所要满足的约束条件 线性规划问题建模步骤 总结 确定决策变量根据影响所要达到目的的因素找到决策变量 写出目标函数由决策变量和所在达到目的之间的函数关系确定目标函数 2020年2月22日12时34分 运筹学的工作步骤 2020年2月22日12时34分 例 用浓度45 和92 的硫酸配置100吨浓度80 的硫酸 决策变量 取45 和92 的硫酸分别为x1和x2吨约束条件 求解二元一次方程组得解 非负约束 x1 0 x2 0 线性规划建模课堂练习 产品配比问题 2020年2月22日12时34分 若有5种不同浓度的硫酸可选 30 45 73 85 92 会如何呢 取这5种硫酸分别为x1 x2 x3 x4 x5 有 若5种硫酸价格分别为400 700 1400 1900 2500元 t 如何使费用最小 线性规划建模课堂练习 产品配比问题 2020年2月22日12时34分 线性规划模型举例2 运输问题 见课本第七页 2020年2月22日12时34分 建立数学模型 目标函数 2020年2月22日12时34分 线性规划模型 运输问题 2020年2月22日12时34分 分析 运输问题模型 2020年2月22日12时34分 建立数学模型 运输问题模型 2020年2月22日12时34分 设 产品甲生产x1 产品乙生产x2 目标 Maxz 70 x1 65x2 约束条件 设备A生产能力限制 7x1 3x2 210 设备B生产能力限制 4x1 5x2 200 设备C生产能力限制 2x1 4x2 180 产量非负限制 x1 x2 0 决策变量 决策变量 目标函数 约束条件 三要素 1 决策变量2 目标函数3 约束条件 例3生产计划 2020年2月22日12时34分 线性规划模型的一般形式 一般地 假设线性规划数学模型中 有m个约束 有n个决策变量xj j 1 2 n 目标函数的变量系数用cj表示 cj称为价值系数 约束条件的变量系数用aij表示 aij称为工艺系数 约束条件右端的常数用bi i 1 2 m 表示 bi称为资源限量 则线性规划数学模型的一般表达式可写成 2020年2月22日12时34分 线性规划模型的一般形式 注释 2020年2月22日12时34分 紧缩形式 线性规划模型的一般形式 在实际中一般xj 0 但有时xj 0或xj无符号限制 2020年2月22日12时34分 其中 线性规划问题的一般形式 矩阵形式 2020年2月22日12时34分 例4生产计划问题2 2020年2月22日12时34分 maxZ 40 x1 50 x2 解 设产品A B产量分别为变量x1 x2 建立模型 2020年2月22日12时34分 1 定义 所谓线性规划就是求一个线性函数在一组线性约束条件下极值的问题 2 构成 线性规划的数学模型由决策变量 Decisionvariables 目标函数 Objectivefunction 及约束条件 Constraints 构成 称为三个要素 3 特征 1 一组决策变量 2 一个线性目标函数 3 一组线性约束条件 小结 2020年2月22日12时34分 线性规划问题的标准形式 在用单纯法求解线性规划问题时 为了讨论问题方便 需将线性规划模型化为统一的标准形式 线性规划问题的标准型为 1 目标函数求最小值 或求最大值 2 约束条件都为等式方程3 变量xj非负4 常数bi非负 注 本教材默认目标函数是min 2020年2月22日12时34分 线性规划问题的标准形式 标准形式为 目标函数最小约束条件等式右端常数非负决策变量非负 2020年2月22日12时34分 简写为 2020年2月22日12时34分 用向量表示 2020年2月22日12时34分 用矩阵表示 C 价值向量b 资源向量X 决策变量向量 2020年2月22日12时34分 目标函数的转换 如果是求极大值 则可将目标函数乘以 1 可化为求极小值问题 非标准形式转化为标准形式的方法 令Z Z 2020年2月22日12时34分 非标准形式转化为标准形式的方法 x3为松弛变量 x4为剩余变量 松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数 均未转化为价值和利润 所以引进模型后它们在目标函数中的系数均为零 当约束条件为 时 当约束条件为 时 约束条件 2020年2月22日12时34分 转化为 minZ 40 x1 50 x2 0 x3 0 x4 0 x5 例1 maxZ 40 x1 50 x2 注 松弛变量在目标函数中的系数均为零 非标准形式转化为标准形式的方法 2020年2月22日12时34分 例2 非标准形式转化为标准形式的方法 2020年2月22日12时34分 右端项b 0时 只需将等式或不等式两端同乘 1 则等式右端项必大于零 非标准形式转化为标准形式的方法 右端项 2020年2月22日12时34分 非标准形式转化为标准形式的方法 1 x 0的情况 令x1 x1 x1 2 x取值无约束的情况 令x x 令x x x 变量 2020年2月22日12时34分 将maxZ x1 2x2 3x3 化为标准型 例 例3 2020年2月22日12时34分 解 令x3 x4 x5 加松弛