运筹学综合练习题

《运筹学》综合练习第一章线性规划及单纯形法1、教材43页——44页题2、教材44页题3、教材45页题4、教材46页题5、教材46页题6、补充：判断下述说法是否正确·LP问题的可行域是凸集。·LP问题的基本可行解对应可行域的顶点。·LP问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。·若LP问题有两个最优解,则它一定有无穷多个最优解.·求解LP问题时,对取值无约束的自由变量，通常令,其中∶,在用单纯形法求得的最优解中,不可能同时出现.·当用两阶段法求解带有大M的LP模型时，若第一阶段的最优目标值为零，则可断言原LP模型一定有最优解。7、补充：建立模型（1）某采油区已建有n个计量站B1，B2…Bn，各站目前尚未被利用的能力为b1，b2…bn（吨液量/日）。为适应油田开发的需要，规划在该油区打m口调整井A1，A2…Am，且这些井的位置已经确定。根据预测，调整井的产量分别为a1，a2…am（吨液量/日）。考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井。按规划要求，每口井只能属于一个计量站。假定Ai到Bj的距离dij已知，试确定各调整井与计量站的关系，使新建集输管线总长度最短。（2）靠近某河流有两个化工厂(见附图)，流经第一个工厂的河流流量是每天500万立方米；在两个工厂之间有一条流量为每天200万立方米的支流。第一个工厂每天排放工业污水2万立方米；第二个工厂每天排放工业污水1.4万立方米。从第一个工厂排出的污水流到第二个工厂之前，有20%可自然净化。根据环保要求，河流中工业污水的含量不应大于%，若这两个工厂都各自处理一部分污水，第一个工厂的处理成本是1000元/万立方米，第二个工厂的处理成本是800元/万立方米。试问在满足环保要求的条件下，每厂各应处理多少污水，才能使总的污水处理费用为最小?建立线性规划模型。工厂2工厂1第二章线性规划的对偶理论与灵敏度分析1、教材77—78页，，题2、教材79—80页题：①写出其对偶问题②用单纯形法求解原问题及对偶问题③比较②中原问题及对偶问题最优解的关系，掌握当求解原问题/对偶问题后，如何辨识对偶问题/原问题的最优解3、教材80页、题4、设有LP模型如下：试用矩阵语言，描述其最优性检验条件为：5、写出二题线性规划的对偶规划（10分）6、某公司计划制造Ⅰ、Ⅱ两种家电产品，已知各制造一件时分别占用的设备A、B的台时、调试时间及每天可用的设备能力和单件产品的获利情况如下表： Ⅰ Ⅱ 每天可用能力 设备A（小时） 0 5 15 设备B（小时） 6 2 24 调试工序（小时） 1 1 5 利润（元） 2 1 ①.建立获利最大的线性规划模型并求解（可不考虑整数要求，10分）②.该公司计划推出新型号的家电产品Ⅲ，生产一件所需设备A、B及调试工序的时间分别为3、4、2小时，该产品单件获利3元，试判断且仅判断该产品是否值得生产？（10分）③.对第一问中获利最大的线性规划模型建立其对偶规划模型，并回答其最优解和说明该公司的短缺资源是哪些？（10分）第三章运输问题1、教材107页、题2、教材103页例题63、教材109页，题4、补充：一个有退化基可行解的运输问题某运输问题的运价及各产地、销地的数据如下表: B1 B2 B3 B4 供应 A1 3 11 4 5 7 A2 7 7 3 8 4 A3 1 2 10 6 9 需求 3 6 5 6 20试确定总运费最低的运输。（注意：本题存在退化的基本可行解）第四章目标规划1、“目标规划不会出现无解”的结论对否？2、用图解法及单纯形法求解教材125页题3、教材114页例3及116页例5.第五章整数规划1、判断说法是否正确：①分枝定界求解整数规划时,分枝问题的最优解不会优于原(上一级)问题的最优解.②整数规划中，割平面的构造应满足能割掉松弛问题的最优解，但不割掉原问题的可行解。2、教材154—155页，题3、教材155页，题4、教材156—157页，题5、对教材11页例1建立其整数规划模型，并用分支定界法与割平面求解。第七章动态规划1、判断结论正误①动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策②对于同一个动态规划问题，逆序法与顺序法的解不一样2、教材237页，题3、某企业有某种高效率设备3台，拟分配给所属甲、乙、丙车间，各车间得到设备后，获利情况如下表，试建立最优分配方案（20分） 工厂 获利 甲 乙 丙 设备台数 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 114、教材238页题5、某企业今有3个可供选择的投资项目，其收益所得及所需投资额如下表，由于可支配资金只有10万元，试进行项目选择。 项目编号 1 2 3 收益（万元） 4 5 6 投资额（万元） 3 4 56、石油公司所属某仪器厂按向勘探单位提供地震勘探仪器，在计划年度内各季度的合同交货量、该厂的生产能力、生产成本及成品库中的维护与保管成本数据如下表，试建立总成本最低的生产计划模型并用表上作业法求解一步。 季度 合同交货（台） 生产能力（台） 生产成本（千元/台） 保管成本（千元/台季） 1 10 25 103 2 15 35 111 3 25 30 110 4 20 10 113 第八章图与网络分析本章只考察——最短路问题与最大流问题1、教材264页例122、下图是一个交通网络，每条边（弧）的容量及一个可行流如下表所示，试求这个网络的最大流。 边 容量 边 容量 s--1 5 5 2--6 2 2 s--2 4 2 3--6 2 2 s--3 3 2 4--t 4 2 1--4 5 2 5--t 3 3 1--5 3 3 6--t 5 4 2--5 3 0 s123456t3、下图为一运输网络，试安排其流量为7的最小费用流。12345图中各边的容量及费用如下表： 边 容量 单位流费用 边 容量 单位流费用 1——2 10 4 3——2 5 2 1——3 8 1 3——4 10 3 2——4 2 6 4——5 4 2 2——5 7 1 第九章网络计划1、判断说法正误①PERT计算中，总时差是线路上的时差，可以串用，但单时差是工序的时差，不能串用②在PERT计算中，将最早节点时刻等于最迟节点时刻、且满足节点连接而成的线路是关键线路2、教材313页题3、某工程的PERT数据如下表：①画出网络图并予节点以正确的编号②计算最早、最迟节点时刻 工序 工序时间 先行工序 A 3 - B 4 A C 5 A D 7 BC E 8 BC F 9 C G 4 C H 2 DE I 3 G J 2 HI③据所画网络图填写计算下表 i j 作业代号 t es ef ls lf tf 关键工序 4、考虑由A、B、……H等八道工序组成的产品加工任务，这些工序的先后顺序和加工的时间如下表所示： 工序 紧前工序 工作时间/天 A \ 10 B \ 5 C B 3 D A、C 3 E A、C 5 F D 6 G E 5 H F、G 5要求：1、绘制所给工序的网络图；2、计算各节点的最早与最迟节点时刻；第十章排队论本章不做重点要求1、在一个随机服务系统中，当其输入过程是一普阿松流时，即有，则同一时间区间内，相继两名顾客到达的时间间隔是相互独立且服从参数为λ的负指数分布，即有说法正确否？第十一章存贮论本章记忆太多，不做重点要求1、分析建立模型不允许缺货、补充时间无限短的确定型存储模型的假设条件是：不允许缺货补充时间无限短需求是连续的且需求速率Ｒ为常数单位物资单位时间的存储费用Ｃ1是常数每次定购费Ｃ3（不考虑货款）是常数试：（１）画出存储量变化曲线　　（2）分析费用，建立总平均费用最低的订货模型（订货周期、订货量）2、参看弄懂教材362页：“模型二，允许缺货，补充时间较长”；能够根据其他模型条件，从而由模型二得到其他模型