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

一、简答题

1． 简述对偶问题的“互补松弛性”。

【答案】互补松弛性:若

当且仅当为最优解。

2． 简述割平面法的基本思想。

【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当，使切割后最终得 到这样的可行域，它的一个有整数坐标的极点的割平面（不见得一次就找到）恰好是问题的最优解。

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

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

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

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

即即

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

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

分别是原问题和对偶问题的可行解。那么

，

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

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

; 。分支定界法就是将B 的可行域分成

:， 最终求到z*。

二、计算题

5． 表是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，a 1、a 2、a 3、d 、c 1、c 2为 待定常数。试说明这些常数分别取何值时，以下结论成立。

（l ）表中解为惟一最优解;

（2）表中解为最优解，但存在无穷多最优解; （3）该线性规划问题具有无界解;

（4）表中解非最优，为对解改进，换入变量为x 1，换出变量为x 6。

表

【答案】（l ）当（2）当（3）当（4）当

且

时，表中解为惟一最优解;

时，表中的解为最优解，且原问题有无穷多个最优解; 时，该线性规划问题具有无界解;

时，表中的解非最优，且满足对解进行改进，

换入变量为x 1， 换出变量为x 6。

6． 有A 、B 、C 、D 四种零件均可在设备甲或设备乙上加工。已知这两种设备上分别加工一个零件的费用 如表5一12所示。又知设备甲或设备乙只要有零件加工就需要设备的启动费用，分别为100元和巧0元。现要求 加工四种零件各3件，问应如何安排生产使总的费用最小? 请建立该问题的线性规划模型（不需求解）。加工一个 零件的费用（单位:元）

表

【答案】设i=1，2，3，4分别表示产品A 、B 、C 、D ; j=1，2表示设备甲、乙; x ij 表示产品i 在设备j 上生产的个数，

则得线性规划模型如下:

其中

7． 求解运输问题:

表

【答案】首先判断发量和收量相等; 第一步，用伏格尔法寻找得到初始基可行解

表

第二步，用位势法计算各空格处的检验数为:

表

可见，所有非基变量的检验数均不为负数，故得到最优解

8． 某公司采用无安全存量的存储策略。每年使用某种零件100000件，每件每年的保管费为30元，每次订购费为600元。试求:

（l ）经济定购批量; （2）订购次数。

【答案】（l ）按E.O.Q 模型计算Q*，得