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

一、选择题

1． 线性规划灵敏度分析应在（ ）的基础上，分析系数的变化对最优解产生的影响。 A. 初始单纯形表 B. 最优单纯形表 C. 对偶问题初始单纯形表 D. 对偶问题最优单纯形表 【答案】BD

【解析】灵敏度分析的是当系数的一个或几个发生变化时, 已求得的线性规划问题的最优解会有什么变化，所以进行灵敏度分析是在最优单纯形表或对偶问题的最优单纯形表的基础上分析的, 最优单纯形表反映的就是系数变化前己求得的最优解。

2． 线性规划可行域为封闭的有界区域，最优解可能是（ ）。 A. 唯一的最优解 B. 一个以上的最优解 C. 目标函数无界 D. 没有可行解 【答案】AB

【解析】可行域非空，故有可行解; 可行域封闭，故目标函数有界，有一个或多个最优解。

二、计算题

3． 写出下列问题的动态规划的基本方程。

【答案】（l ）设状态转移方程为状态s k 到第n 阶段使

，最优值函数

最大的值，则动态规划的基本方程为:

，或

表示从第k 阶段

（2）设状态变量为表示

在s k 状态下从第k 阶段到第n 阶段使

，状态转移方程为，最优值函数

最小的值，则动态规划的基本方程为:

4． 己知下列资料。

表

要求:（l ）绘制网络图;

（2）用图上计算法计算各项时间参数（r 除外）; （3）确定关键路线。

【答案】（l ）由题意绘制网络图如图所示。

（2）事项最早时间见图中“口”中的数字，事项最迟时间见图中“△”中的数字。

、

图

（3）总时差为零的工序为关键工序，所以关键路线为①→③→④→⑤→⑥→⑦→⑩→⑪，对应的工序为 H →B →G →A →F →K 。

5． 己知有六台机床x l ，x 2，…，x 6，六个零件y 1，y 2，…，y 6。机床x 1可加工零件y 1; x 2可加工零件y l ，y 2; x 3可加工零件y l ，y 2，y 3，x 4可加工零件y 2; x 5可加工零件y 2，y 3，x 4; x 6可加工零件y 2，y 5，y 6。现在要求制订一个加工方案，使一台机床只加工一个零件，一个零件只在一台机床上加工，要求尽可能多地安排零件加工。试把这个问题化为求网络最大流的问题，求出能满足上述条件的加工方案。

【答案】依题意，画出最大容量的网络图，并令（l ）标号过程。进行标号，并找出增广链:

因v t 已标号，转入调整过程。

，如图所示。

图

（2

）调整过程。按点的第一个标号找到一条增广链

整:

。按照

在

上调

调整后得如图所示的可行流，对这个可行流进入重新标号，寻找增广链。

图

反复标号过程和调整过程，最后得到如图所示的结果。