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

运筹学试题库（试卷3）一、 填空题：（10分）1、在图论中，图的基本要素有两个，它们是 和 。2、结点的最早开始时间和 时间是同一时间，最早开始是对结点的后接工序而言， 是对结点的紧前工序而言。3、对需要量 供应量的运输问题，求最优解时要先 一个供应点。4、关键路线是从起点到终点所有路中的最 路，它的线路时差为 。5、在图论中，为了表示两个队比赛的胜负关系可以用一条带 的 来表示。二、 选择题（10分）1、若T是图G的最小支撑树，则（ ）AT必唯一 B. G不一定是连通图CT中必不含圈 D.G中不含圈3、在网络计划中，进行时间与成本优化时，随工期延长，间接费用将（ ）。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、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。（ ）4、指派问题效率矩阵地每个元素都乘以同意常数k，将不影响最优指派方案。（ ）5、求网络最大流的问题可归结为求解一个线性规划模型。（ ）四、 规划问题（16分）已知线性规划问题（1） 写出其对偶问题；（2） 用图解法求对偶问题的解；（3） 利用（2）的结果及对偶性质求原问题解。五、 运输问题（10分）某土石方从三个产地运往四个工地，产地的产量、工地的需求量及单位运费如下表，求最优运输方案。产地 销地B1B2B3B4产量A13113107A219284A3741059销量3656六、 支撑树问题（6分）求下面网络图的最小支撑树：七、 指派问题（10分）分配甲、乙、丙、丁、戊五人去完成五项工作，每人完成一项工作，每人完成各项任务时间如下表，试确定总花费时间为最少的指派问题。人 任务ABCDE甲127979乙89666丙71712149丁15146610戊4107109八、 网络最大流问题（10分）求下图所示容量网络中从的最大流。其中每边上的数为。9、 指派问题有三台设备，可用于五项不同的工程。但由于设备数有限，只能分给其中的三项工程。下表给出了不同的工程得到设备后所创的利润，试用匈牙利法确定使总利润最大的设备分配方案（单位：万元）。 利润工程设备B1B2B3B4B5A1372911A2681075A394125610 动态规划某公司决定投资60万元（以10万元为单位），以提高三种主要产品 A、B、C 的产量。现决定每种产品至少要投资10万元。各种产品投资不同资金后可获得的期望利润如下：分配的投资金额利 润产品 A产品 B产品 C1014.516.215.92016.418.418.43018.019.922.64019.624.124.2试确定如何安排对各种产品的投资数，可获得最大总期望利润？11 整数规划某公司拟建立4个超市，可选的地址有A、B、C三处。在不同地址设置不同数量的超市后，每个月的营业利润如下表所示（单位：万元）：超市数地址1234A16203032B12152024C10131617问这些超市应如何分布，可使公司总的营业利润最高。12 指派问题：用匈牙利算法求解下述指派问题，已知效率矩阵分别如下：（a） （b）13 分配甲、乙、丙、丁四个人去完成五项任务。每人完成任务的时间如表所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。 任 务人ABCDE甲2529314237乙3938262033丙3427284032丁2442362345十四求下图的最小生成树和最大生成树： V1 6 V2 6 6 2 2V6 7 V7 3 V