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

一、简答题

1． 简述目标规划单纯形法求解的基本思想。

【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l; 第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;

第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;

第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;

第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。 2． 简述影子价格的经济含义。

【答案】影子价格的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影 子价格对市场具有调节作用，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资 源用于扩大生产; 而当某种资源的市场价高于企业影子价格时，则企业的决策者应把己有资源卖掉。

3． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。

【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。 （2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。

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

【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界

域（称为分支）的方法，逐步减小和增大; 。分支定界法就是将B 的可行域分成子区:， 最终求到z*。

二、计算题

5． 用Gomory 切割法解以下问题。

【答案】（1）在该线性规划问题的约束条件中分别加入松弛变量x3，x4，化为标准型

先不考虑上述模型中的整数约束，利用单纯形法进行求解，如表所示。

表

此时的最优解为最优目标值。

由表中最终单纯形表可得变量间的关系式：

将系数和常数项都分解成整数和非负数真分数之和，移项，则以上两式变为

要求x 1，x 2，x 3，x 4为非负整数，从上述两式看来，等式左边是整数，等式右边括号内是正数，所以等式右边必须是负数，则上述第二个等式的右端可由下式代替：

即

加入松弛变量x 5，即得到切割方程:

表

将该约束条件加入到上表的最终单纯形表中，并进行进一步求解，如下表所示。

由于x l ，x 2己为整数，所以最优解为

（2）在该线性规划问题的约束条件中分别加入松弛变量x 3，x 4，x 6及人工变量x 5，化为标准型

先不考虑模型中的整数约束，利用单纯形法进行求解，如表所示。

表