2017年沈阳师范大学数学与系统科学学院849线性规划考研强化模拟题
● 摘要
一、计算题
1． 在图中，（l ）用Dijkstra 方法求从v l 到各点的最短路; （2）指出对v l 来说，哪些顶点是不可到达的。
图
【答案】（1）
①v1已经获得P 标号，
计算从v l 到各点的最短路的步骤如下:
，修改v2，v5，v7的T 标号
因为
②v5已经获得P 标号，
，改写v6的T 标号为
，所以有
。
于是，有v 1到各点v 2，v 5，v 7，v 6，v 8的最短路为
（2）v 1不能到达v 3及v 4。
，
因为
2． 在图中，分别求v 1至v 6，v 1至V 4，v 6至v Z 和v Z 至vs 的最短路和最短距离。
图
【答案】用Floyd 方法求解 令网络的权矩阵为
其中，
为
到
的距离
由表示从v i 到v j 点的或
直接有边或借v 1点为中间点是的最短路长，括弧中元素为更新元素，得
表示从vi 到vj 点最多经v l ，v 2的最短路长，得
以此类推，
所以v l 至v 6的最短路是v 1一v 3一v 5一v 6，最短距离是-1; v l 至v 4的最短路是v 1一v 3一v 5一v 4，最短距离是3; v 6至v 2的最短路是v 6一v 4一v 2，最短距离是3: v 2至v 5的最短路是v 2一v3一v 5，最短距离1;
3． 已知A 、B 各自的纯策略及A 的赢得矩阵如表所示，求双方的最优策略及对策值。
表
【答案】在A 的赢得矩阵中第4列优超于第2列，第l 列优超于第3列，故可划去第2列和第3列，得到新的赢得矩阵
相关内容
相关标签