2022年运筹学之习题 .pdf
运筹学习题1，A2，A3三地设有三个仓库，它们分别存40，20，40 个单位产品，而其零售店分布在地区 Bi，i=1， 5，他们需要的产品数量分别是25，10，20，30，15 个单位，产品从 Ai到 Bj的每单位装运费列于下表：B1B2B3B4B5A155 30 40 50 40 A235 30 100 45 60 A340 60 95 35 30 试建立装运费最省调运方案的数学模型。2.某饲养场所用混合饲料由n 种配料组成， 要求这种混合饲料必须含有m 种不同的营养成分，并且每一份混合饲料中第i 种营养成分的含量不能低于bj。已知每单位的第 j 种配料中所含第i 种营养成分的量为aij，每单位的第 j 种配料的价格为 cj。在保证营养的条件下，应如何配方，使混合饲料的费用最省。试建立这个营养问题的数学模型，然后将其化成标准形式的线性规划问题。3.用图解法求解以下线性规划问题：(1) 121212min3.206122xxstxxxx(2)12121212min2.25122843xxstxxxxxx 0 04.用单纯形法求解以下线性规划问题：(1) 123123123123min2.360210200,1,2,3jzxxxstxxxxxxxxxxj(2) 1234123124min3.22460,1,2,3,4jzxxxxstxxxxxxxj 35.用两阶段法求解以下问题：(1) 123123412342max342.30040,1,2,3,4jzxxxstxxxxxxxxxxj 36 -2(2) 12121212min24.2323,0zxxstxxxxx x -精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 7 页6.写出下面线性规划的对偶规划：(1) 121212121212min1010.52533224,xxstxxxxxxxxx x4 8为自由变量(2) 123123123123123min24.2342263355,xxxstxxxxxxxxxx xx0，为自由变量7.用对偶单纯形法求解下面问题：123123123123min234.23234,xxxstxxxxxxx x x08.某厂生产 A，B 两种产品，每件产品均要在甲，乙，丙各台设备上加工。每件第 j 种产品在第 i 台设备上加工消耗工时为aijij，j=1,2.根据需要 A，B 产品的生产量不能少于kj0 件，j=1,2.而生产的 A，B 数量必须取整数。问如何安排生产能使该厂利润最大？试建立该问题的数学模型。9.用分枝定界法解下述ILP 问题：(1) 12121212max32.23149,zxxstxxxxx x 230, 且为整数(2) 1212121212min114.245164,zxxstxxxxxxx x2 20，且为整数10.用分枝定界法求解下面的混合整数线性规划问题：121212121max32.23149,zxxstxxxxx xx 230,为整数11.写出下述问题的数学规划模型。将机床用来加工产品A，6 小时可加工 100 箱，假设用机床加工产品B，5小时可加工 100 箱。设产品 A 和产品 B 每箱占用生产场地分别是10 和 20 个体积单位，而生产场地 (包括仓库 )允许 15000 个体积单位的存储量。假设机床每周加工时数不超过 60 小时，产品 A 生产 x1(百箱)的收益为 (60-5x1)x1元，产品 B 生产 x2(百箱)的收益为 (80-4x2)x2元，又由于收购部门的限制，产品A 的生产量每周不能超过 800 箱。试制订最优的周生产计划，使机床生产获最大收益。12.求以下无约束非线性规划问题的最优解：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 7 页2221212121222412121(1)min,22016(2) min,12xxxxxxxxx xxxxff13.写出以下问题的 K-T 条件，并求出它们的K-T 点。(1) 221222121212min32.5040,xxstxxxxx x20(2) 221222122min11.2010 xxstxxx14.某人外出旅游， 需将 n 个物品供他选择装入行李袋， 但行李袋的重量不能超过 w。第 i 件物品的重量为 ai。价值为 ci，求这人应装哪几件物品使总重量不超过 w，但总价值最大。 把这个问题看成多阶段决策问题并利用最优化原理找出递推公式。15.有个畜牧场，每年出售部分牲畜，出售y 头牲畜可获利( )y元。留下t头牲畜再繁殖，一年后可得到at(a1)头牲畜。已知该畜牧场年初有x 头牲畜，每年应该出售多少，留下多少，使N 年后还有 z 头牲畜并且获得的收入总和最大。把这个问题当作多阶段决策问题，利用最优化原理找出递推公式。(1)2123123123max492.410,zxxxstxxxx xx230(2)1212max.nnizxxxstxxxax0,i=1,2,n17.用 Kruskal 算法求以下图所示网络中的最小树. 18.用 Dijkstra 算法求以下图所示有向网络中自点1 到其他点的最短有向路 . 19.用 Ford-Fulkerson算法求以下图所示有向网络中从S到 T 的最大流 . 1 1 2 7 6 3 4 8 5 4 2 5 3 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 7 页20.用对偶算法求以下图所示有向网络中从s 到 t 其值为 3 的最小费用流 . 21.一汽车出租公司有三个支队,某天需供给汽车到四个目的地,其供需要求和各队到目的地之间的距离如以下图所示. A B C D 供给车数1 7 11 3 2 6 2 1 6 0 1 1 3 9 15 8 5 10 需要车数2 3 5 7 22 设 abc,ab,bc,ac,bdef,def是六个字母组 ,现希望用每组中的一个字母分别表示它们 ,并且不回混淆 ,问是否可能 ?为什么? 23.求以下图所示图的最大基数对象. 24. 求以下图所示网络的最大权对象. 目的地距离车队精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 7 页25.某单人到理发店，顾客到达服从最简单流，平均每小时到达3 人，理发时间服从负指数分布，平均15 分钟，试求a.顾客来理发店不必等待的概率. b.理发店内顾客的平均数 . c.顾客在理发店内平均停留时间. 26系统N(t);t 0，顾客带来服从参数为的最简单流，但顾客发现系统人多就不愿意排队等候，顾客接受服务的决心大小用概率an表示，这一概率与系统人数成反比，11nan，n 表示顾客的数目。服务时间服从参数为的负指数分布(1)，试证明这系统组成生灭过程，并求出0.,nqqppL LW W系统，顾客到达都是参数c的最简单流。服务时间服从参数为的负指数分布。另有一个M/M/c/ 系统，顾客到达服从参数为的最简单流，每个服务台都服从参数为的负指数分布，1，试比较这两者的：空闲概率p0，等待概率 1-p0，等待队长 Lq，队长 L，等待时间 Wq及逗留时间。28.某铁路局为经常油漆车厢，考虑了两个方案：方案一是设置一个手工油漆工场。年总开支为20 万元(包括固定资产投资，人工费，使用费)。每节车厢油漆时间服从1=6(小时)的负指数分布。 方案二是建立一个喷漆车间， 年总开支为 45 万元，每节车厢的油漆时间服从2=3(小时)的负指数分布。设要油漆的车厢按最简单流到达，平均每小时1/8 节。油漆工场常年开工 (即每年开工时间为36524=8760(小时)，每节车厢闲置的时间损失为每小时15元。问铁路局应采用哪个方案更好。29某单位有10 部电梯，设电梯工作寿命服从负指数分布，平均工作15天，有一个修理工，修一部电梯的时间服从负指数分布，平均需时2 天。求平均发生故障的电梯数及每部电梯平均停工时间。30.某工厂欲新建一个车间，生产一种新产品。有三种方案可以选择。方案甲：从国外引进设备，固定成本800 万元，每件产品的可变成本为10 元；方案乙：采用一般国产自动化设备， 固定成本 500 万元，每件产品的可变成本12 元；方案丙：采用自动化较低的国产设备，固定成本 300 万元，每件产品的可变成本为 15 元。 该工厂决定生产规模为每年产80 万件，试确定最优生产方案。 一般地，假设该厂生产规模为年产Q0万件，试讨论最优方案的选择。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 7 页31.某工厂为提高经济效益，决定研制具有现代化管理水平的经营管理信息系统，以加强市场的预测和管理决策，现有三种方案可供选择， 各方案的性能和计分如下表所示。试决定最优方案。市场预测精度市场信息处理速度经济性13w22w31w方案134231 方案2 121 12方案3 1 1 0 32.某工程队承担一座桥梁的施工任务，由于施工地区夏季多雨，需停工三个月，在停工期间该工程队可将施工机械搬走或留在原处。如搬走，一种方案是搬到附近仓库里，需花费2000 元。一种是搬到较远的城里，需花费4000元。但当发生洪水时第一种方案将受到50000 元的损失。如留在原处，一种方案是花1500 元筑一护堤，防止河水上涨发生高水位的侵袭，假设不筑护堤，发生高水位侵袭将损失 10000 元。如发生洪水时， 则不管是否筑护堤， 施工机械留在原处都受到 60000元的损失。 据历史资料， 该地区夏季高水位发生的概率是0.02，试用决策树法找出最优方案。33.某公司欲开发一个新项目。 估计成功率为 40%，一旦成功可获利润8000元。如果失败，则亏损4000 元。该公司假设请咨询部门帮助调查，则需要咨询费 500 元。在成功的情况下，咨询部门给出正确预报的概率为0.8，在失败的情况下，咨询部门给出正确预报概率为0.6，问该公司是否值得求助于咨询部门的帮助？该公司是否应该开发新项目？34.假设甲，乙双方交战，乙方用三个师的兵力防卫一座城市，有两条公路可通过该城 .甲方用两个师的兵力进攻这座城，可能两个师各攻一条公路，也可能都攻同一条公路。 防守方可用三个师的兵力防守一条公路，也可以用两个师防守一条公路， 用一个师防守另一条公路。 哪方军队在某一条公路上的数量多，哪方军队就控制这条公路。 如果军队数量相同，则有一半时机防守方控制这条公路，一半时机进攻方攻入该城。把进攻方作为局中人1，攻下这座城市的概率作为支付，写出该问题的矩阵对策。35.求以下矩阵对策的最稳妥策略。(1) 123253640242(2)656514218575026236.用线性规划方法解下面对策问题。12112234337.考虑一对策，其特征函数为性能计分方案精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 7 页14,230,1,251,37,1,2,310,2,36VVVVVVV求(1)分配集 . (2)核心. (3)核仁. (4)证明4,6,06Vx xx是稳定集 . (5)Shapley值。38.某个理事会，有 5 个理事，其中 2 个理事有否决权，通过一个提案必须有半数以上理事同意，且都不能投弃权票。通过提案得到为1，否则得到为0.求这个合作对策的核心，核仁，Shapley值，稳定集。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 7 页
