应用运筹学复习卷

1 研究生应用运筹学复习试卷研究生应用运筹学复习试卷 一 问答题 1 左边图 1 能否一笔画出 为什么 2 用单纯型法求解极大化线性规划时 当检验数 j满足什 么条件时 所得解为最优解 当检验数 j满足什么条件 时 线性规划所得解为有无穷多最优解之一 3 某一求目标函数极大值线性规划用单纯形法求解得到的某一步的单纯形表如下 j c 1200 CBXBbx1x2x3x4 2 x2 3011 2 1 x1 d1022 z 400c 2 x1和 x2为非人工变量 问 1 当 c d 满足什么条件时 表中解为惟一最优解 2 当表中 a b 满足什么条件时 表中解为无穷多最优解之一 4 已知为线性规划的对偶问题的最优解 说明在最优生产计划中第 i 中资源的影子价格2 i y 等于 2 在最优生产计划中第 i 中资源是什么资源 这种资源是否耗尽 5 已知线性规划 max z 2x1 5x2 s t x1 4 2x2 12 3x1 2x2 18 x1 x2 0 的可行域 等值线和梯度如图 1 所示 求线性规划的 最优解及最优值 二 根据要求建立下列问题的数学建模 不需要求解 1 某工厂生产 三种产品 已知生产单位产品所需设备台时以及 A B 两种原材料 的消耗数据如下表 产品 设备 材料 总供给 设备使用和原材 料单价 设 备348100 台时3 元 台时 原材料 A5912210kg4 元 kg 原材料 B4810150kg6 元 kg 又 三种产品的销售价格为 80 元 120 元和 168 元 假定要求产品 的数量不少 于三种产品总数的 40 试建立使工厂利润最大的产品生产数学模型 2 某工厂要做 100 套钢架 每套用长为 2 米 1 6 米 1 4 米的钢材各一根 已知所用原料每根 长 6 米 问应如何下料 可使所用原料最省 建立数学模型 三 银鸽公司有 2 亿资金可供投资 根据市场调研 发现有 12 个值得投资的项目 每个项目只 能投资一次 每个项目的预计的收益 净现值 和所需的投资资金各不相同 这些信息在下 表中给出 单位 百万元 图 1 v1 v2 v3 v4 v5 v6 x1 x2 3x1 2x2 18 x2 6 x1 4 5 2 z x2 图 1 0 B A C D 2x1 5x2 z0 2 投资项目 123456789101112 预期收益预期收益352826303236294222304538 需要的资金需要的资金272019232528183217223529 假定投资项目选择要满足下列限制 1 投资项目 7 8 和 12 中至多选一个投资 2 投 资项目 5 6 10 选择一个投资 3 投资项目 1 2 3 4 9 和 11 中至少选两个投资 4 项目 5 和项目 11 不同时投资 5 项目 10 只有在选择项目 2 投资的前提下才能投资 6 如果选择了项目 4 或项目 6 就不选择项目 12 反之 如果选择了项目 12 就不选择 项目 4 和项目 6 试建立投资项目选择的 0 1 规划模型 使总投资收益最大 4 某工厂生产 A B 二种型号的电机 它们均需经过两道主要工序加工 二种电机生产所需的 加工时间 需要的资金 单位产品利润见下表试建立该问题的目标规划模 电机 A电机 B 每周可用时间 小时 工序一 小时 台 4 小时6 小时800 小时 工序二 小时 台 3 小时2 小时600 小时 需要的资金 元 300450 产品利润 元 台 8001200 市场每周需求 台 90110 工厂期望经营目标的各优先级为 第 1 优先权 P1 每周利润不低于 120000 元 第 2 优先权 P2 工序一每周的生产时间要充分利用 但尽量不加班 工序二生产时间要充 分利用 可适当加班 第 3 优先权 P3 两种电机应尽量满足市场的需求 按产品利润比率来确定相应的权系数 第 4 优先权 P4 资金控制在 80000 元以内 第 5 优先权 P5 工序二加班生产时间不超过 90 小时 试建立该问题的目标规划模型 5 邮局一周中每天需要不同数目的雇员 设一周每天所需要雇员数如下表 时 间所需雇员数 星期一16 人 星期二15 人 星期三16 人 星期四19 人 星期五14 人 星期六12 人 星期日18 人 又规定应聘者需连续工作五天 然后连续休息两天 每天雇员的工资为 100 元 建立邮局能 满足需求 又使聘用费用最少的每天聘用雇员数量的数学模型 6 投资者有资金 8 万元 在未来 3 年内有 4 种投资选择 第一种投资方案 3 年内每年年初购 3 买债券 于当年年末归还 并加息 8 第二种方案 第 1 年年初投资 第 2 年年末可获利 35 并将本金收回 但该项投资金额不得超过 3 万元 第 3 种方案 在第 2 年年初投资 第 3 年年末可获利 45 并将本金收回 该项投资不得超过 2 万元 第 4 种投资方案 在第 3 年年初投资 年底收回本金 并可获利 20 但该项投资金额不得超过 1 5 万元 问投资 者应如何安排他的资金 确定这些方案的投资额 使到第 3 年年末本利最大 建立数学模 型 设为第 i 年投资第 j 种投资方案的投资金额 4 3 2 1 3 2 1 jix j i 7 某工厂用 A B C 三种原料生产三种不同牌号的产品甲 乙 丙 已知各种产品中对原料 A B C 的含量要求 原料成本 原料每月可供量 三种产品的单位加工费用及售价见下 表 问该厂应如何安排每月生产 使所获利润最大 合 金 原 料 甲乙丙 原料成本 元 kg 每月可供量 kg A 55 15 42000 B32500 C 20 60 50 21200 加工费 元 kg 321 售价 元 kg 1086 8 高压容器公司制造小 中 大三种尺寸的金属容器 所用资源为金属板 劳动力和机器设备 制造一个容器所需的各种资源的数量如下表所示 不考虑固定费用 每种容器售出一只所得 的利润分别为 4 万元 5 万元 6 万元 可使用的金属板有 500 吨 劳动力有 300 人 月 机 器有 100 台 月 此外不管每种容器制造的数量是多少 都要支付一笔固定的费用 小号是 l00 万元 中号为 150 万元 大号为 200 万元 现在要制定一个生产计划 使获得的利润为 最大 资 源小号容器中号容器大号容器 金属板 t248 劳动力 人 月 234 机器设备 台 月 123 9 某公司经营一种家电产品 公司仓库可容纳库存 5000 台 在一月一日 公司已拥有库存 1000 台 并拥有资金 200 万元 据估计 一季度这种家电的进货价和销售价分别为 一月 份进价 280 元 台 销价 305 元 台 二月份进价 300 元 台 销价 320 元 台 三月份进价 290 元 台 销价 298 元 台 公司进货后 需在下月才能卖出 进货时规定 货到付款 公司希望到季末 三月末 库存不超过 2000 台 问公司应在每月进货和销货多少 经营策 略 使三个月的总的获利最大 设每月的进货量为 xi 销货量为 xj 考虑库存约束 即销 量小于库存量 资金约束 库容约束 三 计算与分析 1 已知线性规划问题 max z 2x1 2x2 s t x1 2x2 10 3x1 2x2 4 x1 x2 0 用单纯形法求最优解 2 求下列网络图从 v1到 v7的最短路和路长 v1 v2 v3 v4 v6 v5 v7 7 4 6 5 1 2 5 8 6 7 1 4 5 4 3 求下图所示网络的最大流与流量 写出最小截集 4 设某工程的工序明细表如下 工序紧前工序工序时间工序紧前工序工序时间 A 2FC D3 B 5GC D5 CA3HE2 DB2IF4 EB2 1 绘制网络图 2 计算各事项最早时间 事项最迟时间和各工序的最早开始时间 最 iTE iTL jiTES 早结束时间 最迟开始时间 最迟结束时间和总时差 并找 jiTEF jiT SL jiT FL 出关键路线 5 某企业生产一种易变质的食品 单位产品成本为 20 元 售价为 60 元 每件售出可获利 40 元 如果销售不完 就要损失 20 元 即产品报废无用 这种食品的销量预计为 10000 只 11000 只 12000 只和 13000 只 1 写出收益矩阵 分别用乐观准则和悲观准则求最优决策方案 2 具统计资料 这种食品销售量的概率如下表 销售量10000 只11000 只12000 只13000 只 概 率0 20 40 30 1 vsv7 8 9 7 9 12 5 10 11 11 5 6 v1 v2 v3 v4 v5 5 答 案 一 1 能 所有点均为偶点 2 当所有检验数 j 0 时 所得解为最优解 当所有检验数 j 0 且有一个非基变量的检验数等于零时 线性规划有无穷多最优解 3 1 当 d 0 c 0 2 d 0 c 0 4 说明在最优生产计划中第 i 中资源是稀缺资源 这种资源 已全部耗尽 5 当等值线沿着梯度正方向移动到与可行域交于 B 点时 等值线的值最大 故 B 点为最优解 B 点为方程组的解 解方程得 x1 2 x2 6 最优值 1823 6 21 2 xx x 34 z 二 建立下列问题的数学建模 1 设 三种产品的产量分别为 x1 x2和 x3 三种产品的单位利润分别 为 27 24 和 36 数学模型为 max z 27x1 24x2 36x3 s t 3x1 4x2 8x3 100 5x1 9x2 12x3 210 4x1 8x2 10 x3 150 0 6x2 0 4x1 0 4x3 0 x1 x2 x3 0 2 套裁方案为 方案 规格 12345678 2 米03022101 1 6 米20110201 1 4 米20301041 料头 米 000 20 40 60 80 41 设 xj j 1 5 8 为第 j 方案所用钢材的根数 数学模型为 min z 0 2x3 0 4 x4 0 6 x5 0 8 x6 0 4 x7 x8 s t 3x2 2x4 2 x5 x6 x8 100 2x1 x3 x4 2x6 x8 100 2x1 3x3 x5 4 x7 100 x1 x2 x3 x4 x5 x6 0 且为整数 3 数学模型为 1221 0 1 j j j xj 不不不不不 不不不不 不 max z 35x1 28x2 26x3 30 x4 32x5 36x6 29x7 42x8 22x9 30 x10 45x11 38x12 s t x7 x8 x12 1 x5 x6 x10 1 x1 x2 x3 x4 x9 x11 2 x5 x11 1 x10 x2 x4 x12 1 x6 x12 1 27x1 20 x2 19x3 23x4 25x5 28x6 18x7 32x8 17x9 22x10 35x11 29x12 200 xi i 1 2 12 等于 0 或 1 4 设生产电机 A B 的数量分别为 x1 x2 数学模型为 6 1122233454657 1211 1222 1233 144 min 23 s t 500 1200 120000 46 800 32 600 zPdP dddPddP dP d xxdd xxdd xxdd xdd 255 1266 377 12 90 110 300450 80000 90 0 0 1 7 jj xdd xxdd ddd xxddj 5 设周一 周二 周日开始工作的雇员为 x1 x2 x7 则数学模型为 min z 100 x1 x2 x3 x4 x5 x6 x7 s t x1 x4 x5 x6 x7 16 x1 x2 x5 x6 x7 15 x1 x2 x3 x6 x7 16 x1 x2 x3 x4 x7 19 x1 x2 x3 x4 x5 14 x2 x3 x4 x5 x6 12 x3 x4 x5 x6 x7 18 x1 x2 x7 0 6 设为第 i 年投资第 j 种投资方案的投资金额 数学模型为 4 3 2 1 3 2 1 jix j i 4 3 2 1 3 2 1 0 5 1 008 135 1 2 008 1 3 8 s t 2 108 1 45 1max 34 21123431 23 112321 12 1211 343123 jix x xxxx x xxx x xx xxxz ji 7 解 设 xij 表示第 i 种 甲 乙 丙 产品中含原料 j 分别用 j 1 2 3 表示原料 A B 和 C 的含量 则产品甲的产量为 x11 x12 x13 产品乙的产量为 x21 x22 x23 产品丙的产 量为 x31 x32 x33 原料 A 的用量为 x11 x21 x31 原料 B 的用量为 x12 x22 x32 原料 B 的用量为 x13 x23 x33 则数学模型为 max z 10 3 x11 x12 x13 8 2 x21 x22 x23 6 1 x31 x32 x33 4 x11 x21 x31 3 x12 x22 x32 2 x13 x23 x33 规格约束 x11 0 55 x11 x12 x13 x13 0 2 x11 x12 x13 x23 0 6 x21 x22 x23 x31 0 15 x31 x32 x33 x33 0 5 x31 x32 x33 原材料供应 x11 x21 x31 2000 x12 x22 x32 2500 x13 x23 x33 1200 xij 0 8 答案见书 P167 7 9 设每月的进货量为 销货量为 则线性规划模型为 i x i y 且为整数 资金约束 库容约束 存货约束 0 20001000 2983003202803052000000298 3202803052000000300 3052000000280 5000 1000 5000 1000 1000 1000 1000 t s 290300280298320305max 321321 332211 312113 2112 11 2211 11 22113 112 1 321321 yyyxxx xyxyxy yxyxyx yxyx yx xyxy xy xyxyy xyy y xxxyyyz 三 计算题 1 化成标准性为 max z 2x1 2x2 s t x1 2x2 x3 10 3x1 2x2 x4 4 用单纯形法计算表格如下 c j 2200 CB XB x1 x2 x3x4 右端项右端项 b 0 x3 1210105 0 x43 2014 z 22000 4x2 1 211 2 0 5 0 x4201114 z 10 10 10 最优解为 X x1 x2 x3 x4 T 0 5 0 14 T 最优值为 z 10 2 最短路为 v1 v2 v3 v5 v7 和 v1 v2 v3 v6 v5 v7 路长 r 16 3 最大流为 v F 26 4 网络图为 vs