2017年天津职业技术师范大学运筹学(同等学力加试)考研复试核心题库
● 摘要
一、简答题
1． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。
【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。（2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。
（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。
（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不 使整个施工按照最短施工时间保持一定施工节拍进同施工工序如何搭接排序组成一定施工工艺，行流水作业，同时消耗人、机、材等资源也合理。
2． 试写出求解最短径路的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）。
二、计算题
3． 利用Kuhn 一Tucker 条件求解以下问题:
其中a 为实常数。
（l ）试写出勘hn 一Tueker 条件。 （2）a 满足什么条件时以上问题有最优解? （3）分别求出相应的最优解和最优值。 【答案】（1）
K-T 条件
（3）
综上
时无最优解
时时，
4． 用图解法求解下列线性规划问题，并指出问题是具有惟一最优解、无穷多最优解、无界解还是无可行解?
（1）
为最优解
为最优解
（2）
（3）
（4）
【答案】（1）如图所示，该问题的可行域为有界域。目标函数之=x1+3x2在点A 3处取得最大值，求解方程组
规划问题具有惟一最优解。
T
可得A 4的坐标为（2，4），所以x*=（2，4），z*=14，该线性
相关内容
相关标签