运筹学（）解答.doc

运 筹 学 解 答 6 5 2 5 3 2 1 3 1 4 2 4 1 2 2 1 2 2 2 2 2 1 四、（12分）在下图中，用Dijkstra算法求顶点到其余各个顶点的最短有向路的长度及其路径。 解： V1V2V3V4V5V6V7V8V9V10V1110262536434127587681097101098101013912最短路：V1V2 ；长度：2； 最短路：V1V2V3 ；长度：5； 最短路：V1V2 V3V4；长度：7； 最短路：V1V2 V3V6V5；长度：8； 最短路：V1V2 V3V6；长度：6； 最短路：V1V2 V3V7；长度：7； 最短路：V1V2 V3V6V5V8；长度：10； 最短路：V1V2 V3V7V9；长度：10； 最短路：V1V2 V3V7V10；长度：9； 最短路：V1V2 V3V7V9V11；长度：12； 五、（12分） 对如下的工程网络图，标号求出各工序的最早开工时间、最迟完工时间，以及关键路径。 2 10 2 8 6 2 3 5 1 4 2 4 3 6 3 1 2 3 2 2 5 1 解：各工序的最早开工时间、最迟完工时间，以及关键路径如下图所示： 16 12 21 21 2 3 2 10 2 8 6 2 3 5 1 4 2 4 3 6 3 1 2 3 2 2 5 1 6 17 17 11 7 26 26 0 6 0 8 8 14 14 22 18 六、（12分）在如下图所示的有向网络中（边上的数字是容量），用增广链法求网络最大流。 2 10 2 8 6 2 3 5 1 4 2 4 3 6 3 1 2 3 2 2 5 1 解： 从零流出发； 增广链V1V4 V7V10V11；=2； 增广链V1V4 V7 V9V10V11；=1； 增广链V1V4 V7V9V11；=2； 增广链V1V2 V5V8V11；=2； 增广链V1V3 V5V9V8V11；=1； 增广链V1V3 V6V9V8V11；=1； 2 2 2 10 2 8 6 2 3 5 1 4 2 4 3 6 3 1 2 3 2 2 5 1 最大流量 = 9；如下图所示： 2 4 2 1 0 1 2 0 2 1 1 1 0 0 0 3 5 5 2 3 七、（12分）用图解法求解下面的矩阵对策问题。 乙方甲方14-45314-6 解： 设甲的最优混合策略为：； 甲方的赢得为： ①乙方选第一个策略： ②乙方选第二个策略： ③乙方选第三个策略： ④乙方选第四个策略： 根据最小赢得最大准则求③、④交点； 得到 所以，甲的最优混合策略为： 设乙的最优混合策略为：； 由 解得：；所以，乙的最优混合策略为： 八、（15分） 电视机厂，2005年产品更新方案有三个：A1，A2，A3；收益矩阵如下 销路 收益 方案好中差S1 (万元)S2 (万元)S3 (万元)A181－1A2333A365－1问在下列准则下：如何决策？ ①乐观准则；②悲观准则；③等可能性准则；④最小最大后悔准则。 解： ①乐观准则 销路 收益 方案好中差S1 (万元)S2 (万元)S3 (万元)MaxA181－18A23333A365－16决策选A1 ②悲观准则 销路 收益 方案好中差S1 (万元)S2 (万元)S3 (万元)MinA181－1-1A23333A365－1-1决策选A2 ③等可能性准则 销路 收益 方案好中差S1 (万元)S2 (万元)S3 (万元)(S1+ S2+ S3)/3A181－18/3A23333A365－110/3决策选A3 ④最小最大后悔准则，后悔矩阵： 销路 收益 方案好中差S1 (万元)S2 (万元)S3 (万元)MaxA10444A25205A32044决策选A1 或 A3