2014考研西安建筑科技大学-《816运筹学》习题解析.pdf

第 讲 第一章 线性规划 一 线性规划 例 试述线性规划问题数学模型的组成部分及特征 判别下列数学模型是否是线性规划模型 模型中 为常数 为可取某一常数值的参变量 为变量 例 将下列线性规划问题化成标准型 无约束 无约束 单纯形法 例 用单纯形法求解线性规划 西安建筑科技大学 运筹学 习题解析 例 用单纯形法求解线性规划 考试点 名师精品课程电话 第 讲 第一章 线性规划 二 线性规划应用举例 经营规划 配料选取 任务分配 投资预算 任务指派 合理利用线材 补充 例 用长 米的角钢切割钢窗用料 每付钢窗含长 米的 根 米的 根 米的 根 米的 根 若需钢窗用料 付 问最少需切割 米长的角钢多少根 例 某厂计划在下月内生产 种产品 每种产品都可用三条流水线作业 中任何一条加工出来 每条流水线 加工每件产品 所需的工时数 每条流 水线在下月内可供利用的工时数及各种产品的需求量均列于下表中 又 三条流水线的生产 成本分别为每小时 元 问应如何安排各条流水线在下月的生产任务 才能使总的生产成本 最少 每件产品 产品 耗时数 流水线 可用工时数 需求量 件 例 某公司下月需要 四种型号的钢板分别为 吨 吨 吨和 吨 他准备向生产这些钢板的 三家工厂订货 该公司掌握了这三家工厂生产各种钢板的效率 吨 小时 及下月的生产能力 小时 如下表 所示 而他们生产各种型号钢板的成本也如下表 所 示 该公司当然希望能以最少的代价得到自己所需的各种钢板 问他应该向各钢厂订购每种钢板各 多少吨 西安建筑科技大学 运筹学 习题解析 表 生产效率 钢板型号 吨 小时 钢厂名称 下月生产能力 小时 钢板需求量 吨 表 单位成本 钢板型号 百元 吨 钢厂名称 例 某造纸厂接到一份定货单 要求供应三种规格的卷纸 米宽的 米 米宽的 米 米宽的 米 该厂只生产 米宽和 米宽两种标准宽度的卷纸 现需将他们按定单要求 的大小切开 对标准纸的长度没有限制 因为可以按实际需要 把有限长度的卷纸连接起来 达到所 需要的长度 现问应如何进行切割 才能既满足用户要求 又使切割损失最小 例 中华家电公司最近生产了一种新型洗衣机 为了推销这种新产品 该公司销售部决定利用 多种广告宣传形式来使顾客了解新洗衣机的优点 经过调查研究 销售部经理提出了五种可供选择 的宣传方式 销售部门并收集了许多数据 如每项广告的费用 每种宣传方式在一个月内可利用的最 高次数以及每种广告宣传方式每进行一次所期望得到的效果等 这种期望效果以一种特定的相对价 值来度量 是根据长期的经验判断出来的 上述有关数据见下表 广告方式每次广告费用 元每月可用的最高次数期望的宣传效果 单位 电视台 白天 分钟 电视台 晚上 秒种 每日晨报 半版 星期日报 半版 广播电台 分钟 公司现拨了 万元给销售部作为第一个月的广告预算费 同时提出 月内至少得有 个电视商业 节目 条报纸广告 且整个电视广告费不得超过 万元 电台广播至少隔日有一次 现问该公司 考试点 名师精品课程电话 销售部应当采取怎样的广告宣传计划 才能取得最好的效果 例 长城家电公司最近研制了一种新型电视机 准备在三种类型的商场即一家航空商场 一家 铁路商场和一家水上商场进行销售 由于三家商场的类型不同 他们的批发价和推销费都不同 因而 产品的利润也不同 此外 公司根据过去的经验 对这三家商场所需的广告费和推销人员的工时作了 估计 这些数据列于下表中 由于这种电视机的性能良好 各家商场都纷纷争购 但公司的生产能力 有限 每月只能生产 台 故公司规定了如下的销售方针 铁路商场至少经销 台 水上商场至 少经销 台 航空商场至少经销 台 至多 台 公司计划在一个月内的广告预算费为 元 推销人员最高可用工时数为 小时 同时 公司只根据经销数进行生产 即生产台数 销售 台数 经销商场每销售一台的利润 元每销售一台的广告费 元每销售一台需推销工时 小时 航空商场 铁路商场 水上商场 公司现在要确定下月的市场对策 具体说来 就是要对下面三个问题作出决策 应为各家商场生产多少台电视机 用于各家商场的广告费是多少 为各家商场各安排多少推销人员的工时 西安建筑科技大学 运筹学 习题解析 第 讲 第一章 线性规划 三 第二章 对偶规划 一 线性规划应用举例 例 某厂现有资金 万元 准备投资若干项目 据了解在今后五年内 已有下列四个项目欢迎 该厂投资 第一年年初投资 到次年末可收回本金的 第三年末除收回全部本金外 还可获利 第三年初投资 第四年末可收回本利 项目投资额至少 万元 第二年初投资 第四 年末可收回本金 第五年末 除收回全部本金外 还可获利润 第四年年初投资 第五年末可 收回本利 项目投资额至少 万元 至多 万元 第三年年初投资 第五年末可收回本利 但投资额不得超过 万元 也不得少于 万元 每年年初在银行进行定期储蓄 当年末取 出 年利 该厂决定对上述四个投资项目都进行投资 但每年度对各项目的投资金额 完全可由该厂根据自 己的情况确定 现问该厂应如何安排每年给各个项目的投资额 以便到第五年末能拥有最多的资金 例 设有 名运动员 组成的一个游泳队准备参加 米的混合接力赛 由爬 泳 蝶泳 仰泳 蛙泳各 米组成 这 名运动员的 米爬泳 蝶泳 仰泳 蛙泳成绩如下表所示 现问应指派每个人各游什么姿势 才能使总的成绩最好 爬泳 蝶泳 仰泳 蛙泳 对偶规划 问题 怎样写出原问题的对偶问题 针对对称形式的对偶问题 上 下 交换 左 右 换位 不等式变号 极大 变 极小 针对非对称形式的对偶问题 考试点 名师精品课程电话 把一个等式约束写成两个不等式约束 再根据对称形式的对偶关系定义写出 按照原始 对偶表直接写出 对称形式下对偶问题的一般形式 项目原问题对偶问题 目标函数 约束条件 决策变量 约束系数矩阵 约束条件的右端项向量 目标函数中的价格系数向量 其约束系数矩阵的转置 目标函数中的价格系数向量 约束条件的右端项向量 例 写出下面线性规划的对偶问题 对称形式 原始 对偶表 原问题 或对偶问题 对偶问题 或原问题 目标函数 目标函数 约束条件数 个 第 个约束条件类型为 第 个约束条件类型为 第 个约束条件类型为 对偶变量数 个 第 个变量 第 个变量 第 个变量是自由变量 决策变量数 个 第 个变量 第 个变量 第 个变量是自由变量 约束条件数 第 个约束条件类型为 第 个约束条件类型为 第 个约束条件类型为 课堂练习 写出下面线性规划的对偶规划 符号不限 下面的答案哪一个是正确的 为什麽 西安建筑科技大学 运筹学 习题解析 符号不限 符号不限 原问题是极小化问题 因此应从原始对偶表的右边往左边查 例 列出线性规划问题的对偶问题 自由 自由 自由 自由 对偶问题的基本性质 对称性 原始问题与对偶问题是两个互为对偶的问题 弱对偶性 两个问题的可行解对应的目标函数值互为上下界 最优性 两个问题最优解的目标函数值必相等 强对偶性 两个问题都有可行解时则两个问题必都有最优解 互补松弛性 两个问题最优解中 一个问题中某个变量取值非零 则该变量在对偶问题中对应 的某个约束条件必为紧约束 严格等式 反之 如果约束条件为松约束 严格不等式 则其对应的对 偶变量一定取值为零 因此 该定理又称为松紧定理 原问题与对偶问题解的对应关系表 问题与解的状态 对偶问题 有最优解无界解无可行解 原 问 题 有最优解一定不可能不可能 无界解不可能不可能可能 无可行解不可能可能可能 考试点 名师精品课程电话 第 讲 第二章 对偶规划 二 对偶单纯形法 例 用对偶单纯形法求解 其化为标准型为 灵敏度分析 例 考虑以下线性规划问题 应用单纯形得到部分最优单纯形表如下 完成以上单纯形表 当右端项 变为 时 最优解如何变化 当 的价值系数变为 时 最优解如何变化 当 的价值系数为何值 原最优解仍是最优的 且为无穷多个最优解 并求出这些解 若增加一个变量 其价值系数为 相应的技术系数为 最优解将如何变化 西安建筑科技大学 运筹学 习题解析 若增加一个约束 最优解如何变化 定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划 问题 一般形式 其中 是定义在 上的实值函数 其它情况 求目标函数的最大值或约束条件为小于等于零的情况 都可通过取其相反数化为上述 一般形式 证明定理 设 为定义在凸集 上的凸函数 则对任一实数 集合是 凸集 定理 有限个凸函数的非负线性组合仍为凸集 凹凸函数的定义及其证明方法 例 证明 为凸函数 凸规划的一些性质 其中 为凸函数 为凹函数 这样的非线性规划是凸规划 性质 凸规划的可行域为凸集 其局部最优解即为全局最优解 最优解的集合形成一个凸集 当凸规划的函数 为严格凸时 其最优解必定唯一 假定最优解存在的情况下 线性函数即可是凸函数 又可以凹函数 例 分析下面非线性规划是否是凸规划 考试点 名师精品课程电话 第 讲 第三章 运输规划 表上作业法 表上作业法的步骤 找出初始基可行解 表上给出 个数字格 求各非基变量的检验数 计算表中空格检验数 判断是否最优解 判断方法相同 确定换入变量和换出变量找出新的基可行解 表上调整 闭回路调整 重复 直至求出最优解 运输问题必有最优解 例 某部门有 个同类型的工厂 产地 生产的产品由 个销售点出售 各工厂的生产量 各销 售点的销售量 假定单位为 以及各工厂到销售点的单位运价 元 示于下表中 问如何调运才能使 总运费最小 销地 产地 产量 销 量 具有上下界的运输问题 例 求解下列运输问题 西安建筑科技大学 运筹学 习题解析 销地 产地 收量 最低需求 最高需求 不限 请大家关注 有转运的运输问题 关键是怎样求解 运输问题的应用 例 某厂按合同规定须于当年每个季度末分别提供 台同一规格的柴油机 已知该 厂各季度的生产能力及生产每台柴油机的成本如表 所示 又如果生产出来的柴油机当季不交 货的 每台每积压一个季度需储存 维护等费用 万元 要求在完成合同的情况下 作出使该厂全 年生产 包括储存 维护 费用最小的决策 季度生产能力 台 单位成本 元 例 腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器 大连分厂每月生产 台 广 州分厂每月生产 台 该公司在上海和天津有两个销售公司负责对南京 济南 南昌 青岛四个城 市的仪器供应 另外因为大连距离青岛较近 公司同意大连分厂向青岛直接供货 运输费用如下图 单位百元 应该如何调运可使总运输费用最低 图见视频 考试点 名师精品课程电话 第 讲 第四章 整数规划 割平面法 令 是相应线性规划最优解中为分数值的一个基变量 由单纯形表的最终表得到 其中 指构成基变量号码的集合 指构成非基变量号码的集合 将 和 都分解成整数部分 与非负真分数 之和 即 其中 其中 而 表示不超过 的最大整数 代入 中的方程得 提出变量为整数的条件 包括非负的条件 则由上式由左边看必须是整数 但由右边看 因为 所以不能为正 即 即可得到一个切割方程 例 求解下列整数规划问题 整数 隐枚举法 例 求解下列整数规划问题 或 指派问题 例 求下表所示效率矩阵的指派问题的最小解 西安建筑科技大学 运筹学 习题解析 任务 人员 甲 乙 丙 丁 戊 非标准形式的指派问题 在实际应用中 常会遇到各种非标准形式的制派问题 一般的处理方法是先将其转化为标准形 式 然后再用匈牙利法求解 最大化指派问题 设最大化指派问题系数矩阵 其中最大元素为 令矩阵 则以 为 系数矩阵的最小化指派问题和以 为系数矩阵的最大化指派问题有相同最优解 人数和事数不等的指派问题 若人少事多 则添加一些虚拟的 人 其费用系数取 若人多事少 则添加一些虚拟的 事 其 费用系数取 一个人可做几件事的指派问题 若某个人可以做几件事 则将该人化作几个 人 来接受指派 这几个 人 做同一件事的费用系 数当然都一样 某事一定不能由某人做的指派问题 若某事一定不能由某人做 则可将相应的费用系数取为足够大的数 怎样产生最少的直线 找出矩阵 中含有 元素最少的一行 或一列 从该行 或该列 中圈一个 再通过这个 作 一竖线 或横线 划去此 所在之列 或行 对 中余下的各行各列重复步骤 已圈数的行和列不再圈数 如果划线数不等于 则应在 那些未划直线的地方产生一些 元素 在所有未划去的数中找出最小的 设为 将所有未划去的各数 都减去 而位于已画的两直线交点处的数则加上 如果有 个互相排斥的约束条件 型 为了保证这 个约束条件只有一个起作用 我们引入 个 变量 和一个充 分大的常数 而下面这一组 个约束条件 考试点 名师精品课程电话 就合于上述的要求 这是因为 由于 式 个 中只有一个能取 值 设 代入 式 就只有 的约束条件起作用 而别的式子都是多余的 例 某厂拟用集装箱托运甲乙两种货物 运货有车运和船运两种方式 每箱的体积 重量 可获 利润以及托运所受限制如下所示 问两种货物各托运多少箱 可使获得利润为最大 货运方式 货物 车运船运 体积 箱 体积 箱 体积 箱 体积 箱 利润 元 箱 甲 乙 托运限制 西安建筑科技大学 运筹学 习题解析 第 讲 第六章 动态规划 一 动态规划 建立动态规划的模型的十步曲 正确 明确地划分阶段 依据决策过程的时间和空间的顺序关系 正确选择并确定状态变量 及状态集合 状态变量的确定有时并非显而易见 要确定它 通 常可对问题作如下分析而帮助确定状态变量 什么关系将各个阶段联系在一起 为了决定今后的最优 子 策略 需要事件现状的哪些信息 确定决策变量 及决策集合 写出状态转移方程 定义阶段指标值 函数 定义第 至 阶段 后部子过程 的最优指标 目标 函数 作出动态规划结构图 建立动态规划基本方程 逆序递推方程 或 或 边界条件 为已知函数 逆序递推求解动态规划基本方程 求出最优决策序列 顺序确定最优策略 逆推解法 例 用逆推法求解下面问题 考试点 名师精品课程电话 动态规划应用举例 例 某工厂的 台机器 拟分四个周期使用 在每一周期有两种生产任务 据经验 把机器 台投入第一种生产任务 则在生产周期中将有 台机器作废 余下的机器全部投入第二种生产任 务 则有 台机器作废 如果于第一种生产任务每台机器可收益 单位 于第二种生产任务每台 机器可收益 单位 问怎样分配机器 使总的收益最大 例 给定一个线路网络 要从 向 铺设一条输油管 各点间连线上的数字表示距离 问应选择 什么路线 可使总距离最短 图见视频 西安建筑科技大学 运筹学 习题解析 第 讲 第六章 动态规划 二 动态规划应用举例 例 某工厂根据国家的需要其交货任务如下表 月份 货物量 百件 表中数字为月底的交货量 该厂的生产能力为每月 件 该厂仓库的存货量为 件 已知 每百件货物的生产费用为 万元 在进行生产的月份 工厂要支出经常费用 元 仓库保管费为 每百件货物每月 元 假定开始时及六月底交货后无存货 试问应在每个月个生产多少件物品 才能既满足交货任务又使总费用最小 例 某台新设备的年效益及年均维修费 更新净费用如表所示 试确定今后 年内的更新策 略 使总收益最大 单位 万元 役龄 项目 效益 维修费 更新费 例 某部门欲在五周内采购一批原料 事先可估计出未来五周的每周内可能有三种价格 而每 种价格的概率变化如下表所示 该部门由于生产需要 必须在这五周内采购此种原料 问该部门究竟 应该在哪周 按什么价格采购 使得采购费用最小 价格 概率 例 设有 个工件需在机床 上加工 加工顺序是先 后 每个工件所需加工时间 单位 小时 如下表所示 问如何安排加工顺序 使机床连续加工完所有工件的加工总时间最少 并求出总 加工时间 考试点 名师精品课程电话 加工时间 机床 工件号码 例 某厂有 台完好机器 每台机器全年在高负荷下运行可创利 千元 在低负荷下运行可 创利 千元 机器在高 低负荷下运行一年的折损率分别为 试拟订一个五年计划使总利润 最大 西安建筑科技大学 运筹学 习题解析 第 讲 第八章 存储论 存储问题 存储问题中牵涉到的费用的相关概念 存储费 存储费用是由于对库存物资进行保管而引起的费用 货物占用资金的利息 为了 库存物资安全而向保险机构缴纳的保险金 部分库存物资损坏 变质 短缺而造成的损失 库存物资占 用仓库面积而引起的一系列费用 建立费 对于外购物资来说主要是订货费 它包括二项 一项是订货费用 固定费 用 它与订购次数有关 与订购数量无关 另一项是货物的成本费用 它与订购数量有关 可变费 用 对于自行生产的物资来说主要是生产费 这时仍需要支出两项费用 一项是装配费用 固定费 用 另一项是与生产产品的数量有关的费用 可变费用 缺货损失费 当某种物资存储量不足 不能满足需求时所造成的损失 如工厂停工待料 失 去销售机会以及不能履行合同而缴纳的罚款等 在不允许缺货的情况下 缺货费为无穷大 四种模型 四种公式的记忆规律 确定的存储模型 最佳生产间隔期 最佳生产批量 最大存储量 例 某厂每月需甲产品 件 每月生产率为 件 每批装配费用为 元 每月每件产品存贮 费用为 元 求 及最低费用 例 某商店经售甲商品成本单价 元 年存储费用为成本的 年需求量 件 需求速度 为常数 甲商品的定购费为 元 提前期为 天 求 及最低费用 例 某厂按合同每年需提供 个产品 不许缺货 假设每一周期工厂需装配费 元 存贮费 每年每单位产品为 元 问全年应分几批供货才能使装配费 存贮费两者之和最少 例 某商店拟在新年期间出售一批日历画片 每售出一千张可赢利 元 如果在新年期间不 能售出 必须削价处理 作为画片出售 由于削价 一定可以售完 此时每千张赔损 元 根据以往 的经验 市场需求的概率见表 需求 概率 每年只能订货一次 问应订购日历画片几千张才能使获利的期望值最大 例 设某公司利用塑料作原料制成产品出售 已知每箱塑料购价为 元 订购费 考试点 名师精品课程电话 元 存贮费每箱 元 缺货费每箱 元 原有存贮量 箱 已知对原料需求的概率 箱 箱 箱 箱 求该公司订购原料的最佳订购量 例 已知某产品的需求量服从正态分布 已知 又知每件产品的进价为 元 售价 为 元 存储费为 元 问该产品的订货量应为多少件才能使预期的利润最大 西安建筑科技大学 运筹学 习题解析 第 讲 第九章 排队论 排队问题 排队系统可用如下符号表示 其中 表示相继到达间隔时间的分布 表示服务时间的分布 表示服务台的个数 表示系统容量 表示顾客源数 表示服务规则 系统中并联服务台的数目 平均到达率 平均到达间隔 平均服务率 平均服务时间 服务强度 即每个服务台单位时间内的平均服务时间 一般有 稳态系统任一时刻的状态 即系统中的顾客数 顾客在稳态系统中的逗留时间 顾客在稳态系统中的等待时间 稳态系统任一时刻状态为 的概率 特别当 时 即 为稳态系统所有服 务台全部空闲的概率 描述排队系统的四个指标变量 或 平均队长 稳态系统任一时刻的顾客数的期望值 平均等待队长或队列长 稳态系统任一时刻等待服务的顾客数期望值 或 平均逗留时间 在任意时刻进入稳态系统的顾客逗留时间期望值 平均等待时间 在任意时刻进入稳态系统的顾客等待时间期望值 这四项主要性能指标 又称主要工作指标 的值越小 说明系统排队越少 等待时间越少 因而系 统性能越好 显然 它们是顾客与服务系统的管理者都很关注的 排队问题解题步骤 对于泊松输入 负指数分布服务的排队系统的一般决策过程 根据已知条件绘制状态转移速度图 转入率 转出率 考试点 名师精品课程电话 依据状态转移速度图写出各稳态概率之间的关系 求出 及 计算各项数量运行指标 用系统运行指标构造目标函数 对系统进行优化 排队问题 例 某修理店只有一个工人 每小时平均有四个顾客来修理东西 工人平均每 分钟修好一 个 若顾客到达是最简单流 服务时间是负指数分布 求这个服务系统的运行指标 例 某单位理发店内有 把椅子接待人们排队等待理发 当 把椅子都坐满顾客时 后来的顾 客就不进入理发店而离开 顾客平均到达率为 人 小时 理发时间平均 分钟 人 设顾客到达 是最简单流 服务时间服从负指数分布 求 顾客一到达就能理发的概率 系统中顾客的期望值 和排队等待的顾客的期望 顾客在理发店内逗留的全部时间的期望值 在可能到来的顾客中因客满而不等待就离开的概率 例 一个机修工负责 台机器的维修工作 设每台机器在修理之后平均可运行 天 而平均 修理一台机器的时间为 天 试求稳态下的各状态概率和各运行指标 例 一个大型露天矿山 考虑建设矿石卸位数 是建一个好 还是两个 估计矿车按普阿松流到 达 平均每小时到达 辆 卸载时间服从负指数分布 平均卸载时间是 分钟 每辆卡车的售价是 万元 建设第二个卸位的投资是 万元 例 某售票处共有三个窗口 顾客到达为普阿松流 平均速率为 人 分钟 服务 售票 时 间服从负指数分布 平均服务率为 人 分钟 试求整个售票处空闲的概率 顾客必须等待的概率及运行指标 这里假设顾客到达后排成一队 依次向空闲的窗口购 票 西安建筑科技大学 运筹学 习题解析 第 讲 第七章 目标规划 目标规划 目标规划的解 若多目标规划问题的解能使所有的目标都达到 就称该解为多目标规划的最优解 若解只能满足部分目标 就称该解为多目标规划的次优解 若找不到满足任何一个目标的解 就称该问题为无解 前面的目标可以保证实现或部分实现 而后面的目标就不一定能保证实现或部分实现 有些 可能就不能实现 就称该解为多目标规划的满意解 具有层次意义的解 例 用单纯形法求解下列目标规划问题 例 某种牌号的酒系由三种等级的酒兑制而成 已知各种等级酒的每天供应量和单位成本 如下 等级日供应量成本 商标兑制配比要求单位售价 元 红 少于 多于 黄 少于 多于 蓝 少于 多于 考试点 名师精品课程电话 该种牌号的酒有三种商标 红 黄 蓝 各种商标的混合比及售价如上表所示 为保持声誉 确定 经营目标为 兑制要求必须严格满足 企业获取尽可能多的利润 红色商标酒每天产量不低 于 单位 试对此问题建立目标规划模型 例 某彩色电视机组装工厂 生产 三种规格电视机 装配工作在同一生产线上完成 三 种产品装配时的工时消耗分别为 和 生产线每月正常工作时间为 三种规格电视机销 售后 每台可获利分别为 元 元和 元 每月销售量预计为 台 台 台 该厂经营目 标如下 利润指定为每月 元 充分利用生产能力 加班时间不超过 产量以预计销售量为标准 为确定生产划 试建立该问题的目标规划模型 例 友谊农场有 万亩农田欲种植玉米 大豆和小麦三种农作物 各种作物每亩需施化肥分别 为 预计秋后玉米每亩可收获 售价为 元 大豆每亩可收获 售 价为 元 小麦每亩可收获 售价为 元 农场年初规划时考虑如下几个方面 年终收益不低于 万元 总产量不低于 万 小麦产量以 万 为宜 大豆产量不超为 万 玉米产量不超过 万 农场现能提供 化肥 若不够 可在市场高价购买 但希望高价采购量愈少愈好 试就该农场生产计划建立数学模型 例 某公司下属三个小型煤矿厂 每天煤炭的生产量分别为 供应 四个工厂 需求量分别为 公司调运时依次考虑的目标优先级为 产地因库存限制 应尽量全部调出 因煤质要求 需求最好由 供应 满足各销地需求 调运总费用尽可能小 从煤矿至各厂调运的单位运价如下表 工厂 煤矿 西安建筑科技大学 运筹学 习题解析 第 讲 第十章 对策问题 对策问题 局中人 参与竞争的各方 可以是一个人 也可以是一个集团 可以有两方 也可以有多方 局中人 之间可以有结盟和不结盟之分 策略 指局中人用于对付其他局中人的行动方案 策略集合 一个局中人的策略全体 如只含有限个策略 则称之为有限对策 否则为无限对策 局势 在一局对策中 各局中人选定的策略构成一个策略组称为局势 收益函数 在竞争的局势中 当一个局势确定后 就决定了局中人的输赢 这个输赢的值是局势的 函数 称作收益函数 矩阵对策的模型 矩整对策 二人有限零和对策 在这样的对策中 只有两个局中人 每个局中人的策略集合中只 含有有限个策略 一个局势形成后 一个局中人的赢得值恰为另一个局中人输掉的值 即两个局中人 的得失总和为零 由于局中人的收益函数可用矩阵表示 故简称矩阵对策 设有两个局中人 和 他们的策略集合分别为 其中 称为纯策略 称为纯策略集合 如果局中人 选取纯策略 局中人 选取纯策略 就形成纯局势 这时 局中 人 得到收益 而局中人 得到收益为 考虑到各种可能出现的局势 局中人 的所得收益矩 阵 或赢得矩阵 为 矩阵对策模型可记为 例 纯策略 求解矩阵对策 甲 乙 其中 例 优超策略解决 设赢得矩阵为 求解这个矩阵对策 考试点 名师精品课程电话 例 单纯形法 石头 剪刀 布 游戏 两名儿童甲 乙玩 石头 剪刀 布 游戏 他们的策略 集合都是 石头 剪刀 布 当双方选定自己的策略后 一个局势就形成了 我们规定 赢的一方得 分 输的一方得 分 平局得 分 则在各种可能局势下 儿童甲的得分如下表所示 因为甲和乙在同 一局势下的得分之和为零 故矩阵中各元素的相反数表示儿童乙在各种局势下的得分 在这个游戏 中 双方都必须考虑对方的可能策略来决定自己的策略选择 对策问题 当局中人 采用混合策略 局中人 分别采取纯策略 时 局中人 的期望赢得分别为 依据小中取大原则 局中人 的最终期望赢 得 若令 则上式可写为 上式中的每个约束均除以 又 令 则有 西安建筑科技大学 运筹学 习题解析 同理 当局中人 采用混合策略 局中人 分别采取纯策略 时 局中人 的期望损 失分别为 依据大中取小原则 局中人 的最终期望赢得 若令 则上式可写为 和 互为对偶线性规划问题 注意 和 模型中的 和 不允许为零 故当支付矩阵 中元素有负值时 可将该矩 阵的每一个元素都加上一个常数 变换为正值 得到矩阵 可以证明矩阵对策 和 同解 且有 考试点 名师精品课程电话 第 讲 考试试题形式 判断题 在下列各题中 你认为体重描述的内容为正确者 在题尾括号内写 错误者写 图解法提供了求解线性规划问题的通用方法 用单纯形法求解一般线性规划时 当目标函数求最小值时 若所有的检验数 则问题 达到最优 在单纯形表中 基变量对应的系数矩阵往往为单位矩阵 满足线性规划问题所有约束条件的解称为基本可行解 在线性规划问题的求解过程中 基变量和非基变量的个数是固定的 对偶问题的目标函数总是与原问题目标函数相等 原问题与对偶问题是 对应的 运输问题的可行解中基变量的个数一定遵循 的规则 这牌问题的解中基变量的个数为 网络最短路径是指从网络起点至终点的一条权和最小的路线 动态规划中运用图解法的顺推方法和网络最短路径的标号法伤是一致的 名词解释 运筹学 线性规划 可行解 最优解 运输问题 闭回路 问答题 试述组成对策模型的三个基本及其含义 试述存储问题的费用分类及其含义 用符号 表示一个排队模型时 符号中各个字母的含义 试述凸函数及其严格凸函数的定义 试述如何在单纯形表上判断规划具有唯一最优解 无穷多个最优解 无界解或者无可行解 试从经济上解释对偶问题及其对偶变量的含义 西安建筑科技大学 运筹学 习题解析 填空题 线性规划问题如果没有最优解 则单纯形计算表的终点表中必然有 用分枝定界法求解纯整数规划问题的过程可以大概分为以下三步 第一步 用单纯形法求的解 如果有解且不满足纯整要求 转下步 第二步 建立并加入线性规划问题 转下步 第三步 用方法定界 确定下一个问题 然后转第一步 对偶问题的性质有 至少答三个 线性规划问题求解的优点中有 缺点有 对偶价格是指 排队问题 天大考研 某购物中心设有一个能容纳 辆轿车的停车场 设轿车的到达为一泊松流 顾客的购物 时间服从负指数分布 当轿车到达停车场时 若停车场已满 则轿车将不再等待而离去 此问题可看作何种类型的排队模型 请解释本问题中的状态概率 队长 排队长 逗留时间 和等待时间 的实际 意义 如果购物中心的经理希望知道是否需扩大停车场容量 你认为对此可怎样分析 存储问题 天大 在确定性存贮问题中 记 为订货费 为存贮费 为缺货费 为需求率 设 和 均 为常数 不需要提前订货 且一订货即可全部供货 请分别写出不允许缺货和允许缺货 缺货要补 两种条件下最佳批量相应的总费用表达式 并说明允许缺货时的费用不会超过不允许缺货时的费用 若 箱 月 元 次 元 月 允许缺货且缺货要补 元 箱 周 求 最佳订货批量及订货间隔时间 考试点 名师精品课程电话 第 讲 考试样题 一 不定项选择题 每小题 分 共 分 线性规划的标准型有特点 右端项非零 目标求最大 有等式或不等式约束 变量均非负 一个线性规划问题 与它的对偶问题 有关系 无可行解则 一定无可行解 均有可行解则都有最优解 的约束均为等式 则 的所有变量均无非负限制 若 是 的对偶问题 则 是 的对偶问题 关于动态规划问题的下列命题中 是错误的 动态规划阶段的顺序与求解过程无关 状态是由决策确定的 用逆序法求解动态规划问题的重要基础之一是最优性原理 列表法是求解某些离散变量动态规划问题的有效方法 二 判断题