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

一、简答题

1． 考虑一个（线性）目标规划在计算机上求解的问题。假设手头只有一个线性规划的求解软件，想要仅仅 借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）?

【答案】想要仅仅借助该软件来实现对目标规划的求解，则应按如下步骤进行。

先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划; 其次，将己经实现的第一个目标作 为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。以此类推，逐次求解k 个线性规划（k 为优先级的个数），即可求出目标规划的满意解。

2． 什么是关于可行流f 的增广链?

【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若

满足下列条件: （l ）在弧（2）在弧称

是关于可行流f 的一条增广链。

即即

中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。

是从v s 到v t ，的一条链，

二、计算题

3． 某企业用甲、乙、丙三种原料生产A 、B 、C 、D 四种产品，每种产品消耗原料定额以及三种原料的数量 如表所示.

表

求使总利润最大的生产计划。现求得最优单纯形表为:

表

请解答下列问题:

（1）写出此问题的线性规划模型及其对偶问题，并写出此问题的最优解、最优基、最优基的逆和对偶问题的解;

（2）解释最优生产计划中有的产品不安排生产的原因; （3）对产品B 的利润进行灵敏度分析;

（4）若原料甲增加420吨，影子价格是否变化，求原料甲增加后的最优解和各原料的影子价格。

【答案】（l ）设产品A 、B 、C 、D 分别生产x l ，x 2，x 3，x 4万件，则可建立如下线性规划模型:

其对偶问题为:

由最终单纯形表知，问题的最优解为最优基为B=

。

最优基的逆B =

-1

对偶问题的最优解为y 1=6，y 2=4，y 3=0。

（2）产品A 和D 没有安排生产，原因是:虽然他们单位产品的利润高，但是生产时消耗的原料也多，这两 种产品对三种原料都消耗，而产品B 和C 都只消耗两种原料，在原料有限的情况下，生产A 和D 较生产B 和C 不划算，所以没有安排他们的生产。

（3）设产品B 的利润cZ 未知，则在最终单纯形表中，要满足各非基变量的检验数非正，则

解得11≤c 2≤28，所以当11≤c 2≤28时，最优解不发生变化，否则最优解发生变化。 （4）原材料甲增加420吨后

b’中有负分量，所以最优解发生变化。用对偶单纯形法进行求解如表所示:

表

T

所以原料甲增加后的最优解为X*=（15，595，1585，0，0），原料甲、乙、丙的影子价格

分别为 21/4，35/8，1/2。

4． 某项目由8项作业组成，相关参数如表所示。

表

试回答下述问题。 （l ）绘制网络图;

（2）计算作业C ，D ，G 的最早开工、最早完工、最迟开工、最迟完工时间、单时差和总时差;

（3）如果项目组共有工人27人，试问如何安排项目的开工时间。 【答案】（l ）绘制网络图为: （2）