当前位置：问答库＞考研试题

一、选择题

1． 在求解整数规划问题时，不可能出现的是（ ）。

A. 唯一最优解

B. 无可行解

C. 多重最优解

D. 无穷多最优解

【答案】D

【解析】整数规划的可行解的个数是有限的，所以整数规划中不可能出现无穷多最优解。

2． 用线性规划制定某一企业的生产计划问题，两种资源的影子价格分别为y 甲=5，y 乙=8，说明这两种资源在该企业中的稀缺程度为:（ ）。

A. 甲比乙更稀缺

B. 甲和乙同样稀缺

C. 乙比甲更稀缺

D. 甲和乙都不稀缺

【答案】C

【解析】影子价格是对系统内部资源稀缺程度的一种客观评价，某种资源的影子价格越高，说明该资源在系统内越稀缺，增加该资源的供应量对系统目标函数值的贡献也越大。

3． 关于最小费用最大流，求解时不会用到下面哪种方法（ ）。

A.Dijkstra 算法

B.Floyd 算法

C.Ford 一Fulkerson 算法

D. 奇偶点作业法

【答案】D

【解析】奇偶点作业法为中国邮递员问题中寻找欧拉圈时所用的方法，最小费用最大流问题并不涉及此法。

4． 己知Y i 为线性规划的对偶问题的最优解，若Y i >0，说明（ ）。

A. 原问题的最优解x i =0

B. 在最优生产计划中第i 种资源己完全耗尽

C. 在最优生产计划中第i 种资源有剩余

D. 无法判断

【答案】B

【解析】当影子价格为0时，表示某种资源未得到充分利用; 而当资源的影子价格不为零时，表明该种资源在生产中己耗费完毕。

二、简答题

5． 简述对偶问题的“互补松弛性”。

【答案】互补松弛性:若

分别是原问题和对偶问题的可行解。那么，当且仅当为最优解。

6． 说明本书所述货运车辆优化调度算法的原理和求解步骤，并绘出求解过程框图。请简要回答以下问题。

（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）推广到多目标情形:车辆优化的目标函数可以有很多个，如总运费最小，司机总的驾驶时间最短，车 辆满载行驶的时间最长等; 而约束条件，如路径的最大输入输出流、车载量、发车和收车约束等。也可以加入惩 罚算子将约束条件转化为惩罚函数，利用多目标方法进行求解。