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

一、简答题

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

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

2． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。

【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。

（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。

二、计算题

3． 利用Kuhn 一Tucker 条件求解以下问题:

其中a 为实常数。

（l ）试写出勘hn 一Tueker 条件。 （2）a 满足什么条件时以上问题有最优解? （3）分别求出相应的最优解和最优值。 【答案】（1）

K-T 条件

（3）

综上

时无最优解

时时，

4． 某出版单位有4500个空闲的印刷机时和4000个空闲的装订工时，拟用于下列4种图书的印刷和装订。已知各种书每册所需要的印刷和装订工时如下表所示:

为最优解

为最优解

设x j 表示第j 种书的出版数量（单位:千册），据此建立如下线性规划模型:

用单纯形法求解得最终的单纯形表如表所示:（x 5，x 6为松弛变量）

表

试回答以下问题:（假定各问题条件相互独立，也就是在其他条件与原问题相同时来回答本问题）

（l ）据市场调查第4种书最多能销5000册，当销量多于5000时，超量部分每册降价2元，据此假设求新的最优解

（2）经理对不出版第2种书提出意见，要求该种书必须出2000册，求此条件下的最优解; （3）作为替代方案，第2种书仍须出2000册，印刷由该厂承担，而装订工序交别的厂承担，但装订每册成 本比该厂高0.5元，求新最优解。

【答案】（l ）将5000册第4种书所需工时扣除，并将其利润降为1，重新求解得