2017年沈阳大学F19运筹学复试实战预测五套卷
● 摘要
一、简答题
1． 简述对偶问题的“互补松弛性”。
【答案】互补松弛性:若
分别是原问题和对偶问题的可行解。那么
，
当且仅当为最优解。
2． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。
【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。（2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。
（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。
（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不 使整个施工按照最短施工时间保持一定施工节拍进同施工工序如何搭接排序组成一定施工工艺，行流水作业，同时消耗人、机、材等资源也合理。
二、计算题
3． 试用步长加速法（模矢法）求下述函数始点
，步长
。并绘图表示整个迭代过程。
的极小点，初
【答案】按照题目要求，采用步长加速法进行迭代，迭代过程如表所示。
表
注：表中的“-”表示其值不必计算。
，此时应在点
附近搜索，缩小步长以求得符合精度要求的
结果。所以，最优解为（4, 2）. 其迭代过程如图所示。
T
图
4． 用破圈法和避圈法求下图的一个支撑树。
【答案】（l ）用破圈法求解，求解过程如下。
①取圈（v 1，v 2，v 3），去掉其中一条边，如e 2=[v1，v 3]; ②取圈（v 1，v 2，v 5），去掉其中一条边，如e 7=[v1，v 5]; ③取圈（v 2，v 3，v 4），去掉其中一条边，如e 3=[v2，v 3]; ④取圈（v 2，v 4，v 5），去掉其中一条边，如e 5=[v2，v 5]; ⑤取圈（v 4，v 5，v 6），去掉其中一条边，如e 10=[v5，v 6];
⑥取圈（v 8，v 9，v 10），去掉其中一条边，如e 15=[v8，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。这时，剩余的图中不含圈，即得到了一个支撑树，如图所示。
图
5． 表表示某运输问题的运价表和供需关系表。用最小元素法确定初始调运方案，并判断是否最优:
表
【答案】用最小元素法确定初始方案为表
表
用位势法对上述的初始方案进行检验，
表
由上可看出，所有非基变量的检验数均不为负数，故该方案是最优方案。
6． 线性规划问题
相关内容
相关标签