管理运筹学知识(ppt 40页).ppt

1 管理运筹学 绪论线性规划 运输问题 整数规划动态规划存储论排队论对策论决策分析 2 第一章绪论 运筹学 OperationalResearch 直译为 运作研究 运筹学是应用分析 试验 量化的方法 对经济管理系统中的人力 物力 财力等资源进行统筹安排 为决策者提供有依据的最优方案 以实现最有效的管理 运筹学有广泛应用运筹学的产生和发展 3 1决策 定量分析与管理运筹学 决策过程 问题解决的过程 1 提出问题 认清问题2 寻求可行方案 建模 求解3 确定评估目标及方案的标准或方法 途径4 评估各个方案 解的检验 灵敏性分析等5 选择最优方案 决策6 方案实施 回到实践中7 后评估 考察问题是否得到完满解决1 2 3 形成问题 4 5 分析问题 定性分析与定量分析 构成决策 4 2运筹学的分支 线性规划非线性规划整数规划图与网络模型存储模型 排队论排序与统筹方法决策分析动态规划预测 多目标规划 随机规划 模糊规划等 5 3运筹学在工商管理中的应用 生产计划 生产作业的计划 日程表的编排 合理下料 配料问题 物料管理等库存管理 多种物资库存量的管理 库存方式 库存量等运输问题 确定最小成本的运输线路 物资的调拨 运输工具的调度以及建厂地址的选择等人事管理 对人员的需求和使用的预测 确定人员编制 人员合理分配 建立人才评价体系等市场营销 广告预算 媒介选择 定价 产品开发与销售计划制定等财务和会计 预测 贷款 成本分析 定价 证券管理 现金管理等 设备维修 更新 项目选择 评价 工程优化设计与管理等 6 运筹学方法使用情况 美1983 7 运筹学方法在中国使用情况 随机抽样 8 运筹学的推广应用前景 据美劳工局1992年统计预测 运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73 增长速度排到各项职业的前三位 结论 运筹学在国内或国外的推广前景是非常广阔的工商企业对运筹学应用和需求是很大的在工商企业推广运筹学方面有大量的工作要做 9 4如何学习运筹学 MBA学员学习运筹学要把重点放在结合实际的应用上 不要被一些概念 理论的困难吓倒 要用好计算机这个强有力的工具 MBA学员学习运筹学要充分发挥自己实践经验丰富和理论联系实际能力强的优势 MBA学员学习运筹学要把注意力放在 入口 和 出口 两头 中间过程尽可能让计算机软件去完成 入口 即结合实际问题建立运筹学模型 出口 即解决问题的方案或模型的解 本书附有运筹学教学软件 使用方法很简单 MBA学员必须尽快学会使用这个运筹学教学软件 并借助它来学好本课程 10 第二章线性规划的图解法 在管理中一些典型的线性规划应用合理利用线材问题 如何下料使用材最少配料问题 在原料供应量的限制下如何获取最大利润投资问题 从投资项目中选取方案 使投资回报最大产品生产计划 合理利用人力 物力 财力等 使获利最大劳动力安排 用最少的劳动力来满足工作的需要运输问题 如何制定调运方案 使总运费最小线性规划的组成 目标函数Maxf或Minf约束条件s t subjectto 满足于决策变量用符号来表示可控制的因素 11 1问题的提出 例1 某工厂在计划期内要安排甲 乙两种产品的生产 已知生产单位产品所需的设备台时及A B两种原材料的消耗以及资源的限制 如下表 问题 工厂应分别生产多少单位甲 乙产品才能使工厂获利最多 线性规划模型 目标函数 Maxz 50 x1 100 x2约束条件 s t x1 x2 3002x1 x2 400 x2 250 x1 x2 0 12 线性规划模型 一般形式目标函数 Max Min z c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0标准形式目标函数 Maxz c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 13 2图解法 例1 目标函数 Maxz 50 x1 100 x2约束条件 s t x1 x2 300 A 2x1 x2 400 B x2 250 C x1 0 D x2 0 E 得到最优解 x1 50 x2 250最优目标值z 27500 14 进一步讨论 线性规划的标准化内容之一 引入松驰变量 含义是资源的剩余量 例1中引入s1 s2 s3模型化为目标函数 Maxz 50 x1 100 x2 0s1 0s2 0s3约束条件 s t x1 x2 s1 3002x1 x2 s2 400 x2 s3 250 x1 x2 s1 s2 s3 0对于最优解x1 50 x2 250 s1 0s2 50s3 0说明 生产50单位甲产品和250单位乙产品将消耗完所有可能的设备台时数及原料B 但对原料A则还剩余50千克 解的性质 1 线性规划的最优解如果存在 则必定有一个顶点 极点 是最优解 2 有的线性规划问题存在无穷多个最优解的情况 3 有的线性规划问题存在无有限最优解的情况 也称无解 4 有的线性规划问题存在无可行解的情况 作业 P24 1 2 3 4 5 15 3图解法的灵敏度分析 灵敏度分析 建立数学模型和求得最优解后 研究线性规划的一个或多个参数 系数 ci aij bj变化时 对最优解产生的影响 3 1目标函数中的系数ci的灵敏度分析考虑例1的情况 ci的变化只影响目标函数等值线的斜率 目标函数z 50 x1 100 x2在z x2 x2 z斜率为0 到z x1 x2 x2 x1 z斜率为 1 之间时 原最优解x1 50 x2 100仍是最优解 一般情况 z c1x1 c2x2写成斜截式x2 c1 c2 x1 z c2目标函数等值线的斜率为 c1 c2 当 1 c1 c2 0 时 原最优解仍是最优解假设产品乙的利润100元不变 即c2 100 代到式 并整理得0 c1 100假设产品甲的利润50元不变 即c1 50 代到式 并整理得50 c2 假若产品甲 乙的利润均改变 则可直接用式 来判断 假设产品甲 乙的利润分别为60元 55元 则 2 60 55 1那麽 最优解为z x1 x2和z 2x1 x2的交点x1 100 x2 200 16 3 2约束条件中右边系数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个单位时1 若约束条件的对偶价格大于0 则其最优目标函数值得到改善 变好 2 若约束条件的对偶价格小于0 则其最优目标函数值受到影响 变坏 3 若约束条件的对偶价格等于0 则其最优目标函数值不变 作业 P24 6 7 8 17 第三章线性规划问题的计算机求解 1 管理运筹学软件1 0版使用说明 演示例1 一 系统的进入与退出 1 在WINDOWS环境下直接运行main exe文件 或者在DOS下UCDOS中文平台环境下运行 也可直接运行各可执行程序 2 退出系统的方法可以在主菜单中选退出项 也可按Ctrl Break键直接退出 3 在WINDOWS环境下直接运行软件 如果出现乱码 那是因为启用了全屏幕方式 解决办法是按ALT ENTER键 即可转换成非全屏的界面 一般就会消除乱码 如果还是乱码 可以点击菜单的 汉 选项 若要每次启动程序都没有乱码 则需要修改屏幕设置的相应属性 具体方法是 在非全屏界面下点击菜单的 属性 选项 再选择 窗口 选项 然后选中其中的 窗口 项 并取消 启动时恢复设置 项 这样就可保证每次运行软件时以非全屏方式显示 二 输入部分 1 线性规划 整数规划的目标函数和约束的输入必须按由小到大的序号顺序输入 同时约束变量必须放在运算符的左侧 如 x1 x2 x3 0 不能输为x2 x3 x1 0 x1 x2 x3 0 不能输为x1 x3 x2 2 输入的约束中不包括 或 或 2 则输入X1 2 而不是X1 2 18 第三章线性规划问题的计算机求解 2 结果考察 演示例1 1 当目标函数的系数ci单一变化时 只要不超过其上 下限 最优解不变 2 当约束条件中右边系数bj变化时 当其不超过上 下限 对偶价格不变 最优解仍是原来几个线性方程的解 3 当有多个系数变化时 需要进一步讨论 百分之一百法则 对于所有变化的目标函数决策系数 约束条件右边常数值 当其所有允许增加的百分比与允许减少的百分比之和不超过100 时 最优解不变 对偶价格不变 最优解仍是原来几个线性方程的解 允许增加量 上限 现在值c1的允许增加量为100 50 50b1的允许增加量为325 300 25 允许减少量 现在值 下限c2的允许减少量为100 50 50b3的允许减少量为250 200 50 允许增加的百分比 增加量 允许增加量 允许减少的百分比 减少量 允许减少量 19 第三章线性规划问题的计算机求解 3 例 c1变为74 c2变为78 则 74 50 50 100 78 50 92 故最优解不变 b1变为315 b3变为240 则 315 50 25 250 240 50 80 故对偶价格不变 最优解仍是原来几个线性方程的解 在使用百分之一百法则进行灵敏度分析时 要注意 1 当允许增加量 允许减少量 为无穷大时 则对任意增加量 减少量 其允许增加 减少 百分比均看作0 2 百分之一百法则是充分条件 但非必要条件 3 百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况 这种情况下 只有重新求解 20 第四章线性规划在工商管理中的应用 1 一 人力资源分配的问题例1 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下 设司机和乘务人员分别在各时间段一开始时上班 并连续工作八小时 问该公交线路怎样安排司机和乘务人员 既能满足工作需要 又配备最少司机和乘务人员 解 设xi表示第i班次时开始上班的司机和乘务人员数 这样我们建立如下的数学模型 目标函数 Minx1 x2 x3 x4 x5 x6约束条件 s t x1 x6 60 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30 x1 x2 x3 x4 x5 x6 0 21 第四章线性规划在工商管理中的应用 2 一 人力资源分配的问题例2 福安商场是个中型的百货商场 它对售货员的需求经过统计分析如右表 为了保证售货人员充分休息 售货人员每周工作5天 休息两天 并要求休息的两天是连续的 问应该如何安排售货人员的作息 既满足工作需要 又使配备的售货人员的人数最少 解 设xi i 1 7 表示星期一至日开始休息的人数 这样我们建立如下的数学模型 目标函数 Minx1 x2 x3 x4 x5 x6 x7约束条件 s t x1 x2 x3 x4 x5 28x2 x3 x4 x5 x6 15x3 x4 x5 x6 x7 24x4 x5 x6 x7 x1 25x5 x6 x7 x1 x2 19x6 x7 x1 x2 x3 31x7 x1 x2 x3 x4 28x1 x2 x3 x4 x5 x6 x7 0 22 第四章线性规划在工商管理中的应用 3 二 生产计划的问题例3 明兴公司生产甲 乙 丙三种产品 都需要经过铸造 机加工和装配三个车间 甲 乙两种产品的铸件可以外包协作 亦可以自行生产 但产品丙必须本厂铸造才能保证质量 数据如右表 问 公司为了获得最大利润 甲 乙 丙三种产品各生产多少件 甲 乙两种产品的铸造中 由本公司铸造和由外包协作各应多少件 解 设x1 x2 x3分别为三道工序都由本公司加工的甲 乙 丙三种产品的件数 x4 x5分别为由外协铸造再由本公司机加工和装配的甲 乙两种产品的件数 求xi的利润 利润 售价 各成本之和可得到xi i 1 2 3 4 5 的利润分别为15 10 7 13 9元 这样我们建立如下的数学模型 目标函数 Max15x1 10 x2 7x3 13x4 9x5约束条件 s t 5x1 10 x2 7x3 80006x1 4x2 8x3 6x4 4x5 120003x1 2x2 2x3 3x4 2x5 10000 x1 x2 x3 x4 x5 0 23 第四章线性规划在工商管理中的应用 4 二 生产计划的问题例4 永久机械厂生产 三种产品 均要经过A B两道工序加工 设有两种规格的设备A1 A2能完成A工序 有三种规格的设备B1 B2 B3能完成B工序 可在A B的任何规格的设备上加工 可在任意规格的A设备上加工 但对B工序 只能在B1设备上加工 只能在A2与B2设备上加工 数据如右上表 问 为使该厂获得最大利润 应如何制定产品加工方案 解 设xijk表示第i种产品 在第j种工序上的第k种设备上加工的数量 利润 销售单价 原料单价 产品件数 之和 每台时的设备费用 设备实际使用的总台时数 之和 这样我们建立如下的数学模型 Max0 75x111 0 7753x112 1 15x211 1 3611x212 1 9148x312 0 375x121 0 5x221 0 4475x122 1 2304x322 0 35x123s t 5x111 10 x211 6000 设备A1 7x112 9x212 12x312 10000 设备A2 6x121 8x221 4000 设备B1 4x122 11x322 7000 设备B2 7x123 4000 设备B3 x111 x112 x121 x122 x123 0 产品在A B工序加工的数量相等 x211 x212 x221 0 产品在A B工序加工的数量相等 x312 x322 0 产品在A B工序加工的数量相等 xijk 0 i 1 2 3 j 1 2 k 1 2 3 24 第四章线性规划在工商管理中的应用 5 三 套裁下料问题例5 某工厂要做100套钢架 每套用长为2 9m 2 1m 1 5m的圆钢各一根 已知原料每根长7 4m 问 应如何下料 可使所用原料最省 解 设计下列5种下料方案 设x1 x2 x3 x4 x5分别为上面前5种方案下料的原材料根数 这样我们建立如下的数学模型 目标函数 Minx1 x2 x3 x4 x5约束条件 s t x1 2x2 x4 1002x3 2x4 x5 1003x1 x2 2x3 3x5 100 x1 x2 x3 x4 x5 0 25 第四章线性规划在工商管理中的应用 6 四 配料问题例6 某工厂要用三种原料1 2 3混合调配出三种不同规格的产品甲 乙 丙 数据如右表 问 该厂应如何安排生产 使利润收入为最大 解 设xij表示第i种 甲 乙 丙 产品中原料j的含量 这样我们建立数学模型时 要考虑 对于甲 x11 x12 x13 对于乙 x21 x22 x23 对于丙 x31 x32 x33 对于原料1 x11 x21 x31 对于原料2 x12 x22 x32 对于原料3 x13 x23 x33 目标函数 利润最大 利润 收入 原料支出约束条件 规格要求4个 供应量限制3个 26 第四章线性规划在工商管理中的应用 6续 例6 续 目标函数 Maxz 15x11 25x12 15x13 30 x21 10 x22 40 x31 10 x33约束条件 s t 0 5x11 0 5x12 0 5x13 0 原材料1不少于50 0 25x11 0 75x12 0 25x13 0 原材料2不超过25 0 75x21 0 25x22 0 25x23 0 原材料1不少于25 0 5x21 0 5x22 0 5x23 0 原材料2不超过50 x11 x21 x31 100 供应量限制 x12 x22 x32 100 供应量限制 x13 x23 x33 60 供应量限制 xij 0 i 1 2 3 j 1 2 3 例7由学员自己看懂 27 第四章线性规划在工商管理中的应用 7 五 投资问题例8 某部门现有资金200万元 今后五年内考虑给以下的项目投资 已知 项目A 从第一年到第五年每年年初都可投资 当年末能收回本利110 项目B 从第一年到第四年每年年初都可投资 次年末能收回本利125 但规定每年最大投资额不能超过30万元 项目C 需在第三年年初投资 第五年末能收回本利140 但规定最大投资额不能超过80万元 项目D 需在第二年年初投资 第五年末能收回本利155 但规定最大投资额不能超过100万元 据测定每万元每次投资的风险指数如右表 问 a 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利金额为最大 b 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小 解 1 确定决策变量 连续投资问题设xij i 1 5 j 1 2 3 4 表示第i年初投资于A j 1 B j 2 C j 3 D j 4 项目的金额 这样我们建立如下的决策变量 Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24 28 第四章线性规划在工商管理中的应用 7续 2 约束条件 第一年 A当年末可收回投资 故第一年年初应把全部资金投出去 于是x11 x12 200 第二年 B次当年末才可收回投资故第二年年初的资金为x11 于是x21 x22 x24 1 1x11 第三年 年初的资金为x21 x12 于是x31 x32 x33 1 1x21 1 25x12 第四年 年初的资金为x31 x22 于是x41 x42 1 1x31 1 25x22 第五年 年初的资金为x41 x32 于是x51 1 1x41 1 25x32 B C D的投资限制 xi2 30 I 1 2 3 4 x33 80 x24 1003 目标函数及模型 a Maxz 1 1x51 1 25x42 1 4x33 1 55x24s t x11 x12 200 x21 x22 x24 1 1x11 x31 x32 x33 1 1x21 1 25x12 x41 x42 1 1x31 1 25x22 x51 1 1x41 1 25x32 xi2 30 I 1 2 3 4 x33 80 x24 100 xij 0 i 1 2 3 4 5 j 1 2 3 4 b Minf x11 x21 x31 x41 x51 3 x12 x22 x32 x42 4x33 5 5x24s t x11 x12 200 x21 x22 x24 1 1x11 x31 x32 x33 1 1x21 1 25x12 x41 x42 1 1x31 1 25x22 x51 1 1x41 1 25x32 xi2 30 I 1 2 3 4 x33 80 x24 1001 1x51 1 25x42 1 4x33 1 55x24 330 xij 0 i 1 2 3 4 5 j 1 2 3 4 29 第七章运输问题 1 1运输模型例1 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往个销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 解 产销平衡问题 总产量 总销量设xij为从产地Ai运往销地Bj的运输量 得到下列运输量表 Minf 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 30 第七章运输问题 2 设xij为从产地Ai运往销地Bj的运输量 得到下列一般运输量问题的模型 mnMinf cijxiji 1j 1ns t xij sii 1 2 mj 1m xij djj 1 2 ni 1xij 0 i 1 2 m j 1 2 n 一般运输模型 产销平衡A1 A2 Am表示某物资的m个产地 B1 B2 Bn表示某物质的n个销地 si表示产地Ai的产量 dj表示销地Bj的销量 cij表示把物资为从产地Ai运往销地Bj的单位运价 变化 1 有时目标函数求最大如求利润最大或营业额最大等 2 当某些运输线路上的能力有限制时 模型中可直接加入 等式或不等式 约束 3 产销不平衡时 可加入虚设的产地 销大于产时 或销地 产大于销时 31 第七章运输问题 3 2运输问题的计算机求解例2 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往个销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 解 增加一个虚设的销地运输费用为0 例3 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往个销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 解 增加一个虚设的产地运输费用为0 32 第七章运输问题 4 3运输问题的应用 一 产销不平衡的运输问题例4 石家庄北方研究院有一 二 三三个区 每年分别需要用煤3000 1000 2000吨 由河北临城 山西盂县两处煤矿负责供应 价格 质量相同 供应能力分别为1500 4000吨 运价为 由于需大于供 经院研究决定一区供应量可减少0 200吨 二区必须满足需求量 三区供应量不少于1700吨 试求总费用为最低的调运方案 解 根据题意 作出产销平衡与运价表 这里M代表一个很大的正数 其作用是强迫相应的x31 x33 x34取值为0 33 第七章运输问题 5 3运输问题的应用 一 产销不平衡的运输问题例5 设有A B C三个化肥厂供应1 2 3 4四个地区的农用化肥 假设效果相同 有关数据如下表 试求总费用为最低的化肥调拨方案 解 根据题意 作出产销平衡与运价表 最低要求必须满足 因此把相应的虚设产地运费取为M 而最高要求与最低要求的差允许按需要安排 因此把相应的虚设产地运费取为0 对应4 的销量50是考虑问题本身适当取的数据 根据产销平衡要求确定D的产量为50 34 第七章运输问题 6 3运输问题的应用 二 生产与储存问题例6 某厂按合同规定须于当年每个季度末分别提供10 15 25 20台同一规格的柴油机 已知该厂各季度的生产能力及生产每台柴油机的成本如右表 如果生产出来的柴油机当季不交货 每台每积压一个季度需储存 维护等费用0 15万元 试求在完成合同的情况下 使该厂全年生产总费用为最小的决策方案 解 设xij为第i季度生产的第j季度交货的柴油机数目 那末应满足 交货 x11 10生产 x11 x12 x13 x14 25x12 x22 15x22 x23 x24 35x13 x23 x33 25x33 x34 30 x14 x24 x34 x44 20 x44 10把第i季度生产的柴油机数目看作第i个生产厂的产量 把第j季度交货的柴油机数目看作第j个销售点的销量 成本加储存 维护等费用看作运费 可构造下列产销平衡问题 目标函数 Minf 10 8x11 10 95x12 11 1x13 11 25x14 11 1x22 11 25x23 11 4x24 11 0 x33 11 15x34 11 3x44 35 第七章运输问题 7 3运输问题的应用 二 生产与储存问题例7 光明仪器厂生产电脑绣花机是以产定销的 已知1至6月份各月的生产能力 合同销量和单台电脑绣花机平均生产费用见下表 已知上年末库存103台绣花机 如果当月生产出来的机器当月不交货 则需要运到分厂库房 每台增加运输成本0 1万元 每台机器每月的平均仓储费 维护费为0 2万元 在7 8月份销售淡季 全厂停产1个月 因此在6月份完成销售合同后还要留出库存80台 加班生产机器每台增加成本1万元 问应如何安排1 6月份的生产 可使总的生产费用 包括运输 仓储 维护 最少 解 这个生产存储问题可化为运输问题来做 考虑 各月生产与交货分别视为产地和销地1 1 6月份合计生产能力 包括上年末储存量 为743台 销量为707台 设一假想销地销量为36 2 上年末库存103台 只有仓储费和运输费 把它列为的0行 3 6月份的需求除70台销量外 还要80台库存 其需求应为70 80 150台 4 1 6表示1 6月份正常生产情况 1 6 表示1 6月份加班生产情况 36 第七章运输问题 8 3运输问题的应用 产销平衡与运价表 37 第七章运输问题 9 例8 腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器 大连分厂每月生产450台 广州分厂每月生产60