运筹学之习题

1、运筹学习题.某商业集团公司在 A, A, A三地设有三个仓库，它们分别存 40, 20, 40 个单位产品，而其零售店分布在地区 B, i=1 ,5,他们需要的产品数量分别是25, 10, 20, 30, 15个单位，产品从A到B的每单位装运费列于下表：B1B2B3B5A5530405040A35301004560A4060953530试建立装运费最省调运方案的数学模型。.某饲养场所用混合饲料由n种配料组成，要求这种混合饲料必须含有 m种不同的营养成分，并且每一份混合饲料中第i种营养成分的含量不能低于bjo已 知每单位的第j种配料中所含第i种营养成分的量为a。，每单位的第j种配料 的价格为Cj

2、0在保证营养的条件下，应如何配方，使混合饲料的费用最省。试建 立这个营养问题的数学模型，然后将其化成标准形式的线性规划问题。.用图解法求解下列线性规划问题:minx1 3x2s.txminx1 3x2s.tx1 x2 206 x1 12 x2 2s.t2x1 5x2 12x1 2x2 80 x1 40 x2 34.用单纯形法求解下列线性规划问题:minz2x1x2x3s.t3x1X2x360 x1x22x310(2)x1x2x320 xj 0, j 1,2,3min z 3x1 x2 x3 x4s.t2x1 2x2x343 kx2x4 6X 0, j 1,2,3,4.用两阶段法求解下列问题:m

3、ax3x14x2 2x3s.txix2x3x4max3x14x2 2x3s.txix2x3x430 xix3 -2 x4x2xj0,j1,2,3,4minz2x14x2s.t2K3x222 c-x1x23x1 , x20.写出下面线性规划的对偶规戈U：min 10为 10 x2 TOC o 1-5 h z s.t5x12x25x14x23x13 x228 x12x24x1, x2为自由变量minx1 2x2 4x3s.t2x1 3x2 4x3 22x1x2 6x3 3x13x2x13x2X1, x20 ,5x3 5x3为自由变量7.用对偶单纯形法求解下面问题:min2x1 3x2 4 x3s.

4、tx1 s.tx1 2x2x3 32为x 3x3 4 x1,x2,x3 0.某厂生产A, B两种产品，每件产品均要在甲，乙，内各台设备上加工每件第j种产品在第i台设备上加工消耗工时为a。，i=1,2,3;j=1,2.现在各台设备可用于生产这两种产品的工时分别为bi,i=1,2,3.每件第j种产品可提供利润Cj, j=1,2.根据需要A, B产品的生产量不能少于kj0件，j=1,2.而生产的A, B数量必须取整数。问如何安排生产能使该厂利润最大试建立该问题的数学模 型。.用分枝定界法解下述ILP问题:maxs.t2z 3xmaxs.t2z 3x1 2x22x1 3x2 14x1 3x2 9x1,

5、x2 0,且为整数min z11x1 4x2s.tx1 2x2 45x1 2x2 162 x1 x2 4x1,x2 0,且为整数.用分枝定界法求解下面的混合整数线性规划问题:max z 3x1 2x2s.t 2xi 3x2 142x1 3x2 9K,x2 0,x1为整数.写出下述问题的数学规划模型将机床用来加工产品 A, 6小时可加工100箱，若用机床加工产品B, 5小时 可加工100箱。设产品A和产品B每箱占用生产场地分别是10和20个体积单位， 而生产场地（包括仓库）允许15000个体积单位的存储量。若机床每周加工时数不 超过60小时，产品A生产xi（百箱）的收益为（60-5xi）xi元，

6、产品B生产x2（百箱） 的收益为（80-4x2元，又由于收购部门的限制，产品 A的生产量每周不能超过 800箱。试制订最优的周生产计划，使机床生产获最大收益。.求以下无约束非线性规划问题的最优解：222（1）min f x，x22x1 网 x 220 x1 16x2- X22 / c 4（2） min f x，x2为 x2 12为13.写出下列问题的K-T条件，并求出它们的K-T点22minx22minx1 3x2 2s.tx2 x2 5 0 x1 2x2 4 00minxi1x21s.tx； x2 2 0 x2 1 0.某人外出旅游，需将n个物品供他选择装入行李袋，但行李袋的重量不 能超过w

7、。第i件物品的重量为a0价值为g,求这人应装哪几件物品使总重量 不超过w,但总价值最大。把这个问题看成多阶段决策问题并利用最优化原理找 出递推公式。.有个畜牧场，每年出售部分牲畜，出售 y头牲畜可获利(y)元。留下t头牲畜再繁殖，一年后可得到 at(a1)头牲畜。已知该畜牧场年初有 x头牲畜， 每年应该出售多少，留下多少，使N年后还有z头牲畜并且获得的收入总和最大。 把这个问题当作多阶段决策问题，利用最优化原理找出递推公式。.用动态规划方法解下列非线性规划问题max z 4x1 9x2 2x2max zxx2 L . xns.t2x,4x23x310(2) s.tx1x2Lxna%,x2,x3

8、 0 xi 0,i=1,2, L ,n.用Kruskal算法求下图所示网络中的最小树.用Dijkstra 算法求下图所示有向网络中自点1到其他点的最短有向路.用Ford-Fulkerson算法求下图所示有向网络中从S到T的最大流.用对偶算法求下图所示有向网络中从s到t其值为3的最小费用流.一汽车出租公司有三个支队，某天需供应汽车到四个目的地，其供需要求和各队到目的地之间的距离如下图所示车队ABCD供应车数171132621601139158510需要车数235722设abc,ab,bc,ac,bdef,def是六个字母组，现希望用每组中的一个字母分别表示它们，并且不回混淆，问是否可能为什么23

9、.求下图所示图的最大基数对象.24.24.某单人到理发店，顾客到达服从最简单流，平均每小时到达3人，理发时间服从负指数分布，平均15分钟，试求a.顾客来理发店不必等待的概率.b.理发店内顾客的平均数.c.顾客在理发店内平均停留时间.系统N(t);t 0,顾客带来服从参数为人的最简单流，但顾客发现系统人多就不愿意排队等候，顾客接受服务的决心大小用概率an表示，这一概率与系统人数成反比，ann表示顾客的数目。服务时间服从参数为小的负n 1指数分布(-1),试证明这系统组成生灭过程，并求出P0, Pn, ,L, Lq,W,Wq.设有c个M/M/1/oo系统，顾客到达都是参数 一的最简单流。服务时间服

10、 c从参数为小的负指数分布。另有一个 M/M/c/ 8系统,顾客到达服从参数为人的最简单流，每个服务台都服从参数为小的负指数分布，-1 ,试比较这两者的：空闲概率p。，等待概率1-P。，等待队长Lq,队长L,等待时间W及逗留时间。.某铁路局为经常油漆车厢，考虑了两个方案：方案一是设置一个手工油 漆工场。年总开支为20万元（包括固定资产投资，人工费，使用费）。每节车厢 油漆时间服从仙1=6（小时）的负指数分布。方案二是建立一个喷漆车间，年总开 支为45万元，每节车厢的油漆时间服从仙2=3（小时）的负指数分布。设要油漆的 车厢按最简单流到达，平均每小时1/8节。油漆工场常年开工（即每年开工时间 为

11、365X 24=8760（小时），每节车厢闲置的时间损失为每小时15元。问铁路局应采用哪个方案更好。.某单位有10部电梯，设电梯工作寿命服从负指数分布，平均工作 15 天,有一个修理工，修一部电梯的时间服从负指数分布，平均需时 2天。求平均 发生故障的电梯数及每部电梯平均停工时间。.某工厂欲新建一个车间，生产一种新产品。有三种方案可以选择。方案 甲：从国外引进设备，固定成本 800万元，每件产品的可变成本为10元；方案 乙：采用一般国产自动化设备，固定成本500万元，每件产品的可变成本12元； 方案内：采用自动化较低的国产设备，固定成本300万元，每件产品的可变成本 为15元。该工厂决定生产规

12、模为每年产 80万件，试确定最优生产方案。一般地， 若该厂生产规模为年产 Q万件，试讨论最优方案的选择。.某工厂为提高经济效益，决定研制具有现代化管理水平的经营管理信息 系统，以加强市场的预测和管理决策， 现有三种方案可供选择，各方案的性能和计分如下表所示。试决定最优方案。市场预测精度市场信息处理速度经济性方w13w22W311不 134231方案212112力杀3110.某工程队承担一座桥梁的施工任务，由于施工地区夏季多雨，需停工三个月，在停工期间该工程队可将施工机械搬走或留在原处。如搬走，一种方案是搬到附近仓库里，需花费2000元。一种是搬到较远的城里，需花费 4000元。但 当发生洪水时

13、第一种方案将受到 50000元的损失。如留在原处，一种方案是花 1500元筑一护堤，防止河水上涨发生高水位的侵袭，若不筑护堤，发生高水位 侵袭将损失10000元。如发生洪水时，则不管是否筑护堤，施工机械留在原处都 受到60000元的损失。据历史资料，该地区夏季高水位发生的概率是， 试用决策 树法找出最优方案。.某公司欲开发一个新项目。估计成功率为40% 一旦成功可获利润8000 元。如果失败，则亏损4000元。该公司若请咨询部门帮助调查，则需要咨询费 500元。在成功的情况下，咨询部门给出正确预报的概率为，在失败的情况下， 咨询部门给出正确预报概率为，问该公司是否值得求助于咨询部门的帮助该公司 是否应该开发新项目.假设甲，乙双方交战，乙方用三个师的兵力防卫一座城市， 有两条公路 可通过该城.甲方用两个师的兵力进攻这座城，可能两个师各攻一条公路，也可 能都攻同一条公路。防守方可用三个师的兵力防守一条公路，也可以用两个师防 守一条公路，用一个师防守另一条公路。哪方军队在某一条公路上的数量多，哪 方军队就控制这条公路。如果军队数量相同，则有一半机会防守方控制这条公路,半机会进攻方攻入该城。把进攻方作为局中人 1,攻下这座城市的概率作为支付，写出该问题的矩阵对策65651 4 21857565651 4 2185