2015-2016-2运筹学试题A(1)

GDOU-B-11-302

《运筹学II》课程试题

★ 考试 ★ A卷 ★ 闭卷

课程号： 19221204

□ 考查 □ B卷 □ 开卷 题 号 一 二 三 四 五 六 七 八 九 十 总分 阅卷教师 各题分数 20 20 20 15 10 15 实得分数 100 一、判断下列说法是否正确？正确的打“?”错误的打“?”。（20分）

1.求解指派问题的系数矩阵当中某一行加上同一个数不会改变最优解，且最优值也不会改变。（ ）。 2.在无向图中哈密尔顿回路存在的充要条件是每个节点的度数都是偶数（ ）。 3.规划问题的三个要素是：（1）决策变量；（2）目标函数；（3）约束条件（ ）。 4. 线性规划问题如果有最优解，则它的最优解一定可以在可行域凸集的一个顶点上取得（ ）。 5.在网络规划中某工序的总时差刻画了该工序在整个规划中的机动性（ ）。 6.求解整数规划的分支定界法是一种只能求出近似解的方法。（ ） 7.树是最小连通路图，树是最大无回路图，任何树的顶点数总是比边数多一（ ）。 8.在网络规划图中，只能有唯一的起点，但可以有不同的终点。（ ）。 9. 某种资源的影子价格为零说明企业急需该资源。（ ）。 10.混合策略意义下的矩阵对策一定有解，而且解是唯一的。（ ）。

第 页 共 页

二、用两阶段法求解下面的线性规划问题（20分）

minz?5x1?21x3?x1?x2?6x3?x4?2?s.t.?x1?x2?2x3?x5?1?x??0;j?1,2,3,4,5?j

第 2 页 共 6 页

三、A、B、C、D、E五人分别完成G1G2G3G4G5各项工作所须的最短时间如下表。问：如果每人完成一项工作，最后完成工作的人用时不得超过8小时，如何安排才能使完成五项工作的总用时最少？请给出最优方案和完成工作的最短时间。 （20分）。

密 封 线

G1G2G3G4G5A57639B68725C899511

D68854E64753第 3 页 共 6 页

四、已知图的五个顶点V1,V2,V3,V4,V5。图的权矩阵A5?(aij)5?5

v1v1v2v3v4v503653097v269038v37302v45820v5A 5?

画出网络图并用狄克斯特拉算法求出v1 到其余各点的最短路（15分）。

第 4 页 共 6 页