2017年东北大学工商管理学院852运筹学考研仿真模拟题
● 摘要
一、简答题
1． 说明本书所述货运车辆优化调度算法的原理和求解步骤，并绘出求解过程框图。请简要回答以下问题。
（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）推广到多目标情形:车辆优化的目标函数可以有很多个，如总运费最小，司机总的驾驶时间最短，车 辆满载行驶的时间最长等; 而约束条件，如路径的最大输入输出流、车载量、发车和收车约束等。也可以加入惩 罚算子将约束条件转化为惩罚函数，利用多目标方法进行求解。
2． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
3． 试写出M/M/1排队系统的Little 公式。
【答案】M/M/1排队系统的Little 公式为
二、证明题
4． 现有一个线性规划问题（P 1）:
, 其对偶问题的最优解为Y*=（y1, y2, y3, …ym ）
另有一线性规划（P 2）:
【答案】问题（P 2）的对偶问题为:
T
其中，d=（d 1, d 2, ...d 3） 。 求证:
问题（P 2）的对偶问题为:
易见，问题（P 1）的对偶问题与问题（P 2）的对偶问题具有相同的约束条件，从而，问题（P 1）的对偶问 题的最优解
令问题（P 2）的对偶问题的最优解为
5． 假设线性规划问题为:
其中
，秩
运用单纯形算法求得的最优基可行解时，所有的非基变量检验数全都<0，试证明这时所得到的最优解必定 是线性规划问题（l ）的准最优解。
【答案】一般情况下，经过迭代后解变为
一定是问题（P 2）的对偶问题的可行解。 ，则:
。
因为原问题与对偶问题的最优值相等，所以
再将上式代入目标函数式，整理后得到
令于是
再令则
时，此时的解就为最优解。
这样当所有非基变量的检验数即
6． 车间内有m 台机器，有c 个修理工（m>c），每台机器发生故障率为兄，符合M/M/c/m/m模型， 试证:
【答案】由题设知
并说明上式左右两端的概率意义。
相关内容
相关标签