（2020年整理）《管理运筹学》复习提纲.pptx

学海无涯 管理运筹学 复习提纲第一章绪论 P1 P9 1 决策过程 解决问题的过程 认清问题 找出一些可供选择的方案 确定目标或评估方案的标准 评估各个方案 解的检验 灵敏性分析等 选出一个最优的方案 决策 执行此方案 回到实践中 进行后评估 考察问题是否得到圆满解决 其中 1 2 3 形成问题 4 5 分析问题 定性分析与定量分析 构成决策运筹学的分支 线性规划 整数线性规划 动态规划 图与网络模型 存储论 排队论 排序与统筹方法 决策分析 对策论 预测 目标规划 此外 还有多目标规划 随机规划 模糊规划等 运筹学在工商管理中的应用生产计划 生产作业的计划 日程表的编排 合理下料 配料问题 物料管理等 追求利润最大化和成本最小化 库存管理 多种物资库存量的管理 某些设备的库存方式 库存量等的确定 运输问题 确定最小成本的运输线路 物资的调拨 运输工具的调度以及建厂地址的选择等 人事管理 对人员的需求和使用的预测 确定人员编制 人员合理分配 建立人才评价体系等 市场营销 广告预算 媒介选择 定价 产品开发与销售计划制定等 财务和会计 预测 贷款 成本分析 定价 证券管理 现金管理等 此外 还有设备维修 更新 项目选择 评价 工程优化设计与管理等 3 学习管理运筹学必须使用相应的计算机软件 必须注重学以致用的原则 第二章线性规划的图解法 P10 P26 一些典型的线性规划在管理上的应用合理利用线材问题 如何在保证生产的条件下 下料最少 配料问题 在原料供应量的限制下如何获取最大利润 投资问题 从投资项目中选取方案 使投资回报最大 产品生产计划 合理利用人力 物力 财力等 使获利最大 劳动力安排 用最少的劳动力来满足工作的需要 运输问题 如何制定调运方案 使总运费最小 线性规划的组成目标函数 maxf或minf 学海无涯约束条件 s t subjectto 满足于 决策变量 用符号来表示可控制的因素 建模过程理解要解决的问题 明确在什么条件下 要追求什么目标 定义决策变量 x1 x2 xn 每一组值表示一个方案 用决策变量的线性函数形式写出目标函数 确定最大化或最小化目标 用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 一般形式目标函数 max min z c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0对于只包含两个决策变量的线性规划问题 可以在平面直角坐标系上作图表示线性规划问题的有关概念 并求解 下面通过例1详细介绍图解法的解题过程 学海无涯 取各约束条件的公共部分 如图2 1 f 所示 目标函数z 50 x1 100 x2 当z取某一固定值时得到一条直线 直线上的每一点都具有相同的目标函数值 称之为 等值线 平行移动等值线 当移动到B点时 z在可行域内实现了最大化 A B C D E是可行域的顶点 有限个约束条件其可行域的顶点也是有限的 线性规划的标准化内容之一 引入松弛变量 资源的剩余量 例1中引入s1 s2 s3 模型变化为 4 重要结论 如果线性规划有最优解 则一定有一个可行域的顶点对应一个最优解 无穷多个最优解 若将例1中的目标函数变为maxz 50 x1 50 x2 则线段BC上的所有点都代表了最优解 无界解 即可行域的范围延伸到无穷远 目标函数值可以无穷大或无穷小 一般来说 这说明模型有错 忽略了一些必要的约束 学海无涯条件 无可行解 若在例1的数学模型中再增加一个约束条件4x1 3x2 1200 则可行域为空域 不存在满足约束条件的解 当然也就不存在最优解了 5 线性规划的标准化 线性规划的标准形式有四个特点 目标最大化 约束为等式 决策变量均非负 右端项非负 对于各种非标准形式的线性规划问题 我们总可以通过变换 将其转化为标准形式 为了使约束由不等式成为等式而引进的变量s 当不等式为 小于等于 时称为 松弛变量 当不等式为 大于等于 时称为 剩余变量 如果原问题中有若干个非等式约束 则将其转化为标准形式时 必须对各个约束引进不同的松弛变量或剩余变量 学海无涯 8 9 灵敏度分析 在建立数学模型和求得最优解之后 研究线性规划的一个或多个参数 系数 ci aij bj变化时 对最优解产生的影响 一 目标函数中的系数ci的灵敏度分析 学海无涯 二 约束条件中常数项bj的灵敏度分析当约束条件中常数项bj变化时 线性规划的可行域发生变化 可能引起最优解的变化 考虑例1的情况 假设设备台时增加10个台时 即b1变化为310 这时可行域扩大 最优解为x2 250和x1 x2 310的交点x1 60 x2 250 变化后的总利润 变化前的总利润 增加的利润 50 60 100 250 50 50 100 250 500 500 10 50 元 说明在一定范围内每增加 或减少 1个台时的设备能力就可增加 或减少 50元利润 这称为该约束条件的对偶价格 假设原料A增加10千克 即b2变化为410 这时可行域扩大 但最优解仍为x2 250和x1 x2 300的交点x1 50 x2 250 此变化对总利润无影响 该约束条件的对偶价格为0 解释 原最优解没有把原料A用尽 有50千克的剩余 因此增加10千克只增加了库存 而不会增加利润 在一定范围内 当约束条件中常数项增加1个单位时 若约束条件的对偶价格大于0 则其最优目标函数值得到改善 变好 若约束条件的对偶价格小于0 则其最优目标函数值受到影响 变坏 若约束条件的对偶价格等于0 则其最优目标函数值不变 课本重点习题 P23 26习题1268第三章线性规划问题的计算机求解 P27 P38 随书软件为 管理运筹学 2 5版 Windows版 是 管理运筹学 2 0版 Windows版 的升级版 它包括 线性规划 运输问题 整数规划 0 1整数规划 纯整数规划和混合整数规划 目标规划 对策论 最短路径 最小生成树 最大流量 最小费用最大流 关键路径 存储论 排队论 决策分析 预测问题和层次分析法 共15个子模块 学海无涯3 管理运筹学 软件的输出信息分析 当有多个系数变化时 需要进一步讨论 百分之一百法则 对于所有变化的目标函数决策系数 约束条件右端常数值 当其所有允许增加的百分比与允许减少的百分比之和不超过100 时 最优解不变 对偶价格不变 最优解仍是原来几个线性方程的解 在使用百分之一百法则进行灵敏度分析时 要注意以下几方面 当允许增加量 允许减少量 为无穷大时 则对任意增加量 减少量 其允许增加 减少 百分比均看作零 百分之一百法则是充分条件 但非必要条件 也就是说超过100 最优解或对偶价格并不一定变化 百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况 这种情况下 只能重新求解 学海无涯 在松弛 剩余变量栏中 约束条件2的值为125 它表示对原料A的最低需求 即对A的剩余变量值为125 同理可知约束条件1的剩余变量值为0 约束条件3的松弛变量值为0 在对偶价格栏中 约束条件3的对偶价格为1万元 也就是说如果把加工时数从600小时增加到601小时 则总成本将得到改进 由800万元减少到799万元 也可知约束条件1的对偶条件为 4万元 也就是说如果把购进原料A和B的总量下限从350t增加到351t 那么总成本将增加 由800万元增加到804万元 当然如果减少对原料A和B的总量的下限 那么总成本将得到改进 在常数项范围一栏中 知道当约束条件1的常数项在300到475范围内变化 且其他约束条件不变时 约束条件1的对偶价格不变 仍为 4 当约束条件2的常数项在负无穷到250范围内变化 且其他约束条件的常数项不变时 约束条件2的对偶价格不变 仍为0 当约束条件3的常数项在475到700范围内变化 且其他约束条件的常数项不变时 约束条件3的对偶价格不变 仍为1 3 注意当约束条件中的常数项增加一个单位时 最优目标函数值增加的数量称为影子价格 在求目标函数最大值时 当约束条件中的常数项增加一个单位时 目标函数值增加的数量就为改进的数量 此时影子价格等于对偶价格 在求目标函数最小值时 改进的数量就是减少的数量 此时影子价格即为负的对偶价格 管理运筹学 软件可以解决含有100个变量50个约束方程的线性规划问题 可以解决工商管理中大量的问题 如果想要解决更大的线性规划问题 可以使用由芝加哥大学的L E Schrage开发的LINDO计算机软件包的微型计算机版本LINDO PC 课本重点习题 P34 38习题1234第四章线性规划在工商管理中的应用 P39 P66 包括 人力资源分配的问题生产计划的问题 套裁下料问题 学海无涯配料问题投资问题 1人力资源分配问题例1 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如表4 1所示 设司机和乘务人员分别在各时间段一开始时上班 并连续工作8h 问该公交线路怎样安排司机和乘务人员 既能满足工作需要 又使配备最少司机和乘务人员的人数最少 例2 一家中型的百货商场对售货员的需求经过统计分析如表4 2所示 为了保证售货员充分休息 要求售货员每周工作五天 休息两天 并要求休息的两天是连续的 问应该如何安排售货员的休息日期 既满足工作需要 又使配备的售货员的人数最少 学海无涯 2生产计划的问题例3 某公司面临一个是外包协作还是自行生产的问题 该公司生产甲 乙 丙三种产品 这三种产品都需要经过铸造 机加工和装配三道工序 甲 乙两种产品的铸件可以外包协作 亦可以自行生产 但产品丙必须本厂铸造才能保证质量 数据如表4 3所示 问 公司为了获得最大利润 甲 乙 丙三种产品各生产多少件 甲 乙两种产品的铸造中 由本公司铸造和外包协作各应多少件 学海无涯解 设x1 x2 x3分别为三道工序都由本公司加工的甲 乙 丙三种产品的件数 x4 x5分别为由外包协作铸造再由本公司进行机械加工和装配的甲 乙两种产品的件数 每件产品的利润如下 可得到xi i 1 2 3 4 5 的利润分别为15元 10元 7元 13元 9元 该公司的最大利润为29400元 最优的生产计划为全部由自己生产的产品甲1600件 铸造工序外包而其余工序自行生产的产品乙600件 例4 永久机械厂生产 三种产品 均要经过A B两道工序加工 设有两种规格的设备A1 A2能完成A工序 有三种规格的设备B1 B2 B3能完成B工序 产品 可在A B的任何规格的设备上加工 产品 可在工序A的任何一种规格的设备上加工 但对B工序 只能在B1设备上加工 产品 只能在A2与B2设备上加工 数据如表4 4所示 问 为使该厂获得最大利润 应如何制定产品加工方案 解 设xijk表示第i种产品 在第j种工序上的第k种设备上加工的数量 建立如下的数学模型 学海无涯 目标函数为计算利润最大化 利润的计算公式为 利润 销售单价 原料单价 产品件数 之和 每台时的设备费用 设备实际使用的总台时数 之和 这样得到目标函数 max 1 25 0 25 x111 x112 2 0 35 x211 x212 2 80 0 5 x312 300 6000 5x111 10 x211 321 10000 7x112 9x212 12x312 250 4000 6x121 8x221 783 7000 4x122 11x322 200 4000 7x123 经整理可得 max0 75x111 0 7753x112 1 15x211 1 3611x212 1 9148x312 0 375x121 0 5x221 0 4474x122 1 2304x322 0 35x123 该厂的最大利润为1146 6005元 4套裁下料问题例5 某工厂要做100套钢架 每套用长为2 9m 2 1m 1 5m的圆钢各一根 已知原料每根长7 4m 问 应如何下料 可使所用原料最省 解 共可设计下列8种下料方案 如表4 5所示 设x1 x2 x3 x4 x5 x6 x7 x8分别为