2016年陕西科技大学理学院陕西科技大学943运筹学(同等学力加试)考研复试题库
● 摘要
一、计算题
1． 求图中，从任意一点到另外任一点的最短路。
【答案】用Dijtstra 算法寻求最短路，计算结果如表所示。
表
从表可以得出任意一点到另外任一点的最短路。 （l ）从v 1开始到各点的最短路。
（2）从v 2开始到v j 的最短路。
V 2不能到达v l ，故对v 2而言，v 1为不可达点。 （3）从v 3出发到各点的最短路。
v 3不能到达v l 和v 2，故v 1，v 2为v 3的不可达点。
，且d （v 4，v 6）=3。 （4）从v 4出发，只有一条路（v 4，v 6）
，且d （v 5，v 6）=6。 （5）从v 5出发，只有一条路（v 5，v 6）（6）从v 6出发，则无路。
2． 试用可行方向法求解
【答案】原非线性规划问题可改写为:
取精度气
，初始可行点
。则
因为而
取搜索方向则得又令
，即
，解得
，所以，
为空集。
不是近似极小点。 ，将其代入约束条件，并令
; 令
，得
。
， ，因此
，
则构成下述线性规划问题:
为便于用单纯形法求解，令
从而得到
，得线性规划问题:
引入剩余变量y 4，松弛变量y 5，y 6，y 7及人工变量y 8。
其最优解为：
，而
搜索方向为
所以
。