2018年安徽工业大学管理科学与工程学院875运筹学考研仿真模拟五套题
● 摘要
一、简答题
1． 试写出M/M/1排队系统的Little 公式。
【答案】M/M/1排队系统的Little 公式为
2． 简述目标规划单纯形法求解的基本思想。
【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l;
第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;
第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;
第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;
第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。 3． 说明本书所述货运车辆优化调度算法的原理和求解步骤，并绘出求解过程框图。请简要回答以下问题。
（1）若有两种车型的车可用，书中提出的模型应怎样修改? 在书中所提算法的启发下，试拟定出一套求解的迭代步骤。
（2）你认为应如何将书中提出的模型和算法推广到多目标的情形。
【答案】①货运车辆优化调度算法的原理:最小费用最大流原理。求解步骤为:a. 仅考虑重载点，运用表上作业法求出最优解作为原问题的可行解; b. 进行解的扩展和解的收缩，直至得到可接受的可行解; c. 以该可接受的可行解为依据确定初始行车线路; d. 根据具体约束条件进行调整，直至得到最优行车路线。求解过程框图如图所示。
图
（2）修改后的迭代算法即神经网络（neural networks）算法。
①建立结合矩阵:将车辆经过的点包括源点看成神经网络的结点，即神经元，令神经元数目为Ni 神经元 和j 神经元的结合权值为
，j 神经元的输出为r j 。
②将车辆调度的各种约束条件转化为约束能量函数为E 约。
③神经网络计算:令时刻t 神经元i 的输出为r i （t ），且r i （t ）只能取0或1，令神经元i 的阈值为Q i ，则输出能量
为
，其中
，因此总的能量函数
为
，则该网络相对处于稳定状态。由于
如果
，且E 有界，系统必
趋向一个比较好的稳定状态，再把此稳定状态时r i （t ） 形成换位阵中元素为l 的结点连接起来，形成所求的最满意车辆调度线路。
④根据所形成的最满意线路来选择车辆调度方案。
（3）推广到多目标情形:车辆优化的目标函数可以有很多个，如总运费最小，司机总的驾驶时间最短，车 辆满载行驶的时间最长等; 而约束条件，如路径的最大输入输出流、车载量、发车和收车约束等。也可以加入惩 罚算子将约束条件转化为惩罚函数，利用多目标方法进行求解。
4． 试写出标准指派问题的线性规划问题。
【答案】
A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:
二、证明题
5． 证明:（1）若
（2）若
和
和
是对策G 的两个解，则是对策G 的两个解，则是G 的解，所以
①
同理，因为
是G 的解，所以
②
由不等式①可知
③
由不等式②可知
由不等式③与不等式④可知
（2）由（1）证明过程中不等式③和不等式④可知即也是解。
6． 假设线性规划问题为:
其中
，秩
。
和
也是对策G 的解。
【答案】（1）因为
④
，即可知，
故
。
相关内容
相关标签