2017年西南财经大学运筹学复试仿真模拟三套题
● 摘要
一、简答题
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 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]
（3）比较所有具有T 标号的点，把最小者改为P 标号，即:
当存在两个以
上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
2． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
二、计算题
3． 用单纯形法求解以下目标规划问题的满意解。
（2）
（3）
+
【答案】 （1）在第三个约束条件中加入松弛变量x 3，该目标规划的标准型为:
建立初始单纯形表，在表中将检验数列按优先因子个数排成两行，并采用单纯形法进行进一步迭代，如表所示。
表
由表可知，为该目标规划的满意解。由于非基变量
。
，所以该的检验数为。
问题有多重解。进一步迭代得另一满意解为进一步迭代，如表所示。
（2）建立初始单纯形表，在表中将检验数列按优先因子个数排成4行，并采用单纯形法进行
表
由表可知，
进一步迭代，如 表所示。
为该目标规划的满意解。
（3）建立初始单纯形表，在表中将检验数列按优先因子个数排成两行，并采用单纯形法进行
表
由表可知，为该目标规划的满意解。
4． 已知某运输问题的供需关系及单位运价如表所示，要求:
（l ）用表上作业的方法求出最优调运方案:
（2）分析从A 1到B l 的单位运价可变化范闺，使（l ）中求得的最优调运方案保持不变: （3）分析从A 1到B 1的单位运价可变化范围，使（1）中求得的最优调动方案保持不变:
相关内容
相关标签