2016年华中科技大学自动化学院828运筹学考研强化班模拟试题及答案
● 摘要
一、简答题
1． 试写出求解最短径路的Dijkstra 算法的步骤。
【答案】Dijkstra 算法的步骤为:
（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。
（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T
，p （v i ）+lij ] 标号进行如下修改:T （v j ）=min[T（v i ）
（3）比较所有具有T 标号的点，把最小者改为P 标号，即: 当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。 2． 一个运输问题，如果其单位运价表的某一行元素分别加上一个常数，最优调运方案是否发生变化，试说明理由（用表或直接用公式）;
【答案】最优方案不会发生变化。因为在计算任意空格的检验数时，若其通过变化行的一个基格，则其必经过两个基格，
则最优方案不发生变化。
3． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
二、证明题
4． 设m*m对策的矩阵为
其中，当时，当i=j时，证明此对策的最优策略为
【答案】由题意知，
，所以A 没有鞍点，故令最优混合策略
，则
即
即
。
5． 证明:矩阵对策G={S1，S 2; A}在混合策略意义下有解的充要条件是:存在
为函数以的一个鞍点，即对一切
【答案】（l ）先证明充分性
对任意X , Y 均有，故得出
又
，
使，有
相关内容
相关标签