运筹学试题库(试卷3).doc

《运筹学试题库(试卷3).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学试题库（试卷3）一、填空题：（10分）1、在图论中，图的基本要素有两个，它们是和。2、结点的最早开始时间和时间是同一时间，最早开始是对结点的后接工序而言，是对结点的紧前工序而言。3、对需要量供应量的运输问题，求最优解时要先一个供应点。4、关键路线是从起点到终点所有路中的最路，它的线路时差为。5、在图论中，为了表示两个队比赛的胜负关系可以用一条带的来表示。二、选择题（10分）1、若T是图G的最小支撑树，则（）A．T必唯一B.G不一定是连通图C．T中必不含圈D.G中不含圈3、在网络计划中，进行时间与成

2、本优化时，随工期延长，间接费用将（）。A．减少B.增加C.不变D.不易估计4、若线性规划问题的最优解在可行域的两个顶点达到，则最优解（）。A．有两个B.有无穷多个C.过这两点的直线D.不可能发生5、在n个产地，m个销地的产销平衡运输问题中，（）是错误的。A．运输问题是线性规划问题B．基变量的个数是数字格的个数C．空格有mn-n-m+1个D．每一格在运输图中均有一闭合回路三、判断题（10分）1、用单纯形法求解标准型式的线性规划问题时，与>0对应的变量都可以被选作换入变量。（）2、对偶问题的对偶一定是原问题

3、。（）3、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。（）4、指派问题效率矩阵地每个元素都乘以同意常数k，将不影响最优指派方案。（）5、求网络最大流的问题可归结为求解一个线性规划模型。（）四、规划问题（16分）已知线性规划问题（1）写出其对偶问题；（2）用图解法求对偶问题的解；（3）利用（2）的结果及对偶性质求原问题解。五、运输问题（10分）某土石方从三个产地运往四个工地，产地的产量、工地的需求量及单位运费如下表，求最优运输方案。产地销地B1B2B3B4

4、产量A13113107A219284A3741059销量3656一、支撑树问题（6分）求下面网络图的最小支撑树：二、指派问题（10分）分配甲、乙、丙、丁、戊五人去完成五项工作，每人完成一项工作，每人完成各项任务时间如下表，试确定总花费时间为最少的指派问题。人任务ABCDE甲127979乙89666丙71712149丁15146610戊4107109三、网络最大流问题（10分）求下图所示容量网络中从～的最大流。其中每边上的数为。九、指派问题有三台设备，可用于五项不同的工程。但由于设备数有限，只能分给其中的

5、三项工程。下表给出了不同的工程得到设备后所创的利润，试用匈牙利法确定使总利润最大的设备分配方案（单位：万元）。　利润工程设备B1B2B3B4B5A1372911A2681075A3941256十．动态规划某公司决定投资60万元（以10万元为单位），以提高三种主要产品A、B、C的产量。现决定每种产品至少要投资10万元。各种产品投资不同资金后可获得的期望利润如下：分配的投资金额利润产品A产品B产品C1014.516.215.92016.418.418.43018.019.922.64019.624.124.

6、2试确定如何安排对各种产品的投资数，可获得最大总期望利润？十一．整数规划某公司拟建立4个超市，可选的地址有A、B、C三处。在不同地址设置不同数量的超市后，每个月的营业利润如下表所示（单位：万元）：超市数地址1234A16203032B12152024C10131617问这些超市应如何分布，可使公司总的营业利润最高。十二．指派问题：用匈牙利算法求解下述指派问题，已知效率矩阵分别如下：（a）（b）十三．分配甲、乙、丙、丁四个人去完成五项任务。每人完成任务的时间如表所示。由于任务数多于人数，故规定其中有一人可

7、兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。任务人ABCDE甲2529314237乙3938262033丙3427284032丁2442362345十四．求下图的最小生成树和最大生成树：V16V26622V67V73V38343V51V4十五．求下图中从A到E的最短路线和最短路长（图中每条边上的数字为该条边的长度）。AB2B1C3C2C1D1D2E589643577108691135