运筹学（）解答.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
显示全部