数据、模型和决策PPT课件.ppt

数据 模型与决策 汕头大学商学院林佳丽 2020 1 15 数据 模型与决策 1 2020 1 15 可编辑 2 围猫游戏 围猫策略分析 更大范围内围点最短路径分析猫行动的方向隔点围法 在猫跑出包围圈之前围堵薄弱环节 2020 1 15 可编辑 3 灵敏度分析与最优解的解释 2020 1 15 数据 模型与决策 4 5 线性规划模型的构建 1 理解要解决的问题 了解解题的目标和条件 2 定义决策变量 x1 x2 xn 每一组值表示一个方案 3 用决策变量的线性函数形式写出目标函数 确定最大化或最小化目标 4 用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 定性 定量 权重 可行域的设置 一般形式目标函数 Max Min z c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 2020 1 15 可编辑 6 AB公司 AB公司在这一周内只生产两种产品 产品A和产品B 管理部门必须决定每种产品各生产多少吨 产品A的售价为每吨25美元 产品B的售价为每吨10美元 生产出的全部产品都将被出售 产品A和产品B由多种材料混合而成 这些材料都从仓库中提取 可供这一周使用的三种原材料数量如下 原料1 12000吨原料2 4000吨原料3 6000吨产品A由60 的原料1和40 的原料2制成产品B由50 的原料1 10 的原料2和40 的原料3制成 有人以1美元 吨的价格提供500吨的原料1 我们是否接受 有人以50美元 吨的价格提供原料2 是否接受 一个公司彻底用完了原料3 而以15美元 吨的价格向我们求购原料3 有多少要多少 我们是否应该卖给他们一些 2020 1 15 可编辑 7 如何决策 2020 1 15 可编辑 8 例1 某工厂在计划期内要安排 两种产品的生产 已知生产单位产品所需的设备台时及A B两种原材料的消耗 资源的限制 如下表 问题 工厂应分别生产多少单位 产品才能使工厂获利最多 线性规划模型 目标函数 Maxz 50 x1 100 x2约束条件 s t x1 x2 3002x1 x2 400 x2 250 x1 x2 0 9 图解法 1 分别取决策变量X1 X2为坐标向量建立直角坐标系 在直角坐标系里 图上任意一点的坐标代表了决策变量的一组值 例1的每个约束条件都代表一个半平面 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 10 2 对每个不等式 约束条件 先取其等式在坐标系中作直线 然后确定不等式所决定的半平面 图解法 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 11 3 把五个图合并成一个图 取各约束条件的公共部分 如图2 1所示 图解法 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 12 4 目标函数z 50 x1 100 x2 当z取某一固定值时得到一条直线 直线上的每一点都具有相同的目标函数值 称之为 等值线 平行移动等值线 当移动到B点时 z在可行域内实现了最大化 A B C D E是可行域的顶点 对有限个约束条件则其可行域的顶点也是有限的 x1 x2 z 20000 50 x1 100 x2 z 27500 50 x1 100 x2 z 0 50 x1 100 x2 z 10000 50 x1 100 x2 C B A D E 图解法 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 13 建立数学模型和求得最优解后 研究线性规划的一个或多个参数 系数 ci aij bj变化时 对最优解产生的影响 灵敏度分析 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 例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 2020 1 15 可编辑 14 15 x1 x2 z 20000 50 x1 100 x2 z 27500 50 x1 100 x2 z 0 50 x1 100 x2 z 10000 50 x1 100 x2 C B A D E 图解法 2020 1 15 数据 模型与决策 改变目标向量 目标函数中的系数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 时 原最优解仍是最优解 2020 1 15 可编辑 16 17 假设产品 的利润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 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 18 约束条件中右边系数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元利润 称为该约束条件的对偶价格 改变右端向量 2020 1 15 数据 模型与决策 19 假设原料A增加10千克时 即b2变化为410 这时可行域扩大 但最优解仍为x2 250和x1 x2 300的交点x1 50 x2 250 此变化对总利润无影响 该约束条件的对偶价格为0 解释 原最优解没有把原料A用尽 有50千克的剩余 因此增加10千克值增加了库存 而不会增加利润 在一定范围内 当约束条件右边常数增加1个单位时 1 若约束条件的对偶价格大于0 则其最优目标函数值得到改善 变好 2 若约束条件的对偶价格小于0 则其最优目标函数值受到影响 变坏 3 若约束条件的对偶价格等于0 则最优目标函数值不变 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 20 当有多个系数变化时 需要进一步讨论 百分之一百法则 对于所有变化的目标函数决策系数 约束条件右边常数值 当其所有允许增加的百分比与允许减少的百分比之和不超过100 时 最优解不变 对偶价格不变 最优解仍是原来几个线性方程的解 允许增加量 上限 现在值c1的允许增加量为100 50 50b1的允许增加量为325 300 25 允许减少量 现在值 下限c2的允许减少量为100 50 50b3的允许减少量为250 200 50 允许增加的百分比 增加量 允许增加量 允许减少的百分比 减少量 允许减少量 百分百法则 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 21 例 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 百分之一百法则是充分条件 但非必要条件 也就是说超过100 并不一定变化 3 百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况 这种情况下 只有重新求解 2020 1 15 数据 模型与决策 22 管理运筹学 软件的输出信息分析 相差值表示相应的决策变量的目标系数需要改进的数量 使得决策变量为正值 当决策变量已为正数时 相差数为零 松弛 剩余变量的数值表示还有多少资源没有被使用 如果为零 则表示与之相对应的资源已经全部用上 对偶价格表示其对应的资源每增加一个单位 将增加多少个单位的最优值 目标函数系数范围表示最优解不变的情况下 目标函数的决策变量系数的变化范围 当前值是指当前的最优解中的系数取值 常数项范围是指约束条件的右端常量 上限值和下限值是指当约束条件的右端常量在此范围内变化时 与其对应的约束条件的对偶价格不变 当前值是指现在的取值 以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变 只有一个系数变化的基础上得出的 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 23 注意 当约束条件中的常数项增加一个单位时 最优目标函数值增加的数量称之为影子价格 在求目标函数最大时 当约束条件中的常数项增加一个单位时 目标函数值增加的数量就为改进的数量 所以影子价格等于对偶价格 在求目标函数值最小时 改进的数量就是减少的数量 所以影子价格即为负的对偶价格 管理运筹学 软件可以解决含有100个变量50个约束方程的线性规划问题 可以解决工商管理中大量的问题 如果想要解决更大的线性规划问题 可以使用由芝加哥大学的L E Schrage开发的Lindo计算机软件包的微型计算机版本Lindo PC 管理运筹学 软件的输出信息分析 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 2020 1 15 可编辑 24 AB公司 AB公司在这一周内只生产两种产品 产品A和产品B 管理部门必须决定每种产品各生产多少吨 产品A的售价为每吨25美元 产品B的售价为每吨10美元 生产出的全部产品都将被出售 产品A和产品B由多种材料混合而成 这些材料都从仓库中提取 可供这一周使用的三种原材料数量如下 原料1 12000吨原料2 4000吨原料3 6000吨产品A由60 的原料1和40 的原料2制成产品B由50 的原料1 10 的原料2和40 的原料3制成 2020 1 15 25 目标函数 max25A 10B 2020 1 15 可编辑 26 2020 1 15 可编辑 27 有人以1美元 吨的价格提供500吨的原料1 我们是否接受 回答 除非我们要为将来使用原料1做储备才接受 因为我们已经有过量的原料1 有人以50美元 吨的价格提供原料2 是否接受 回答 接受 在500吨以内每增加1吨的原料2 就将会有62 5美元的收益 如果以50美元 吨的价格接受 我们还会有12 5美元 吨的纯收入 总共收入6250美元 2020 1 15 可编辑 28 续 一个公司彻底用完了原料3 而以15美元 吨的价格向我们求购原料3 有多少要多少 我们是否应该卖给他们一些 回答 如果他们负责运输 就把6000吨原料3卖给他们 我们放弃了原料3的9 375美元 吨的收益 从而使得B产品的产量为零 如果我们以15美元 吨的价格卖掉6000吨的原料3 总贡献将会有33750美元的增加 15 9 375 6000 线性规划在工商管理中的应用 2020 1 15 数据 模型与决策 29 30 人力资源分配的问题 例1 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下 设司机和乘务人员分别在各时间段一开始时上班 并连续工作八小时 问该公交线路怎样安排司机和乘务人员 既能满足工作需要 又配备最少司机和乘务人员 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 31 人力资源分配的问题 解 设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 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 32 人力资源分配的问题 例2 一家中型的百货商场 它对售货员的需求经过统计分析如下表所示 为了保证售货人员充分休息 售货人员每周工作5天 休息两天 并要求休息的两天是连续的 问应该如何安排售货人员的作息 既满足工作需要 又使配备的售货人员的人数最少 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 33 人力资源分配的问题 解 设xi i 1 2 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 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 往往一些服务行业的企业对人力资源的需求一周内像例2所描述的那样变化 而每天的各时间段的需求又像例1往往描述的那样变化 在保证工作人员每天工作8h 每周休息两天的情况下 如何安排能使人员的编制最小呢 2020 1 15 可编辑 34 35 生产计划的问题 例3 某公司面临一个是外包协作还是自行生产的问题 该公司生产甲 乙 丙三种产品 都需要经过铸造 机加工和装配三个车间 甲 乙两种产品的铸件可以外包协作 亦可以自行生产 但产品丙必须本厂铸造才能保证质量 数据如表 问 公司为了获得最大利润 甲 乙 丙三种产品各生产多少件 甲 乙两种产品的铸造中 由本公司铸造和由外包协作各应多少件 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 36 生产计划的问题 解 设x1 x2 x3分别为三道工序都由本公司加工的甲 乙 丙三种产品的件数 x4 x5分别为由外协铸造再由本公司加工和装配的甲 乙两种产品的件数 求xi的利润 利润 售价 各成本之和产品甲全部自制的利润 23 3 2 3 15元产品甲铸造外协 其余自制的利润 23 5 2 3 13元产品乙全部自制的利润 18 5 1 2 10元产品乙铸造外协 其余自制的利润 18 6 1 2 9元产品丙的利润 16 4 3 2 7元可得到xi i 1 2 3 4 5 的利润分别为15元 10元 7元 13元 9元 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 37 生产计划的问题 通过以上分析 可建立如下的数学模型 目标函数 Max15x1 10 x2 7x3 13x4 9x5约束条件 5x1 10 x2 7x3 80006x1 4x2 8x3 6x4 4x5 120003x1 2x2 2x3 3x4 2x5 10000 x1 x2 x3 x4 x5 0 2020 1 15 数据 模型与决策 2020 1 15 数据 模型与决策 38 套裁下料问题 例4 某工厂要做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 2020 1 15 数据 模型与决策 39 用 管理运筹学 软件计算得出最优下料方案 按方案1下料30根 按方案2下料10根 按方案4下料50根 即x1 30 x2 10 x3 0 x4 50 x5 0 只需90根原材料就可制造出100套钢架 注意 在建立此类型数学模型时 约束条件用大于等于号比用等于号要好 因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢 但它可能是最优方案 如果用等于号 这一方案就不是可行解了 3套裁下料问题 2020 1 15 数据 模型与决策 40 投资问题 例5 某部门现有资金200万元 今后五年内考虑给以下的项目投资 已知项目A 从第一年到第五年每年年初都可投资 当年末能收回本利110 项目B 从第一年到第四年每年年初都可投资 次年末能收回本利125 但规定每年最大投资额不能超过30万元 项目C 需在第三年年初投资 第五年末能收回本利140 但规定最大投资额不能超过80万元 项目D 需在第二年年初投资 第五年末能收回本利155 但规定最大投资额不能超过100万元 据测定每万元每次投资的风险指数如右表 问 a 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利金额为最大 b 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小 2020 1 15 数据 模型与决策 2020 1 15 可编辑 41 解 1 确定决策变量 连续投资问题设xij i 1 5 j 1 4 表示第i年初投资于A j 1 B j 2 C j 3 D j 4 项目的金额 这样我们建立如下的决策变量 Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24 投资问题 2 约束条件 第一年 A当年末可收回投资 故第一年年初应把全部资金投出去 于是x11 x12 200 第二年 B次年末才可收回投资 故第二年年初有资金1 1x11 于是x21 x22 x24 1 1x11 第三年 年初有资金1 1x21 1 25x12 于是x31 x32 x33 1 1x21 1 25x12 第四年 年初有资金1 1x31 1 25x22 于是x41 x42 1 1x31 1 25x22 第五年 年初有资金1 1x41 1 25x32 于是x51 1 1x41 1 25x32 B C D的投资限制 xi2 30 i 1 2 3 4 x33 80 x24 100 2020 1 15 数据 模型与决策 42 投资问题 3 目标函数及模型 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 2020 1 15 数据 模型与决策 43 44 投资问题 b 所设变量与问题a相同 目标函数为风险最小 有Minf x11 x21 x31 x41 x51 3 x12 x22 x32 x42 4x33 5 5x24在问题a