运筹学试题库(试卷3)

一、填空题：（10分）

1、在图论中，图的基本要素有两个，它们是 和 。

2、结点的最早开始时间和 时间是同一时间，最早开始是对结点的后接工序而言， 是对结点的紧前工序而言。

3、对需要量 供应量的运输问题，求最优解时要先 一个供应点。

4、关键路线是从起点到终点所有路中的最 路，它的线路时差为 。 5、在图论中，为了表示两个队比赛的胜负关系可以用一条带 的 来表示。 二、选择题（10分）

1、若T是图G的最小支撑树，则（ ） A．T必唯一 B. G不一定是连通图 C．T中必不含圈 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、用单纯形法求解标准型式的线性规划问题时，与量。（ ）

2、对偶问题的对偶一定是原问题。（ ）

3、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。（ ）

4、指派问题效率矩阵地每个元素都乘以同意常数k，将不影响最优指派方案。（ ） 5、求网络最大流的问题可归结为求解一个线性规划模型。（ ） 四、规划问题（16分）

已知线性规划问题

minzj>0对应的变量都可以被选作换入变

2x3x125x36x4x12x23x3x422x1x2x33x430(j1,2,3,4)xj

（1） 写出其对偶问题；

（2） 用图解法求对偶问题的解；

（3） 利用（2）的结果及对偶性质求原问题解。

五、运输问题（10分）

某土石方从三个产地运往四个工地，产地的产量、工地的需求量及单位运费如下表，求最优运输方案。

产地 销地 B1 A1 A2 A3 销量 3 1 7 3 B2 11 9 4 6 B3 3 2 10 5 B4 10 8 5 6 产量 7 4 9 六、支撑树问题（6分）

求下面网络图的最小支撑树：

七、指派问题（10分）

分配甲、乙、丙、丁、戊五人去完成五项工作，每人完成一项工作，每人完成各项任务时间如下表，试确定总花费时间为最少的指派问题。 人 任务 甲 乙 丙 丁 戊 八、网络最大流问题（10分） 求下图所示容量网络中从vs～vt的最大流。其中每边上的数为(cij,A 12 8 7 15 4 B 7 9 17 14 10 C 9 6 12 6 7 D 7 6 14 6 10 E 9 6 9 10 9 fij)。

九、指派问题

有三台设备，可用于五项不同的工程。但由于设备数有限，只能分给其中的三项工程。下表给出了不同的工程得到设备后所创的利润，试用匈牙利法确定使总利润最大的设备 分配方案（单位：万元）。

利润 工程 设备 A1 A2 A3

十．动态规划

B1 3 6 9 B2 7 8 4 B3 2 10 12 B4 9 7 5 B5 11 5 6 某公司决定投资60万元（以10万元为单位），以提高三种主要产品 A、B、C 的产量。现决定每种产品至少要投资10万元。各种产品投资不同资金后可获得的期望利润如下：

分配的 利 润 投资金额 产品 A 产品 B 产品 C 10 14.5 16.2 15.9 20 16.4 18.4 18.4 30 18.0 19.9 22.6 40 19.6 24.1 24.2

试确定如何安排对各种产品的投资数，可获得最大总期望利润？

十一．整数规划

某公司拟建立4个超市，可选的地址有A、B、C三处。在不同地址设置不同数量的超市后，每个月的营业利润如下表所示（单位：万元）：

超市数 地址 A B C 16 12 10 20 15 13 30 20 16 32 24 17 1 2 3 4

问这些超市应如何分布，可使公司总的营业利润最高。

十二．指派问题：用匈牙利算法求解下述指派问题，已知效率矩阵分别如下： 713（a）15119121612101614151217151638 （b）68987441022226109739375510

十三．分配甲、乙、丙、丁四个人去完成五项任务。每人完成任务的时间如表所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项。试确

定总花费时间为最少的指派方案。

任 务 人 甲 乙 丙 丁 A 25 39 34 24 B 29 38 27 42 C 31 26 28 36 D 42 20 40 23 E 37 33 32 45

十四．求下图的最小生成树和最大生成树：

V1 6 V2 6 6 2 2

V6 7 V7 3 V3

8 3 4 3

V5 1 V4

十五．求下图中从A到E的最短路线和最短路长（图中每条边上的数字为该条边的长度）。

9 B1 C1 7 10 8 D1 5 A 6 4 3 C2 3 6 9 D2 E 8 5 B2 5 7 C3 11