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

一、简答题

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

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

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

【答案】互补松弛性:若当且仅当为

最优解。

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

，

二、计算题

3． 试解二次规划

【答案】上述二次规划问题可改写为下列形式:

显然，目标函数为严格凸函数，并且

因为c 1，c 2小于0，引入人工变量z 1，z 2并在前面取负号，得到如下的线性规划模型:

解之得:

于是，

4． 设某工厂每年需用某种原料1800吨，不需每日供应，但不得缺货。设每吨每月的保管费为60元，每次订购费为200元，试求最佳订购量。

【答案】由题意知，该模型为“不允许缺货，生产时间很短”，按E.Q.Q 计算Q*得

所以最佳订购量为32顿。

5． 有四个工件J 1，J 2，J 3，J 4，要求在三台设备A ，B ，C 上顺次加工，各工件在各设备上的加工时间示于表中，试构造一启发式算法，用于寻求使总加工时间最短的工件加工顺序。

表

【答案】可设计如下启发式算法:

利用该启发式算法求解，求解过程如表所示。

表

所以，最优加工顺序为

6． 已知矩阵对策

的解为

对策的解，其赢得矩阵A 分别为

，总加工时间为40。

，对策值为24/l3。求下列矩阵

【答案】（l ）因为

所以可由定理7可知

（2）因为

所以

7． 已知线性规划问题:

。