《运筹学》习题集汇总资料.docx

《《运筹学》习题集汇总资料.docx》由会员分享，可在线阅读，更多相关《《运筹学》习题集汇总资料.docx（21页珍藏版）》请在三一文库上搜索。

1、第一章 线性规划11 将下述线性规划问题化成标准形式 1 min z 3x 1 4x 2 2x 3 5 x4st.4x 1 x 2 2x 3 x 4 2 x 1 x 2 x 3 2 x4 14 2x 1 3x 2 x 3 x 4 2 x， 1 x 2 ，x 3 ， 0x 4 无约束2 min z 2x 1 2x 2 3x 3 x 1 x 2 x 3 4 2x 1 x 2 x 3 6 x 1 ，x0 2 ， 0x 3 无约束st.12用图解法求解 LP 问题，并指出问题具有唯一最优解、无穷多最优解、无界解 还是无可行解。1 min z 2x 1 3x 24x 1 6x 2 6st 2x 12x

2、2 4 x， 1x 2 02 max z 3x 12x 2 2x 1x 2 2 st 3x 14x 2 12x 1， x 2 03 max z 3x 15x 2 6x 110x 2 120 st 5 x 1 103 x 2 84 max z 5x 16x 2 2x 1x 2 213 找出下述 LP 问题所有基解，指出哪些是基可行解，并确定最优解 （1） min z 5x 12x 23x 3 2x 41st 2x 13x 2 2 x， 1x 2 0x 12x 2 3x 34x 47 st 2x 12x 2x 3 2x 43x 1，x 2，x 3， x 4 014 分别用图解法与单纯形法求解下列

3、LP 问题，并对照指出最优解所对应的顶点。 1 maxz 10x 15x 23x 14x 2 9 st 5x 12x 2 8 x ，1x 2 02 maxz 2x 1 x 23x 15x 2 15 s6tx 12x 2 24x 1， x 2 015 分别用大 M 法与两阶段法求解下列 LP 问题。 1 minz 2x 13x 2x 3x 1 4x 2 2x 3 8st 3x 1 2x 2 6 x， 1x 2 ，x 3 02 max z 4x 15x 2 x 3. 3x 12x 2 x 3 18St. 2x 1 x 2 4x 1 x 2 x 3 53 maxz 5x 13x 2 +6x3 x 1

4、2x 2 x 3 18 st 2x 1x 2 3 x3 16 x 1x 2 x 310 x 1，x 2 ，x 3 04 max z =10x 1+15x 2+12x 3 ? 5x9 1+3x 2+x 3? -5x +6x +15x ?11253st . ?x 3 ?52x 1+x 2+? x , x , x ?123 01621.7某班有男生 30 人，女生 20人，周日去植树。根据经验，一天男生平均每 人挖坑 20个，或栽树 30棵，或给 25 棵树浇水；女生平均每人挖坑 10个，或栽树 20 棵，或给 15棵树浇水。问应怎样安排，才能使植树（包括挖坑、栽树、浇水） 最多？请建立此问题的线性

5、规划模型，不必求解。1.8某糖果厂用原料 A 、B 、C 加工成三种不同牌号的糖果甲、乙、丙。已知 各种牌号糖果中 A 、B 、C 含量，原料成本，各种原料的每月限制用量，三种牌 号糖果的单位加工费及售价如下表所示。问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立此问 题的线性规划的数学模型。甲 乙 丙 原料成本 ( 元/千克 每月限量(千克)A 6015 2.00 2000 B 1.50 2500 C20605加0 工1.0费0( 12元00/ 千克 0.500.40 0.30 售 价 3.40 2.85 2.251.9某商店制定 712 月进货售货计划，已知商店仓库容量不得

6、超过 500件， 6 月底已存货 200 件，以后每月初进货一次，假设各月份此商品买进售出单价如下表 所示，问各月进货售货各多少，才能使总收入最多？请建立此问题的线性规划模 型。 月 份 7 8 9 10 11 12 买进单价 28 24 25 27 23 231.10某厂接到生产 A 、B 两种产品的合同，产品 A 需 200件，产品 B 需 300 件。这两种产品的生产都经过毛坯制造与机械加工两个工艺阶段。在毛坯制造阶 段，产品 A 每件需要 2小时，产品 B 每件需要 4小时。机械加工阶段又分粗加工 和精加工两道工序，每件产品 A 需粗加工 4小时，精加工 10小时；每件产品 B 需 粗

7、加工 7 小时，精加工 12 小时。若毛坯生产阶段能力为 1700小时，粗加工设备拥 有能力为 1000 小时，精加工设备拥有能力为 3000 小时。又加工费用在毛坯、粗加 工、精加工时分别为每小时 3 元、3元、2 元。此外在粗加工阶段允许设备可进行 500 小时的加班生产，但加班生产时间内每小时增加额外成本4.,5元。试根据以上资料，为该厂制订一个成本最低的生产计划。1.11某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技 工单独完成，或由一个技工和两个力工组成的小组来完成。第二项工作可由一个技 工或一个力工单独去完成。第三项工作可由五个力工组成的小组完成，或由一个技 工领

8、着三个力工来完成。已知技工和力工每周工资分别为 100元和 80元，他们每周都工作 48小时，但他们每人实际的有效工作小时数分别为 42和 36。为完成这 三项工作任务，该公司需要每周总有效工作小时数为：第一项工作10000 小时。第二项工作 20000小时，第三项工作 30000 小时。又能招收到的工人数为技工不超过 400 人，力工不超过 800人。试建立数学模型，确定招收技工和力工各多少人。使 总的工资支出为最少 (3第二章 对偶与灵敏度分析21 写出以下线性规划问题的 DLP 1 minz 2x 12x 24x 3stx 13x 24x 3 2 2x 1 x 23x 3 3 x 14x

9、 23x 3 5 x 1，x 2 ，0x 3无 约束 x 12x 22x 3 5 x 15x 2 x 3 3 4x 17x 23x 3 8 x 无1约束， x 20， x 3 02 max z 5x 16x 23x 3st3 max z c 1x 1c 2x 2c 3x 3sta 11x 1a 12x 2a 13x 3 b 1a 21x 1a 22x 2a 23x 3 b 2 a 31x 1a 32x 2a 33x 3 b 3 x 1，x 20，0x 3无约束22 st对于给出的 LP ：minz 2x 13x 25x 36x 4 x 12x 23x 3x 4 2 2x 1x 2x 33x4

10、3x j 0 (j=1,2,3,4) 1 写出 DLP ；2 用图解法求解 DLP ；3 利用 2 )的结果及根据对偶性质写出原问题的最优解。23 对于给出 LP ： maxz x 12x 2x 3stx 1 x 2 x 3 2 x 1 x 2 x 3 1 2x 1 x 2 x 3 2 x 1，x0 2 ，0x 3 无 约束1 写出 DLP ；2 利用对偶问题性质证明原问题目标函数值 Z 124 已知 LP ： max z x 1 x 2st x 1 x 2 x 3 22x 1 x 2 x 3 1 x j 04 试根据对偶问题性质证明上述线性问题目标函数值无界。25 给出 LP ： maxz

11、2x 14x 2x 3x 4 x 1 3x 2 x 4 82x 1 x 2 6 st. x 2 x 3 x 4 6x 1 x 2 x 3 9 x j01 写出 DLP ；2 已知原问题最优解 X （ 2,2，4,0），试根据对偶理论，直接求出对偶问题 的最优解。26 用对偶单纯形法求解下列线性规划问题 1 minz 4x 112x 218x 3stx 1 3x 3 32 x22x 3 5 x j 0 （j=1,2,32 min z =5x 1+2x 2+4x 3? 3x 1+x 2+2x 3 ? 4st . ? 6x 1+3x 2+5x 3 ?1x0 , x , x ? 123027 考虑如下

12、线性规划问题minz 60x 140x 2 80x 3 3x 1 2x 2 x 3 2st4x 1 x 2 3x 3 42x 1 2x 22x 3 3 x j 01 写出 DLP ；2 用对偶单纯形法求解原问题； 3 用单纯形法求解其对偶问题； 4 对比以上两 题计算结果。28 已知 LP ：maxz 2x 1 x 2x 3 x 1 x 2 x 3 6st x 12x 2 4 x， 1x 2，x 3 01 用单纯形法求最优解2 分析当目标函数变为 maxz 2x 13x 2x 3时最优解的变化； 3 分析第 个约束条件右端系数变为 3 时最优解的变化。529 给出线性规划问题 maxz 2x

13、1 3x 2x 31/3x11/3x21/3x3 1 st 1/3x14/3x27/3x3 3 x j 01 目标函数中变量 x 3 的系数变为 6 ；2 分别确定目标函数中变量 x 1 和 x 2 的系数 C 1、 C 2 在什么范围内变动时最优解不变； 3 约束条件的右端由 1 变为 2 ； 3 32.10 某厂生产甲、乙两种产品，需要 A 、B 两种原料，生产消耗等参数如下 表（表中的消耗系数为千克 /件）。（2）原料 A 、B 的影子价格各为多少。（3）现有新产品丙，每件消耗 3千克原料 A 和4千克原料 B ，问该产品的销 售价格至少为多少时才值得投产。（4）工厂可在市场上买到原料

14、A 。工厂是否应该购买该原料以扩大生产？在 保持原问题最优基的不变的情况下，最多应购入多少？可增加多少利润？3. 5 某玩具公司分别生产三种新型玩具，每月可供量分别为1000、2000、2000件，它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预 期销售量均为 1500件，由于经营方面原因，各商店销售不同玩具的盈利额不同 , 见 下表。又知丙百货商店要求至少供应 C 玩具 1000 件，而拒绝进 A 玩具。求满足上 述条件下使总盈利额最大的供销分配方案。甲 乙 丙 可供量A 5 4 1000B 16 8 9 2000 C 12 10 11 2000第三章 运输问题31323

15、33.4 某市有三个面粉厂，他们供给三个面食加工厂所需的面粉，各面粉厂的产 量、各面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均 式于下表。假定在第 1，2和 3面食加工厂制作单位面粉食品的利润分别为 12元、 16 元和 11元，试确定使总效益最大的面粉分配计划（假定面粉厂和面食加工厂都 属于同一个主管单位）。3.5 光明仪器厂生产电脑绣花机是以产定销的。已知 1 至 6 月份各月的生产能 力、合同销量和单台电脑绣花机平均生产费用见下表：如果当月生产出来的机器当月不交货，则需要运到分厂库房， 已知上年末库 存 103 台绣花机，每台增加运输成本 0.1 万元, 每台机器每

16、月的平均仓储费、维护费为 0.2万元 在 7-8 月份销售淡季，全厂停产 1 个月，因此在 6 月份完成销售合同后还要留出 库存 80 台。加班生产机器每台增加成本 1 万元。问应如何安排 1-6 月份的生产， 可使总的生产费用（包括运输、仓储、维护）最少？3.6 设有 A 、B 、C 三个化肥厂供应 1、2、3、4 四个地区的农用化肥。假设 效果相同，有关数据如下表：试求总费用为最低的化肥调拨方案第四章 动态规划41现有天然气站 A ，需铺设管理到用气单位 E ，可以选择的设计路线如下图，B 、 C 、 D各点是中间加压站，各线路的费用如图所标注（单位：万元），试设计费用最 低的线路。 42

17、一艘货轮在 A 港装货后驶往 F 港，中途需靠港加油、加淡水三次，从 A 港到 F 港全部可能的航运路线及两港之间距离如图， F 港有 3个码头 F 1，F 2，F 3，试 求最合理停靠的码头及航线，使总路程最短。F43某公司有资金 4万元，可向 A 、B 、C 三个项目投资，已知各项目的投资回 报如下，求最大回报。4.4 某厂有 1000台机器，高负荷生产，产品年产量 S1与投入机器数 Y1 的关 系为 S18Y1，机器完好率为 0.7；低负荷生产，产品年产量 S2 与投入机器数 Y2 的关系为 S2 5Y2，机器完好率为 0.9；请制定一个五年计划，使总产量最大。4.5某厂准备连续 3个月

18、生产 A 种产品，每月初开始生产。 A 的生产成本费用 为 x 2，其中 x 是 A 产品当月的生产数量。仓库存货成本费是每月每单位为 1 元。 估计 3个月的需求量分别为 d 1100，d 2110，d 3120。现设开始时第一个月 月初存货 s 00，第三个月的月末存货 s 30。试问：每月的生产数量应是多少才 使总的生产和存货费用为最小。4.6 某公司为主要电力公司生产大型变压器，由于电力采取预订方式购买，所 以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产计划，这四个月的需求如表 1 所示。生产成本随着生产数量而变化 调试费为 4，除了调度费用外，每

19、月生产的头两台各花费为2，后两台花费为1。最大生产能力每月为 4 台，生产成本如 2 所示。表1表24.7某工厂生产三种产品，各种产品重量与利润关系如下表，现将此三种产品 运往市场出售，运输能力总重量不超过 6t ，问应运输每种产品各多少件可使总利 润最大。4.8 用动态规划方法求解2max z =4x 1+9x 2+2x 3? 2x 1+4x 2+3x 3 ? 10? x 1, x 2, x 3 0第五章 存储论51 某建筑工地每月需用水泥 800t ，每 t 定价 2000元，不可缺货。设每 t 每 月保管费率为 0.2%，每次订购费为 300 元，求最佳订购批量、经济周期与最小费 用。5

20、2 一汽车公司每年使用某种零件 150，000件，每件每年保管费 0.2元，不 允许缺货，试比较每次订购费为 1,000 元或 100元两种情况下的经济订购批量、经 济周期与最小费用。53 某拖拉机厂生产一种小型拖拉机，每月可生产 1000台，但对该拖拉机的 市场需要量为每年 4,000 台。已知每次生产的准备费用为 15,000 元，每台拖拉机每 月的存贮费为 10 元，允许缺货（缺货费为 20元/台月），求经济生产批量、经济 周期与最小费用。54 某产品每月需求量为 8件，生产准备费用为 100元，存贮费为 5元/月 件。在不允许缺货条件下，比较生产速度分别为每月 20件和 40 件两种情

21、况下的经 济生产批量、经济周期与最小费用。55 对某种电子元件每月需求量为 4,000件，每件成本为 150元，每年的存贮 费为成本的 10%，每次订购费为 500 元。求：1） 不允许缺货条件下的最优存贮策略；（2） 允许缺货（缺货费为 100 元/件年）条件下的最优存贮策略。56 某农机维修站需要购一种农机配件，其每月需要量为 150件，订购费为 每次 400 元，存贮费为 0.96元/件月，并不允许缺货。（1） 求经济订购批量、经济周期与最小费用；（2） 该厂为少占用流动资金，希望进一步降低存贮量。因此，决定使订购和 存贮总费用可以超过原最低费用的 10%，求这时的最优存贮策略。57 某

22、公司每年需电容器 15,000个，每次订购费 80元，保管费 1元/个年， 不允许缺货。若采购量少于 1000个时，每个单价为 5 元，当一次采购 1000个以上 时每个单价降为 4.9 元。求该公司的最优采购策略。58 某工厂对某种物料的年需要量为 10,000单位，每次订货费为 2,000元， 存贮费率为 20%。该物料采购单价和采购数量有关，当采购数量在 2,000 单位以下 时，单价为 100 元；当采购数量在 2,000及以上单位时，单价为 80元。求最优采 购策略。运筹学习题集 59 某制造厂在装配作业中需用一种外购件，全年需求 量为 300 万件，不允许缺 货；一次订购费为 10

23、0 元；存贮费为 0.1 元/件月。该外 购件进货单价和订购批量 Q 有关， 具体如下表，求最佳订购策略。 批量（件） 0Q10000 单价（元） 1.00 10000 Q30000 0.98 30000 Q50000 0.96 Q 50000 0.94 510 试证明： 一个允许缺货的 EOQ 模型的费用， 决不会超过一个具有 相同存贮费、 订购费、但又不允许缺货的 EOQ 模型的费用。 511 下表： 某 时装屋在某年春季欲销售某种流行时装。据估计，该时装可能的销售量见 150 0.05 160 0.1 170 0.5 180 0.3 190 0.05销 售量 r（套） 概率 P（r） 该

24、款式时装每套进价 180 元，售价 200 元。因隔季会过时，故在季末需低价抛售完，较 有把握的抛售价 为每套 120 元。问该时装屋在季度初时一次性进货多少为宜？ 第六章 6 1 排队论 某店仅有一个修理工人，顾客到达过程为 Poisson 流，平均 3 人/h，修理时间服从负 指数分布，平均需 10min。求： （1） 店内空闲的概率； （2） 有 4 个顾客的 概率； （3） 至少有 1 个顾客的概率； （4） 店内顾客的平均数； （5） 等待服务 的顾客的平均数； （6） 平均等待修理时间； （7） 一个顾客在店内逗留时间超过 15 min 的概率。 设有一单人打字室，顾客的到达为为

25、Poisson 流，平均到达时间间 隔为 20 min ，打 字时间服从负指数分布，平均为 15min。求： （1） 顾客来打字 不必等待的概率； （2） 打字室内顾客的平均数； （ 3） 顾客在打字室内的平均逗 留时间； （4） 若顾客在打字室内的平均逗留时间超过 1.25h， 则主人将考虑增加 设备及打 字员。问顾客的平均到达率为多少时，主人才会考虑这样做。 汽车按平 均 90 辆 /h 的 Poisson 流到达高速公路上的一个收费关卡， 通过关卡的平均 时间为 38s。由于驾驶人员反映等待时间太长，主管部门打算采用新装置，使汽车通过关卡的平均时间减少到平均 30s。但增加新装置只有在原

26、系统中等待的汽车平 均数超 过 5 辆和新系统中关卡的空闲时间不超过 10%时才是合算的。 根据这一要求， 分 析采用新装置是否合算。 6 2 6 3 11运筹学习题集 6.4 有一个 M/M/1/5 系统，平均服务率 10。就两种到达 率 6，15 已得到相 应的概率 pn,如下表所示，试就两种到达率分析： （1） 有效到达率和系统的服务强度； （2） 系统中顾客的平均数； （3） 系统的满员 率； （4） 服务台应从哪些方面改进工作，理由是什么？ 系统中顾客数 n 0 1 2 3 4 5 1 （ 6） pn, 0.42 0.25 0.15 0.09 0.05 0.04（ 15） pn, 0.05 0.07 0.11 0.16 0.24 0.37 12