运筹学之习题

运筹学习题

1.某商业集团公司在A1，A2，A3三地设有三个仓库，它们分别存40，20，40个单位产品，而其零售店分布在地区Bi，i=1，┅，5，他们需要的产品数量分别是25，10，20，30，15个单位，产品从Ai到Bj的每单位装运费列于下表：

B1 B2 B3 B4 B5 A1 55 30 40 50 40 A2 35 30 100 45 60 A3 40 60 95 35 30 试建立装运费最省调运方案的数学模型。 2.某饲养场所用混合饲料由n种配料组成，要求这种混合饲料必须含有m种不同的营养成分，并且每一份混合饲料中第i种营养成分的含量不能低于bj。已知每单位的第j种配料中所含第i种营养成分的量为aij，每单位的第j种配料的价格为cj。在保证营养的条件下，应如何配方，使混合饲料的费用最省。试建立这个营养问题的数学模型，然后将其化成标准形式的线性规划问题。

3.用图解法求解下列线性规划问题：

?min x1?3x2??s.t. x1?x2?20(1) ? (2)

6?x?121?? x2?2??min x1?2x2?s.t. 2x1?5x2?12??? x1?2x2?8 ? 0?x?41??? 0?x2?3 4.用单纯形法求解下列线性规划问题：

?min z?3x1?x2?x3?x4??s.t. ?2x1?2x2? x3 ?4 ? 3x? x ?x?6124?? xj?0,j?1,2,3,4??min z??2x1?x2?x3??s.t. 3x1?x2? x3?60?(1) ? x1?x2?2x3?10 (2)

? x?x? x?20123??? xj?0,j?1,2,3 5.用两阶段法求解下列问题：

?min z?2x1?4x2??s.t. 2x1?3x2?2 ? -x? x?312??? x1,x2?0?max z?3x1?4x2?2x3??s.t. x1? x2?x3? x4?30?(1) ? 3x1?6x2?x3 -2x4?0 (2)

? x ?42??? xj?0,j?1,2,3,4

6.写出下面线性规划的对偶规划：

?min 10x1?10x2?s.t. 5x1?2x2?5??? x1?4x2?3(1) ? (2)

x?3x?212?? 8x1?2x2?4??? x1,x2为自由变量?min x1?2x2?4x3??s.t. 2x1?3x2?4x3?2? ? 2x1? x2?6x3?3? x?3x?5x?5123??? x1,x2?0，x3为自由变量 7.用对偶单纯形法求解下面问题：

?min 2x1?3x2?4x3??s.t. x1?2x2? x3?3 ? 2x? x?3x?4123?? x1,x2,x3?0?8.某厂生产A，B两种产品，每件产品均要在甲，乙，丙各台设备上加工。每件第j种产品在第i台设备上加工消耗工时为aij，i=1,2,3;j=1,2.现在各台设备可用于生产这两种产品的工时分别为bi，i=1,2,3.每件第j种产品可提供利润cj，j=1,2.根据需要A，B产品的生产量不能少于kj>0件，j=1,2.而生产的A，B数量必须取整数。问如何安排生产能使该厂利润最大？试建立该问题的数学模型。

9.用分枝定界法解下述ILP问题：

?min z??11x1?4x2?max z?3x1?2x2???s.t. ?x1?2x2?4s.t. 2x?3x?14??12(1) ? (2) ? 5x1?2x2?16

2x?3x?912? 2x? x?4?12?? x,x?0,且为整数?12?? x1,x2?0，且为整数 10.用分枝定界法求解下面的混合整数线性规划问题：

?max z?3x1?2x2??s.t. 2x1?3x2?14 ? 2x?3x?912?? x,x?0,x为整数?12111.写出下述问题的数学规划模型。

将机床用来加工产品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(1)minf?x1,x2??2x12?x2??x1?x2??20x1?16x22(2)minf?x1,x2??x?x?12x212241

13.写出下列问题的K-T条件，并求出它们的K-T点。

?min ??x1?1?2??x2?1?2??22 ?s.t. x1?x2?2?0? x?1?02???min ?x1?3?2??x2?2?2?2?s.t. x12?x2?5?0(1) ? (2)

? x1?2x2?4?0? x,x?0?12 14.某人外出旅游，需将n个物品供他选择装入行李袋，但行李袋的重量不能超过w。第i件物品的重量为ai。价值为ci，求这人应装哪几件物品使总重量不超过w，但总价值最大。把这个问题看成多阶段决策问题并利用最优化原理找出递推公式。

15.有个畜牧场，每年出售部分牲畜，出售y头牲畜可获利?(y)元。留下t

头牲畜再繁殖，一年后可得到at(a>1)头牲畜。已知该畜牧场年初有x头牲畜，每年应该出售多少，留下多少，使N年后还有z头牲畜并且获得的收入总和最大。把这个问题当作多阶段决策问题，利用最优化原理找出递推公式。 16.用动态规划方法解下列非线性规划问题

2?max z?4x1?9x2?2x3?(1) ?s.t. 2x1?4x2?3x3?10 (2)

? x,x,x?0123??max z?x1?x2??????s.t. x1?x2???xn?a? x?0,i=1,2,?,ni??xn

17.用Kruskal算法求下图所示网络中的最小树.

1 1 2 7 6 3 3 4 8 5 4 2 5

18.用Dijkstra算法求下图所示有向网络中自点1到其他点的最短有向路.

19.用Ford-Fulkerson算法求下图所示有向网络中从S到T的最大流.

20.用对偶算法求下图所示有向网络中从s到t其值为3的最小费用流.

21.一汽车出租公司有三个支队,某天需供应汽车到四个目的地,其供需要求和各队到目的地之间的距离如下图所示. 距离 车队 目的地 1 2 3 A 7 1 9 2 B 11 6 15 3 C 3 0 8 5 D 2 1 5 7 供应车数 6 1 10 需要车数

22设abc,ab,bc,ac,bdef,def是六个字母组,现希望用每组中的一个字母分别表示它们,并且不回混淆,问是否可能?为什么?

23.求下图所示图的最大基数对象.

24. 求下图所示网络的最大权对象.

25.某单人到理发店，顾客到达服从最简单流，平均每小时到达3人，理发时间服从负指数分布，平均15分钟，试求

a.顾客来理发店不必等待的概率. b.理发店内顾客的平均数.

c.顾客在理发店内平均停留时间.

26．系统{N(t);t≥0}，顾客带来服从参数为λ的最简单流，但顾客发现系统人多就不愿意排队等候，顾客接受服务的决心大小用概率an表示，这一概率与系统人数成反比，an?数分布(1n?1，n表示顾客的数目。服务时间服从参数为μ的负指

????1)，试证明这系统组成生灭过程，并求出p0,pn,??,L,Lq,W,Wq. ??的最简单流。服务时间服c从参数为μ的负指数分布。另有一个M/M/c/∞系统，顾客到达服从参数为λ的

27.设有c个M/M/1/∞系统，顾客到达都是参数

最简单流，每个服务台都服从参数为μ的负指数分布，

????1，试比较这两者?的：空闲概率p0，等待概率1-p0，等待队长Lq，队长L，等待时间Wq及逗留时间。

28.某铁路局为经常油漆车厢，考虑了两个方案：方案一是设置一个手工油漆工场。年总开支为20万元(包括固定资产投资，人工费，使用费)。每节车厢油漆时间服从μ1=6(小时)的负指数分布。方案二是建立一个喷漆车间，年总开支为45万元，每节车厢的油漆时间服从μ2=3(小时)的负指数分布。设要油漆的车厢按最简单流到达，平均每小时1/8节。油漆工场常年开工(即每年开工时间为365×24=8760(小时))，每节车厢闲置的时间损失为每小时15元。问铁路局应采用哪个方案更好。

29．某单位有10部电梯，设电梯工作寿命服从负指数分布，平均工作15天，有一个修理工，修一部电梯的时间服从负指数分布，平均需时2天。求平均发生故障的电梯数及每部电梯平均停工时间。

30.某工厂欲新建一个车间，生产一种新产品。有三种方案可以选择。方案甲：从国外引进设备，固定成本800万元，每件产品的可变成本为10元；方案乙：采用一般国产自动化设备，固定成本500万元，每件产品的可变成本12元；方案丙：采用自动化较低的国产设备，固定成本300万元，每件产品的可变成本为15元。该工厂决定生产规模为每年产80万件，试确定最优生产方案。一般地，

若该厂生产规模为年产Q0万件，试讨论最优方案的选择。

31.某工厂为提高经济效益，决定研制具有现代化管理水平的经营管理信息系统，以加强市场的预测和管理决策，现有三种方案可供选择，各方案的性能和计分如下表所示。试决定最优方案。 计分 方案 方案1 方案2 方案3 性能 市场预测精度 w1?3 市场信息处理速度 w2?2 经济性 w3?1 3412 23 1 121 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?(1) ?5?0?2323642??4? (2) 2???6??1?8??0545262765???1? ?5?2?36.用线性规划方法解下面对策问题。

??12??1?2?34?1??2? ?3??37.考虑一对策，其特征函数为

V??1???4,V??2???V??3???0,V??1,2???5V??1,3???7,V??1,2,3???10,V??2,3???6

求(1)分配集. (2)核心. (3)核仁. (4)证明V???4,6?x,x?0?x?6?是稳定集. (5)Shapley值。

38.某个理事会，有5个理事，其中2个理事有否决权，通过一个提案必须有半数以上理事同意，且都不能投弃权票。通过提案得到为1，否则得到为0.求这个合作对策的核心，核仁，Shapley值，稳定集。

本文来源：https://www.bwwdw.com/article/cl35.html