高项运筹学 PPT课件VIP

第27章高项运筹学 2020 4 7 1 基本介绍 运筹学是一门专门的学科 博大精深 在信息系统项目管理师考试中通常会考察3分左右 且计算量很大 但是只要把一些常见的思想 常见的解题方法掌握了 再把历年的真题搞清楚 基本就OK了 2020 4 7 2 知识点分布 规划论 线性规划 非线性规划 整数规划 目标规划图论与网络存储论排队论决策论 2020 4 7 3 常见题型和解题思路 线性规划线性规划主要用于解决生活 生产中的资源利用 人力调配 生产安排等问题 它是一个重要的数学模型 简单的线性规划指的是目标函数含两个自变量的线性规划 其最优解可以用数形结合方法求出 用数学语言来说 就是在一组约束条件下寻找目标函数的极值问题 2020 4 7 4 常见题型和解题思路 对策论 博弈 按决策者的主观态度不同分为5中准则 悲观主义 乐观主义 折中主义 等可能性和后悔值准则五种 乐观主义准则 也称为最大最大准则 MAXMAX准则 其决策的原则是 大中取大 悲观主义准则 也称为最大最小准则 MAXMIN准则 其决策的的原则是 小中取大 折中主义准则 也称为赫尔威斯准则 折中决策方法的特点是事物既不乐观冒险 也不悲观保守 而是折中平衡一下 等可能准则 也称为拉普拉斯准则 后悔值准则 即遗憾值也称为萨维奇准则 最小机会损失准则 在制定决策后 如果不符合理想情况 必然有后悔的感觉 2020 4 7 5 常见题型和解题思路 随机决策问题是指决策者所面临的各种自然状态是随机出现的一类决策问题 随机决策必备条件 1 存在着决策者希望达到的明确目标2 存在着不以决策者的主观意志为转移的两种以上的自然状态3 存在着两个以上的可供选择的行动方案4 不同行动方案在不同自然状态下的益损值可以计算出来 随机决策问题可以进一步分为风险型和非确定型决策问题 在风险型中 虽然未来自然状态的发生是随机的 但每种状态发生的概率是已知或可以预先估计的 在非确定型中 不仅未来自然状态的发生时随机的 而且各种自然状态发生的概率也是未知和无法预先估计的 2020 4 7 6 常见题型和解题思路 经济计量分析的工作程序经济计量分析是用统计推论方法对经济变量之间的关系做出数值估计的一种数量分析方法 它首先把经济理论表示为可计量的数学模型即经济计量模型 然后用统计推论方法加工实际资料 使这个数学模型数值化 2020 4 7 7 常见题型和解题思路 状态转移矩阵状态转移矩阵是俄国数学家马尔科夫提出的 他在20世纪初发现 一个系统的某些因素在转移中 第n次结果只受第n 1的结果影响 即只与当前所处状态有关 而与过去状态无关 在马尔科夫分析中 引入状态转移这个概念 所谓状态是指客观事物可能出现或存在的状态 状态转移是指客观事物由一种状态转移到另一种状态的概率 2020 4 7 8 常见题型和解题思路 组合分析组合分析是一种用来研究消费者对于产品或服务偏好的技术 通过这种技术 我们可以获取有关新产品的各种相关属性在消费者的购买行为中所起到的影响程度 及在各种属性中各种可替换因素的具体效用函数 从而帮助客户从多种可选择的产品性能中做出准确判断 2020 4 7 9 常见题型和解题思路 最小生成树最小生成树 对于连通的带权图 连通图 G 其生成树也是带权的 生成树T各边的权值总和称为该树的权 这里 TE表示T的边集 w u v 表示边 u v 的权 权最小的生成树为G的最小生成树 最小生成树可简记为MST 2020 4 7 10 常见题型和解题思路 决策表 期望货币价值 决策表又称判断表 是一种呈表格状的图形工具 适用于描述处理判断条件较多 各条件又相互组合 有多种决策方案的情况 精确而间接描述逻辑的方式 将多个条件与这些条件满足后要执行动作相对应 2020 4 7 11 常见题型和解题思路 决策树每个决策或事件 即自然状态 都可能引出两个或多个时间 导致不同的结果 把折中决策分支画成图形很像一棵树的枝干 故称决策树 一般都是自上而下的来生成的 其算法是一种逼近离散函数值的方法 2020 4 7 12 常见题型和解题思路 图论图论 GraphTheory 是数学的一个分支 它以图为研究对象 图论中的图是由若干给定的点及连接两点的线所构成的图形 这种图形通常用来描述某些事物之间的某种特定关系 用点代表事物 用连接两点的线表示相应两个事物间具有这种关系 2020 4 7 13 历年试题解析 2020 4 7 14 历年试题解析 所谓决策 是指为确定未来某个行动的目标 根据自己的经验 在占有一定信息的基础上 借助于科学的方法和工具 对需要决定的问题的各个因素进行分析 计算和评价 并从两个以上的可行方案中 选择一个最优方案的分析判断过程 根据决策结局的多少 可以将决策分为确定型决策 每个方案只有一个结局 和不确定型决策 每个方案有多个结局 本试题属于不确定型决策问题 决策准则包括乐观准则 悲观准则 后悔值准则等 其中 Maxmin悲观准则 最大最小准则 是指对于任何行动方案 都认为将是最坏的状态发生 即收益值最小的状态发生 然后 比较各行动方案实施后的结果 取具有最大收益值的行动作为最优行动的决策原则 2020 4 7 15 历年试题解析 2020 4 7 16 历年试题解析 从节点1到节点6可以同时沿多条路径运输 总的最大流量应该是各条路径上最大流量之和 每条路径上的最大流量由其各段流量的最小值决定 按照习惯 每次应尽量先找出具有最大流量的路径 理论上可以证明 虽然寻找各种路径的办法可以不同 运输方案也可以有很多种 但总的最大流量值是唯一确定的 比较直观的解题方法是 每找出一条路径算出流量后 该路径上各段线路上的流量应扣除已经算过的流量 形成剩余流量 剩余流量为0的线路应将其删除 计算方法如下 路径1356的最大流量为10 将13之间的路径断开路径1256的剩余最大流量为6 将12之间的路径断开路径146的剩余最大流量为5 将46之间的路径断开路径14256的剩余最大流量为1 将25之间的路径断开路径14356的剩余最大流量为1 将43之间的路径断开 至此不存在从1到6的运输路径 故而其最大流量是所有可能运输路径上的最大流量之和 即为 10 6 5 1 1 23 2020 4 7 17 历年试题解析 2020 4 7 18 历年试题解析 为了缩短总工时 应适当安排加工各零件的顺序 以缩短其铣床最后的加工时间 并缩短车床最先的加工时间 因此应采取如下原则来安排各零件的加工顺序 在给定的工时表中找出最小值 如果它是铣床时间 则该零件应最后加工 如果它是车床时间 则该零件应最先加工 除去该零件后 再按此原则继续进行安装 在表中 最小工时为2小时 这是零件C所用的铣床加工时间 因此零件C应该放在最后加工 除去零件C后 工时表中最小工时为4小时 这是零件B所需的车床加工时间 因此零件B应最先加工 再除去B之后 工时表中最小时间为5小时 是零件D所需的铣床加工时间 因此零件D应安排在零件A之后进行加工 此时所得的最优加工方案是 按B A D C的顺序来加工 需要4 8 6 6 24小时 2020 4 7 19 历年试题解析 将部分公路改造成高速公路 使各个城市之间均可通过高速公路通达 至少要改造总计 公里的公路 这种总公里数最少的改造方案共有 个 A 1000B 1300C 1600D 2000A 1B 2C 3D 4 2020 4 7 20 历年试题解析 从题目来看 本题要求得到图的最小支撑树 即选取部分边 使其保持连通 又使其总长度最小 1 任取一点 例如A 将其纳入已完成部分 点A与其他各点中的最小距离为AE 200 从而将AE及点E纳入已完成部分 2 点A E与其他各点之间的最短距离是AB AF 300 从而可以将边AB与点B 或边AF与点F 纳入已完成部分 3 点A B E与点C D F两个集合之间的最短距离为AF BF 从而将边AF 或BF 与点F纳入到已完成部分 4 点A B E F与点C D两个集合之间的最短距离为FD 200 从而将边FD与点D纳入到已完成部分 5 点A B E F D与点C两个集合之间的最短距离为CD 300 从而将点C与边CD纳入已完成部分 6 所有6个点都已接通 其边为AB AE AF FD CD 总长度为300 200 300 200 300 1300其中CD在最短总长度方案中不可少 而AB BF AF中可以任选2条 因此 总共有3个最短总长度的方案 2020 4 7 21 历年试题解析 2020 4 7 22 历年试题解析 将6门课程作为6个节点画出 然后在两个课程节点之间画连线表示它们不可以在同一天安排考试 那么 每个博士的各门选修课之间都应画出连线 如图所示 例如 B1博士选修了A B D3门课程 则ABD之间都应有连线 表示这3门课中的任何两门都不能安排在同一天考试 从图中可以看出 能够安排在同一天考试的课程有AE BC DE DF 所以AE排在第一天 BC排在第二天 DF排在第三天 排除法 直接对各个选择答案进行试探 排除不合理的 确认合理的安排选择答案A不合理 BD排在同一天 B1等考试一天考两门选择答案B不合理 AC排在同一天 B2等考生一天考两门选择答案C不合理 AF排在同一天 B3等考生一天考两门所以只能选D 2020 4 7 23 历年试题解析 A 甲采取高价策略 乙采取低价策略B 甲采取高价策略 乙采取高价策略C 甲采取低价策略 乙采取低价策略D 甲采取高价策略 乙采取高价策略 2020 4 7 24 历年试题解析 这是一个简短的博弈问题 站在A网站的立场上看 假设B网站采用高价策略 那么自己采用高价策略得1000万元 采用低价策略得1500万元 如果B网站采用低价策略 那么自己采用高价策略得200万元 采用低价策略得700万元 显然也应该采用低价策略 同理 站在B网站的立场上看 也是这样 不管A网站采用什么价格策略 自己都应采用低价策略为好 因此 这个博弈的结果一定是两个网站都采用低价策略 各得到700万元的利润 2020 4 7 25 历年试题解析 某公司准备将新招聘的4名销售员分配到下属3个销售点甲 乙和丙 各销售点增加若干名销售员后可增加的月销售额如下表所示 增加销售额 千元 根据此表 只要人员分配适当 公司每月最多可以增加销售额 千元A 43B 47C 48D 49 2020 4 7 26 历年试题解析 由于各个点增加同样的人数后增加的销售额不尽相同 且要求使公司每月所增加的销售额最大 因此分配时应优先考虑增加销售额多的销售点 方案1 4人集中在一个点 应将4个人分派到销售点甲 公司每月所增加的销售额为38千元 方案2 三个人分配到同一个点 另一个人分配到另一点 即第二列和第四列数据的排列组合 其中 当3个人分配到甲 另一人分配到丙时 公司每月所增加的销售额最高 43千元方案3 两个人分配到一个销售店 另两个人分配到另一个销售点 此时考虑第3列数据的排列组合 共有3种 其中当甲 乙两个销售点各分配2人时 增加的销售额最高 47千元方案4 2人分配到同一个销售点 其他两个销售点各分配1人 此时所需考虑的是第2列 第3列数据的排列组合 共有3种方案 其中2人分配到丙 甲 乙各分配一人时 销售额增加最多 48千元 答案 C 2020 4 7 27 历年试题解析 制造某种产品需要4道工序 每道工序可选用多种方法 下图列出了指导这种产品各道工序可选用的不同方法 从节点1开始 连续经过4条线段 表示4道工序所选用的方法 组成一条线路 直到节点12结束 每条线段上标记的数字表示利用相应方法每件产品可获得的利润 元 企业为了获取最大利润 需要找出从节点1到节点12的一条线路 使其对应的各道工序的利润之和达到最大 利用运筹方法计算后可知 指导每件产品可以获得最大利润是 元 A 28B 31C 33D 34 2020 4 7 28 历年试题解析 解析 从图论上看 本题就是求节点1到节点12的最长路径 其算法类似于求最短路径的方法 采用倒推标记方法进行推算的解题步骤如下 1 先找出离终点只有一步的结点9 10 11 分别标记其到达终点的路径与长度 2 再找出前往结点9 10 11只有一步的结点5 6 7 8 对其中每个结点 找出其到终点的最长路径 分别将其路径与长度标记出来 得到5 9 12 15 6 11 12 13 7 11 12 16 8 9 12 19 3 再找前往结点5 6 7 8只有一步的结点2 3 4 对其中每个结点 找出其到终点的最长路径 这些结点到终点的最长路径及长度值如下 2 8 9 12 26 3 8 9 12 29 4 8 9 12 23 4 最后 找出结点1通过结点2 3 4到终点的路径中的最长路径 并标记出来 即1 3 8 9 12 33 2020 4 7 29 历年试题解析 某工程包括A B C D E F G H八个作业 各个作业的紧前作业 所需时间和所需人数如下表所示 假设每个人均能承担各个作业 该工程的工期应为 周 按此工期 整个工程至少需要 人A 8B 9C 10D 11A 8B 9C 10D 11 2020 4 7 30 历年试题解析 某IT企业计划对一批新招聘的技术人员进行岗前脱产培训 培训内容包括编程和测试两个专业 每个专业要求在基础知识 应用技术和实际训练三个方面都得到提高 根据培训大纲 每周的编程培训可以同时获得基础知识3学分 应用技术7学分以及实际训练10学分 每周的测试培训可以同时获得基础知识5学分 应用技术2学分以及实际训练7学分 企业要求这次岗前培训至少能完成基础知识70学分 应用技术86学分 实际训练185学分 以上说明如下表所示 那么这样的岗前培训至少需要 周时间才能满足企业的要求 A 15B 18C 20D 23 2020 4 7 31 历年试题解析 从应试的角度出发 可采用尝试法快速做题 假设这样的岗前培训为15周 且全部安排编程培训 则基础知识总分为3 15 4586分 实际训练总分为10 15 150分 185分 因此假设不能满足实体要求 同理 假设这样岗前培训为18周 实际训练总分为10 18 180分 185分 因此假设不能满足试题要求 若这样的岗前培训为20周 编程培训和测试培训分别安排15周 5周 则基础知识总分为70分 应用技术总分为115分 实际训练总分为185分 能够满足要求 答案 C 2020 4 7 32 历年试题解析 载重量限24吨的某架货运飞机执行将一批金属原料运往某地的任务 待运输的各箱原料的重量 运输利润如下表所示 经优化安排 该飞机本次运输可以获得最大利润为 千元A 11B 10C 9D 8 2020 4 7 34 历年试题解析 解析 将表中重量最少的4个数据相加 即5 6 7 8 26吨 24吨 因此该架飞机不能同时运载表中任何4箱的物品 按利润从高到低同时运载表中任何3箱物品进行试排 当同时运载箱号为1 4 6的物品时 载重量刚好为24吨 此时利润为3 4 3 10 千元 2020 4 7 35 历年试题解析 某工厂生产甲 乙两种产品 生产1公斤甲产品需要煤9公斤 电4度 油3公斤 生产1公斤乙产品需要煤4公斤 电5度 油10公斤 该工厂现有煤360公斤 电200度 油300公斤 已知甲产品每千克利润为7千元 乙产品每公斤利润为1 2万元 为了获取最大利润应该生产甲产品 公斤 乙产品 公斤 A 20B 21C 22D 23A 22B 23C 24D 25 2020 4 7 36 历年试题解析 依题意 X1为甲产品生产量 X2为乙产品生产量 为可获取的最大利润 则反映了该生产计划问题的线行规划数学模型表示如下 目标函数 约束条件 2020 4 7 37 历年试题解析 某厂需要购买生产设备生产某种产品 可以选择购买四种生产能力不同的设备 市场对该产品的需求状况有三种 需求量较大 需求量中等 需求量较小 厂方估计四种设备在各种需求状况下的收益如下表 根据收益期望值最大的原则 应该购买 A 设备1B 设备2C 设备3D 设备4 2020 4 7 38 历年试题解析 对于每种设备 其收益期望值 选择设备1的收益期望值为17选择设备2的收益期望值为16选择设备3的收益期望值为18选择设备4的收益期望值为10所以 选择C 2020 4 7 39 历年试题解析 某公司新建一座200平米的厂房 现准备部署生产某产品的设备 该公司现空闲生产该产品的甲 乙 丙 丁四种型号的设备各3台 每种型号设备每天的生产能力由下表给出 在厂房大小限定的情况下 该厂房每天最多能生产该产品 个 A 520B 540C 524D 530 2020 4 7 40 历年试题解析 这是一个整数背包问题 其中一种解法是贪婪法 按设备单位面积的生产能力从高到低排序 一次选取对应设备 直到把厂房面积用完 根据表中的数据 将甲 乙 丙 丁4种型号的设备 每天生产能力 除以各自的 占地面积 可得每种型号的设备每平方米每天的生产能力 计算结果分别为2 5个 3 0个 2 0个和1 6个 因此在相同面积的情况下 应按乙 甲 丙 丁的顺序选择设备 依题意 生产该产品的甲 乙 丙 丁4中型号的设备各3台 在厂房大小限定的情况下 若要使该厂房每天的生产能力最大 则需要选择3台乙型号设备 3台甲型号设备 两台丙型号设备 这8台设备的总占地面积为20 3 40 3 10 2 200平方米 该厂房每天最多能生产指定产品的个数为520个 2020 4 7 41 历年试题解析 在软件开发项目中 关键路径是项目事件网络中 组成关键路径的活动称为关键活动 下图中关键路径历时 个时间单位 A 最长的回路B 最短的回路C 源点和汇点间的最长路径D 源点和汇点件的最短路径A 14B 18C 23D 25 2020 4 7 42 历年试题解析 某工厂生产两种产品S和K 受到原材料供应的设备加工工时的限制 单件产品的利润 原材料消耗及加工工时如下表 为获得最大利润 S应生产 件A 7B 8C 9D 10 2020 4 7 43 历年试题解析 设x y分别表示在计划期内产品S K的产量x 0 y 0 依题意 列出以下列方程式及相应的求解过程 当x 8 y 2时 将获得最大利润128元 2020 4 7 44 历年试题解析 公司开发一套信息管理软件 其中一个核心模块的性能对整个系统的市场销售前景影响极大 该模块可以采用S公司自己研发 采购代销和有条件购买三种方式实现 S公司的可能利润 单位 万元 收入如下表 按经验 此类管理软件销售50万套 20万套 5万套和销售不出的概率分别为15 25 40 和20 则S公司应选择 方案 A 自己研发B 采购代销C 有条件购买D 条件不足无法选择 2020 4 7 45 历年试题解析 分别计算采用三种方式时的货币期望值为67500万元 65000万元和62500万元 故而选择A 自己研发 2020 4 7 46 历年试题解析 某公司打算经销一种商品 进价为450元 件 售价500元 件 若进货商品一周内售不完 则每件损失50元 假定根据以往统计资料估计 每周最多销售4件 并且每周需求量分别为0 1 2 3和4件的统计概率如下表所示 则公司每周进货 件可使利润最高 2020 4 7 47 历年试题解析 本题主要考查运筹学中的风险性决策方法 1 根据已知条件 可计算出不同进货量及销量下可能获得的收益结果 第一行 进货量如果是1件 销售一件只能获得50元 如果市场上可以销售2件 但是由于进货量只有1件 因此收益仍然是50元第二行 如果进货2件 但是只能销售一件 获得50元 同时因为有一件没有卖出去损失50元 两者相抵 总收益为50 50 如果可以销售两件 可以获得收益100元依次类推可以得到其他收益值2 不同进货量及销量下可能获得收益结果填好以后 根据决策树计算公式 得到进货量为1时的期望收益 50 0 1 50 0 2 50 0 3 50 0 4 50 同理得到进货量为2 3 4时的期望值 3 决策结论 进货3件可获得最高收益110元 2020 4 7 48 历年试题解析 某项目有 四项不同任务 恰有甲 乙 丙 丁四个人去完成各项不同的任务 由于任务性质及每人的技术水平不同 他们完成各项任务所需时间也不同 具体如下表所示项目要求每个人只能完成一项任务 为了使项目花费的总时间最短 应该指派丁完成 任务 A B C D 2020 4 7 49 历年试题解析 此题为运筹学中标准的指派问题 以人员指派为例 大都满足以下三个前提假设 人数等于任务数 每个人必须且只需完成一项任务 每项任务必须且只需一人去完成 本题的效率矩阵为本题求最小值 下面用匈牙利解法求解 1 行变换 找出每一行 每一列 的最小值 然后让每一行 每一列都减去这个数 2020 4 7 50 历年试题解析 2 试指派 找独立的零元素 独立零元素个数为 矩阵阶数为 当时 问题得解 最优解为 最短时间为 4 4 9 11 28应指派丁完成任务 C是正确答案 2020 4 7 51 历年试题解析 某项目各期的现金流量如下表所示 设贴现率为10 则项目的净现值约为 A 140B 70C 34D 6 2020 4 7 52 历年试题解析 根据净现值公式可知 目前项目的净现值 630 330 1 10 440 1 10 2 630 300 364 34 2020 4 7 53 历年试题解析 某企业需要采用甲 乙 丙三种原材料生产 两种产品 生产两种产品所需原材料数量 单位产品可获得理人以及企业西安有原材料数如表所示 则公司可以获得的最大利润是 万元 取得最大利润时 原材料 尚有剩余 A 21B 34C 39D 48A 甲B 乙C 丙D 乙和丙 2020 4 7 54 历年试题解析 设生产的产品 为x吨 产品 为y吨 1x 1y 4 4x 3y 12 1x 3y 6解上述方程可知 x 2 y 4 3 因此 最大利润是 9 2 12 4 3 34 原料 甲 还剩余 4 2 1 3333 B A 2020 4 7 55 历年试题解析 决策树分析法通常用决策树图表进行分析 根据下表的决策树分析法计算 图中机会节点的预期收益EMV分别是 90和 2020 4 7 56 历年试题解析 两家工厂A1和A2向三个零售店B1 B2和B3供应某种商品 A1和A2可供应的商品件数是200和300 而B1 B2和B3的需求量是100件 200件和50件 各工厂和零售店之间可以进行转运 如果运输的单位成本如下所示 例如 表中第4列第3行的数字 5 表示将一件商品从A2运到B1的成本 在最优的转运安排中 满足各零售商品需求的运输总成本是 A 1750B 1550C 1350D 850 2020 4 7 57 历年试题解析 1 分别求出A1节点和A2节点通往B1B2B3的最短路径2 判断最优方案首先A2运往B3最优 首先应满足B3 A2运往B350件 完全满足 A2剩余250件 其次A2运往B2200件 完全满足 A2剩余50件再次A2运往B150件 A2全部消耗 B1仍需50件 最后A1运往B150件 完全满足 A1剩余150件3 50 3 200 4 50 5 50 7 150 800 250 350 1550