运筹学综合练习题

1、综 合 练 习 题第一章线性规划及单纯形法1、教材43页44页1.1题2、教材44页1.4题3、教材45页1.8题4、教材46页1.13题5、教材46页1.14题6、补充：判断下述说法是否正确LP问题的可行域是凸集.LP问题的根本可行解对应可行域的顶点.LP问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解.假设LP问题有两个最优解,那么它一定有无穷多个最优解Ffrf求解LP问题时,对取值无约束的自由变量,通常令Xj=Xj - Xj淇中：Xj Xj 0在用单纯形法求彳#的最优解中,不可能同时出现 Xj Xj M0.当用两阶段法求解带有大M的LP模型时,假设第一阶段的最优目标函数值为零,

2、那么可断言原LP模型一定有最优解.7、补充：建立模型1某采油区已建有 n个计量站B1,B2 - Bn,各站目前尚未被利用的水平为b1, b2-bn 吨7近量/日为适应油田开发的需要,规划在该油区打m 口调整井A1, A2Am,且这些井的位置已经确定.根据预测,调整井的产量分别为为,a2am 吨液量/日.考虑到原有计量站充裕的水平,决定不另建新站,而用原有老站分工管辖调整井.按规划要求,每口井只能属于一个计量站.假定Ai到Bj的距离dij,试确定各调整井与计量站的关系,使新建集输管线总长度最短.2靠近某河流有两个化工厂 见附图,流经第一个工厂的河流流量是每天500万立方米；在两个工厂之间有一条流

3、量为每天200万立方米的支流.第一个工厂每天排放工业污水2万立方米；第二个工厂每天排放工业污水1.4万立方米.从第一个工厂排出的污水流到第二个工厂之前,有20%可自然净化.根据环保要求,河流中工业污水的含量不应大于0.2%,假设这两个工厂都各自处理一局部污水,第一个工厂的处理本钱是1000元/万立方米,第二个工厂的处理本钱是800元/万立方米.试问在满足环保要求的条件下,每厂各应处理多少污水,才能使总的污水处理费用为最小？建立线性规划模型.1、教材 7778 页 2.1, 2.2, 2.3 题2、教材79 80页2.10题:写出其对偶问题用单纯形法求解原问题及对偶问题比拟中原问题及对偶问题最优

4、解的关系,掌握当求解原问题/对偶问题后,如何辨识对偶问题/原问题的最优解3、教材 80 页 2.12、2.14 题4、设有LP模型如下：C -CbB JA 0试用矩阵语言,描述其最优性检验条件为：-CbB05、写出二题线性规划的对偶规划10分A、B的台时、调试时间及6、某公司方案制造I、n两种家电产品,各制造一件时分别占用的设备每天可用的设备水平和单件产品的获利情况如下表:In每大可用水平设备A 小时0515设备B 小时6224调试工序小时115利润元21.建立获利最大的线性规划模型并求解可不考虑整数要求,10分.该公司方案推出新型号的家电产品田,生产一件所需设备A、B及调试工序的时间分别为3

5、、4、2小时,该产品单件获利 3元,试判断且仅判断该产品是否值得生产？ 10分并答复其最优解和说明该公司的短缺资源.对第一问中获利最大的线性规划模型建立其对偶规划模型,是哪些？ 10分第三章运输问题1、教材107页3.1、3.5题2、教材103页例题63、教材 109 页 3.10, 3.11 题4、补充：一个有退化基可行解的运输问题某运输问题的运价及各产地、销地的数据如下表B1B2B3B4供给A1311457A277384A3121069需求365620试确定总运费最低的运输方案.注意：此题存在退化的根本可行解第四章目标规划1、“目标规划不会出现无解的结论对否？2、用图解法及单纯形法求解教材

6、125页4.2题3、教材114页例3及116页例5.第五章整数规划1、判断说法是否正确：分枝定界求解整数规划时,分枝问题的最优解不会优于原上一级问题的最优解.整数规划中,割平面的构造应满足能割掉松弛问题的最优解,但不割掉原问题的可行解.2、教材 154155 页 5.4, 5.5 题3、教材155页5.6, 5.7题4、教材 156157 页 5.13, 5.14 题5、对教材11页例1建立其整数规划模型,并用分支定界法与割平面求解.第七章动态规划1、判断结论正误动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策对于同一个动态规划问题,逆序法与顺序法的解不一样2、教材 2

7、37页7.1 , 7.2题3、某企业有某种高效率设备3台,拟分配给所属甲、乙、丙车间,各车间得到设备后,获利情况如下表,试建立最优分配方案20分设备台数甲乙丙00001354271063911114、教材238页7.6题5、某企业今有3个可供选择的投资工程,其收益所得及所需投资额如下表,由于可支配资金只有10万元,试进行工程选择.工程编号123收益万元456投资额力兀3456、石油公司所属某仪器厂按合同向勘探单位提供地震勘探仪器,在方案年度内各季度的合同交货量、该厂的生产水平、生产本钱及成品库中的维护与保管本钱数据如下表,试建立总本钱最低的生产方案模型 并用表上作业法求解一步季度合同交货台生产

8、水平台生厂本钱千元/台保管本钱千元/台季110251031.5215351111.5325301101.5420101131.5第八章图与网络分析本章只考察一一最短路问题与最大流问题1、教材264页例122、下列图是一个交通网络,每条边弧的容量及一个可行流如下表所示,试求这个网络的最大流.边容量边容量S-1552-622S-2423-622S-3324-t421-4525-t331-5336-t542-530图中各边的容量及费用如下表:边容量单位流费用边容量单位流费用1210432521381341032426454225712第九章网络方案1、判断说法正误PERT计算中,总时差是线路上的时差

9、,可以串用,但单时差是工序的时差,不能串用在PERT计算中,将最早节点时刻等于最迟节点时刻、且满足tLj-ti, j-tEi 二节点连接而成的线路是关键线路2、教材313页9.2题3、某工程的PERT数据如下表：画出网络图并予节点以正确的编号计算最早、最迟节点时刻工序工序时间先行工序A3-B4AC5AD7B CE8B CF9CG4CH2D EI3GJ2H I据所画网络图填写计算下表ij作业代号teseflslftf关键工序4、考虑由A、B、H等八道工序组成的产品加工任务,这些工序的先后顺序和加工的时间如下表所示：工序紧前工序工作时间/天A10B5CB3DA、C3EA、C5FD6GE5HF、G5要求:1、绘制所给工序的网络图；2、计算各节点的最早与最迟节点时刻；第十章排队论本章不做重点要求P(N(t )= n=)e?1、在一个随机效劳系统中,当其输入过程是一普阿松流时,即有n! ,那么同一时间区间内,相继两名顾客到达的时间间隔是相互独立且服从参数为人的负指数分布,即有 p(X =.=也说法正确否？第H一章存贮论本章公式记忆太多,不做重点要求1、分析建立模型不允许缺货、补充时间无限短确实定型存储模型的假设条件是：不允许