《运筹学》习题集

第一章 线性规划 11 将下述线性规划问题化成标准形式 1) min z 3x 1 4x2 2x3 5 x4 4x 1 x2 2x3 x 4 2 st. x1 x2 x3 2 x4 14 2x 1 3x2 x3 x4 2 x1 ，x 2 ，x 3 0，x 4 无约束 2) min z 2x1 2x 2 3x 3 x1 x2 x3 4 st. 2x 1 x2 x3 6 x10 ，x 2 0，x 3 无约束 12 用图解法求解 LP 问题，并指出问题具有唯一最优解、无穷多最优解、无界解还 是无可行解。 1) minz2x 13x 2 4x16x 26 st 2x 12x 24 x1，x 20 2) maxz3x 12x 2 2x1x 22 st 3x 14x 212 x1，x 20 3) maxz3x 15x 2 6x110x 2120 st 5x 110 3x 28 4) maxz5x 16x 2 2x1x 22 st 2x 13x 22 x1，x 20 13 找出下述 LP 问题所有基解，指出哪些是基可行解，并确定最优解 （1）minz5x 12x 23x 32x 4 x12x 23x 34x 47 st 2x 12x 2x 3 2x43 x1，x 2，x 3，x 40 14 分别用图解法与单纯形法求解下列 LP 问题，并对照指出最优解所对应的顶点。 1) maxz10x 15x 2 3x14x 29 st 5x12x 28 x1，x 20 2) maxz2x 1x 2 3x15x 215 st 6x 12x 224 x1，x 20 15 分别用大 M 法与两阶段法求解下列 LP 问题。 1) minz2x 13x 2x 3 x14x 22x 38 st 3x 12x 2 6 x1，x 2 ，x 30 2) max z 4x1 5x2 x3 . 3x1 2x2 x3 18 St. 2x1 x2 4 x1 x2 x3 5 3) maxz 5x13x 2 +6x3 x12x 2 x 3 18 st 2x1x 2 3 x 3 16 x1x 2 x 310 x1，x 2 ，x 30 1231231234)ma05596.,0zxxst 16 求下表中 a l 的值。 cj （a ） 1 2 0 0 CB XB b x1 x2 x3 x4 x5 0 x4 6 （b） （c ） （d） 1 0 0 x5 1 -1 3 （e ） 0 1 j （a ） -1 2 0 0 （a） x1 （f） （g） 2 -1 1/2 0 0 x5 4 （h） （I） 1 1/2 1 运筹学习题集 - 3 - cj （a） 1 2 0 0 CB XB b x1 x2 x3 x4 x5 j 0 -7 （j） （k） （l） 1.7 某班有男生 30 人，女生 20 人，周日去植树。根据经验，一天男生平均每人挖坑 20 个， 或栽树 30 棵，或给 25 棵树浇水；女生平均每人挖坑 10 个，或栽树 20 棵，或给 15 棵树浇 水。问应怎样安排，才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线性规 划模型，不必求解。 1.8 某糖果厂用原料 A、B、C 加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果 中 A、B、C 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及 售价如下表所示。 问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立此问题的线 性规划的数学模型。 甲 乙 丙 原料成本(元/千克) 每月限量（千克） A 60 15 2.00 2000 B 1.50 2500 C 20 60 50 1.00 1200 加工费（元/千克） 0.50 0.40 0.30 售 价 3.40 2.85 2.25 1.9 某商店制定 712 月进货售货计划，已知商店仓库容量不得超过 500 件，6 月底已存货 200 件，以后每月初进货一次，假设各月份此商品买进售出单价如下表所示，问各月进货 售货各多少，才能使总收入最多？请建立此问题的线性规划模型。 月 份 7 8 9 10 11 12 买进单价 28 24 25 27 23 23 售出单价 29 24 26 28 22 25 1.10 某厂接到生产 A、B 两种产品的合同，产品 A 需 200 件，产品 B 需 300 件。这两种产 品的生产都经过毛坯制造与机械加工两个工艺阶段。在毛坯制造阶段，产品 A 每件需要 2 小时，产品 B 每件需要 4 小时。机械加工阶段又分粗加工和精加工两道工序，每件产品 A 需粗加工 4 小时，精加工 10 小时；每件产品 B 需粗加工 7 小时，精加工 12 小时。若毛坯 生产阶段能力为 1700 小时，粗加工设备拥有能力为 1000 小时，精加工设备拥有能力为 3000 小时。又加工费用在毛坯、粗加工、精加工时分别为每小时 3 元、3 元、2 元。此外 在粗加工阶段允许设备可进行 500 小时的加班生产，但加班生产时间内每小时增加额外成 本 4.,5 元。试根据以上资料，为该厂制订一个成本最低的生产计划。 1.11 某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技工单独完成， 或由一个技工和两个力工组成的小组来完成。第二项工作可由一个技工或一个力工单独去 完成。第三项工作可由五个力工组成的小组完成，或由一个技工领着三个力工来完成。已 知技工和力工每周工资分别为 100 元和 80 元，他们每周都工作 48 小时，但他们每人实际 的有效工作小时数分别为 42 和 36。为完成这三项工作任务，该公司需要每周总有效工作 小时数为：第一项工作 10000 小时。第二项工作 20000 小时，第三项工作 30000 小时。又 能招收到的工人数为技工不超过 400 人，力工不超过 800 人。试建立数学模型，确定招收 技工和力工各多少人。使总的工资支出为最少( 第二章 对偶与灵敏度分析 21 写出以下线性规划问题的 DLP 1) minz2x 12x 24x 3 x 13x 24x 3 2 st 2x1 x23x 3 3 x 14x 23x 3 5 x1，x 20，x 3 无约束 2) maxz5x 16x 23x 3 x 12x 22x 3 5 st x 15x 2 x3 3 4x17x 23x 3 8 x1 无约束，x 20，x 30 3) maxzc 1x1c 2x2c 3x3 a11x1a 12x2a 13x3 b 1 st a21x1a 22x2a 23x3 b 2 a31x1a 32x2a 33x3 b 3 x10，x 20，x 3 无约束 22 对于给出的 LP： minz 2x13x 25x 36x 4 x 12x 23x 3x 4 2 st 2x 1x 2x 33x 4 3 x j0 （j=1,2,3,4） 1) 写出 DLP； 2) 用图解法求解 DLP； 3) 利用 2）的结果及根据对偶性质写出原问题的最优解。 23 对于给出 LP： maxzx 12x 2x 3 x 1 x 2 x 3 2 st x 1 x 2 x 3 1 2x1 x 2 x 3 2 x10， x20，x 3 无约束 1) 写出 DLP； 2) 利用对偶问题性质证明原问题目标函数值 Z1 24 已知 LP： maxzx 1x 2 x 1 x 2 x 3 2 st 2x 1 x2 x 3 1 x j0 运筹学习题集 - 5 - 试根据对偶问题性质证明上述线性问题目标函数值无界。 25 给出 LP： maxz2x 14x 2x 3x 4 x 1 3x2 x 4 8 2x1 x2 6 st. x 2 x 3 x46 x1 x2 x 3 9 xj0 1) 写出 DLP； 2) 已知原问题最优解 X（ 2,2，4,0） ，试根据对偶理论，直接求出对偶问题的最优 解。 26 用对偶单纯形法求解下列线性规划问题 1) minz4x 112x 218x 3 x1 3x 3 3 st 2 x 22x 3 5 x j0 (j=1,2,3)123231)min54.60,zxstx 27 考虑如下线性规划问题 minz60x 140x 280x 3 3x12x 2 x3 2 st 4x1 x23x 3 4 2x12x 22x 3 3 x j0 1) 写出 DLP； 2) 用对偶单纯形法求解原问题； 3) 用单纯形法求解其对偶问题； 4) 对比以上两题计算结果。 28 已知 LP：maxz2x 1x 2x 3 x1 x2 x36 st x 12x 2 4 x1，x 2，x 30 1) 用单纯形法求最优解 2) 分析当目标函数变为 maxz2x 13x 2x 3 时最优解的变化； 3) 分析第一个约束条件右端系数变为 3 时最优解的变化。 29 给出线性规划问题 maxz2x 13x 2x 3 1/3x1 1/3x21/3x 31 st 1/3x1 4/3x27/3x 33 xj0 用单纯形法求解得最终单纯形表如下 cj 2 3 1 0 0 CB XB B x1 x2 x3 x4 X5 2 x1 1 1 0 1 4 1 3 x2 2 0 1 2 1 1 j 0 0 3 5 1 试分析下列各种条件下，最优解（基）的变化： 1) 目标函数中变量 x3 的系数变为 6； 2) 分别确定目标函数中变量 x1 和 x2 的系数 C1、C 2 在什么范围内变动时最优解不变； 3) 约束条件的右端由 1 变为 2 ； 3 3 2.10 某厂生产甲、乙两种产品，需要 A、B 两种原料，生产消耗等参数如下表（表中的消 耗系数为千克/件） 。 产品原料 甲 乙 可用量（千克） 原料成本（元/千克） A 2 4 160 1.0 B 3 2 180 2.0 销售价（元） 13 16 （1）请构造数学模型使该厂利润最大，并求解。 （2）原料 A、B 的影子价格各为多少。 （3）现有新产品丙，每件消耗 3 千克原料 A 和 4 千克原料 B，问该产品的销售价格 至少为多少时才值得投产。 （4）工厂可在市场上买到原料 A。工厂是否应该购买该原料以扩大生产？在保持原问 题最优基的不变的情况下，最多应购入多少？可增加多少利润？ 3.5 某玩具公司分别生产三种新型玩具，每月可供量分别为 1000、2000、2000 件， 它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均 为 1500 件，由于经营方面原因，各商店销售不同玩具的盈利额不同,见下表。又知丙百货 商店要求至少供应 C 玩具 1000 件，而拒绝进 A 玩具。求满足上述条件下使总盈利额最大 的供销分配方案。 甲 乙 丙 可供量 A 5 4 1000 B 16 8 9 2000 C 12 10 11 2000 运筹学习题集 - 7 - 第三章 运输问题 31 根据下表，用表上作业法求最优解。 B1 B2 B3 B4 产量 A1 4 1 4 6 8 A2 1 2 5 0 8 A3 3 7 5 1 4 销量 6 5 6 3 20 32 根据下表，用表上作业法求最优解。 B1 B2 B3 B4 产量 A1 9 3 8 7 3 A2 4 9 4 5 3 A3 5 7 6 2 5 销量 1 3 2 5 11 33 求给出的产销不平衡问题的最优解 B1 B2 B3 B4 产量 A1 5 12 3 4 8 A2 11 8 5 9 5 A3 9 7 1 5 9 销量 4 3 5 6 3.4 某市有三个面粉厂，他们供给三个面食加工厂所需的面粉，各面粉厂的产量、各面食 加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均式于下表。假定在 第 1，2 和 3 面食加工厂制作单位面粉食品的利润分别为 12 元、16 元和 11 元，试确定使 总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位） 。 食品厂 面粉厂 1 2 3 面粉厂产值 1 2 3 3 4 8 10 11 11 2 8 4 20 30 20 销量 15 25 20 3.5 光明仪器厂生产电脑绣花机是以产定销的。已知 1 至 6 月份各月的生产能力、合同销 量和单台电脑绣花机平均生产费用见下表： 正 常 生 产 能 力 （ 台 ） 加 班 生 产 能 力 （ 台 ） 销 量 （ 台 ） 单 台 费 用 （ 万 元 ） 1月 份 60 10 104 15 2月 份 5 75 4 3月 份 90 20 1 13.5 4月 份 1 4 60 5月 份 0 0 13 13 6月 份 8 4 70 .5 已知上年末库存 103 台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库 房，每台增加运输成本 0.1 万元,每台机器每月的平均仓储费、维护费为 0.2 万元。在 7-8 月份销售淡季，全厂停产 1 个月，因此在 6 月份完成销售合同后还要留出库存 80 台。加班 生产机器每台增加成本 1 万元。问应如何安排 1-6 月份的生产，可使总的生产费用（包括 运输、仓储、维护）最少？ 3.6 设有 A、B、C 三个化肥厂供应 1、2、3、4 四个地区的农用化肥。假设效果相同，有 关数据如下表： 试求总费用为最低的化肥调拨方案 1 2 3 4 产 量 A 6 13 2 17 50 B 14 19 5 6 C 9 20 23 - 50 最 低 需 要 量 30 7 0 10 最 高 需 要 量 5 0 3 不 限 运筹学习题集 - 9 - 第四章 排队论 4.1 某店仅有一个修理工人，顾客到达过程为 Poisson 流，平均 3 人/h ，修理时间服从负指 数分布，平均需 10min。求： （1） 店内空闲的概率； （2） 有 4 个顾客的概率； （3） 至少有 1 个顾客的概率； （4） 店内顾客的平均数； （5） 等待服务的顾客的平均数； （6） 平均等待修理时间； （7） 一个顾客在店内逗留时间超过 15 min 的概率。 4.2 设有一单人打字室，顾客的到达为为 Poisson 流，平均到达时间间隔为 20 min ，打字 时间服从负指数分布，平均为 15min。求： （1） 顾客来打字不必等待的概率； （2） 打字室内顾客的平均数； （3） 顾客在打字室内的平均逗留时间； （4） 若顾客在打字室内的平均逗留时间超过 1.25h，则主人将考虑增加设备及 打字员。问顾客的平均到达率为多少时，主人才会考虑这样做。 4.3 汽车按平均 90 辆/h 的 Poisson 流到达高速公路上的一个收费关卡，通过关卡的平均时 间为 38s。由于驾驶人员反映等待时间太长，主管部门打算采用新装置，使汽车通过关卡 的平均时间减少到平均 30s。但增加新装置只有在原系统中等待的汽车平均数超过 5 辆和 新系统中关卡的空闲时间不超过 10%时才是合算的。根据这一要求，分析采用新装置是否 合算。 4.4 有一个 M/M/1/5 系统，平均服务率 10。就两种到达率 6，15 已得到相 应的概率 pn,如下表所示，试就两种到达率分析： （1） 有效到达率和系统的服务强度； （2） 系统中顾客的平均数； （3） 系统的满员率； （4） 服务台应从哪些方面改进工作，理由是什么？ 系统中顾客数 n （6） pn, （15） pn, 0 1 2 3 0.42 0.25 0.15 0.09 0.05 0.07 0.11 0.16 4 5 0.05 0.04 0.24 0.37 第五章 动态规划 51 现有天然气站 A，需铺设管理到用气单位 E，可以选择的设计路线如下图， B、C、D 各点是中间加压站，各线路的费用如图所标注（单位：万元） ，试设计费用最低的 线路。 5.2 一艘货轮在 A 港装货后驶往 F 港，中途需靠港加油、加淡水三次，从 A 港到 F 港全部 可能的航运路线及两港之间距离如图，F 港有 3 个码头 F1，F 2，F 3，试求最合理停靠的码 头及航线，使总路程最短。 5.3 某公司有资金 4 万元，可向 A、B、C 三个项目投资，已知各项目的投资回报如下，求 最大回报。 项目 投资额及收益 7 1 3 4 7 5 1 4 7 10 5 15 13 1 2 A B1 1 B2 C1 1 C2 C3B3 D1 D2 E5 10 6 40 30 50 25 50 60 30 20 40 30 20 30 60 45 50 A B1 1 B2 C1 1 C2 C3 D1 F1 D2 40 30 F2 F3 F 运筹学习题集 - 11 - 0 1 2 3 4 A 0 41 48 60 66 B 0 42 50 60 66 C 0 64 68 78 76 5.4 某厂有 1000 台机器，高负荷生产，产品年产量 S1 与投入机器数 Y1 的关系为 S18Y1，机器完好率为 0.7；低负荷生产，产品年产量 S2 与投入机器数 Y2 的关系为 S25Y2，机器完好率为 0.9；请制定一个五年计划，使总产量最大。 5.5 某厂准备连续 3 个月生产 A 种产品，每月初开始生产。A 的生产成本费用为 x2，其中 x 是 A 产品当月的生产数量。仓库存货成本费是每月每单位为 1 元。估计 3 个月的需求量 分别为 d1 100， d2 110， d3 120。现设开始时第一个月月初存货 s00，第三个月的月 末存货 s3 0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 5.6 某公司为主要电力公司生产大型变压器，由于电力采取预订方式购买，所以该公司可 以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产计划， 这四个月的需求如表 1 所示。生产成本随着生产数量而变化。调试费为 4，除了调度费用 外，每月生产的头两台各花费为 2，后两台花费为 1。最大生产能力每月为 4 台，生产成本 如 2 所示。 表 1 表 2 5.7 某工厂生产三种产品，各种产品重量与利润关系如下表，现将此三种产品运往市场出售， 运输能力总重量不超过 6t，问应运输每种产品各多少件可使总利润最大。 产品 重量（t/ 件） 利润（千元/件） 1 2 80 2 3 130 3 4 180 5.8 用动态规划方法求解 213213max490,zx 第六章 存储论 6.1 某建筑工地每月需用水泥 800t，每 t 定价 2000 元，不可缺货。设每 t 每月保管费率 为 0.2%，每次订购费为 300 元，求最佳订购批量、经济周期与最小费用。 6.2 一汽车公司每年使用某种零件 150，000 件，每件每年保管费 0.2 元，不允许缺货， 试比较每次订购费为 1,000 元或 100 元两种情况下的经济订购批量、经济周期与最小费 用。 6.3 某拖拉机厂生产一种小型拖拉机，每月可生产 1000 台，但对该拖拉机的市场需要量 为每年 4,000 台。已知每次生产的准备费用为 15,000 元，每台拖拉机每月的存贮费 为 10 元，允许缺货（缺货费为 20 元/台月） ，求经济生产批量、经济周期与最小费用。 6.4 某产品每月需求量为 8 件，生产准备费用为 100 元，存贮费为 5 元/月件。在不允许 缺货条件下，比较生产速度分别为每月 20 件和 40 件两种情况下的经济生产批量、经济 周期与最小费用。 6.5 对某种电子元件每月需求量为 4,000 件，每件成本为 150 元，每年的存贮费为成本的 10%，每次订购费为 500 元。求： （1） 不允许缺货条件下