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

一、简答题

1． 简述求解整数规划分枝定界法的基本思想。

【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界; 。分支定界法就是将B 的可行域分成子区域（称为分支）的方法，逐步减小和增大:， 最终求到z*。

2． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。

【答案】（l ）某枝已经达到其范围内的最优解;

（2）某枝域内没有可行解时，即是不可行域;

（3）某枝所得数据不优于当前最优解时。

二、计算题

3． 试求解下列线性规划问题:

将本问题的目标变成maxz=-xl +x2，约束条件不变，何为其解?

【答案】（1）用图解法可得图

由图形可知，在（0，l ）处，-x 1+x2取得最大值为1。

故最优解为x 1=0，x 2=1，目标函数值为z=1。

（2

）当目标函数变为，由于约束条件不变，即为上图中所示的阴影部分，

由x 1+x2=0可 得，目标函数与边界直线x 1+x2=0平行。

故最优解为x 1+x2=1即故目标函数值为下z=l。

4． 某工厂利用原材料A 、B 生产产品甲、乙、丙，有关资料见表。

表

（1）怎样安排每天的生产计划，使利润最大（注:要求建立数学模型，写出求解过程）。 （2）若增加1kg 原材料A ，总利润增加多少。

（3）设原材料A 的市场价格为15元/g，若要转卖原材料A ，工厂应至少叫价多少，为什么。

（4）单位产品利润分别在什么范围内变化时，原生产计划不变。

（5）由于市场的变化，产品乙的单件利润变为55元，这时生产计划是否要调整，总利润是否变化，为什么。

（6）工厂计划生产新产品丁，每件产品丁消耗原材料A 、B 分别为2kg ，2kg ，每件产品丁应至少获利多少时才有利于投产。

【答案】设生产甲、乙、丙三种产品的数量分别为x 1，x 2，x 3，则此题的数学模型为:

（l ）将上述模型加入松弛变量x 4，x 5化为标准型:

采用单纯形法求解，过程如表所示:

表

由上表可得，最优解为

最大利润Z*=30×2+50×12=660。 。因此有:

（2）由单纯形表可得，原材料A 的影子价格为10，所以, 增加1kg 原材料A ，总利润会增加10。

（3）至少应叫价10元，因为A 材料的影子价格为10，叫价10元可以保证与企业自己生产获得同等的利润。

（4）即求G j 的变化范围，当最优解不变时，应满足以下条件:

（5）由（4）得G 1在内变化时，最优解不变，即生产计划不变，仍然是生产甲产生

T 2，产生工产品12, 总利润发生变化:

为:

所以，J 产品要想获利，则必须满足C 6-40≥0，即C 6≥40

因此，每件产品J 应至少获利40时才能投产。 （6）设生产产品x 6，利润为c 6，其技术系数向量P 6=（2, 2）则最终表中对应x 6的检验数

5． 网络图中第一个工序，第二个代表完成该工序需要的正常工作时间:试计算

（1）网络图中各工序最早开工、最早完工、最迟开工、最迟完工时间，各工序的总时差，确定关键路线和工期: