2017年山东科技大学交通学院847运筹学考研冲刺密押题
● 摘要
一、简答题
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． 考虑一个（线性）目标规划在计算机上求解的问题。假设手头只有一个线性规划的求解软件，想要仅仅 借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）?
【答案】想要仅仅借助该软件来实现对目标规划的求解，则应按如下步骤进行。
先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划; 其次，将己经实现的第一个目标作 为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。以此类推，逐
，即可求出目标规划的满意解。 次求解k 个线性规划（k 为优先级的个数）
3． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。
【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。
（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。
4． 说明本书所述货运车辆优化调度算法的原理和求解步骤，并绘出求解过程框图。请简要回答以下问题。
（1）若有两种车型的车可用，书中提出的模型应怎样修改? 在书中所提算法的启发下，试拟定出一套求解的迭代步骤。
（2）你认为应如何将书中提出的模型和算法推广到多目标的情形。
【答案】①货运车辆优化调度算法的原理:最小费用最大流原理。求解步骤为:a. 仅考虑重载点，运用表上作业法求出最优解作为原问题的可行解; b. 进行解的扩展和解的收缩，直至得到可接受的可行解; c. 以该可接受的可行解为依据确定初始行车线路; d. 根据具体约束条件进行调整，直至得到最优行车路线。求解过程框图如图所示。
图
（2）修改后的迭代算法即神经网络（neural networks）算法。
①建立结合矩阵:将车辆经过的点包括源点看成神经网络的结点，即神经元，令神经元数目为Ni 神经元 和j 神经元的结合权值为，j 神经元的输出为r j 。
②将车辆调度的各种约束条件转化为约束能量函数为E 约。
，且r i （t ）只能取0或1，令神经元i 的阈③神经网络计算:令时刻t 神经元i 的输出为r i （t ）
值为Q i ，则输出能量
为
，其中，因此总的能量函数
为，则该网络相对处于稳定状态。由于如
果，且E 有界，系统必
趋向一个比较好的稳定状态，再把此稳定状态时r i （t ） 形成换位阵中元素为l 的结点连接起来，形成所求的最满意车辆调度线路。
④根据所形成的最满意线路来选择车辆调度方案。
（3）推广到多目标情形:车辆优化的目标函数可以有很多个，如总运费最小，司机总的驾驶时间最短，车 辆满载行驶的时间最长等; 而约束条件，如路径的最大输入输出流、车载量、发车和收车约束等。也可以加入惩 罚算子将约束条件转化为惩罚函数，利用多目标方法进行求解。
二、计算题
5． 用破圈法和避圈法求下图的一个支撑树。
【答案】（l ）用破圈法求解，求解过程如下。
，去掉其中一条边，如e 2=[v1，v 3]; ①取圈（v 1，v 2，v 3）
，去掉其中一条边，如e 7=[v1，v 5]; ②取圈（v 1，v 2，v 5）
，去掉其中一条边，如e 3=[v2，v 3]; ③取圈（v 2，v 3，v 4）
，去掉其中一条边，如e 5=[v2，v 5]; ④取圈（v 2，v 4，v 5）
，去掉其中一条边，如e 10=[v5，v 6]; ⑤取圈（v 4，v 5，v 6）
，去掉其中一条边，如e 15=[v8，v 10]. 这时，剩余的图中不含圈，即得⑥取圈（v 8，v 9，v 10）
到了一个支撑树，如图所示。
图
（2）用避圈法求解，求解过程如下:
①在图中，任取一条边e 1，找一条与e 1不构成圈的边e 4;
②找一条与{el ，e 4}不构成圈的边e 6;
③找一条与{el ，e 4，e 6}不构成圈的边e 8;
④找一条与{el ，e 4，e 6，e 8}不构成圈的边e 9;
⑤找一条与毛{el ，e 4，e 6，e 8，e 9}不构成圈的边e 11;
⑥找一条与{el ，e 4，e 6，e 8，e 9，e 11}不构成圈的边e 12;
⑦找一条与{el ，e 4，e 6，e 8，e 9，e 11，e 12}不构成圈的边e 13;
⑧找一条与{el ，e 4，e 6，e 8，e 9，e 12，e 13}不构成圈的边e 14。这时，剩余的图中不含圈，即得
相关内容
相关标签